Malbolge - Malbolge

Dieser Artikel behandelt die Programmiersprache. Für den achten Kreis der Hölle in Dantes Inferno siehe Malebolge .
Malbolge
Paradigma Esoterisch, Imperativ, Skalar, Wertstufe
Entworfen von Ben Olmstead
Erstmals erschienen 1998
Schreibdisziplin Nicht typisiert
Dateinamenerweiterungen .mal, .mb
Beeinflusst von
Brainfuck , INTERCAL (Tri-INTERCAL), Befunge
Beeinflusst
Dis, Malbolge Entfesselt

Malbolge ( / m æ l b oʊ l dʒ / ) ist eine public domain esoterische Programmiersprache von Ben Olmstead 1998 erfunden, nach dem achten Kreis der Hölle in namens Dante ‚s Inferno , die Malebolge . Es wurde speziell so konzipiert, dass es durch eine kontraintuitive „verrückte Operation“, eine Basis-Drei-Arithmetik und einen sich selbst ändernden Code fast unmöglich zu verwenden ist. Es baut auf dem Schwierigkeitsgrad früherer, herausfordernder esoterischer Sprachen (wie Brainfuck und Befunge ) auf, treibt diesen Aspekt jedoch auf die Spitze und spielt mit der verstrickten Geschichte von Informatik und Verschlüsselung . Trotz dieses Designs ist es möglich, nützliche Malbolge-Programme zu schreiben.

Programmierung in Malbolge

Malbolge war sehr schwer zu verstehen, als es ankam. Es dauerte zwei Jahre, bis das erste Malbolge-Programm erschien. Der Autor selbst hat noch nie ein Malbolge-Programm geschrieben. Das erste Programm wurde nicht von einem Menschen geschrieben; es wurde von einem erzeugten Strahlsuchalgorithmus entworfen von Andrew Cooke und umgesetzt in Lisp .

Später veröffentlichte Lou Scheffer eine Kryptoanalyse von Malbolge und stellte ein Programm zur Verfügung, um seine Eingaben in ihre Ausgabe zu kopieren. Er rettete auch den ursprünglichen Interpreter und die Spezifikation, nachdem die ursprüngliche Site nicht mehr funktionierte, und bot eine allgemeine Strategie zum Schreiben von Programmen in Malbolge sowie einige Gedanken zur Turing-Vollständigkeit an .

Olmstead glaubte, Malbolge sei ein linear begrenzter Automat . Es wird diskutiert, ob man in Malbolge sinnvolle Schleifen implementieren kann – es hat viele Jahre gedauert, bis die erste nicht terminierende Schleife eingeführt wurde. Ein richtiges 99 Bottles of Beer-Programm , das sich mit nicht-trivialen Schleifen und Bedingungen befasst, wurde sieben Jahre lang nicht angekündigt; das erste richtige war 2005 von Hisashi Iizawa. Hisashi Iizawa et al. schlug auch einen Leitfaden für die Programmierung in Malbolge vor, um den Softwareschutz zu verschleiern.

Im Jahr 2020 hat der GitHub- Benutzer kspalaiologos einen funktionierenden Lisp- Interpreter in Malbolge Unshackled erstellt.

Beispielprogramme

Hallo Welt!

Dieses Programm zeigt " Hallo, Welt. " an. 

