P''

(Lese "P double prime")

• esolang
• brainfuck
• befunge
• interpreter
• P''

Eine theoretische Meisterleistung!

Wenn INTERCAL die scherzhaft gemeinte Mutter aller esoterischen Programmiersprachen darstellt, so ist P'' wegen ihrer kryptischen Radikalität gewissermaßen die Großmutter, allerdings nicht nur der esolangs, sondern auch aller modernen produktiven Programmiersprachen. Als allererste 'goto-lose' Sprache, die zwar maximal reduktionistisch, dabei aber dennoch Turing-vollständig ist, war sie die konzeptionelle Wegbereiterin des Paradigmas der strukturierten Programmierung. Ihre Herleitung stellt eine Sternstunde der theoretischen Informatik dar.

Meine bescheidene Implementierung von P'' versucht, die syntaktischen und semantischen Regeln, die Corrado Böhm in seiner wegweisenden Arbeit von 1964 "Über eine Familie von Turing-Maschinen und die damit verbundenen Programmiersprachen" [1] dargelegt hat, so genau wie möglich einzuhalten.

P'' ist eine Sprache, welche für rein theoretische Zwecke entwickelt wurde. Sie war nie für die praktische Programmierung gedacht. Eine strikte Umsetzung wird daher aus praktischer Sicht unweigerlich mit erheblichen Nachteilen verbunden sein. Die meisten früheren Implementierungen von P'' versuchen, diese Mängel zu umgehen (mehr dazu weiter unten). Alle "erweiterten" Implementierungen können jedoch nicht als »echte" Implementierungen von P''« im engeren Sinne angesehen werden.

Die konzeptionelle Umgebung für P'' ist eine Turingmaschine mit einem unendlichen unidirektionalen Speicherband und einem beliebigen endlichen Alphabet {c₀, c₁, ..., c_n}, wobei n ≥ 1 und c₀ das leere Symbol des Bandes ist. Das Band wird über einen Lese- / Schreibkopf, der über einer gegebenen Speicherzelle positioniert ist, ausgelesen und / oder beschrieben. P'' (Double Prime) ist eine kontextfreie, drastisch spartanische Subsprache der allgemeinen Programmiersprache P' (Single Prime), welche ihrerseits der gesamten Familie möglicher Turing-Maschinen entspricht.

Böhms Arbeit beweist im weiteren Verlauf, dass selbst diese reduzierte Sprache die Fähigkeit besitzt, alle partiellen rekursiven Funktionen zu berechnen. Durch die Verwendung der bijektiven Basis-k-Notation für das Bandalphabet konnte Böhm seine Beweisformeln so auslegen, dass sie unabhängig von der Anzahl n der Symbole im Bandspeicheralphabet sind.

P'' wird durch die folgenden Formationsregeln definiert:

1. λ, R sind Wörter in P'' (Axiom der Atome);
2. Wenn α, β Wörter in P'' sind, dann ist dies auch αβ (Zusammensetzungsregel);
3. Wenn α ein Wort in P'' ist, dann ist dies auch (α) (Iterationsregel).

Das endliche Alphabe Ω'' (von P'') besteht nur aus vier Zeichen, d.h. Ω'' = { λ, R, (, ) }. Diese entsprechen den Anweisungen:

• R : Bewege den Kopf um eine Zelle nach rechts, soweit vorhanden.
• λ : Ersetze das eingelesene Zeichen c_i durch c_i+1 mod (n+1) und bewege den Kopf um eine Zelle nach links.
• ( : Gehe in die Schleife innerhalb der Klammer, wenn die aktuelle Zelle ≠ c₀.
• ) : Verlasse die Schleife, wenn die aktuelle Zelle = c₀, und führe die nächste Anweisung außerhalb der Klammer aus.

Es ist wichtig, sich zu vergegenwärtigen, daß der numerische Inhalt einer Zelle 'umlaufend inkrementiert', d.h. c_n+1 = c₀.

Lassen Sie uns nun einen Blick auf drei wichtige praktische Limitationen werfen, die dieser eingeschränkte Befehlssatz von P'' mit sich bringt:

1. Um die aktuelle Zelle mit dem inhalt c_i zu dekrementieren, muss ein Programm [λR]ⁿ ausführen, d.h. n-mal λR, um den Umlauf nach c_i-1 vorzunehmen. Wenn die Zellen der Maschine beispielsweise jeweils ein Byte enthalten, würde das Dekrementieren der aktuellen Zelle erforderlich machen, dass 255 Wiederholungen von λR ausgeführt werden, was rechnerisch ineffektiv zu implementieren ist, und eine Quälerei beim Codieren darstellt.
2. Die umständliche Art des Dekrementierens einer Zelle in P'' macht darüber hinaus eines der bemerkenswertesten Merkmale der Sprache, d.h. die 'while'-Schleife zum Steuern des Programmflusses, sehr mühsam in der tatsächlichen Anwendung im Code. Viele Anwendungen von '(' ... ')' setzen einen Iterator in einer benachbarten Zelle voraus, der durch Code in den Klammern dekrementiert wird, bis '0' zum Beenden der Schleife erreicht ist. Bei Implementierung von 'Dekrement um 1' mittels 255 x 'λR' wird dies keinen begeisterten Einsatz finden.
3. Da P'' im Rahmen eines mathematischen Beweiseses auf dem Gebiet der theoretischen Informatik entwickelt wurde, waren keine Eingabe- / Ausgabefunktionen erforderlich. Daher gibt es in P'' weder eine Methode zur Benutzerinteraktion, noch zur Ausgabe von Ergebnissen.

