Malbolge

Malbolge (/mælˈboʊldʒ/) is a public domain esoteric programming language invented by Ben Olmstead in 1998, named after the eighth circle of hell in Dante's Inferno, the Malebolge. It was specifically designed to be almost impossible to use, via a counter-intuitive 'crazy operation', base-three arithmetic, and self-altering code.[1] It builds on the difficulty of earlier, challenging esoteric languages (such as Brainfuck and Befunge), but takes this aspect to the extreme, playing on the entangled histories of computer science and encryption. Despite this design, it is possible to write useful Malbolge programs.

This article is about the programming language. For the eighth circle of hell in Dante's Inferno, see Malebolge.

Malbolge

Paradigm	Esoteric, imperative, scalar, value-level
Designed by	Ben Olmstead
First appeared	1998
Typing discipline	Untyped
Filename extensions	.mal, .mb
Influenced by
Brainfuck, INTERCAL (Tri-INTERCAL), Befunge
Influenced
Dis, Malbolge Unshackled

Programming in Malbolge

Malbolge was so difficult to understand when it arrived that it took two years for the first Malbolge program to appear. Indeed, the author himself has never written a single Malbolge program.[1] The first program was not written by a human being: it was generated by a beam search algorithm designed by Andrew Cooke and implemented in Lisp.[2]

Later, Lou Scheffer posted a cryptanalysis of Malbolge and provided a program to copy its input to its output.[3] He also saved the original interpreter and specification after the original site stopped functioning, and offered a general strategy of writing programs in Malbolge as well as some thoughts on its Turing-completeness.[4]

Olmstead believed Malbolge to be a linear bounded automaton. There is a discussion about whether one can implement sensible loops in Malbolge—it took many years before the first non-terminating one was introduced. A correct 99 Bottles of Beer program, which deals with non-trivial loops and conditions, was not announced for seven years; the first correct one was by Hisashi Iizawa in 2005.[5] Hisashi Iizawa et al. also proposed a guide for programming in Malbolge for the purpose of obfuscation for software protection.[6]

Example programs

Hello, World!

This Malbolge program displays "Hello World!", with both words capitalized and exclamation mark at the end.

 (=<`#9]~6ZY32Vx/4Rs+0No-&Jk)"Fh}|Bcy?`=*z]Kw%oG4UUS0/@-ejc(:'8dc

cat program

This program reads a string from a user and prints that string, similar to Unix cat.

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

Design

Malbolge is machine language for a ternary virtual machine, the Malbolge interpreter.

The standard interpreter and the official specification do not match perfectly.[7] One difference is that the compiler stops execution with data outside the 33–126 range. Although this was initially considered a bug in the compiler, Ben Olmstead stated that it was intended and there was in fact "a bug in the specification".[1]

Registers

Malbolge has three registers, a, c, and d. When a program starts, the value of all three registers is zero.

a stands for 'accumulator', set to the value written by all write operations on memory and used for standard I/O. c, the code pointer, is special: it points to the current instruction.[8] d is the data pointer. It is automatically incremented after each instruction, but the location it points to is used for the data manipulation commands.

Pointer notation

d can hold a memory address; [d] is register indirect; the value stored at that address. [c] is similar.

Memory

The virtual machine has 59,049 (3¹⁰) memory locations that can each hold a ten-trit ternary number. Each memory location has an address from 0 to 59048 and can hold a value from 0 to 59048. Incrementing past this limit wraps back to zero.

The language uses the same memory space for both data and instructions. This was influenced by how hardware such as x86 architecture worked.[1]

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

In 2007, Ørjan Johansen created Malbolge Unshackled, a version of Malbolge which does not have the arbitrary memory limit. The hope was to create a Turing-Complete language while keeping as much in the spirit of Malbolge. No other rules are changed, and all Malbolge programs that do not reach the memory limit are completely functional.[9]

Instructions

Malbolge has eight instructions. Malbolge figures out which instruction to execute by taking the value [c], adding the value of c to it, and taking the remainder when this is divided by 94. The final result tells the interpreter what to do:

Instructions

Value of ([c] + c) % 94	Instruction represented	Explanation
4	jmp [d]	Copies the value at [d] to c. Note that c will still be incremented after execution of this instruction, so the next instruction to be executed will be the one at [d] + 1 (modulo 59049).
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 will not 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.

Crazy operation[1][6]

crz		Input 2
		0	1	2
Input 1	0	1	0	0
	1	1	0	2
	2	2	2	1

Encipherment

After an instruction is executed, the value at [c] (without anything added to it) will be replaced with itself mod 94. Then, the result is enciphered 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].

Encryption table

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

Lou Scheffer's cryptanalysis of Malbolge mentions six different cycles in the permutation. 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.

Variants

Malbolge is not Turing-complete, due to its memory limits. However, it otherwise has sequential execution, repetition, and conditional-execution. Several attempts have been made to create Turing-complete versions of Malbolge:

• Malbolge-T is a theoretical version of Malbolge that resets the input/output stream upon reaching the end, allowing for unbounded programs. Malbolge-T would be backward compatible with Malbolge.[3]
• Malbolge Unshackled is a hopefully Turing-complete variation, allowing for programs of any length. However, due to command variations to allow for values above 257, valid Malbolge programs will not necessarily run correctly in Malbolge Unshackled.[10]

Popular culture

In the television series Elementary, during the episode "The Leviathan" (season 1, episode 10), a clue written on a coffee order is described as having been written in Malbolge. It appears to be a small modification of the more verbose "Hello World" example shown above.[1][11]

See also

• INTERCAL
• Obfuscated code

References

1. Temkin, Daniel (2014-11-03). "Interview with Ben Olmstead". esoteric.codes. Retrieved 2017-06-09.
2. Cooke, Andrew (2016-06-06). "malbolge: hello world". Retrieved 2017-06-09.
3. Scheffer, Lou (2015-04-17). "Introduction to Malbolge". Retrieved 2017-06-09.
4. Mykhailova, Mariya (2012-05-11). "Malbolge - Programming language". Progopedia. Retrieved 2017-06-09.
5. "Language Malbolge". 99 Bottles of Beer. 2005-12-29. Retrieved 2017-06-09.
6. IIZAWA, Hisashi. "Programming Method in Obfuscated Language Malbolge" (PDF) (in Japanese). Nagoya University. Retrieved 2017-06-09.
7. Green, Austin (2000-12-01). "Malbolge". Louisiana Tech University. Retrieved 2017-06-09.
8. Olmstead, Ben (1998). "Malbolge Specification". www.lscheffer.com. Retrieved 2017-06-09.
9. Johansen, Ørjan (2013-10-25). "An interpreter for the Malbolge Unshackled dialect" (Haskell). oerjan.nvg.org. Retrieved 2017-06-09.
10. "Malbolge Unshackled". esolangs.org. 2017-04-14. Retrieved 2017-06-09.
11. "Leviathan". Elementary. Season 1. Episode 10. Manhattan. 2012-12-14. CBS.

External links

• Malbolge interpreter (C source code)
• Malbolge interpreter, debugger, assembler and example Malbolge Assembly code (Java source code)
• Description of Andrew Cooke's algorithm for creating the first Malbolge program
• Treatise on writing Malbolge programs; takes Scheffer's analysis a bit further
• "99 bottles" in Malbolge (real loop version)
• Malbolge SDK – A collection of programs to make your life easier when coding in Malbolge (In Portuguese)
• Malbolge interpreter on-line in JavaScript with collection of programs
• A project devoted to present programs written in Malbolge