(=<`#9]~6ZY327Uv4-QsqpMn&+Ij"'E%e{Ab~w=_:]Kw%o44Uqp0/Q?xNvL:`H%c#DD2^WV>gY;dts76qKJImZkj

Katze Programm

Dieses Programm liest einen String von einem Benutzer und gibt diesen String aus, ähnlich wie bei Unix cat .

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

Entwurf

Malbolge ist eine Maschinensprache für eine ternäre virtuelle Maschine , den Malbolge- Interpreter .

Der Standardinterpreter und die offizielle Spezifikation passen nicht perfekt zusammen. Ein Unterschied besteht darin, dass der Compiler die Ausführung mit Daten außerhalb des Bereichs 33–126 stoppt. Obwohl dies zunächst als Fehler im Compiler angesehen wurde, erklärte Ben Olmstead, dass dies beabsichtigt war und tatsächlich "ein Fehler in der Spezifikation" enthalten war.

Register

Malbolge hat drei Register , a , c und d . Wenn ein Programm startet, ist der Wert aller drei Register Null.

a steht für 'Akkumulator', wird auf den Wert gesetzt, der von allen Schreiboperationen in den Speicher geschrieben und für Standard-I/O verwendet wird . c , der Codezeiger, ist etwas Besonderes: Er zeigt auf die aktuelle Anweisung . d ist der Datenzeiger. Er wird nach jedem Befehl automatisch inkrementiert, aber die Stelle, auf die er zeigt, wird für die Datenmanipulationsbefehle verwendet.

Zeigernotation

d kann eine Speicheradresse halten; [d] ist Register indirekt ; der unter dieser Adresse gespeicherte Wert. [c] ist ähnlich.

Speicher

Die virtuelle Maschine verfügt über 59.049 (3 10 ) Speicherorte , die jeweils eine ternäre Zahl mit zehn Trits aufnehmen können . Jeder Speicherplatz hat eine Adresse von 0 bis 59048 und kann einen Wert von 0 bis 59048 aufnehmen. Ein Inkrementieren über diese Grenze hinaus wird auf Null zurückgesetzt.

Die Sprache verwendet den gleichen Speicherplatz für Daten und Anweisungen . Dies wurde durch die Funktionsweise von Hardware wie der x86-Architektur beeinflusst.

Bevor ein Malbolge-Programm startet, wird der erste Teil des Speichers mit dem Programm gefüllt. Alle Leerzeichen im Programm werden ignoriert und um die Programmierung zu erschweren, muss alles andere im Programm wie eine der folgenden Anweisungen beginnen.

Der Rest des Speichers wird mit der verrückten Operation (siehe unten) an den vorherigen beiden Adressen ( [m] = crz [m - 2], [m - 1] ) gefüllt . Auf diese Weise gefüllter Speicher wird alle zwölf Adressen wiederholt (die einzelnen ternären Ziffern werden alle drei oder vier Adressen wiederholt, so dass eine Gruppe von ternären Ziffern garantiert alle zwölf wiederholt wird).

Im Jahr 2007 schuf Ørjan Johansen Malbolge Unshackled, eine Version von Malbolge, die nicht das beliebige Speicherlimit hat. Die Hoffnung bestand darin, eine Turing-vollständige Sprache zu schaffen und dabei so weit wie möglich im Geiste von Malbolge zu bleiben. Andere Regeln werden nicht geändert und alle Malbolge-Programme, die das Speicherlimit nicht erreichen, sind voll funktionsfähig.

Anweisungen

Malbolge hat acht Anweisungen . Malbolge findet heraus, welche Anweisung ausgeführt werden soll, indem er den Wert [c] nimmt , den Wert von c hinzufügt und den Rest nimmt, wenn dieser durch 94 geteilt wird. Das Endergebnis sagt dem Interpreter, was zu tun ist:

Anweisungen
Wert von
([c] + c) % 94 		Anleitung
dargestellt		 Erläuterung
4 jmp [d] Kopiert den Wert bei [d] nach c . Beachten Sie, dass c nach der Ausführung dieses Befehls noch inkrementiert wird, so dass der nächste auszuführende Befehl der bei [d] + 1 (modulo 59049) ist .
5 aus a Gibt den Wert von a als ASCII- Zeichen auf dem Bildschirm aus.
23 in einem Gibt ein Zeichen als ASCII-Code in eine . Zeilenumbrüche oder Zeilenumbrüche sind beide Code 10 . Eine Dateiende-Bedingung ist Code 59048 .
39 rotr [d]
mov a, [d]		 Dreht den Wert bei [d] um eine ternäre Stelle (000211111 2 wird zu 2 000211111). Speichert das Ergebnis sowohl in [d] als auch in a .
40 bewegen d, [d] Kopiert den Wert bei [d] nach d .
62 crz [d], a
mov a, [d]		 Führt die verrückte Operation (siehe unten) mit dem Wert bei [d] und dem Wert von a aus . Speichert das Ergebnis sowohl in [d] als auch in a .
68 nein Tut nichts.
81 Ende Beendet das Malbolge-Programm.
Jeder andere Wert tut das gleiche wie 68 : nichts. Diese anderen Werte sind in einem Programm während des Ladens nicht erlaubt, aber danach erlaubt.

Nachdem jede Anweisung ausgeführt wurde, wird die schuldige Anweisung verschlüsselt (siehe unten), damit sie beim nächsten Mal nicht dasselbe tut, es sei denn, es ist gerade ein Sprung passiert. Direkt nach einem Sprung verschlüsselt Malbolge die unschuldige Anweisung kurz vor der, zu der sie stattdessen gesprungen ist. Dann werden die Werte von sowohl c als auch d um eins erhöht und der nächste Befehl wird ausgeführt.

Verrückter Betrieb

Verwenden Sie für jede ternäre Ziffer beider Eingaben die folgende Tabelle, um eine ternäre Ziffer des Ergebnisses zu erhalten. Beispielsweise ergibt crz 0001112220, 0120120120 1001022211.

Verrückter Betrieb
crz Eingang 2
0 1 2
Eingang 1 0 1 0 0
1 1 0 2
2 2 2 1

Verschlüsselung

Nachdem eine Anweisung ausgeführt wurde, wird der Wert bei [c] (ohne etwas hinzugefügt) durch sich selbst mod 94 ersetzt. Dann wird das Ergebnis mit einer der beiden folgenden äquivalenten Methoden verschlüsselt .

Methode 1
Finden Sie das Ergebnis unten. Speichern Sie den ASCII-Code des Zeichens darunter unter [c] .
 0000000000111111111122222222223333333333444444444455555555556666666666777777777788888888889999
 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123
 ----------------------------------------------------------------------------------------------
 9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb
Methode 2
Finden Sie das Ergebnis unten. Speichern Sie die verschlüsselte Version unter [c] .
Verschlüsselungstabelle
Ergebnis Verschlüsselt Ergebnis Verschlüsselt Ergebnis Verschlüsselt Ergebnis Verschlüsselt Ergebnis Verschlüsselt
0 57 19 108 38 113 57 91 76 79
1 109 20 125 39 116 58 37 77 65
2 60 21 82 40 121 59 92 78 49
3 46 22 69 41 102 60 51 79 67
4 84 23 111 42 114 61 100 80 66
5 86 24 107 43 36 62 76 81 54
6 97 25 78 44 40 63 43 82 118
7 99 26 58 45 119 64 81 83 94
8 96 27 35 46 101 65 59 84 61
9 117 28 63 47 52 66 62 85 73
10 89 29 71 48 123 67 85 86 95
11 42 30 34 49 87 68 33 87 48
12 77 31 105 50 80 69 112 88 47
13 75 32 64 51 41 70 74 89 56
14 39 33 53 52 72 71 83 90 124
fünfzehn 88 34 122 53 45 72 55 91 106
16 126 35 93 54 90 73 50 92 115
17 120 36 38 55 110 74 70 93 98
18 68 37 103 56 44 75 104

Lou Scheffers Kryptoanalyse von Malbolge erwähnt sechs verschiedene Zyklen in der Permutation . Sie sind hier aufgelistet:

  • 33 ⇒ 53 ⇒ 45 ⇒ 119 ⇒ 78 ⇒ 49 ⇒ 87 ⇒ 48 ⇒ 123 ⇒ 71 ⇒ 83 ⇒ 94 ⇒ 57 ⇒ 91 ⇒ 106 ⇒ 77 ⇒ 65 ⇒ 59 ⇒ 92 ⇒ 115 ⇒ 82 ⇒ 118 ⇒ 107 ⇒ 75 ⇒ 104 ⇒ 89 ⇒ 56 ⇒ 44 ⇒ 40 ⇒ 121 ⇒ 35 ⇒ 93 ⇒ 98 ⇒ 84 ​​⇒ 61 ⇒ 100 ⇒ 97 ⇒ 46 ⇒ 101 ⇒ 99 ⇒ 86 ⇒ 95 ⇒ 109 ⇒ 88 ⇒ 47 ⇒ 52 ⇒ 72 ⇒ 55 ⇒ 110 ⇒ 126 ⇒ 64 ⇒ 81 ⇒ 54 ⇒ 90 ⇒ 124 ⇒ 34 ⇒ 122 ⇒ 63 ⇒ 43 ⇒ 36 ⇒ 38 ⇒ 113 ⇒ 108 ⇒ 39 ⇒ 116 ⇒ 69 ⇒ 112 ⇒ 68 ⇒ 33 ...
  • 37 103 ⇒ 117 ⇒ 111 ⇒ 120 ⇒ 58 ⇒ 37 ...
  • 41 102 ⇒ 96 ⇒ 60 ⇒ 51 ⇒ 41 ...
  • 42 114 ⇒ 125 ⇒ 105 ⇒ 42 ...
  • 50 80 ⇒ 66 ⇒ 62 ⇒ 76 ⇒ 79 ⇒ 67 ⇒ 85 ⇒ 73 ⇒ 50 ...
  • 70 74 ⇒ 70 ...

Diese Zyklen können verwendet werden, um Schleifen zu erstellen, die jedes Mal unterschiedliche Dinge tun und die sich schließlich wiederholen. Lou Scheffer nutzte diese Idee, um ein Malbolge-Programm zu erstellen (in seiner unten verlinkten Kryptoanalyse enthalten), das alles wiederholt, was der Benutzer eingibt.

Varianten

Malbolge ist aufgrund seiner Speicherbeschränkungen nicht Turing-vollständig . Ansonsten hat es jedoch sequentielle Ausführung, Wiederholung und bedingte Ausführung. Es wurden mehrere Versuche unternommen, Turing-vollständige Versionen von Malbolge zu erstellen:

  • Malbolge-T ist eine theoretische Version von Malbolge, die den Eingabe-/Ausgabestrom bei Erreichen des Endes zurücksetzt und unbegrenzte Programme ermöglicht. Malbolge-T wäre abwärtskompatibel mit Malbolge.
  • Malbolge Unshackled ist eine hoffentlich Turing-komplette Variante, die Programme jeder Länge zulässt. Aufgrund von Befehlsvariationen, die Werte über 257 zulassen, werden gültige Malbolge-Programme jedoch nicht unbedingt korrekt in Malbolge Unshackled ausgeführt.

Popkultur

In der Fernsehserie Elementary wird während der Episode "The Leviathan" (Staffel 1, Episode 10) ein Hinweis auf einer Kaffeebestellung als in Malbolge geschrieben beschrieben. Es scheint eine kleine Modifikation des weiter oben gezeigten Beispiels "Hello World" zu sein.

In der Seifenoper General Hospital hat Colonel Sanders von KFC einen Gastauftritt, weil jemand versucht, ihn zu töten, um das Geheimrezept von 11 Kräutern und Gewürzen zu erhalten. Er kennt Malbolge und kann die Zerstörungssequenz entschärfen.

In der Leverage: Redemption- Episode "The Golf Job" (Staffel 1, Folge 12) lautet eine automatische SMS-Antwort "Breanna ist von Donnerstag bis Sonntag nicht verfügbar oder bis sie den Malbolge-Code beherrscht."

Siehe auch

Verweise

Externe Links