Urs Müllers viel später entstandene Sprache Brainfuck aus dem Jahr 1993 wird oft als einfaches Homolog zu P'' beschrieben. Dies gilt jedoch nur auf konzeptioneller Ebene, ist jedoch in Bezug auf die syntaktische Konstruktion unzutreffend. Obwohl es im Brainfuck- Anweisungsalphabet durchaus einige direkte Äquivalente zu Elementen aus Ω'' gibt, d.h.

• ' [ ' ≡ ' ( '
• ' ] ' ≡ ' ) '
• ' > ' ≡ ' R ' ,

benötigen drei weitere Brainfuck-Anweisungen zusammengesetzte Äquivalente in P'', d.h.:

• ' + ' ≡ ' λR '
• ' - ' ≡ ' [λR]ⁿ '
• ' < ' ≡ ' [λR]ⁿλ ' ,

Aus Gründen der Lesbarkeit verwendete sogar Böhm selbst in seinen Codebeispielen "Unterprogramme" zur Erstellung seines Beweises, die letztendlich genau den "fehlenden" Brainfuck-Anweisungen entsprechen, d.h.:

• r ≡ λR ,
• r' ≡ [λR]ⁿ ,
• L ≡ r'λ .

In dieser Kurzschrift sieht dann eine Zeile Beispielcode in P'' folgendermaßen aus: » T- ≡ (r) R² ( (r' L r R) R) L «.

Darüber hinaus fehlen in P'' jegliche Äquivalente für die Ein- und Ausgabeinstruktionen von Brainfuck, d.h. ' , ' und ' . ' Infolgedessen wäre streng implementiertes P'' selbst zu Demonstrationszwecken ziemlich unbrauchbar. So unpraktisch es für sich genommen auch sein mag, ist Brainfuck ein hochgradig "praxistauglicher" Nachkomme von P ", welche dennoch ein theoretisches Meisterwerk bleibt.

Führen Sie sich erneut vor Augen, dass es für jedes erdenkliche Programm in jeder anderen erdenklichen Programmiersprache tatsächlich ein äquivalentes Programm P_f ∈ P'' gibt, welches dieselben rechnerischen Fähigkeiten besitzt. Und das mit nur vier Anweisungen!

[1] ICC Bulletin, Vol. 3, No. 3, July 1964

P'' implementiert:

Einige Kompromisse...

1. Böhms Turingmaschine besitzt ein links-unendliches Speicherband. Aufgrund der in unserem Kulturkreis konventionellen Leserichtung von links nach rechts ist die Indizierung des Speichers in der hiesigen Implementierung spiegelbildlich vorgenommen.
2. Um die Darstellung von ASCII-Zeichen zu vereinfachen, wurde ein Speicheralphabet von 8 bit (0-255) gewählt.
3. P'' weist eigentlich keinerlei Ausgabefunktion auf. Ich habe dennoch in Analogie zu Brainfuck einen Ausgabebefehl implementiert, da man sonst das Programmverhalten gar nicht nachvollziehen könnte. Mit der Instruktion ' ô ' wird der Inhalt der aktuellen Speicherzelle als ASCII / UTF-8 Zeichen ausgegeben. Puristen können ja auf diesen Befehl verzichten ;-)

Der restriktive Instruktionssatz von P'' wurde ansonsten vollständig aufrecht erhalten. Es wurden keinerlei weiteren Instruktionen aus möglichen Subroutinen generiert. Es wird ohnehin niemand auf die Idee kommen, P'' für produktive Programmierung einzusetzen...

Wer tatsächlich ein 'größeres' Programm bei der Arbeit sehen möchte, kann sich meine P''-Version von '99 bottles of beer' ansehen. Aber vielleicht erst nach dem Beispielprogramm auf dieser Seite. Oder nach ein paar Bierchen.

Schreibe Deinen eigenen Code hierhin:

Beispiel-Code findet sich weiter unten auf dieser Seite.

---

; oder

; oder

ms

◀ Speicherband

Output ▼

Beispiel-Code:

(Klicke auf die Schaltfläche▼ um das Beispiel in den RUN-Bereich zu kopieren ▲)

λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRô
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRô
λRλRλRλRλRλRλRô
ô
λRλRλRô
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRλRλRλR
λRλRλRλRλRλRλRô

Für Spielkinder:

Man kann P'' sogar mit der am MIT zur Informatik-Ausbildung von Kindern und Jugendlichen entwickelten symbolischen Programmiersprache 'Scratch' implementieren:

Klicken Sie auf das Miniaturbild, um das Video zu sehen.