Malbolge Tutorial – Malbolge lernen

In diesem Anfänger-Tutorial schreiben wir ein einfaches cat-Programm in Malbolge. Unser Ergebnis wird das Malbolge-cat-Programm von Esolangs sein. Zur Einführung und zum besseren Verständnis schauen wir uns zunächst eine ganze Reihe Screenshots eines fertigen cat-Programm in der HeLL IDE an. Später werden wir zum Schreiben des cat-Programms lediglich die Malbolge-Seiten von Lou Scheffer sowie ein Tool zum Umrechnen ins ternäre Zahlensystem benötigen. D.h., Sie müssen für dieses Tutorial keinerlei Software installieren.
Die HeLL IDE erlaubt es uns, Malbolge-Programme in der Assembler-Sprache HeLL zu schreiben und zu debuggen. Wir werden zunächst HeLL kennen lernen, bevor wir uns an reines Malbolge heranwagen. Dazu schauen wir uns ein fertiges cat-Programm in HeLL an.

Hinweis: Die englischsprachige Version dieses Malbolge-Tutorials ist zur Zeit an einigen Stellen etwas besser oder auch ausführlicher.

Wir unterscheiden in Malbolge grundsätzlich zwischen der Code-Section, in HeLL eingeleitet durch .CODE, und der Data-Section, eingeleitet durch .DATA.
Innerhalb dieser Sections benutzen wir Labels, um unseren Code und unsere Daten zu adressieren.
Malbolge besteht aus zyklisch selbst-modifizierendem Code. Solche Zyklen können wir in der Code-Section angeben, indem wir die gewünschten Befehle eines Zyklus hintereinander mit Slash getrennt notieren. So bedeutet Nop/MovD, dass an dieser Stelle zu Beginn ein Nop-Befehl (No Operation) stehen soll, der nach erstmaliger Modifikation zu einem MovD-Befehl wird. Danach wird er wieder zu einem Nop-Befehl und so weiter.
Ist gar kein Zyklus angegeben (im Screenshot ist dies bei den Jmp-Befehlen der Fall), so wird nur garantiert, dass dort zu Programm-Beginn der entsprechende Befehl steht, während die Modifikation einem beliebigen Zyklus folgt.
Beachten Sie bitte, dass es bei der Wahl der Zyklen viele Beschränkungen gibt. Später mehr dazu.
Der eigentliche Programmfluss findet in der Data-Section statt. Wie das mit dem Programmfluss genau funktioniert, werden wir uns im Folgenden genauer ansehen.

Beim Übersetzen von HeLL nach Malbolge müssen unserer Code und unsere Daten in bestimmte Speicherstellen geschrieben werden. Dies übernimmt der Übersetzer LMAO für uns. Dabei verwendet LMAO sogenannte Blöcke. Alle Daten innerhalb eines Blocks sind direkt aufeinander folgend, während die Position eines Blockes frei gewählt werden kann. Zwei in HeLL aufeinander folgende Blöcke müssen also in Malbolge nicht aufeinander folgen. Wir verwenden in HeLL eine leere Zeile, um Blöcke zu trennen. Daher ist es wichtig, dass Sie die leeren Zeilen exakt wie oben übernehmen, sollten Sie das Beispiel selbst in der HeLL IDE ausprobieren.

Lassen Sie uns nun den Debug-Modus starten, um das Programm Schritt-für-Schritt auszuführen und dabei zu verstehen, wie ein Programm in HeLL funktioniert.

