Malbolge

Malbolge (named after eights circle of hell in Dante’s Inferno, where fraudsters are punished) is an esoteric programming language.

It was invented by Ben Olmstead in 1998. The intention was to create a language that would make writing programs as hard as possible. The author succeeded: it took two years to produce a “Hello, World!” program, and it was not written by hand but generated by a Lisp program which implemented beam search algorithm.

The second most significant person in the history of the language is Lou Scheffer who saved the original interpreter and specification after the original site stopped functioning, did a research on cryptanalysis of the language, created a program which copies its input into its output and offered a general strategy of writing programs in Malbolge as well as some thoughts on its Turing-completeness.

Malbolge virtual machine works in ternary system. Machine word is 10 trits (ternary digits) long, so it can store unsigned integers between 0 and 59048, inclusive. Both program instructions and data are stored in the same one-dimensional memory segment, consisting of 59049 memory cells. Besides, the machine has three one-word registers: A (accumulator, used for data manipulations), C (code pointer) and D (data pointer). Initially all registers hold value of 0.

Before starting to interpret the program, the interpreter loads it to the memory, one cell per instruction. If the program has a character which is impossible to interpret as an instruction (see later) or a whitespace, it is rejected as a whole. Uninitialized memory cells are filled with results of performing crazy operation on two previous (filled) cells.

Interpreting a single instruction looks like this. ASCII-code of the current instruction can be denoted as [C] (the value stored in the cell pointed to by C register). If [C] is not between 33 and 126, inclusive, the instruction is invalid. Otherwise the interpreter calculates (C + [C]) mod 94 and uses is as an index in decoding table. If it doesn’t decode into one of the following 8 commands, this instruction is invalid.

• j D = [D] Sets data pointer to the value in the cell pointed to by its current value.
• i C = [C] Sets instruction pointer to the value in the cell pointed to by its current value.
• * [D] = ROTATE([D]) Rotates the value in the cell pointed to by D one trit to the right. As a side effect, this value is stored in A.
• p [D] = CRAZY(A, [D]) Applies crazy operation to the value of A and the cell pointed to by D.
• / A = INPUT Reads one character from input stream and stores its ASCII to A.
• < PRINT A Prints a character with ASCII value of A mod 256.
• v STOP Stop program execution.
• o NOP The only valid program to do nothing.

crazy operation performs tritwise calculation on the arguments using the following rule:

        | A trit:  
________|_0__1__2_  
      0 | 1  0  0  
  *D  1 | 1  0  2  
 trit 2 | 2  2  1