Rubrik: Denksportaufgaben

 

Selbstreproduzierende Programme

Ein recht bekanntes Programmier-Denkspiel, dessen Lösung selten in der Literatur auftaucht.

 

Aufgabe

Man soll ein Programm schreiben, das sich selber (Quellcode) ausgibt. Dieses alte Programmierproblem wird in dieser Notiz näher formuliert, untersucht und gelöst.

 

Präzisierung

Das Programm soll in einer ASCII-Datei abgespeichert sein, die mit dem Turbo Pascal Compiler von Borland (Version 4.0 oder höher) kompiliert die Liste des Quellcodes an den Bildschirm schreibt. Die Aufgabe gilt als gelöst, wenn die Programm-Quelldatei identisch ist mit der Ausgabedatei, die man erhält, wenn man die Bildschirmausgabe mit Redirection in eine zweite ASCII-Datei umleitet.

Selbstverständlich sind "billige" Lösungen nicht zugelassen, die etwa die Quelldatei als vorhanden annehmen, sie einlesen und wieder ausschreiben.

Bevor man zur Lösung weiterblättert oder die Überlegungen zur Lösung liest, kann man hier ein paar Minuten Bedenkzeit einschalten, und eine eigene Lösung erarbeiten.

* * *

 

Abstraktion

Die Aufgabe verblüfft anfangs wegen ihrer Unbestimmtheit. Sie scheint nicht wesentlich von der gewählten Programmiersprache abzuhängen. Konstruieren wir eine abstrakte Programmiersprache, in der die Aufgabe gewiss lösbar ist. Eine solche Sprache muss mindestens einen Befehl besitzen, der ein Argument an den Bildschirm ausgibt. Wenn alle Ausgabebefehle nur ihre Argumente höchstens einmal ausgeben, so ist die Aufgabe offensichtlich nicht lösbar. Wir brauchen also mindestens einen Befehl, der sein Argument mehrmals ausgibt.

Die minimalste Programmiersprache, die diesen Bedingungen genügt, besitzt einen einzigen Befehl, der das nachfolgende Zeichen zweimal an den Bildschirm schreibt. Der Quellcode für diese Befehl sei A. Nehmen wir weiter an, dass die Programmiersprache keine weiteren Garnierungen für Beginn und Ende benötigt. In dieser Sprache lautet das Programm, das die Aufgabe löst:

AA

Offenbar schreibt diesen Programm seinen eigenen Quellcode an den Bildschirm, da der Befehl A das darauffolgende A zweimal ausgibt.

 

Konkretisierung

In Pascal und ähnlichen Sprachen, müssen wir einerseits die Bezeichner als Zeichenkette konzipieren und andererseits am Anfang und Ende eine Minimalgarnierung anbringen. Um dieser Tatsache Rechnung zu tragen, modifizieren wir die obige Programmiersprache etwas:

Syntax:

A : mit den zwei folgenden Symbolen als Argumente

B : ohne Argumente

Semantik:

A : startet das Programm und gibt jedes der beiden Argumente zweimal am Bildschirm aus

B : beendet das Programm ordnungsgemäss

Die Lösung des Problems in dieser erweiterten Sprache lautet offensichtlich

AABB

Nach dieser Grundidee entwickelt man dann das Pascal-Programm, das die Aufgabe löst.

 

