Zum Inhalt springen

Quine (Computerprogramm) und Friedhof Pasing: Unterschied zwischen den Seiten

aus Wikipedia, der freien Enzyklopädie
(Unterschied zwischen Seiten)
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
 
K Halbgeviertstrich
 
Zeile 1: Zeile 1:
Der '''Friedhof Pasing''' wurde 1903 in der Gemeinde [[Pasing]] auf einem quadratischen [[Grundstück]] angelegt. Heute befindet er sich in einem [[Wohngebiet]] und wird von der Lampertstraße im Norden, der Karl-Hromadnik-Straße im Westen und der Blumenauer Straße im Osten umrahmt. Als Pasing 1938 von [[München]] eingemeindet wurde, ging die Zuständigkeit für den Friedhof an die Landeshauptstadt über.<ref>[http://www.muenchen.de/sehenswuerdigkeiten/orte/120235.html Friedhof Pasing auf www.muenchen.de]</ref> Auf dem Friedhof befinden sich 6913 [[Grab|Gräber]] – davon 5807 [[Erdgrab|Erdgräber]]. Unter anderem befinden sich hier auch Gräber von Persönlichkeiten, die in der Entwicklung von Pasing und München eine Rolle gespielt haben – darunter [[Elmar Messerschmitt]] (1920–1992, Erfinder und Neffe des [[Flugzeugkonstrukteur]]s [[Willy Messerschmitt]], Grab 25-A-8), [[Carl von Scapinelli|Carl Graf von Scapinelli]] (1876–1959, [[Schriftsteller]] und [[Kabarettist]]. Er verfasste u. a. [[Drehbuch|Drehbücher]] für [[Emelka]]-Filmproduktionen (Vorgänger der [[Bavaria Film]]), Grab M-W-49), [[Alois Ebenböck]] (1867–1937, Hofwachslichterfabrikant und Ehrenbürger von Pasing, Grab Mauer-N-6/7) und [[Karl Hromadnik]] (1857–1918, [[Fabrikant]] und Ehrenbürger, Grab W-36/39).<ref>[http://unikat-krawatten.de/Friedhof%20Pasing.htm Bilder vom Friedhof Pasing auf http://unikat-krawatten.de]</ref>
Ein '''Quine''' ist ein [[Computerprogramm]], das eine Kopie seiner selbst (üblicherweise seines [[Quelltext]]es) als Ausgabe schreibt.
Es handelt sich somit um eine Form der [[Selbstbezüglichkeit]].


== Aussegnungshalle ==
[[Hacker]] und [[Geek]]s sehen es als sportliche Herausforderung, die kleinstmöglichen Quines in [[Programmiersprache]]n ihrer Wahl zu erstellen (siehe [[International Obfuscated C Code Contest|IOCCC]]).
Das städtische Referat für [[Gesundheit]] und [[Umwelt]] (Abteilung: Städtische Bestattung) erhielt für die [[Sanierung]] der [[Aussegnungshalle]] des Friedhofs Pasing eine lobende Erwähnung beim [[Fassadenpreis der Landeshauptstadt München 2006]]. Im Rahmen der Sanierung wurden die Sandsteinrundsäulen in den Schallöffnungen des [[Glockenturm]]s saniert, Teilflächen des Daches erneuert, Fenster, Türen und Tore teilerneuert und überarbeitet sowie der historische Fassadenputz saniert.<ref>[http://www.muenchen.de/Rathaus/rgu/friedhoefe/aussenfriedhoefe/pasing/index.html Bericht über die lobende Erwähnung der Sanierung der Fassade der Aussegnungshalle im Friedhof Pasing im Rahmen des Fassadenwettbewerbs 2006 auf www.muenchen.de]</ref>


== Weblinks ==
Quines sind nach dem Logiker und Philosophen [[Willard Van Orman Quine]] benannt.
* [http://www.muenchen.de/sehenswuerdigkeiten/orte/120235.html Friedhof Pasing auf www.muenchen.de]

* [http://friedhof.stadt-muenchen.net/d_friedhof.php?friedhof=Friedhof%20Pasing Friedhof Pasing auf http://friedhof.stadt-muenchen.net]
== Konstruktion von Quines ==
* [http://unikat-krawatten.de/Friedhof%20Pasing.htm Bilder vom Friedhof Pasing auf http://unikat-krawatten.de]
=== Frage dich selbst ===
Ein Quine ließe sich in einem [[C (Programmiersprache)|C]]-ähnlichen Pseudo-Code so schreiben<ref>Craig S. Kaplan: ''[http://www.cgl.uwaterloo.ca/~csk/washington//paper/index.html The Search For Self-Documenting Code]''</ref>

<source lang="c">
main() {
print myself out.
}
</source>

Üblicherweise werden C-Programme [[Compiler|übersetzt]], d.&nbsp;h. die [[Laufzeit (Informatik)|Laufzeit]]version des Programms liegt in [[Maschinensprache]] vor (Repräsentation als Folge von [[Byte]]s, abgespeichert in einer sog. binären 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, die Bibliotheksfunktion ''ein Zeichen ausgeben'' etwa ist noch zulässig.

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

Eine [[Interpreter|interpretierte]] Programmiersprache, wie zum Beispiel [[Perl (Programmiersprache)|Perl]] oder [[Python (Programmiersprache)|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 ([[Parser|Parsen]]),
* aus vorhandenen Repräsentationen neue Programme zu erzeugen ([[Komposition (UML)|Komposition]]) und insbesondere
* das repräsentierte Programm auszuführen ([[Auswertung (Informatik)|Applikation]]).

Ein bekanntes Anwendungsbeispiel wäre ein [[Funktionsplotter]], das ist ein Programm zum [[Plotter|Plotten]] der [[Funktionsgraph|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, geht das in einigen Sprachen leichter und in anderen schwieriger, zum Beispiel je nachdem, ob Funktionen ''[[First-Class-Funktion|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.

{| class="wikitable"
|- class="hintergrundfarbe5"
! Sprache !! Beispiel !! Hinweise
|-
| [[Lisp]] ||
<source lang="lisp">
((lambda (x)
(list x (list (quote quote) x)))
(quote
(lambda (x)
(list x (list (quote quote) x)))))
</source>
||
|-
| [[C (Programmiersprache)|C]] ||
<source lang="c">
char*f="char*f=%c%s%c;main() {printf(f,34,f,34,10);}%c";main() {printf(f,34,f,34,10);}
</source>
|| Nutzt die ASCII-Kodierung des Anführungszeichens
|-
| [[Lua]] ||
<source lang="lua">
a="a=%c%s%c;io.write(string.format(a,34,a,34))";io.write(string.format(a,34,a,34))
</source>
|| Nutzt die ASCII-Kodierung des Anführungszeichens
|-
| [[Python (Programmiersprache)|Python 2]] ||
<source lang="python">
a="a=%c%s%c;print a%%(34,a,34)";print a%(34,a,34)
</source>
|| Nutzt die ASCII-Kodierung des Anführungszeichens
|-
| [[Python (Programmiersprache)|Python 3]] ||
<source lang="python">
a="a=%c%s%c;print(a%%(34,a,34))";print(a%(34,a,34))
</source>
|| Nutzt die ASCII-Kodierung des Anführungszeichens
|-
| [[Perl (Programmiersprache)|Perl]] ||
<source lang="perl">
$a='$a=%c%s%c;printf($a,39,$a,39,10);%c';printf($a,39,$a,39,10);
</source>
|| Nutzt die ASCII-Kodierung des Anführungszeichens
|-
| Perl ||
<source lang="perl">
$r='\'; $_=$r; s/([\\\'\\\\])/\\\\$1/g; print \'$r=\\\'\'.$_.$r;
'; $_=$r; s/([\'\\])/\\$1/g; print '$r=\''.$_.$r;
</source>
|| Vom Zeichensatz unabhängig
|-
| [[Ruby (Programmiersprache)|Ruby]] ||
<source lang="ruby">
puts <<2*2,2
puts <<2*2,2
2
</source>
|| Vom Zeichensatz unabhängig
|-
| Ruby ||
<source lang="ruby">
eval s=%q(puts"eval s=%q(#{s})")
</source>
|| Vom Zeichensatz unabhängig
|-
| [[C-Sharp|C#]] ||
<source lang="csharp">
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));}}
</source>
||
|-
| [[Java (Programmiersprache)|Java]] ||
<source lang="java">
public class q{static String s="public class q{1}static String s={3}{0}{3};
public static void main(String[] a){1}System.out.println(java.text.MessageFormat.format(s,s,''{1}'',''{2}'',''{3}''));{2}{2}";
public static void main(String[] a){System.out.println(java.text.MessageFormat.format(s,s,'{','}','"'));}}
</source>
||
|-
| [[Javascript]] ||
<source lang="javascript">
(function f(){console.log('('+f+'())');}())
</source>
||
|-
| [[Sleep (Programmiersprache)|Sleep]] ||
<source lang="php">
[{$s = ';print("[{\$s = ".chr(39).$s.chr(39).$s);}]';print("[{\$s = ".chr(39).$s.chr(39).$s);}]
</source>
||
|-
| [[PHP]] ||
<source lang="php">
$vEngu = 96; printf($c = '$vEngu = %s; printf($c = %c%s%c, $vEngu, 39, $c, 39);', $vEngu, 39, $c, 39);
</source>
||
|-
| [[Pascal (Programmiersprache)|Pascal]] ||
<source lang="pascal">
const a=';begin write(^#^/^.^3^4^`^!^}#39,a,#39,a)end.';begin write(^#^/^.^3^4^`^!^}#39,a,#39,a)end.
</source>
|| nutzt Escape-Sequenzen
|-
| [[Embarcadero Delphi|Delphi]] ||
<source lang="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.
</source>
|| 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:

* 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 [[Bijektion|bijektiv]] auf die [[Natürliche Zahl|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]] lässt sich zeigen, dass es ein Programm mit der Nummer <math>q</math> (mit <math>\forall x: \varphi_q(x) = q</math>) gibt, dessen Ausgabe (für alle möglichen Eingaben <math>x</math>) wiederum die Zahl <math>q</math> ist. Somit ist dieses <math>q</math> aus dem obigen [[Hilfssatz|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 [[Turingmaschine]]n und damit letztlich auf beliebige [[Turing-Vollständigkeit|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.


== Einzelnachweise ==
== Einzelnachweise ==
<references />
<references/>

== Siehe auch ==
* [[HQ9+]] ([[Esoterische Programmiersprache]]): Gibt mittels des [[HQ9+#Befehlssatz|''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]]: ''[http://cm.bell-labs.com/who/ken/trust.html Reflections on Trusting Trust]''. In: ''[[Communications of the ACM]].'' Vol. 27, No. 8, August 1984, S. 761–763.

== Weblinks ==
* [http://www.madore.org/~david/computers/quine.html Ausführliche Seite zu Quines] (englisch)
* [http://www.nyx.net/~gthompso/quine.htm Quines in vielen Sprachen] (englisch)


{{Coordinate|NS=48.136423|EW=11.45874|type=landmark|region=DE-BY}}
[[Kategorie:Programmierung]]
[[Kategorie:Theoretische Informatik]]
[[Kategorie:Friedhof in München|Pasing]]
[[Kategorie:Berechenbarkeitstheorie]]
[[Kategorie:Baudenkmal in Pasing]]

Version vom 28. September 2014, 22:56 Uhr

Der Friedhof Pasing wurde 1903 in der Gemeinde Pasing auf einem quadratischen Grundstück angelegt. Heute befindet er sich in einem Wohngebiet und wird von der Lampertstraße im Norden, der Karl-Hromadnik-Straße im Westen und der Blumenauer Straße im Osten umrahmt. Als Pasing 1938 von München eingemeindet wurde, ging die Zuständigkeit für den Friedhof an die Landeshauptstadt über.[1] Auf dem Friedhof befinden sich 6913 Gräber – davon 5807 Erdgräber. Unter anderem befinden sich hier auch Gräber von Persönlichkeiten, die in der Entwicklung von Pasing und München eine Rolle gespielt haben – darunter Elmar Messerschmitt (1920–1992, Erfinder und Neffe des Flugzeugkonstrukteurs Willy Messerschmitt, Grab 25-A-8), Carl Graf von Scapinelli (1876–1959, Schriftsteller und Kabarettist. Er verfasste u. a. Drehbücher für Emelka-Filmproduktionen (Vorgänger der Bavaria Film), Grab M-W-49), Alois Ebenböck (1867–1937, Hofwachslichterfabrikant und Ehrenbürger von Pasing, Grab Mauer-N-6/7) und Karl Hromadnik (1857–1918, Fabrikant und Ehrenbürger, Grab W-36/39).[2]

Aussegnungshalle

Das städtische Referat für Gesundheit und Umwelt (Abteilung: Städtische Bestattung) erhielt für die Sanierung der Aussegnungshalle des Friedhofs Pasing eine lobende Erwähnung beim Fassadenpreis der Landeshauptstadt München 2006. Im Rahmen der Sanierung wurden die Sandsteinrundsäulen in den Schallöffnungen des Glockenturms saniert, Teilflächen des Daches erneuert, Fenster, Türen und Tore teilerneuert und überarbeitet sowie der historische Fassadenputz saniert.[3]

Einzelnachweise

  1. ↑ Friedhof Pasing auf www.muenchen.de
  2. ↑ Bilder vom Friedhof Pasing auf http://unikat-krawatten.de
  3. ↑ Bericht über die lobende Erwähnung der Sanierung der Fassade der Aussegnungshalle im Friedhof Pasing im Rahmen des Fassadenwettbewerbs 2006 auf www.muenchen.de

Koordinaten: 48° 8′ 11,1″ N, 11° 27′ 31,5″ O

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Quine_(Computerprogramm)&oldid=134441398“