Die HeLL IDE ist nun in den Debug-Modus gewechselt.
Der gelbe Pfeil zeigt die Speicherposition an, auf die das D-Register zeigt. In der Code-Section ist die aktuelle Position jedes Befehls-Zyklus mittels Fettdruck hervorgehoben. Zu Beginn zeigt das C-Register auf einen Jmp-Befehl irgendwo außerhalb unseres HeLL-Codes, daher ist die Position des C-Registers noch nicht markiert. Im nächsten Schritt wird sie mit einem grünen Pfeil markiert sein.
Unten sehen wir die Konsolen-Ein- und Ausgabe. Dort werden wir mit unserem cat-Programm interagieren können.
Rechts sehen wir den Zustand der Malbolge-Register. Während das C-Register auf irgendeine Speicherstelle zeigt, an der sich ein Jmp/Nop/Nop/...-Befehl befindet (d.h. ein Jmp-Befehl, der nach einer Modifikation zu einem Nop wird usw.), zeigt das D-Register auf eine Speicherzelle, in der sich der Wert "IN_OUT - 1" befindet. Tatsächlich sehen jedoch wir im linken Fenster, dass an der Speicherstelle eigentlich der Wert "IN_OUT" stehen müsste. Die Angabe rechts ist jedoch die korrekte. Wenn LMAO ein HeLL-Programm übersetzt, dann zieht es von jedem Label den Wert eins ab. Der Grund ist wie folgt: Wenn Malbolge den aktuellen Befehl an der Position des C-Registers ausführt (Jmp), dann wird das C-Register auf den Wert gesetzt, auf den das D-Register zeigt, d.h. C wird den Wert "IN_OUT - 1" annehmen. Direkt nach dem Jmp-Befehl wird Malbolge jedoch sowohl das C- als auch das D-Register inkrementieren, d.h. am Ende des Ausführungsschritts wird das C-Register auf die Position IN_OUT zeigen. Damit man beim Schreiben von HeLL-Programmen nicht stets den Wert eins abziehen muss, wenn man Sprungziele angibt, zieht LMAO automatisch eins von jedem Label ab. Bei Zielen für das D-Register (MovD-Befehl) verhält es sich genau so.
Der Wert des A-Registers ist zu Beginn nicht definiert und kann daher beliebig sein. Bevor wir diesen Wert in unserem Programm lesen, sollten wir ihn schreiben. Tatsächlich ist der Wert des A-Registers in der aktuellen Version von LMAO zu Beginn stets "ENTRY - 1", aber dies kann in späteren Versionen von LMAO anders sein.

Wir können zusätzlich zu den oben angezeigten Registern und Speicherzellen auch eigene Ausdrücke überwachen. Dies ist bei einem cat-Programm nicht wirklich nötig. Um das Ganze zu demonstrieren, überwachen wir hier den Inhalt der Speicherzellen an den Adressen MOVD und IN_OUT. Dies entspricht der internen Malbolge-Repräsentation des Nop/MovD bzw. des In/Nop/Out/Nop/...-Zyklus. Wir werden später sehen, dass sich der dort gespeicherte Wert jedes Mal ändert, wenn die nächste Position des Zyklus eingenommen wird.

Lassen Sie uns nun tatsächlich den ersten Schritt ausführen. Beachten Sie auf der rechten Seite, dass das C-Register auf einen Jmp-Befehl zeigt, während die Sprungadresse, auf die das D-Register zeigt, den Wert "IN_OUT - 1" besitzt.

Nach diesem Schritt zeigt das Code-Register auf den In-Befehl, während das D-Register um eins erhöht wurde und nun auf eine nicht-definierte Speicherzelle (angedeutet mittels "?-") zeigt.

Bevor wir den nächsten Schritt ausführen, in dem Malbolge von der Eingabe lesen wird, schreiben wir etwas in die Konsole, das gelesen werden kann. Nun sind wir bereit, einen weiteren Schritt auszuführen und den ersten Buchstaben von der Konsole (ein 'f') in das A-Register zu lesen.

Wie Sie sehen, hat nach diesem Schritt das A-Register den Wert 'f' (ternär: 10210) angenommen. Außerdem wurde der ausgeführte Befehl In modifiziert, sodass sich der Zyklus nun an der Stelle Nop befindet. Das Code- und Daten-Register wurde jeweils um eins erhöht. Der nächste Befehl ist ein Jmp an die Stelle "R_MOVD - 1". Was dies genau bedeutet, steht im Text unter dem nächsten Bild.

