Malbolge: Difference between revisions
m +link |
Added language description and examples (more features are pending) |
||
Line 2: | Line 2: | ||
Malbolge programs are written for a virtual machine based on trits (trinary digits). It has been argued that Malbolge is practically [[Turing-complete]] (that is, ignoring the memory size limitation) and could be made formally Turing-complete with a language extension. The language is named after Malebolge, the eighth level of hell in Dante's ''Inferno''. |
Malbolge programs are written for a virtual machine based on trits (trinary digits). It has been argued that Malbolge is practically [[Turing-complete]] (that is, ignoring the memory size limitation) and could be made formally Turing-complete with a language extension. The language is named after Malebolge, the eighth level of hell in Dante's ''Inferno''. |
||
==Language description== |
|||
The program, except for whitespace (including newlines) which is skipped, is fed directly into the virtual machine's memory starting at position 0. Only valid instructions and whitespace are allowed in the source, but a bug in the reference implementation makes it possible to enter instructions with a code greater than 126, which hang the reference interpreter if executed. There's only one officially allowed NOP code that can be entered, even if many possible NOPs are possible at run time (each non-instruction that is a printable character is a NOP). |
|||
==Virtual machine description== |
|||
The virtual machine is based on ''trits'' ('''tri'''nary, i.e. base 3, digi'''ts'''). Each machine word is ten trits wide, making it range from 0 to 2222222222 trinary = 59048 decimal. Each memory position holds a machine word; the addresses are one machine word wide too. Both data and code share the same memory space. |
|||
There are three registers, each of which holds one machine word: the code register <code>C</code> which is a pointer to the instruction that is about to be executed, the data register <code>D</code> used for data manipulation and the accumulator <code>A</code> also used by several instructions to manipulate data. |
|||
If the instruction to execute is not in the range 33-126, execution stops (the reference interpreter hangs in this case due to a bug). Otherwise, in order to determine the actual instruction to execute, the value pointed to by the <code>C</code> register is added to the <code>C</code> register itself and the result divided by 94, taking the remainder. Depending on the result, the following instructions are executed: |
|||
{| border="1" |
|||
! <code>(C+[C])%94</code> |
|||
! Description |
|||
! Pseudocode |
|||
|- |
|||
| 4 |
|||
| Set code pointer to the value pointed to by the current data pointer |
|||
| <code>C = [D]</code> |
|||
|- |
|||
| 5 |
|||
| Output the character in <code>A</code>, modulo 256, to standard output. |
|||
| <code>PRINT(A%256)</code> |
|||
|- |
|||
| 23 |
|||
| Input a character from standard input and store it in <code>A</code>. |
|||
| <code>A = INPUT</code> |
|||
|- |
|||
| 39 |
|||
| Tritwise rotate right |
|||
| <code>A = [D] = ROTATE_RIGHT([D])</code> |
|||
|- |
|||
| 40 |
|||
| Set data pointer to the value pointed to by the current data pointer |
|||
| <code>D = [D]</code> |
|||
|- |
|||
| 62 |
|||
| Tritwise "crazy" operation (see table below) |
|||
| <code>A = [D] = CRAZY_OP(A, [D])</code> |
|||
|- |
|||
| 68 |
|||
| No operation. |
|||
| <code>NOP</code> |
|||
|- |
|||
| 81 |
|||
| Stop execution of the current program. |
|||
| <code>STOP</code> |
|||
|} |
|||
''Note:'' The table above uses a criterium for input and output instruction codes that matches the reference interpreter instead of the one from the specification, which are reversed with respect to each other. |
|||
If the result is not any of the above, a NOP (no operation) is executed. However no NOP instructions are allowed in the source code except those for which (C+[C])%94 = 68. |
|||
As an example, in the first memory position (as well as in positions which are multiple of 94) the following instructions are allowed in the source code: ' ( < B Q b c u; in the second memory position the list is: & ' = A P a b t, and so on, decreasing the code at each step and wrapping from ! to ~. |
|||
The "crazy" operation is defined according to the following table. It operates on corresponding trits of each machine word (it's a "tritwise" operation). |
|||
{|border="1" |
|||
|colspan="2" rowspan="2"| |
|||
|colspan="3" style="text-align:center"| '''<code>A</code>''' |
|||
|- |
|||
| '''<code>0</code>''' |
|||
| '''<code>1</code>''' |
|||
| '''<code>2</code>''' |
|||
|- |
|||
|rowspan="3"|'''<code>[D]</code>''' |
|||
| '''<code>0</code>''' |
|||
| <code>1</code> |
|||
| <code>0</code> |
|||
| <code>0</code> |
|||
|- |
|||
| '''<code>1</code>''' |
|||
| <code>1</code> |
|||
| <code>0</code> |
|||
| <code>2</code> |
|||
|- |
|||
| '''<code>2</code>''' |
|||
| <code>2</code> |
|||
| <code>2</code> |
|||
| <code>1</code> |
|||
|} |
|||
After each instruction is executed, if the memory position pointed to by <code>C</code> is in the range 33-126 then it is encrypted using the following translation table: |
|||
5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1C |
|||
B6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@ |
|||
(that is, ! becomes 5, " becomes z, and so on). If it is not in the range 33-126 then the result is undefined (the reference interpreter has a bug in this case that can potentially cause a crash). |
|||
After that encryption step is performed, both <code>C</code> and <code>D</code> are incremented modulo 3<sup>10</sup> (59049 decimal) and the execution cycle is repeated. |
|||
==Sample programs== |
|||
The classic [[Hello, world!]] program in Malbolge: |
|||
<pre>'=a;:?87[543216/SR2+*No-,%*#G4</pre> |
|||
The [[cat program]] in Malbolge (this one does not stop on EOF; one which does is several orders of magnitude more complex): |
|||
<pre>(aBA@?>=<;:9876543210/.-,JH)('&%$#"!~}|{zy\J6utsrq |
|||
ponmlkjihgJ%dcba`_^]\[ZYXWVUTSRQPONMLKJIHGF('C%$$^ |
|||
K~<;4987654321a/.-,\*) |
|||
j |
|||
!~%|{zya}|{zyxwvutsrqSonmlO |
|||
jLhg`edcba`_^]\[ZYXWV8TSRQ4 |
|||
ONM/KJIBGFE>CBA@?>=<;{9876w |
|||
43210/.-m+*)('&%$#"!~}|{zy\ |
|||
wvunslqponmlkjihgfedcEa`_^A |
|||
\>ZYXWPUTSRQPONMLKJIH*FEDC& |
|||
A@?>=<;:9876543210/.-m+*)(i |
|||
&%$#"!~}|{zyxwvutsrqpRnmlkN |
|||
ihgfedcba`_^]\[ZYXWVU7SRQP3 |
|||
NMLKJIHGFEDCBA@?>=<;:z8765v |
|||
3210/.-,+*)('&%$#"!~}_{zyx[ |
|||
vutsrqjonmlejihgfedcba`_^]@ |
|||
[ZYXWVUTSRo</pre> |
|||
The same program translated to ''normalized Malbolge'' for clarity (see Andrew Cooke's site and the official specification in the ''External resources'' section below for reference): |
|||
<pre>jivvvvvvvvvvvvvvvvvvvvvvv<ivvvvvvvvvvvvvvoj/ivvvvv |
|||
vvvvvvvvvvjivvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv**v**j< |
|||
v*oopvvvvvvvvv/vvvv/vv |
|||
j |
|||
ppopppp*ooooooooooooo*ooooj |
|||
o*oopoooooooooooooooo*ooooj |
|||
ooo*ooopooopooooooooo*ooooj |
|||
oooooooo*oooooooooooooooooj |
|||
ooopopooooooooooooooo*ooooj |
|||
o*oooopoooooooooooooo*ooooj |
|||
ooooooooooooooooooooo*ooooj |
|||
ooooooooooooooooooooo*ooooj |
|||
ooooooooooooooooooooo*ooooj |
|||
ooooooooooooooooooooo*ooooj |
|||
ooooooooooooooooooooo*ooooj |
|||
oooooopoooopooooooooooooooj |
|||
ooooooooooi |
|||
</pre> |
|||
==See also== |
==See also== |
||
Line 7: | Line 142: | ||
==External resources== |
==External resources== |
||
* [http://www.lscheffer.com/malbolge.html Programming in Malbolge] |
* [http://www.lscheffer.com/malbolge.html Programming in Malbolge (includes original specification)] |
||
* [http://acooke.org/andrew/writing/malbolge.html Hello World in Malbolge] |
* [http://acooke.org/andrew/writing/malbolge.html Hello World in Malbolge] |
||
* [http://www.jess2.net/code/malbolge/ A shorter Hello World in Malbolge] |
* [http://www.jess2.net/code/malbolge/ A shorter Hello World in Malbolge] |
Revision as of 18:00, 11 June 2005
Malbolge, invented by Ben Olmstead in 1998, is an esoteric programming language designed to be as difficult to program in as possible. The first "Hello, world!" program written in it was produced by a Lisp program using genetic algorithms.
Malbolge programs are written for a virtual machine based on trits (trinary digits). It has been argued that Malbolge is practically Turing-complete (that is, ignoring the memory size limitation) and could be made formally Turing-complete with a language extension. The language is named after Malebolge, the eighth level of hell in Dante's Inferno.
Language description
The program, except for whitespace (including newlines) which is skipped, is fed directly into the virtual machine's memory starting at position 0. Only valid instructions and whitespace are allowed in the source, but a bug in the reference implementation makes it possible to enter instructions with a code greater than 126, which hang the reference interpreter if executed. There's only one officially allowed NOP code that can be entered, even if many possible NOPs are possible at run time (each non-instruction that is a printable character is a NOP).
Virtual machine description
The virtual machine is based on trits (trinary, i.e. base 3, digits). Each machine word is ten trits wide, making it range from 0 to 2222222222 trinary = 59048 decimal. Each memory position holds a machine word; the addresses are one machine word wide too. Both data and code share the same memory space.
There are three registers, each of which holds one machine word: the code register C
which is a pointer to the instruction that is about to be executed, the data register D
used for data manipulation and the accumulator A
also used by several instructions to manipulate data.
If the instruction to execute is not in the range 33-126, execution stops (the reference interpreter hangs in this case due to a bug). Otherwise, in order to determine the actual instruction to execute, the value pointed to by the C
register is added to the C
register itself and the result divided by 94, taking the remainder. Depending on the result, the following instructions are executed:
(C+[C])%94
|
Description | Pseudocode |
---|---|---|
4 | Set code pointer to the value pointed to by the current data pointer | C = [D]
|
5 | Output the character in A , modulo 256, to standard output.
|
PRINT(A%256)
|
23 | Input a character from standard input and store it in A .
|
A = INPUT
|
39 | Tritwise rotate right | A = [D] = ROTATE_RIGHT([D])
|
40 | Set data pointer to the value pointed to by the current data pointer | D = [D]
|
62 | Tritwise "crazy" operation (see table below) | A = [D] = CRAZY_OP(A, [D])
|
68 | No operation. | NOP
|
81 | Stop execution of the current program. | STOP
|
Note: The table above uses a criterium for input and output instruction codes that matches the reference interpreter instead of the one from the specification, which are reversed with respect to each other.
If the result is not any of the above, a NOP (no operation) is executed. However no NOP instructions are allowed in the source code except those for which (C+[C])%94 = 68.
As an example, in the first memory position (as well as in positions which are multiple of 94) the following instructions are allowed in the source code: ' ( < B Q b c u; in the second memory position the list is: & ' = A P a b t, and so on, decreasing the code at each step and wrapping from ! to ~.
The "crazy" operation is defined according to the following table. It operates on corresponding trits of each machine word (it's a "tritwise" operation).
A
| ||||
0
|
1
|
2
| ||
[D]
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
2
| |
2
|
2
|
2
|
1
|
After each instruction is executed, if the memory position pointed to by C
is in the range 33-126 then it is encrypted using the following translation table:
5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1C B6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@
(that is, ! becomes 5, " becomes z, and so on). If it is not in the range 33-126 then the result is undefined (the reference interpreter has a bug in this case that can potentially cause a crash).
After that encryption step is performed, both C
and D
are incremented modulo 310 (59049 decimal) and the execution cycle is repeated.
Sample programs
The classic Hello, world! program in Malbolge:
'=a;:?87[543216/SR2+*No-,%*#G4
The cat program in Malbolge (this one does not stop on EOF; one which does is several orders of magnitude more complex):
(aBA@?>=<;:9876543210/.-,JH)('&%$#"!~}|{zy\J6utsrq ponmlkjihgJ%dcba`_^]\[ZYXWVUTSRQPONMLKJIHGF('C%$$^ K~<;4987654321a/.-,\*) j !~%|{zya}|{zyxwvutsrqSonmlO jLhg`edcba`_^]\[ZYXWV8TSRQ4 ONM/KJIBGFE>CBA@?>=<;{9876w 43210/.-m+*)('&%$#"!~}|{zy\ wvunslqponmlkjihgfedcEa`_^A \>ZYXWPUTSRQPONMLKJIH*FEDC& A@?>=<;:9876543210/.-m+*)(i &%$#"!~}|{zyxwvutsrqpRnmlkN ihgfedcba`_^]\[ZYXWVU7SRQP3 NMLKJIHGFEDCBA@?>=<;:z8765v 3210/.-,+*)('&%$#"!~}_{zyx[ vutsrqjonmlejihgfedcba`_^]@ [ZYXWVUTSRo
The same program translated to normalized Malbolge for clarity (see Andrew Cooke's site and the official specification in the External resources section below for reference):
jivvvvvvvvvvvvvvvvvvvvvvv<ivvvvvvvvvvvvvvoj/ivvvvv vvvvvvvvvvjivvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv**v**j< v*oopvvvvvvvvv/vvvv/vv j ppopppp*ooooooooooooo*ooooj o*oopoooooooooooooooo*ooooj ooo*ooopooopooooooooo*ooooj oooooooo*oooooooooooooooooj ooopopooooooooooooooo*ooooj o*oooopoooooooooooooo*ooooj ooooooooooooooooooooo*ooooj ooooooooooooooooooooo*ooooj ooooooooooooooooooooo*ooooj ooooooooooooooooooooo*ooooj ooooooooooooooooooooo*ooooj oooooopoooopooooooooooooooj ooooooooooi