Malbolge

Malbolge ist eine gemeinfreie esoterische Programmiersprache, die 1998 von Ben Olmstead entwickelt wurde. Sie wurde nach dem achten Kreis der Hölle aus Dantes Divina Commedia benannt.

Die Besonderheit von Malbolge besteht darin, dass sie als schlimmstmögliche Programmiersprache entwickelt wurde, die am schwierigsten zu beherrschen ist. Allerdings ist Malbolge aufgrund des begrenzten Speichers nur mit leicht abgewandelten Verarbeitungsregeln Turing-vollständig.

Allgemeines

Als Beweis für die schwierige Entwicklung von Programmen steht, dass das erste Malbolge-Programm erst zwei Jahre nach dem Entstehen der Programmiersprache entstanden ist. Dieses Programm wurde nicht von einem Menschen programmiert, sondern von einem in Lisp geschriebenen Programm unter Anwendung eines Such-Algorithmus gefunden. Entwickelt wurde dieses Suchprogramm von Andrew Cooke.

Es gibt mehrere Gründe dafür, dass Malbolge so schwierig ist. Der wichtigste ist, dass Befehle nach ihrer Ausführung durch andere Befehle ersetzt werden. Dadurch ist es sehr aufwändig, Schleifen in Malbolge umzusetzen. Weitere Faktoren, die das Programmieren in Malbolge erschweren, sind unter anderem die Tatsache, dass die Manipulation von Datenworten nur im ternären Zahlensystem mittels Rechtsshifts und eines sehr ungewöhnlichen Operators möglich ist. Hinzu kommt, dass die Codierung eines Befehls durch ein ASCII-Zeichen von der Position des Befehls Modulo 94 abhängt und Speicherzellen nur mit einem von acht möglichen ASCII-Werten initialisiert werden können.

Dennoch gelang es Lou Scheffer, ein Programm zu entwickeln, das seine Ein- auf seine Ausgabe kopiert. Sein Bericht darüber endet mit Vorschlägen, wie die Sprache noch schwieriger beherrschbar zu machen wäre.

Grundlegende Funktionsweise von Malbolge

Malbolge besitzt die drei Register a, c und d sowie einen Speicher der Größe $3^{10}$, der in jeder Zelle eine 10-stellige ternäre Ganzzahl speichern kann.

Initialisierung

Der Quellcode wird zunächst gefiltert, ohne Leer- und Zeilenwechselzeichen, in den Speicher der Größe $3^{10}$ eingelesen. Der noch verfügbare freie Speicher wird anschließend mit der Crazy-Funktion kodiert: [m] = crz([m - 2], [m - 1]).

Zeigernotation

Die Register c und d enthalten Speicheradressen, mit [c] bzw. [d] wird der an diesen Adressen gespeicherte Wert bezeichnet.

Befehlssatz

Malbolge besitzt 8 Befehlsworte. Dabei wird die aktuelle Anweisung bestimmt, indem der Inhalt von [c] und c addiert und anschließend modulo 94 gerechnet wird. Das Ergebnis wird dann mit folgenden Werten verglichen:

Befehle

Ergebnis aus ([c] + c) % 94	Bedeutung	Erklärung
4	jmp [d]	Setzen des Befehlszeigers c auf [d].
5	out a	Ausgabe des Zeichens, dessen ASCII-Wert in a gespeichert ist.
23	in a	Eingabe eines Zeichens, dessen ASCII-Wert in a abgelegt wird. Enter wird mit 10 kodiert, End-of-File-Markierung mit 59048.
39	rotr [d] mov a, [d]	Rechtsrotation der Zahl in [d], d. h. die letzte Stelle der Ternärdarstellung wird vorn angehängt, der Rest wird nach rechts verschoben. Aus 0002111112 wird z. B. 2000211111. Das Ergebnis wird sowohl in [d] als auch a abgelegt.
40	mov d, [d]	Kopiert den Wert von [d] nach d.
62	crz [d], a mov a, [d]	Wendet die crazy-Funktion auf den Wert von [d] und a an. Das Ergebnis liegt anschließend in [d] und a vor.
68	nop	Macht nichts.
81	end	Beendet das Programm.
Jeder andere Wert verhält sich wie 68.

Nach jeder Operation wird [c] verschlüsselt. Anschließend wird c und d um eins erhöht.

Crazy-Funktion

Die zwei übergebenen Zahlen werden ziffernweise entsprechend der Tabelle kodiert. Beispielsweise wird aus crz 0001112220, 0120120120 die Zahl 1001022211.

Crazy Funktion

crz		Input 2
		0	1	2
Input 1	0	1	0	0
	1	1	0	2
	2	2	2	1

Verschlüsselung

Nach dem Ausführen der Anweisung, jedoch vor der Inkrementierung von c, wird [c] mit Hilfe einer Codetabelle permutiert.

Hello, world

Dieses Malbolge-Programm gibt "Hello, world." aus.

 (=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
 hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<

Weitere Programme in Malbolge

Es ist mittlerweile kein Problem mehr, Programme in Malbolge zu schreiben, die lediglich einen festen String begrenzter Länge ausgeben. Die Länge des Strings ist begrenzt, weil Malbolgeprogramme nicht mehr als 59049 Befehle enthalten können.

Neben dem bereits oben erwähnten cat-Programm von Lou Scheffer (welches einen Bug im Interpreter ausnutzt, der es ermöglicht, Speicherzellen mit Nicht-ASCII-Zeichen zu initialisieren) gibt es bisher (Stand: Dezember 2012) nur sehr wenige Programme in Malbolge, die Schleifen enthalten. Eines davon ist ein weiteres cat-Programm, das jedoch auch ohne Ausnutzung des Interpreter-Bugs funktioniert. Zu den eindrucksvollsten Programmen in Malbolge dürfte ein 2005 erschienenes Programm gehören, das die Lyrics des Liedes „99 Bottles of Beer“ ausgibt und dafür nichttriviale Schleifen und bedingte Verzweigungen benutzt. Der Code dieses Programms ist für einen Menschen nicht lesbar. Ein weiteres Programm in Malbolge, das mit nichttrivialen Schleifen und bedingten Verzweigungen arbeitet, ist ein Ende 2012 erschienenes Quine.

Populärkultur

• In der zehnten Episode der Fernsehserie Elementary, Leviathan, heißt es, ein Ermittlungshinweis sei in Malbolge verfasst.
• In der zwölften Episode der Fernsehserie Leverage Redemption, The Golf Club, wird behauptet, die Hackerin Breanna könne erst wieder auf ihre Nachrichten antworten, wenn sie Malbolge gemeistert hätte.

Weblinks

• Lou Scheffers Hack
• Andrew Cookes Erklärungen zum Lisp-Suchprogramm
• Interpreter-C-Quellcode
• Hisashi Iizawa "99 Bottles of Beer"
• Matthias Ernsts Quine
• Malbolge auf esolangs.org
• Interview mit Ben Olmstead auf esoteric.codes