Quine (Computerprogramm)

Ein Quine ist ein Art von Computerprogramm, das eine Kopie seiner selbst (üblicherweise seines Quelltextes) als Ausgabe schreibt. Es handelt sich somit um eine Form der Selbstbezüglichkeit.

Hacker und Geeks sehen es als sportliche Herausforderung, die kleinstmöglichen Quines in Programmiersprachen ihrer Wahl zu erstellen (siehe IOCCC).

Quines sind nach dem Logiker und Philosophen Willard Van Orman Quine benannt.

Konstruktion von Quines

Frage dich selbst

Ein Quine ließe sich in einem C-ähnlichen Pseudo-Code so schreiben^[1]

main() {
    print myself out.
}

Üblicherweise werden C-Programme übersetzt, d. h. die Laufzeitversion des Programms liegt in Maschinensprache vor (Repräsentation als Folge von Bytes, abgespeichert in einer sogenannten binären Datei), seine ursprüngliche Repräsentation ist jedoch in der Regel ein ASCII-codierter Quelltext, der zudem noch in einer anderen Datei abgelegt ist. Der für diesen Ansatz zur Implementierung eines Quines benötigte Zugriff auf die eigene Repräsentation (myself) wäre also sehr kompliziert.

Weiter fordert man für ein Quine, dass es abgeschlossen ist:

• Es soll ohne Zugriff auf externe Daten auskommen, womit auch der Zugriff auf die eigene Quelltextdatei ausgeschlossen ist.
• Ebenso soll der wesentliche Code im Quine selbst vorhanden sein, weshalb externe Funktionen nur spärlich genutzt werden sollen, die Bibliotheksfunktion ein Zeichen ausgeben etwa ist noch zulässig.

Nur wenige Sprachen unterstützen Selbstbezüglichkeit (Reflexion) in der Form, dass ein Programm dieser Sprache Zugriff auf seine eigene Repräsentation hat.

Eine interpretierte Programmiersprache, wie zum Beispiel Perl oder Python, hätte es prinzipiell leichter, da man die vom Interpreter benötigte Repräsentation des auszuführenden Programms auch dem selbigen verfügbar machen könnte, aber in der Regel wird das nicht unterstützt, zum Beispiel aus Sicherheitsgründen, oder weil die Designer der Sprache nicht so weit gehen wollten (zum Beispiel weil selbstmodifizierender Code abgelehnt wird). Meist ist dem Programm dort nicht viel mehr Reflexion möglich, als seinen Namen und die Namen seiner Variablen und Funktionen vom Laufzeitsystem zu erfahren.

Reflexion führt daher in den meisten Programmiersprachen nicht zu einem korrekten Quine.

Code als Daten

Die meisten Programmiersprachen bieten wenig Hilfe, Programme angemessen intern zu repräsentieren und mit diesen Repräsentationen zu arbeiten:

• sie zu analysieren (Parsen),
• aus vorhandenen Repräsentationen neue Programme zu erzeugen (Komposition) und insbesondere
• das repräsentierte Programm auszuführen (Applikation).

Ein bekanntes Anwendungsbeispiel wäre ein Funktionsplotter, das ist ein Programm zum Plotten der Graphen beliebiger mathematischer Funktionen.

Mit anderen Worten:

Für Funktionen gibt es in vielen Programmiersprachen keinen angemessenen Datentyp mit entsprechenden Operationen.

In C kann man ein Stück Programmcode in einer Zeichenkette ablegen, man kann aber wenig damit anfangen, denn dieser ist mit den Mitteln von C nur aufwendig zu analysieren und auszuführen. Man muss dann zu komplexen verpointerten Strukturen und externen Bibliotheken greifen.

Ein positives Beispiel ist LISP, weil diese Sprache Quellcode im algebraischen Datentyp Liste darstellt, den sie auch selbst hauptsächlich verwendet (Homoikonizität).

Quinierung

Die obigen Ausführungen haben die Schwierigkeit aufgeführt, die ein Programm hat, falls es seine eigene Struktur erfragen will. Dennoch muss es auch in C möglich sein, einen Quine zu realisieren (siehe die Ausführungen zur Existenz von Quines im Theorieteil). Dazu wird folgende Technik verwendet:

