Malbolge Unshackled
| Paradigm(s) | imperative |
|---|---|
| Designed by | Ørjan Johansen |
| Appeared in | 2007 |
| Memory system | contiguous array/register |
| Dimensions | one-dimensional |
| Computational class | Turing complete |
| Reference implementation | Johansen's interpreter in Haskell |
| Influenced by | Malbolge |
| File extension(s) | .mu |
Malbolge Unshackled is a dialect of Malbolge from 2007 by Ørjan Johansen. It was created as an attempt to remove the arbitrary memory limits of Malbolge, in order to create a language that had the potential to be Turing complete, while keeping closely to the spirit of Malbolge in most ways. The language was subsequently discovered to have succeeded at this goal, with the creation in 2020 of MalbolgeLisp.
Changes from Malbolge
The following describes how Malbolge Unshackled deviates from Malbolge, as well as some rationale for the changes.
Values
The values and addresses of cells in Malbolge Unshackled have an unbounded number of trits. This immediately presents a problem with the crazy operation, because op(0,0) is 1, not 0, and so it is not possible to pad values with zeros and expect the value of the tritwise operator to be the same integer.
This is solved by letting the allowable values be a subset of the 3-adic integers. In Malbolge Unshackled the first trit of a value is considered to repeat indefinitely to the left. So ...01 = ...001 = ...00001. The result of op(...01,...01) is then ...10 = ...110 = ...11110. Values beginning with 0 may be identified with the natural numbers, as is done during I/O and instruction decoding.
The width of a value is the number of trits other than the initial repeating ones.
Remainders
Instruction execution depends on calculating remainders modulo 94. The question then is how to do this for values that are not natural numbers. The mathematical ideal would be an operation that is additive, but this is not possible:
...111 + ...111 + ...001 = ...000,
but there is no integer n such that n+n+1 is 0 (mod 94).
Malbolge Unshackled instead lets ...111 and ...222 have the same results with modulo operations as the corresponding 10-trit values, and other values starting with the same trits are calculated as offsets from these. For example,
...1102 mod 94 = (...1111 - 2) mod 94 = (11111111113 - 2) mod 94 = (29524-2) mod 94 = 6.
Initialization
In Malbolge, the memory after the program is filled by an iterative procedure, which repeats the values every 6 cells. Since this iteration can never reach addresses not starting with 0, Malbolge Unshackled continues the filling of these cells by generalizing the pattern and using remainders modulo 6.
Rotation width
The tritwise rotation operation * presents special problems. Once the number of trits becomes unbounded, it is not clear what should happen with the trit that is shifted off to the right. One might try either to drop it altogether or to put it in a fixed position.
Unfortunately neither of these works, because the rotation operation is the only way to create usable values that are larger in size than those we start with, and this happens by the back rotation of the final trit. So either of these would mean an absolute limit on the size of values produced by the program.
Instead, Malbolge Unshackled lets the width of rotation be a variable, which grows with the values in the D register. The growth is fairly unpredictable (and implementation dependent), but not entirely:
- The rotation width starts as at least 10 trits.
- If a j operation increases the width of the D register to more than half the rotation width, then the rotation width changes to correct this.
- As long as the D register does not increase width beyond the previous maximum, the rotation width does not change.
- It is unspecified whether the auto-increment of the D register can register a width change.
I/O
Malbolge Unshackled does not do I/O modulo 256 but considers values starting with 0 to be Unicode characters. Values starting with trits 1 and 2 are reserved for further expansion, so far only the following are used:
...22 represents the end of file ...21 represents the end of line character (automatically converted on I/O)
Compatibility
While the language is intended to keep the spirit of Malbolge, backwards compatibility is a harder matter. An earlier version of the Malbolge cat program did not work in Malbolge Unshackled, but the current cat program does. Initial reports that the old Malbolge cat program was working turned out to be due to an interpreter bug that caused the rotation width to stay at the Malbolge default of 10.
You can make shorter programs that work in both Malbolge and in Malbolge Unshackled as follows:
- Avoid the * operation unless you are sure that the first and last trits of [D] are identical.
- Use exact values on I/O.
- Accept both \10 and ...21 as newline on input, for freshly produced newlines use the Malbolge \10 convention on output (may not work on Macs).
- Avoid programs longer than 1/3 of memory.
- Avoid wrapping across memory thirds.
Sample programs
Hello, world!
A Hello, world! in Malbolge Unshackled can be found here: Hello_world_program_in_esoteric_languages_(H-M)#Malbolge_Unshackled
Truth-machine
A truth-machine in Malbolge Unshackled can be found here: Truth-machine#Malbolge Unshackled
Computational class
Malbolge Unshackled is known to be Turing complete because it has been used to write a brainfuck interpreter, and later a Lisp (MalbolgeLisp) interpreter as well.
See also
- Malbolge
- Malbolge20
- Malbolge programming
- MalbolgeLisp, a Lisp interpreter in Malbolge Unshackled.