Das Präfix "R_" steht für "restore". Es ist jedoch lediglich eine Alternativschreibweise für die Addition von eins, "R_MOVD" ist also das gleiche wie "MOVD + 1". Da LMAO stets den Wert eins von allen Labels in der Data-Section abzieht, entspricht "R_MOVD" also der tatsächlichen Position von MOVD. Aber wozu das Ganze?
Wie Sie sehen, zeigt das Code-Register erneut auf einen Jmp-Befehl, diesmal jedoch auf den Jmp-Befehl unter MOVD. Dies mag zunächst einmal unsinnig erscheinen, hat das Code-Register doch bereits zuvor auf einen Jmp-Befehl gezeigt. Der Sinn der Ganzen liegt darin, die Zyklen der Befehlsmodifikation gezielt zu steuern. Nachdem Malbolge einen Befehl ausgeführt hat und bevor die Register inkrementiert werden, wird stets das Befehl an der Position des C-Registers modifiziert. Bei fast allen Befehlen führt das dazu, dass diese nach der Ausführung verändert werden. Beim Jmp-Befehl hingegen wird zuerst gesprungen, sodass der Befehl an der Position des Sprungziels modifiziert wird, bevor das C-Register abschließend inkrementiert wird. In HeLL sieht es daher so aus, als ob der Wert direkt vor dem Label, das das Sprungziel angibt, verändert wurde. Und wenn wir genau hinsehen, können wir tatsächlich erkennen, dass der Nop/MovD-Befehl tatsächlich verändert wurde und nun das MovD aktiv ist, während das Jmp unter IN_OUT immer noch aktiv ist, obwohl wir hier einen beliebigen Zyklus erlaubt haben.
Haben wir also einen Befehl ausgeführt, dessen Zyklus aus dem Befehl und einem Nop besteht, so können wir den Befehl mittels eines entsprechenden Sprungs wiederherstellen. Daher nennen wir das entsprechende Präfix "restore".
Führen wir nun den nächsten Schritt aus.

Unser Code-Register zeigt nun auf den Befehl MovD und das Data-Register auf den Wert "ENTRY - 1". Da das Data-Register nach jedem Schritt inkrementiert wird, wird es nach dem MovD im nächsten Schritt den Wert "ENTRY" besitzen.

Nun befinden wir uns tatsächlich fast wieder im Anfangszustand. Das Code-Register zeigt auf einen Jmp-Befehl, der Zyklus Nop/MovD unter MOVD befindet sich wieder im Nop-Zustand und das Data-Register befindet sich an unserem Einsprungspunkt ENTRY.
Es gibt jedoch zwei Unterschiede: Das A-Register speichert immer noch den Wert 'f' und der Zyklus In/Nop/Out/Nop/... befindet sich an der zweiten Position auf einem Nop.

Da die weiteren Durchläfe durch unser Programm nun nicht mehr allzu spannend sein dürften, setzen wir einen Breakpoint, um das Programm nun größere Strecken automatisch laufen lassen zu können.

Der Breakpoint wird durch einen roten Kreis symbolisiert.

Nun können wir das Programm nicht nur schrittweise, sondern unbegrenzt laufen lassen. Sobald es erneut an unserem Breakpoint ankommt, wird die Ausführung anhalten, sodass wir weitere Beobachtungen machen können.

Und schon befindet sich das Programm an unserem Breakpoint. Sie können sehen, dass der Zyklus unterhalb des IN_OUT-Labels nun auf den Out-Befehl zeigt.

Diesmal gehen wir noch mal schrittweise vor, um den Out-Befehl zu beobachten. Der Code-Pointer ist soeben an die entsprechende Stelle gesprungen.

Und nun können wir in der Konsole sehen, dass der Wert des A-Registers ausgegeben wurde. Außerdem ist der Zyklus unter IN_OUT um eins weiter gesprungen. Wir gehen nun wieder schneller durch das Programm.

Wie erwartet, sind wir wieder oben angekommen.

Nach vielen weiteren Schritten befindet sich auch der Zyklus unter IN_OUT wieder im Ursprungszustand. Nun ist alles wie zu Beginn, sodass das Programm nun ein weiteres Zeichen lesen und dies später ausgeben wird.

