kspalaiologos / malbolge-lisp

A lightweight (350MB) Lisp interpreter in Malbolge Unshackled, often dubbed the hardest turing complete programming language.

MalbolgeLISP v1.2

Made by Palaiologos, 2020 - 2021. Core (core.mb) to the public domain, the entire program is governed by the GNU GPLv3 license.

During summer and fall of 2021, I wrote a book about MalbolgeLISP's design and implementation

What is MalbolgeLisp?

MalbolgeLisp is a LISP interpreter written in Malbolge. It's as of 2020 and 2021, the most advanced, usable Malbolge program ever created. It supports everything LISPs generally tend to support (like cond, let, lambda, etc...). The v1.2 release greatly improved the performance and reduced the code size, while adding a few features.

MalbolgeLISP supports tacit programming, partial application, de Bruijn indices, monad lifting, and more.

A few fibonacci functions programmed in MalbolgeLISP (and tested on (fibN 6)):

; Naive attempt at 1m 19s
(defun fib1 (n) (
    if [n < 2]
        n
        [(fib1 [n - 1]) + (fib1 [n - 2])]))

; Direct port of accumulator-keeping solution at 1m 6s:
(defun fib2 (n) ((lambda (a w) (
    if [w = 0]
        (#0 a)
        ((bruijn 0) (tie (#1 a) (lift + a)) [w - 1]))) '(0 1) n))

; A more idiomatic solution than the above at 54s:
(defun fib3 (n) ((lambda (x y w) (
    if [w = 0]
        x
        ((bruijn 0) y [x + y] [w - 1]))) 0 1 n))

; Iterative attempt at 43s
(defun fib4 (n) (#0 (
    iterateN n (lambda (x) (
        tie (#1 x) [(#0 x) + (#1 x)])) '(0 1))))

What is Malbolge? Why is it difficult?

Malbolge is a public domain esoteric programming language. It was specifically designed to be almost impossible to use, via a counter-intuitive 'crazy operation', trinary arithmetic, and self-modifying code. It builds on the difficulty of earlier, challenging esoteric languages like Brainfuck, but takes this aspect to the extreme. Despite this design, it is possible to write useful Malbolge programs (as this project proves).

What Malbolge instructions do depends on their position in the source code. After being ran, they are encrypted (so to make a loop, one has to decrypt it after each iteration - sounds hard already?). This is how so-called instruction cycles have been discovered - it has been observed that some instructions on certain locations form looping cycles, which is the basis of Malbolge programming.

The most complex programs made in Malbolge, to date, include an adder, a "99 bottles of beer" program, and a "Hello, world!" program (originally generated by a Lisp program utilizing a genetic algorithm).

MalbolgeLisp uses a special variant of Malbolge called Malbolge Unshackled. It's considerably harder to program for multiple reasons:

1. The rotation width is chosen randomly by the interpreter
2. Malbolge Unshackled lets the width of rotation be variable, which grows with the values in the D register, and since the initial rotation width is unknown, you have to probe it (because otherwise * returns unpredictable results)
3. Malbolge Unshackled's print instruction requires unicode codepoints
4. if the rotation width is unknown then you can't load values larger than 3^4-1, except values starting with a 1 trit
5. to overcome this you need a loop that probes the rotation width which is probably beyond most people's comprehension
6. the specification says that the value 0t21 should be used to print a newline, but this value is theoretically impossible to obtain without having read an end of line or end of file from I/O before.
7. Malbolge Unshackled is actually usable because it's (as this project proves) Turing complete. The default Malbolge rotation width (10) constraints the addressable memory enough to make something cool with it.

A few example Malbolge programs:

A "Hello World" program:

(=<`#9]~6ZY327Uv4-QsqpMn&+Ij"'E%e{Ab~w=_:]Kw%o44Uqp0/Q?xNvL:`H%c#DD2^WV>gY;dts76qKJImZkj

A cat program that doesn't terminate on EOF:

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

How to use

$ git clone https://github.com/kspalaiologos/malbolge-lisp
$ cd malbolge-lisp
$ unzip lisp.mb
$ clang -O3 -march=native fast20.c -o fast20
$ cat init_module.mb core.mb > lisp.mb
$ ./fast20 lisp.mb

malbolge-lisp's Issues

Not sure if the code is public domain

There's a CC-0 dedication in the file, but the interpreter itself outputs:

MalbolgeLisp. Copyleft (C) 2020 THE GREEK EMPRESS.
All wrongs reserved.

If it is indeed copyleft, which license is it under? If it's not, can this greeting be changed?

How

How u learn malbolge?? Very cool.

GPL v3 License violation

This is great work, no doubt.

However, it cannot be released under C0, because it contains the init_module string from LMFAO https://github.com/esoteric-programmer/LMFAO

Well, I may have tolerated that, but I'm a little disappointed that the C0 is more show than real since neither the source code nor the entire tool chain were released or named. Even in the write-up, the use of LMFAO is not named at all. If you don't want to put your into GPL v3 (including a release of your source codes), please contact me to discuss the usage of the init_module.