We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.

Malbolge

From Esolang
Jump to navigation Jump to search

This is a featured language.
Malbolge
Paradigm(s) imperative, cryptographic
Designed by Ben Olmstead
Appeared in 1998
Memory system contiguous array/register
Dimensions one-dimensional
Computational class Bounded-storage machine
Reference implementation Malbolge and Dis (from the Wayback Machine; retrieved on 9 December 2003)
Influenced Dis, Malbolge Unshackled
File extension(s) .mal, .mb

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. More practical programming methods have been found later. 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. However, the reference loader admits non-whitespace bytes outside graphical ASCII without validating their instructions; execution spins if such a value is fetched.[1] 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).

The specification supplies no initialization seeds for sources containing fewer than two characters. The reference interpreter nevertheless reads the two preceding cells when filling memory, causing an out-of-bounds read for these sources and therefore undefined behavior.[1][2]

Virtual machine description

The virtual machine is based on trits (trinary, i.e. ternary or base 3, digits). 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 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 according to the specification; the reference interpreter instead spins without changing its state.[2][1] 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 Op
4 Set code pointer to the value pointed to by the current data pointer. C = [D] i
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] j
62 Tritwise "crazy" operation (see table below). A = [D] = CRAZY_OP(A, [D]) p
68 No operation. NOP o
81 Stop execution of the current program. STOP v

(The Op column specifies the operation letter according to the original specification.)

The table follows the reference interpreter: decoded < outputs and decoded / inputs; the prose specification reverses these directions. On EOF, input sets A to 59048, the ten-trit all-twos value, without halting. Outputting that value on an eight-bit-byte host emits byte 168.[2][1]

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: ' ( > D Q b c u; in the second memory position the list is: & ' = C 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 a non-halting instruction is executed, the word at the current C is enciphered using the following translation table, indexed by its value minus 33:[1] 

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). The reference interpreter does not check whether this value lies in 33–126 before indexing the table; an out-of-range index causes undefined C behavior.[1]

After enciphering, both C and D are incremented modulo 59049 and execution continues. A jump changes C before enciphering: assigning 100 enciphers address 100 and makes the next fetch occur at 101. The enciphered cell is therefore not necessarily the cell from which the jump was fetched. The data-pointer operation likewise increments its newly assigned value. Halt returns before enciphering or incrementing.[1]

Computational class

Malbolge is a bounded-storage machine: its 59049 memory words and three registers have fixed capacity. It is not Turing-complete with this storage model. Loops and useful algorithms remain possible, as illustrated by Hisashi Iizawa's implementation of 99 bottles of beer (link). Variants introducing unbounded storage require a separate analysis.[2][3]

Lou Scheffer defines a variant "Malbolge-T" (see section "Proving formal Turing completeness") which provides access to unlimited memory via allowing the program to read its own output, and believes this variant to be Turing complete (although it has not yet been demonstrated that a program space of 59049 words is large enough).

Malbolge Unshackled is a language based on Malbolge, which eliminates the memory restrictions by extending the commands to be able to address arbitrarily many addresses. Malbolge Unshackled is Turing complete, with a Lisp interpreter available.

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): 

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

The same program translated to normalized Malbolge for clarity: 

jpoo*pjoooop*ojoopoo*ojoooooppjoivvv
o/i
<iviv
i<vvvvvvvvvvvvv
oji

(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

References

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Ben Olmstead, Original Malbolge interpreter, 1998, preserved by Try It Online; see main and exec.
  2. ↑ 2.0 2.1 2.2 2.3 Ben Olmstead, Malbolge specification, 1998, preserved text; “Environment” and “Commands”.
  3. ↑ Lou Scheffer, Programming in Malbolge, sections on practical and formal Turing completeness.

See also

External resources

Retrieved from "https://esolangs.org/w/index.php?title=Malbolge&oldid=202815"