Nachdem die gesamte Eingabe inklusive Zeilenumbruch ausgegeben wurde, sollten wir das Programm abbrechen. Da es keine Abbruch-Bedingung besitzt, würde es sonst unendlich lange weiterlaufen.
Nachdem Sie nun gesehen haben, wie ein cat-Programm in HeLL funktioniert, werden wir es per Hand in Malbolge übersetzen. Dies ist bei einfachen Programmen wie dem cat-Programm sinnvoll, da der Code so deutlich kleiner wird als der von LMAO generierte. Und außerdem lernen wir dabei, wie man Programme per Hand in Malbolge schreibt.

Wir bleiben zunächst noch bei der HeLL-Syntax. Mittels des @-Operators können wir ein Offset angeben, an dem der jeweilige Code- oder Datenblock platziert werden soll. Bei einem Code-Block sind nur bestimmte Offsets möglich, dazu später mehr. Das Ziel ist es, die Labels durch tatsächliche Speicheradressen zu ersetzen, sodass wir dem tatsächlichen Malbolge-Code ein Stück näher kommen.

Nun haben wir in der Data-Section die Labels durch die absoluten Speicheradressen ersetzt. Beachten Sie bitte, dass wir (wie bereits weiter oben besprochen) jeweils die Speicherzelle vor der eigentlich gewünschten Adresse angeben müssen.

Auch dieses Programm kann noch in der HeLL IDE ausgeführt werden.

Bevor wir das Übersetzen nach Malbolge per Hand beginnen, schreiben wir die endgültige Programmversion auf, hier noch einmal mit Labels.
In Malbolge lassen sich Zyklen, die mit einem Befehl außer Nop beginnen (manchmal geht ausnahmsweise auch Nop), direkt in den Malbolge-Code schreiben. Alle anderen Zyklen können nicht direkt in den Code geschrieben werden und müssen erst aufwendig während der Laufzeit im Speicher erzeugt werden.
Aus diesem Grund sollten wir den Zyklus Nop/MovD durch den Zyklus MovD/Nop ersetzen. Dies ist oben geschehen.
Dies ist die letzte Programmversion, die sich mit LMAO übersetzen lässt.

Wir positionieren nun den Code. Diesmal wählen wir jedoch Adressen am Speicherbeginn. Wenn wir Adressen im Bereich gültiger ASCII-Zeichen wählen, hat dies gleich zwei Vorteile. Einerseits muss das Malbolge-Programm nicht besonders lang sein, um trotzdem die gewünschten Werte gleich zu Beginn in die entsprechende Speicherzelle zu laden, anstatt sie mühsam zur Laufzeit zu erzeugen. Und andererseits können die Labels aus der Data-Section durch Werte im ASCII-Bereich ersetzt werden. Dadurch erhöht sich die Chance, dass wir auch diese Werte bereits im Programmcode selbst angeben können, ohne sie aufwendig zur Laufzeit initialisieren zu müssen.
Die Adresse der Data-Section ist mehr oder weniger willkürlich gewählt. Sie darf sich nicht mit der Code-Section überschneiden - und auch nicht der Speicherzelle direkt vor einem Code-Block, da beim Springen in den Code-Block diese Speicherzelle einer Modifikation unterworfen ist (siehe Erläterung weiter oben). Stünden dort Einträge aus der Data-Section, so könnte dies zu einem unvorhersehbarem Verhalten, teils sogar bis zum Absturz des Referenz-Interpreters, führen.
Interessanter ist jedoch die Wahl der Adressen für die Code-Section. Hier müssen wir sicherstellen, dass der jeweilige Zyklus am entsprechenden Adressen möglich ist. Dies können wir auf Lou Scheffers Webseite nachschlagen: Instruction Cycles in Malbolge

Wir können Lou Scheffers Webseite entnehmen, dass bei Adresse 37 ein entsprechender In/Nop/Out/Nop/...-Zyklus existiert. Ein MovD/Nop-Zyklus befindet sich sowohl an Adresse 60 als auch an Adresse 64. Wir wählen willkürlich Adresse 60. Damit erhalten wir das weiter oben in HeLL-Notation angegebene Memory-Layout für unser cat-Programm.
Es ist nun Zeit, unser tatsächliches Malbolge-Programm zu schreiben. Dazu nutzen wir eine weitere Übersicht von Lou Scheffer: Valid Instructions