Wenn man die eigene Struktur nicht erfragen kann, muss man sie von vornherein wissen.

Man entwirft das Programm in zwei Teilen, in einen, den man den Code nennt, und einen, den man die Daten nennt. Die Daten repräsentieren den Code (bzw. seine Textform) und sie sind auf einem algorithmischen Weg vom Code hergeleitet (meistens, indem Anführungszeichen gesetzt wurden, manchmal aber noch auf eine leicht kompliziertere Weise). Der Code benutzt die Daten, um den Code auszugeben (was einfach ist, da die Daten den Code darstellen); dann benutzt er die Daten, um die Daten auszugeben (was möglich ist, da die Daten in einer algorithmischen Transformation besorgt werden).

Wie oben ausgeführt, ist dies in einigen Sprachen leichter und in anderen schwieriger umzusetzen, zum Beispiel je nachdem, ob Funktionen first class citizens der Sprache sind oder nicht.

Im strengen Sinn sollten Quines vom Zeichensatz unabhängig sein, und der Quellcode sollte einschließlich aller Zeilenwechsel exakt wieder ausgegeben werden.

Beispiele

((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=%q print(a:format(a))" print(a:format(a))

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)
}

var f="var f={1}{0}{1};Console.Write(f,f,(char)34);";Console.Write(f,f,(char)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.

Theoretischer Hintergrund

Die Existenz von Quines wird theoretisch durch den Rekursionssatz (auch Fixpunktsatz von Kleene genannt) gesichert.

Grob verläuft die Argumentation so:

• Man kann auf die Eigenschaften von Programmiersprachen durch Ergebnisse der Berechenbarkeitstheorie schließen, welche sehr einfache Modelle von Programmen mathematisch exakt analysiert.
• Da man alle Programme (genauer: deren endliche Quelltexte) abzählen, also bijektiv auf die natürlichen Zahlen abbilden kann, reicht in dieser Modellwelt die Angabe einer natürlichen Zahl als Repräsentation eines Programms vollkommen aus. Diese Zahl leistet dasselbe wie der Quelltext, nämlich die Auswahl genau der Funktion, die der Semantik des Programms entspricht.
• Mit dem Fixpunktsatz von Kleene lässt sich zeigen, dass es ein Programm mit der Nummer ${\displaystyle q}$ (mit ${\displaystyle \forall x:\varphi _{q}(x)=q}$) gibt, dessen Ausgabe (für alle möglichen Eingaben ${\displaystyle x}$) wiederum die Zahl ${\displaystyle q}$ ist. Somit ist dieses ${\displaystyle q}$ aus dem obigen Lemma der Berechenbarkeitstheorie genau das Äquivalent eines Programms, welches seine eigene Repräsentation ausgibt – eines Quines.

Die Aussagen aus der Berechenbarkeitstheorie für berechenbare Funktionen lassen sich leicht auf Turingmaschinen und damit letztlich auf beliebige Turing-vollständige Sprachen verallgemeinern.

Quines sind daher nicht nur zufällig das Ergebnis findiger Programmierer, die eine Programmiersprache austricksen, es handelt sich vielmehr um eine fundamentale Eigenschaft Turing-vollständiger Programmiersprachen, dass für sie Quines existieren.

Siehe auch

• HQ9+ (Esoterische Programmiersprache): Gibt mittels des Q-Befehls den eigenen Quelltext aus.
• Reproduktion

Literatur

• S. Barry Cooper: Computability Theory. Chapman & Hall/CRC mathematics, Boca Raton FL u. a. 2004, ISBN 1-58488-237-9.
• Douglas R. Hofstadter: Gödel, Escher, Bach. Ein Endloses Geflochtenes Band. 16. Auflage. Klett-Cotta, Stuttgart 2001, ISBN 3-608-94338-2.
• Ken Thompson: Reflections on Trusting Trust. In: Communications of the ACM. Vol. 27, No. 8, August 1984, S. 761–763.

Weblinks

• Ausführliche Seite zu Quines (englisch)
• Quines in vielen Sprachen (englisch)

Einzelnachweise

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