Quine (Computerprogramm)

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

Hacker und Geeks haben eine Freude daran, 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 liesse sich in einer C-ähnlichen Programmiersprache naiv so schreiben:

   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 sog. Binary Datei), seine ursprüngliche Repräsention 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, z.B. die Bibliotheksfunktion ein Zeichen ausgeben ist noch zuläsig.

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 Version von C, wie z.B. Java oder C#, 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, z.B. aus Sicherheitsgründen, oder weil die Designer der Sprache nicht so weit gehen wollten (z.B. 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.

Code als Daten

Überhaupt bieten die meisten Programmiersprachen wenig Hilfe Programme angemessen intern zu repräsentieren und dann mit diesen Repräsentationen zu arbeiten:

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

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 anfagen, 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.

Funktionale Programmiersprachen sehen hingegen Funktionen als first class citizens (Bürger erster Klasse) an, und bieten entsprechende Unterstützung, daher sind hier Quines leichter zu realisieren. Ein Beispiel wäre LISP, weil hier Programmcode sehr einfach als Liste repräsentiert und manipuliert werden kann.

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, ein 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, geht das in einigen Sprachen leichter und in anderen schwieriger, z.B. je nachdem, ob Funktionen first class citizens der Sprache sind, oder nicht.

Ein Beispiel in LISP:

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

Ein Beispiel in C:

char*f="char*f=%c%s%c;main()
{printf(f,34,f,34,10);}%c";
main(){printf(f,34,f,34,10);}

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 kann, 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 Nummer leistet das gleiche, wie der Quelltext, nämlich genau die Funktion auszuwählen, die der Semantik des Programms entspricht.
Mit dem Fixpunktsatz lässt sich zeigen, dass es ein Programm mit der Nummer $q$ gibt, mit $\forall x:\varphi _{q}(x)=q$ , bei der also die Ausgabe des $q$ -ten Programms (für alle möglichen Eingaben $x$ ) wiederum die Nummer $q$ ist. Somit ist dieses $q$ aus dem obigen Lemma der Berechenbarkeitstheorie genau das Äquivalent eines Programms, welches seine eigene Repräsentation ausgibt, also ein Quine!

Die Aussagen aus der Berechenbarkeitstheorie für berechenbare Funktionen lassen sich leicht auf Turing-Maschinen 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 von Programmiersprachen, dass für sie Quines existieren.

Literatur

Cooper, Barry S.: Computability Theory, Chapman & Hall/CRC mathematics (2003), ISBN 1-58488-237-9
Hofstadter, Douglas R.: Gödel, Escher, Bach, ein Endloses Geflochtenes Band, ISBN 3-608-94338-2

Weblinks