Page namespace (page_namespace) | 0 |
Page title (without namespace) (page_title) | 'Malbolge' |
Full page title (page_prefixedtitle) | 'Malbolge' |
Old content model (old_content_model) | 'wikitext' |
New content model (new_content_model) | 'wikitext' |
Old page wikitext, before the edit (old_wikitext) | '{{featured language}}
'''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 a local beam search of the space of all possible programs. It is modelled as a virtual machine based on ternary digits.
==Etymology==
The language is named after ''Malebolge'' [sic], the eighth level of hell in Dante's ''Inferno'', which is reserved for perpetrators of fraud. The actual spelling ''Malbolge'' is also used for the sixth hell in the Dungeons and Dragons roleplaying game.
==Memory initialization==
The program is fed directly into the virtual machine's memory starting at position 0. Any whitespace is skipped, including newlines. 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 that 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).
Each word in the remainder of the memory is initialized as the result of applying the crazy operation (see below) to the contents of the previous and the second previous word (in that order).
==Virtual machine description==
The virtual machine is based on ''trits'' ('''tri'''nary, i.e. ternary or base 3, digi'''ts'''). Each machine word is ten trits wide, making it range from 0 to 2222222222 ternary = 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.
(At this place it may be interesting to know that in the 1960s and 1970s trit-based computers were developed in the "eastern bloc" and still some engineers think about trit-based computers when talking about new non-silicon-based technologies.)
There are three registers, each of which holds one machine word, initially 0: 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:
{| class="wikitable"
! <code>(C+[C])%94</code>
! Description
! Pseudocode
! Op
|-
| 4
| Set code pointer to the value pointed to by the current data pointer.
| <code>C = [D]</code>
| '''i'''
|-
| 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>
| '''j'''
|-
| 62
| Tritwise "crazy" operation (see table below).
| <code>A = [D] = CRAZY_OP(A, [D])</code>
| '''p'''
|-
| 68
| No operation.
| <code>NOP</code>
| '''o'''
|-
| 81
| Stop execution of the current program.
| <code>STOP</code>
| '''v'''
|}
(The ''Op'' column specifies the operation letter according to the original specification.)
''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 values in the table, 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: <code>' ( > D Q b c u</code>; in the second memory position the list is: <code>& ' = C P a b t</code>, and so on, decreasing the code at each step and wrapping from <code>!</code> to <code>~</code>.
The "crazy" operation is defined according to the following table. It operates on corresponding trits of each machine word (it's a "tritwise" operation).
{| class="wikitable"
!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:
ORIGINAL: !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
TRANSLATED: 5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=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.
==Computational class==
It has been argued that Malbolge is a [[bounded-storage machine]] (BSM) with interactive input; that is, that it is [[Turing-complete]] if one ignores its memory limitations (and a [[finite-state automaton]] [FSA] if one does not). The difficulty in showing this, however, is in showing that 59049 memory words are enough to implement the FSA that simulates a [[universal Turing machine]], as practical Malbolge programs consume lots of memory. But thanks to [[Hisashi Iizawa]], who wrote a [[99 bottles of beer]] program in just 21945 instructions of Malbolge code [http://www.99-bottles-of-beer.net/language-malbolge-995.html], there are now arguments favouring the BSM hypothesis.
==Sample programs==
===Cat===
A [[cat program]] in Malbolge (this one does not stop on EOF; one which does is several orders of magnitude more complex):
<pre>(=BA#9"=<;:3y7x54-21q/p-,+*)"!h%B0/.
~P<
<:(8&
66#"!~}|{zyxwvu
gJ%</pre>
The same program translated to ''normalized Malbolge'' for clarity:
<pre>jpoo*pjoooop*ojoopoo*ojoooooppjoivvv
o/i
<iviv
i<vvvvvvvvvvvvv
oji
</pre>
(''Normalized Malbolge'' means with the instructions decrypted to match the original specification, but in this variant every instruction has a different value when interpreted as data, depending on the address modulo 94. The term ''normalized Malbolge'' was coined by Andrew Cooke as can be seen in the ''External resources'' section below.)
===Truth-machine===
A [[truth-machine]] in Malbolge can be found here: [[Truth-machine#Malbolge]]
==See also==
* [[Dis]], a slightly less evil version (or [[Wimpmode]]) of Malbolge
* [[Malbolge20]], an extension of Malbolge to 20 trits
* [[Malbolge Unshackled]], an attempt to make a Turing complete dialect of Malbolge
* [[Malbolge programming|How to write Malbolge programs]]
==External resources==
* [http://www.lscheffer.com/malbolge.shtml Programming in Malbolge (includes original specification)]
* [http://acooke.org/malbolge.html The first Hello World in Malbolge, by Andrew Cooke]
* [http://esoteric.sange.fi/orphaned/malbolge/ Malbolge interpreters and programs]
* [http://www.99-bottles-of-beer.net/language-malbolge-995.html 99 bottles of beer program]
* [https://github.com/graue/esofiles/tree/master/malbolge Malbolge] in [[the Esoteric File Archive]]
* [http://matthias-ernst.eu/malbolgequine.html Quine]
* [http://www.sakabe.nuie.nagoya-u.ac.jp/Malbolge/ ROT13 program and online assembler]
* [http://www.malbolge.doleczek.pl/ Malbolge] interpreter on-line in [[JavaScript]] with collection of programs
[[Category:Cell-based]]
[[Category:Usability unknown]]
[[Category:Finite state automata]]
[[Category:Implemented]]
[[Category:Self-modifying]]
[[Category:Languages]]
[[Category:1998]]' |
New page wikitext, after the edit (new_wikitext) | '{{featured language}}
'''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 a local beam search of the space of all possible programs. It is modelled as a virtual machine based on ternary digits.
==Etymology==
The language is named after ''Malebolge'' [sic], the eighth level of hell in Dante's ''Inferno'', which is reserved for perpetrators of fraud. The actual spelling ''Malbolge'' is also used for the sixth hell in the Dungeons and Dragons roleplaying game.
==Memory initialization==
The program is fed directly into the virtual machine's memory starting at position 0. Any whitespace is skipped, including newlines. 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 that 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).
Each word in the remainder of the memory is initialized as the result of applying the crazy operation (see below) to the contents of the previous and the second previous word (in that order).
==Virtual machine description==
The virtual machine is based on ''trits'' ('''tri'''nary, i.e. ternary or base 3, digi'''ts'''). Each machine word is ten trits wide, making it range from 0 to 2222222222 ternary = 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.
(At this place it may be interesting to know that in the 1960s and 1970s trit-based computers were developed in the "eastern bloc" and still some engineers think about trit-based computers when talking about new non-silicon-based technologies.)
There are three registers, each of which holds one machine word, initially 0: 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:
{| class="wikitable"
! <code>(C+[C])%94</code>
! Description
! Pseudocode
! Op
|-
| 4
| Set code pointer to the value pointed to by the current data pointer.
| <code>C = [D]</code>
| '''i'''
|-
| 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>
| '''j'''
|-
| 62
| Tritwise "crazy" operation (see table below).
| <code>A = [D] = CRAZY_OP(A, [D])</code>
| '''p'''
|-
| 68
| No operation.
| <code>NOP</code>
| '''o'''
|-
| 81
| Stop execution of the current program.
| <code>STOP</code>
| '''v'''
|}
(The ''Op'' column specifies the operation letter according to the original specification.)
''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 values in the table, 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: <code>' ( > D Q b c u</code>; in the second memory position the list is: <code>& ' = C P a b t</code>, and so on, decreasing the code at each step and wrapping from <code>!</code> to <code>~</code>.
The "crazy" operation is defined according to the following table. It operates on corresponding trits of each machine word (it's a "tritwise" operation).
{| class="wikitable"
!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 enciphered using the following translation table:
ORIGINAL: !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
TRANSLATED: 5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=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 the ciphering 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.
==Computational class==
It has been argued that Malbolge is a [[bounded-storage machine]] (BSM) with interactive input; that is, that it is [[Turing-complete]] if one ignores its memory limitations (and a [[finite-state automaton]] [FSA] if one does not). The difficulty in showing this, however, is in showing that 59049 memory words are enough to implement the FSA that simulates a [[universal Turing machine]], as practical Malbolge programs consume lots of memory. But thanks to [[Hisashi Iizawa]], who wrote a [[99 bottles of beer]] program in just 21945 instructions of Malbolge code [http://www.99-bottles-of-beer.net/language-malbolge-995.html], there are now arguments favouring the BSM hypothesis.
==Sample programs==
===Cat===
A [[cat program]] in Malbolge (this one does not stop on EOF; one which does is several orders of magnitude more complex):
<pre>(=BA#9"=<;:3y7x54-21q/p-,+*)"!h%B0/.
~P<
<:(8&
66#"!~}|{zyxwvu
gJ%</pre>
The same program translated to ''normalized Malbolge'' for clarity:
<pre>jpoo*pjoooop*ojoopoo*ojoooooppjoivvv
o/i
<iviv
i<vvvvvvvvvvvvv
oji
</pre>
(''Normalized Malbolge'' means with the instructions decrypted to match the original specification, but in this variant every instruction has a different value when interpreted as data, depending on the address modulo 94. The term ''normalized Malbolge'' was coined by Andrew Cooke as can be seen in the ''External resources'' section below.)
===Truth-machine===
A [[truth-machine]] in Malbolge can be found here: [[Truth-machine#Malbolge]]
==See also==
* [[Dis]], a slightly less evil version (or [[Wimpmode]]) of Malbolge
* [[Malbolge20]], an extension of Malbolge to 20 trits
* [[Malbolge Unshackled]], an attempt to make a Turing complete dialect of Malbolge
* [[Malbolge programming|How to write Malbolge programs]]
==External resources==
* [http://www.lscheffer.com/malbolge.shtml Programming in Malbolge (includes original specification)]
* [http://acooke.org/malbolge.html The first Hello World in Malbolge, by Andrew Cooke]
* [http://esoteric.sange.fi/orphaned/malbolge/ Malbolge interpreters and programs]
* [http://www.99-bottles-of-beer.net/language-malbolge-995.html 99 bottles of beer program]
* [https://github.com/graue/esofiles/tree/master/malbolge Malbolge] in [[the Esoteric File Archive]]
* [http://matthias-ernst.eu/malbolgequine.html Quine]
* [http://www.sakabe.nuie.nagoya-u.ac.jp/Malbolge/ ROT13 program and online assembler]
* [http://www.malbolge.doleczek.pl/ Malbolge] interpreter on-line in [[JavaScript]] with collection of programs
[[Category:Cell-based]]
[[Category:Usability unknown]]
[[Category:Finite state automata]]
[[Category:Implemented]]
[[Category:Self-modifying]]
[[Category:Languages]]
[[Category:1998]]' |
Unified diff of changes made by edit (edit_diff) | '@@ -102,5 +102,5 @@
|}
-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:
+After each instruction is executed, if the memory position pointed to by <code>C</code> is in the range 33–126 then it is enciphered using the following translation table:
ORIGINAL: !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
@@ -109,5 +109,5 @@
(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.
+After the ciphering 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.
==Computational class==
' |