Malbolge
|
|
Malbolge is a public domain programming language invented by Ben Olmstead in 1998, named after the eighth circle of hell in Dante's Inferno, the Malebolge.
The peculiarity of Malbolge is that it was designed to be the worst possible (most difficult and esoteric) programming language. However, several of the tricks used to make understanding difficult can be simplified away.
| Contents |
Programming in Malbolge
Malbolge was so difficult to understand when it arrived that it took two years for the first Malbolge program to appear. The program was not even written by a human being: it was generated by a beam search algorithm designed by Andrew Cooke and implemented in Lisp.
On August 24, 2000, Anthony Youhas announced on his blog (http://www.antwon.com/index.php?p=234) that he "beat Malbolge with a stick and mastered its secrets," providing evidence in the form of three Malbolge programs that print various phrases. He did not, however, reveal his techniques.
Later, Lou Scheffer posted a cryptanalysis of Malbolge and provided a program to copy its input to its output.
Olmstead believed Malbolge to be Turing complete, except for infinite memory. There is a more interesting discussion about whether one can implement sensible loops in Malbolge — it was many years before introducing the first non-terminating one.
On August 17, 2004, Tomasz Wegrzanowski wrote a generator of Malbolge programs outputing various strings. According to him, the trick is to forget about the jumps, keep D register pointing at low memory locations, and randomly perform NOP, ROT and Crazy operations until A register contains what we need. Programs produced with this technique are much larger than Anthony's.
Hello, world in Malbolge
This Malbolge program displays "Hello, world."
(=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<
Simplified workings of Malbolge
Malbolge is machine language for a ternary virtual machine, the Malbolge interpreter. To help you write Malbolge programs that run properly, the way the standard interpreter works will be described below.
Notes
- The standard interpreter and the official specification do not match perfectly.
- This is a simplified explanation of the interpreter source code: it obviates useless encryption and subtraction steps and introduces an assembly language.
- Before correcting it, make sure it's actually technically incorrect and not just unfamiliar.
Registers
Malbolge has three registers, a, c, and d, which are like variables in other languages. When a program starts, the value of all three registers is zero. c is special: it points to the current instruction.
Pointer notation
[d] means the value of d is a memory address; [d] is the value stored at the address. [c] is similar.
Memory
The virtual machine has 59049 memory locations that can each hold a ten-digit ternary number. Each memory location has an address from 0 to 59048 and can hold a value from 0 to 59048. A value that reaches 59049 is instantly replaced by 0.
Before a Malbolge program starts, the first part of memory is filled with the program. All whitespace in the program is ignored and, to make programming more difficult, everything else in the program must start out as one of the instructions below.
The rest of memory is filled by using the crazy operation (see below) on the previous two addresses ([m] = crz [m - 2], [m - 1]). Memory filled this way will repeat every twelve addresses (the individual ternary digits will repeat every three or four addresses, so a group of ternary digits is guaranteed to repeat every twelve).
Instructions
Malbolge has eight instructions. Malbolge figures out which instruction to execute by taking the value at [c], adding the value of c to it, and subtracting 94 repeatedly until the number is less than 94. The final result tells the interpreter what to do :
| Value of ([c] + c) % 94 | Instruction represented | Explanation |
|---|---|---|
| 4 | jmp [d] + 1 | The value at [d], plus one, is where Malbolge will jump to and start executing instructions. |
| 5 | out a | Prints the value of a, as an ASCII character, to the screen. |
| 23 | in a | Inputs a character, as an ASCII code, into a. Newlines or line feeds are both code 10. An end-of-file condition is code 59048. |
| 39 | rotr [d] mov a, [d] | Rotates the value at [d] by one ternary digit (0002111112 becomes 2000211111). Stores the result both at [d] and in a. |
| 40 | mov d, [d] | Copies the value at [d] to d. |
| 62 | crz [d], a mov a, [d] | Does the crazy operation (see below) with the value at [d] and the value of a. Stores the result both at [d] and in a. |
| 68 | nop | Does nothing. |
| 81 | end | Ends the Malbolge program. |
| Any other value does the same as 68: nothing. These other values are not allowed in a program while it is being loaded, but are allowed afterwards. | ||
After each instruction is executed, the guilty instruction gets encrypted (see below) so that it won't do the same thing next time, unless a jump just happened. Right after a jump, Malbolge will encrypt the innocent instruction just prior to the one it jumped to instead. Then, the values of both c and d are increased by one and the next instruction is executed.
Crazy operation
For each ternary digit of both inputs, use the following table to get a ternary digit of the result. For example, crz 0001112220, 0120120120 gives 1001022211.
| crz | Input 2 | |||
|---|---|---|---|---|
| 0 | 1 | 2 | ||
| Input 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 2 | |
| 2 | 2 | 2 | 1 | |
Encryption
After an instruction is executed, the value at [c] (without anything added to it) will have 94 subtracted from it repeatedly until the result is less than 94. Then, the result is encrypted with one of the following two equivalent methods.
Method 1
Find the result below. Store the ASCII code of the character below it at [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
Method 2
Find the result below. Store the encrypted version at [c].
| Result | Encrypted | Result | Encrypted | Result | Encrypted | Result | Encrypted | Result | Encrypted |
|---|---|---|---|---|---|---|---|---|---|
| 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 |
| 15 | 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 |
Cycles in the encryption
Lou Scheffer's cryptanalysis of Malbolge mentions six different cycles in the encryption. They are listed here :
- 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 ...
These cycles can be used to create loops that do different things each time and that eventually become repetitive. Lou Scheffer used this idea to create a Malbolge program (included in his cryptanalysis linked below) that repeats anything the user inputs.
External links
- Official Malbolge website (http://web.archive.org/web/20031209180058/http%3A//www.mines.edu/students/b/bolmstea/malbolge/index.html) (archived)
- Malbolge language specification (http://www.antwon.com/other/malbolge/malbolge.txt)
- Malbolge interpreter (C source code) (http://www.lscheffer.com/malbolge_interp.html)
- Description of Andrew Cooke's algorithm for creating the first Malbolge program (http://www.acooke.org/andrew/writing/malbolge.html)
- Lou Scheffer's cryptanalysis of Malbolge (http://www.lscheffer.com/malbolge.html)
- Anthony Youhas' blog announcement (http://www.antwon.com/index.php?p=234)
- "99 bottles" in Malbolge (http://www.99-bottles-of-beer.net/language-malbolge-375.html)
Template:Esolangsde:Malbolge et:Malbolge es:Malbolge ko:Malbolge