Quine (dataprogram)

En quine er et dataprogram som skriver en kopi av seg selv (vanligvis kildekoden ) som utdata. Det er derfor en form for selvreferanse .

Hackere og geeks ser på det som en sportslig utfordring å lage minst mulig kviner på de programmeringsspråkene de selv velger (se IOCCC ).

Quines er oppkalt etter logikeren og filosofen Willard Van Orman Quine .

Bygging av kviner

Spør deg selv

En quine kan skrives slik i en C- lignende pseudokode

main() {
    print myself out.
}

Vanligvis blir C-programmer samlet , dvs. H. Den kjøretids versjon av programmet er tilgjengelig i maskinspråk (representasjon som en sekvens av byte , som er lagret i en såkalt binærfilen), men dens opprinnelige representasjon er vanligvis en ASCII- kodet kildetekst som blir også lagret i en annen fil. Tilgangen til egen representasjon ( meg selv ) som kreves for denne tilnærmingen til implementeringen av en Quines ville derfor være veldig komplisert.

En quine er også nødvendig for å være ferdig.

• Det bør gjøre uten tilgang til eksterne data, noe som betyr at tilgang til din egen kildetekstfil også er ekskludert.
• Den essensielle koden skal også være tilstede i Quine selv, og det er grunnen til at eksterne funksjoner bare skal brukes sparsomt, biblioteksfunksjonen som for eksempel gir et tegn , er fortsatt tillatt.

Bare noen få språk støtter selvreferanse ( refleksjon ) i den form at et program på dette språket har tilgang til sin egen representasjon.

Et tolket programmeringsspråk, som Perl eller Python , ville i prinsippet ha lettere tid, siden representasjonen av programmet som skal utføres av tolken, også kunne gjøres tilgjengelig for den samme, men dette støttes vanligvis ikke, for eksempel av sikkerhetsgrunner eller fordi designerne av språket ikke ønsket å gå så langt (for eksempel fordi selvmodifiserende kode avvises). Vanligvis er det ikke mye mer refleksjon mulig for programmet enn å lære navnet og navnene på variablene og funksjonene fra kjøretidssystemet.

Refleksjon fører derfor ikke til riktig quine på de fleste programmeringsspråk.

Kode som data

De fleste programmeringsspråk gir liten hjelp til å representere programmer internt og til å jobbe med disse representasjonene:

• analysere dem ( parsing ),
• å generere nye programmer fra eksisterende representasjoner ( komposisjon ) og spesielt
• utføre det representerte programmet ( applikasjonen ).

Et velkjent anvendelse eksempel vil være en funksjon plotter , som er et program for plotting av grafene i noen matematiske funksjoner.

Med andre ord:

I mange programmeringsspråk er det ingen passende datatype med tilsvarende operasjoner for funksjoner.

I C kan du lagre et stykke programkode i en streng , men du kan gjøre lite med det, fordi det er vanskelig å analysere og utføre med hjelp av C. Du må da ty til komplekse merkede strukturer og eksterne biblioteker.

LISP er en positiv eksempel fordi dette språket representerer kildekoden i den algebraiske datatype listen , som det i hovedsak benytter seg ( homoiconicity ).

Quination

Ovennevnte har listet opp vanskeligheter et program har med å be om sin egen struktur. Likevel må det også være mulig å realisere en quine i C (se forklaringene på eksistensen av quines i den teoretiske delen). Følgende teknikk brukes for dette:

Hvis du ikke kan spørre om din egen struktur, må du vite det på forhånd.

Du designer programmet i to deler, en kalt koden og en kalt data. Dataene representerer koden (eller dens tekstform) og de er avledet fra koden på en algoritmisk måte (for det meste ved hjelp av anførselstegn, men noen ganger på en litt mer komplisert måte). Koden bruker dataene til å sende ut koden (noe som er enkelt fordi dataene representerer koden); deretter bruker den dataene til å sende ut dataene (noe som er mulig fordi dataene er hentet i en algoritmisk transformasjon).

Som forklart ovenfor er dette lettere å implementere på noen språk og vanskeligere å implementere på andre, for eksempel avhengig av om funksjoner er førsteklasses borgere av språket eller ikke.

I streng forstand bør quines være uavhengige av tegnsettet, og kildekoden, inkludert alle linjeskift, skal sendes ut nøyaktig igjen.

Eksempler

((lambda (x)
  (list x (list (quote quote) x)))
 (quote
    (lambda (x)
      (list x (list (quote quote) x)))))

package main
import "fmt"
func main() {
	fmt.Printf("%s%c%s%c\n", s, 0x60, s, 0x60)
}
var s = `
package main
import "fmt"
func main {
	fmt.Printf("%s%c%s%c\n", s, 0x60, s, 0x60)
}
var s = `

#include <stdio.h>
char*f="#include <stdio.h>%cchar*f=%c%s%c;main() {printf(f,10,34,f,34,10);}%c";main() {printf(f,10,34,f,34,10);}

a="a=%c%s%c;io.write(string.format(a,34,a,34))";io.write(string.format(a,34,a,34))