procedure r(s,t:string); begin writeln(s); writeln(#39,s,#39,#44); writeln(#39,t,#39); writeln(t); end; begin r('procedure r(s,t:string); begin writeln(s); writeln(#39,s,#39,#44); writeln(#39,t,#39); writeln(t); end; begin r(','); end.'); end.

 

Probe

Wenn die Datei WRITEME.PAS compiliert und ausgeführt wird, erscheint der Quellcode am Bildschirm.

C>WRITEME >TEMP.PAS

C>TPC TEMP

Turbo Pascal Version 5.5 Copyright (c) 1983,89 Borland International

TEMPPAS(4)

4 lines, 0,4 seconds, 2624 bytes code, 646 bytes data.

C>TEMP >WRITEME.PAS

C>COMP WRITEME.PAS TEMP.PAS

C:TEMP.PAS und C:WRITEME.PAS

EOF-Markierung nicht gefunden

Dateien sind identisch

Weitere Dateien vergleichen (J/N)? n

Die Probe macht man, in dem man WRITEME mit Redirection aufruft. Die Ausgabedatei (TEMP.PAS im Beispiel) kann man wieder compilieren und mit Redirection aufrufen: Die Quelldatei und die Ausgabedatei sind identisch. Der Zusatzschritt des zweimaligen Compilierens ist nicht immer notwendig. Nur wenn der Programmeditor unerwünschte CRs, LFs oder SUBs am Ende der ursprünglichen Datei hinterlassen hat, ist die Identität beim ersten Vergleich nicht gewährleistet.

 

Diskussion

Das Programm lehnt sich recht nah ans Schema AABB an. Damit keine Schwierigkeiten mit Zeilenenden innerhalb der beiden Argumente entstehen, wurde der übliche Pascal Header "program(input,output);" weggelassen, wie dies im Turbo Pascal ja erlaubt ist. Aus diesem Grund passt das ganze A auf eine Zeile im Turbo Editor und man vermeidet zusätzliche Aufblähung der Lösung mit Mehrfachzeilenbehandlung.

Die Vermeidung der Probleme mit dem Anführungszeichen durch Verwendung der ASCII-Code-Notation könnte "schöner" gelöst werden zulasten der konzisen Darstellung.

 

Nur Spielerei?

Die kleine Programmieraufgabe ist sicherlich nur Spielerei. Die Eigenschaft der Selbstreproduktion hat unter dem Namen "Computerviren" heute vorerst einmal einen sehr schlechten Ruf erhalten. (Im anbrechenden Zeitalter der Computernetze schüren zum Teil dieselben EDV-Manager die Angst vor dem Virus, die vor nicht allzu langer Zeit auf ihrer Time-Sharing-Anlage allen Benützern ihre Macht aufdrängten und ihre Aufsicht zumuteten. Der PC ohne Festplatte wird propagiert und Datenschnüffelprogramme überwachen das firmeninterne LAN, um zu überprüfen, ob auch nur die erlaubte Software (Hilfe! Viren!!) geladen ist. Dieser unglücklichen Entwicklung sollten wir durch Erfahrung gewarnt den Anspruch auf die freie Benützung der persönlichen Lieblings-Textverarbeitung entgegensetzen.) Die Vorteile des gezielten Einsatzes von Virenprogrammierung zu "nützlichen" und "guten" Zwecken liegen dabei auf der Hand: Computerviren haben heute schon eine äusserst robuste Kommunikationsfähigkeit bewiesen. Wo ausgeklügelste Kommunikationsprotokolle trotz zuverlässiger Hardware und kooperierender Software im Deadlock der Retries des internationalen Bankennetzes ersaufen, schaffen Computerviren trotz Mangel an Kooperation und mit bescheidener Hardwarezuverlässigkeit weltweite Kommunikation mit hoher Zuverlässigkeit und Geschwindigkeit. Die "blinde" Vervielfältigung und das gezielte "Impfen" mit "Antikörpern" entfaltet die notwendige Redundanz, die in einer glücklicherweise immer noch oft zufälligen Datenwelt zum Überleben notwendig ist. Wir Programmierer sollten vom prozeduralen, objekt-orientierten Prozessdenken zum viralen Denken vorstossen!

 

Variationen

Für c't-Leser stellt sich die Aufgabe, eine "anständige" Lösung in Standardpascal und mit schöner Zeilenschaltung zu entwickeln. Lösungsversionen in FORTRAN, C, LISP, Assembler, Prolog, BASIC, Smalltalk, Modula2 stehen auch noch aus. Mir scheinen sowohl klassische prozedurale Sprachen, wie auch deklarative Sprachen zur Lösung geeignet. Eine Programmiersprache, die keine Lösung zulässt, würde vielleicht Aufschluss geben, welches notwendige Eigenschaften einer Sprache sind, die Selbstreproduzierbarkeit ermöglichen.

Feb. 1990 Hartwig Thomas