Zunächst schreiben wir einen In-Befehl an Adresse 37. Wir wissen bereits, dass es an dieser Position unserem gewünschten Zyklus entspricht. Um einen In-Befehl, in normalisiertem Malbolge ist dies ein Slash, an Adresse 37 zu schreiben, müssen wir dort ein P notieren. Für ein MovD, in normalisiertem Malbolge ein j, schreiben wir ein J an Adresse 60.
Bei dieser Gelegenheit können wir auch gleich den Jmp-Befehl, in normalisiertem Malbolge ein i, für die Adressen 38 und 61 nachschlagen. Unser bisheriges Malbolge-Programm sieht damit wie folgt aus:

Damit haben wir die Code-Section erfolgreich erstellt, es verbleibt die Data-Section. Auch hier nutzen wir Lou Scheffers Valid-Instructions-Übersicht, um zunächst zu ermitteln, welche Speicherzellen wir direkt in unser Programm schreiben dürfen.

Wir sehen, dass wir die 60 an Adresse 39 und die 38 an Adresse 43 direkt in unser Malbolge-Programm übernehmen können. Die 36 an Adresse 40 und die 59 an Adresse 42 hingegen dürfen wir nicht direkt in unserem Malbolge-Programm notieren, darum kümmern wir uns als nächstes. Unser Malbolge-Programm sieht nun so aus:

Wir müssen nun die fehlenden Speicherzellen in der Data-Section initialisieren. Dies muss zur Laufzeit erfolgen, also schreiben wir Malbolge-Code, der die von uns gewünschten Werte an die entsprechende Stelle schreibt. Es folgt ternäre Zahlendarstellung und die Verwendung des Opr-Befehls. Wer den Opr-Befehl noch nicht auswendig kennt, sollte ihn noch einmal in der Beschreibung von Malbolge nachschlagen.
Wir können Adresse 40 mit dem Wert 58, ternär 0t0000002011, initialisieren, indem wir dort einen Jmp-Befehl mittels Doppelpunkt kodieren. Wenn wir es schaffen, im A-Register den Wert 0t1111112011 zu erzeugen, so können wir mittels eines einfachen Opr-Befehls aus 0t0000002011 unseren Zielwert 0t0000001100 (dezimal 36) erzeugen.
Den Wert 0t1111112011 können wir wie folgt erzeugen:
Lade zunächst 0t0000000200 in das A-Register (z.B. mittels eines Rot-Befehls auf 0t0000002000) und führe dann einen Opr-Befehl auf 0t0000002000 aus.
Schreiben wir nun also ein Malbolge-Programm, das genau dies tut.

Zunächst einmal starten C- und D-Register mit dem Wert 0. Wir müssen diese beiden Zeiger trennen, bevor wir Opr und Rot-Befehle ausführen, da sonst der Referenzinterpreter abstürzt. Wir beginnen uns Malbolge-Programm also mit einem MovD-Befehl, dies trennt die beiden Register (alternativ wäre auch ein Jmp-Befehl möglich). Ein MovD-Befehl an Adresse 0 wird durch eine öffnende Klammer kodiert. Diese besitzt den ASCII-Wert 40, womit unser D-Register nun auf Adresse 41 zeigt, da es nach jedem Befehl noch inkrementiert wird. Unser Malbolge-Programm sieht nun also so aus:

Zu Beginn steht im A-Register der Wert 0. Da dieser Wert sehr nützlich sein kann, speichern wir ihn (bzw. den Wert 0t1111111111) zunächst mittels Opr in einer geeigneten Speicherzelle ab. Geeignet sind alle Speicherzellen, die einfach zu erreichen sind (also Adressen im ASCII-Bereich besitzen) und bei denen keine einzige Stelle in Ternärdarstellung mit einer 2 initialisiert wurde. Dies trifft auf Speicherzelle 41, die wir auch für unser HeLL-Programm nicht benötigen, zu: So kann mit 0t0000001111 initialisiert werden, wenn wir dort einen Hlt-Befehl, kodiert als öfnende Klammer, hinein schreiben. Ein Opr-Befehl an Adresse 1 wird durch ein Gleichheitszeichen kodiert. Unser Malbolge-Code sieht nun wie folgt aus:

Da wir immer noch eine 58 an Adresse 40 erzeugen möchten, versuchen wir, den Wert 0t0000000200 mittels eines Rot-Befehls auf 0t000002000, in Dezimalschreibweise 54, zu laden. Die Speicherzellen 42 und 43 sollten wir dafür nicht verwenden, da wir sie in unserem HeLL-Programm benutzen. Zum Glück dürfen wir Speicherzelle 44 mit einer 54 initialisieren, indem wir dort einen Jmp-Befehl, kodiert als 6, platzieren. Die anderen Speicherzellen überspringen wir mittels Nop-Befehl, bevor wir den Rot-Befehl ausführen. Dabei nutzen wir aus, dass nach jedem Befehl das D-Register erhöht wird. Wir erhalten folgendes Malbolge-Programm:

Nun möchten wir unser A-Register in den Wert 0t000002000 schreiben, um 0t1111112011 zu erhalten. Wir haben Glück und können auch Speicherzelle 45 mit einer 6 initialisieren. Wir fügen diese zusammen mit dem Opr-Befehl unserem Malbolge-Programm hinzu:

Nun haben wir tatsächlich den Wert 0t1111112011 im A-Register stehen. Wir müssen jetzt an Adresse 40 springen und dort einen Opr-Befehl ausführen. Dazu schreiben wir eine Raute (ASCII 35) an Adresse 46 und benutzen diese als Sprungadresse für das D-Register. Anschließend führen wir vier Nop-Befehle aus, bis das D-Register auf Adresse 40 zeigt. Dann folgt ein Opr-Befehl.

Es verbleibt, an Adresse 42 eine 59, ternär 0t0000002012, zu schreiben. Hierfür laden wir 0t1111111101 in das A-Register und überschreiben damit den Wert 0t0000002002, der an Adresse 42 stehen darf (ASCII-Kodierung von 8). Um wiederum den Wert 0t1111111101 in das A-Register zu laden, können wir zunächst den Wert 0t0000000020 laden und diesen in 0t0000000000 schreiben. Zur Zeit steht an Adresse 41 der Wert 0t1111111111, da wir hier zu Beginn 0t0000000000 abgespeichert haben. Wir laden also 0t1111111111 mittels Rot-Befehl und schreiben es dann wieder an Adresse 41 zurück, um dort den Wert 0t0000000000 zu erhalten. Um erneut an Adresse 41 zu schreiben, nutzen wir den Wert 38 von Adresse 43 für einen Rücksprung.

Nun können wir 0t0000000020 in das A-Register laden, indem wir den Rot-Befehl bei Adresse 44 ausführen: An dieser Adresse steht zur Zeit nälich noch 0t0000000200.

Es verbleibt, zu Adresse 41 zurückzukehren, dort 0t0000000020 in 0t0000000000 zu schreiben, um 0t1111111101 zu erhalten, sowie anschließend diesen Wert an Adresse 42 zu schreiben, um dort die gewünschte 59 zu erzeugen.

Nun müssen wir das vollständig initialisierte HeLL-Programm starten. Dazu müssen wir lediglich einen Jmp-Befehl ausführen, während das D-Register auf den Einsprungspunkt ENTRY zeigt. Dieser befindet sich an Adresse 40. Wir bewegen also unser D-Register an diese Adresse und führen dann den Jmp-Befehl aus.

Damit ist unser Malbolge-Programm im Prinzip fertig. Es verbleibt, die freien ungenutzten Speicherzellen (33‐36 und 47‐59) mit beliebigem Inhalt zu füllen. Wir wählen hierfür den Hlt-Befehl, aber es können selbstverständlich beliebige gültige Befehle gewählt werden.
Das fertige Malbolge-Programm sieht dann wie folgt aus:

(=BA#9"=<;:3y7x54-21q/p-,+*)"!h%B0/.
~P<
<:(8&
66#"!~}|{zyxwvu
gJ%

Beachten Sie bitte, dass dieses Programm nicht terminiert.

Besuchen Sie auch meine anderen Malbolge- und Malbolge-Unshackled-Seiten! Oder schreiben Sie mir eine E-Mail: matthias@lutter.cc