a="a=%c%s%c;print a%%(34,a,34)";print a%(34,a,34)

a="a=%c%s%c;print(a%%(34,a,34))";print(a%(34,a,34))

$a='$a=%c%s%c;printf($a,39,$a,39,10);%c';printf($a,39,$a,39,10);

$r='\'; $_=$r; s/([\\\'\\\\])/\\\\$1/g; print \'$r=\\\'\'.$_.$r;
'; $_=$r; s/([\'\\])/\\$1/g; print '$r=\''.$_.$r;

my $t="; say \"my \\\$t=\",\$t.perl,\$t"; say "my \$t=",$t.perl,$t

puts <<2*2,2
puts <<2*2,2
2

eval s=%q(puts"eval s=%q(#{s})")

fn main() {
    let x = "fn main() {\n    let x = ";
    let y = "print!(\"{}{:?};\n    let y = {:?};\n    {}\", x, x, y, y)\n}\n";
    print!("{}{:?};
    let y = {:?};
    {}", x, x, y, y)
}

using System;class Quine{static string f=
"using System;class Quine{{static string f={1}{0}{1};static void Main(){{Console.Write(f,f,Convert.ToChar(34));}}}}";
static void Main(){Console.Write(f,f,Convert.ToChar(34));}}

class Q{public static void main(String[]a){String f=
"class Q{public static void main(String[]a){String f=%c%s%1$c;System.out.printf(f,34,f);}}";
System.out.printf(f,34,f);}}

fun main(args: Array<String>){val f="""fun main(args: Array<String>){val f="%s"%s"%s";System.out.printf(f,'"',f,'"')}""";System.out.printf(f,'"',f,'"')}

(x=>console.log(x+JSON.stringify(x)+')'))("(x=>console.log(x+JSON.stringify(x)+')'))(")

[{$s = ';print("[{\$s = ".chr(39).$s.chr(39).$s);}]';print("[{\$s = ".chr(39).$s.chr(39).$s);}]

<?php printf($c = '<?php printf($c = %c%s%c, 39, $c, 39); ?>', 39, $c, 39); ?>

const a=';begin write(^#^/^.^3^4^`^!^}#39,a,#39,a)end.';begin write(^#^/^.^3^4^`^!^}#39,a,#39,a)end.

program Quine;{$APPTYPE CONSOLE}var x:String=
'program Quine;{$APPTYPE CONSOLE}var x:String=;begin Insert(#39+x+#39,x,46);WriteLn(x);ReadLn;end.';
begin Insert(#39+x+#39,x,46);WriteLn(x);ReadLn;end.

Teoretisk bakgrunn

Eksistensen av quines er teoretisk sikret av rekursjonssetningen (også kalt Kleenes fastpunktssetning ).

Begrunnelsen går omtrent som følger:

• Egenskapene til programmeringsspråk kan utledes fra resultatene av beregbarhetsteori , som analyserer veldig enkle modeller av programmer på en matematisk presis måte.
• Siden alle programmer (mer presist: deres begrensede kildetekster) kan telles, dvs. kartlagt bijectively til de naturlige tall , i denne modellen verden er det tilstrekkelig å angi et naturlig tall som en representasjon av et program. Dette tallet gjør det samme som kildekoden, nemlig valget av akkurat den funksjonen som tilsvarer semantikken i programmet.
• Med fastpunktsblokken kan det vises at det er et program med nummeret (med ), hvis utgang (for alle mulige innganger ) i sin tur er nummeret . Dermed er dette fra ovennevnte lemma i beregbarhetsteorien nøyaktig ekvivalent med et program som sender ut sin egen representasjon - en Quines.${\ displaystyle q}$${\ displaystyle \ forall x: \ varphi _ {q} (x) = q}$${\ displaystyle x}$${\ displaystyle q}$${\ displaystyle q}$

Uttalelsene fra beregbarhetsteorien for beregningsfunksjoner kan lett generaliseres til Turing-maskiner og dermed til slutt til alle Turing-komplette språk.

Quines er derfor ikke bare et resultat av ressurssterke programmerere som lurer et programmeringsspråk, det er heller en grunnleggende egenskap ved Turing-komplette programmeringsspråk at quines eksisterer for dem.

Se også

• HQ9 + ( esoterisk programmeringsspråk ): Skriver ut sin egen kildetekst ved hjelp av Q- kommandoen .
• reproduksjon

litteratur

• S. Barry Cooper: Beregnbarhetsteori. Chapman & Hall / CRC matematikk, Boca Raton FL et al. 2004, ISBN 1-58488-237-9 .
• Douglas R. Hofstadter : Gödel, Escher, Bach . Et endeløst flettet band. 16. utgave. Klett-Cotta, Stuttgart 2001, ISBN 3-608-94338-2 .
• Ken Thompson : Refleksjoner om tillitsfull tillit . I: Kommunikasjon av ACM . Vol. 27, nr. 8, aug 1984, s. 761-763.

weblenker

• Helside Quine (engelsk)
• Quines på mange språk (engelsk)

Individuelle bevis

1. ↑ Craig S. Kaplan: The Search for Self-Documenting Code