Quine (Computerprogramm) - de.LinkFang.org

Quine (Computerprogramm)

Ein Quine ist ein 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.

Inhaltsverzeichnis

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.

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:

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


Sprache Beispiel Hinweise
Lisp
((lambda (x)
  (list x (list (quote quote) x)))
 (quote
    (lambda (x)
      (list x (list (quote quote) x)))))
Go
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 = `
Nutzt die ASCII-Kodierung des Akzents Grave
C
#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);}
Nutzt die ASCII-Kodierung des Anführungszeichens
Lua
a="a=%c%s%c;io.write(string.format(a,34,a,34))";io.write(string.format(a,34,a,34))
Nutzt die ASCII-Kodierung des Anführungszeichens
Python 2
a="a=%c%s%c;print a%%(34,a,34)";print a%(34,a,34)
Nutzt die ASCII-Kodierung des Anführungszeichens
Python 3
a="a=%c%s%c;print(a%%(34,a,34))";print(a%(34,a,34))
Nutzt die ASCII-Kodierung des Anführungszeichens
Perl
$a='$a=%c%s%c;printf($a,39,$a,39,10);%c';printf($a,39,$a,39,10);
Nutzt die ASCII-Kodierung des Hochkommas
Perl
$r='\'; $_=$r; s/([\\\'\\\\])/\\\\$1/g; print \'$r=\\\'\'.$_.$r;
'; $_=$r; s/([\'\\])/\\$1/g; print '$r=\''.$_.$r;
Vom Zeichensatz unabhängig
Perl6
my $t="; say \"my \\\$t=\",\$t.perl,\$t"; say "my \$t=",$t.perl,$t
Ruby
puts <<2*2,2
puts <<2*2,2
2
Vom Zeichensatz unabhängig
Ruby
eval s=%q(puts"eval s=%q(#{s})")
Vom Zeichensatz unabhängig
Rust
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)
}
C#
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));}}
Java
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);}}
Nur eine Zeile
Kotlin
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,'"')}
Nur eine Zeile, vom Zeichensatz unabhängig
JavaScript
var x = '"'+"; alert('var x = '+x[9]+x[0]+x[9]+'+'+x+x);"; alert('var x = '+x[9]+x[0]+x[9]+'+'+x+x);
Sleep
[{$s = ';print("[{\$s = ".chr(39).$s.chr(39).$s);}]';print("[{\$s = ".chr(39).$s.chr(39).$s);}]
PHP
<?php printf($c = '<?php printf($c = %c%s%c, 39, $c, 39); ?>', 39, $c, 39); ?>
Pascal
const a=';begin write(^#^/^.^3^4^`^!^}#39,a,#39,a)end.';begin write(^#^/^.^3^4^`^!^}#39,a,#39,a)end.
nutzt Escape-Sequenzen
Delphi
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.
ohne Zeilenumbrüche (wäre sonst zu lang für diese Tabelle)

Theoretischer Hintergrund


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

Grob verläuft die Argumentation so:

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


Literatur


Weblinks


Einzelnachweise


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



Kategorien: Programmierung | Theoretische Informatik | Berechenbarkeitstheorie

Werbung:


Quelle: Wikipedia - https://de.wikipedia.org/wiki/Quine (Computerprogramm) (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 01.03.2020 07:32:45 CET - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.