Piet Malbolge

Standard-compliant Malbolge interpreter implemented in Piet, a stack-based 2D esoteric programming language.

Comment 1

Inspiration

Self-hosting language

A self-hosting language is a programming language that has a compiler/interpreter implemented in its own language (often through bootstrapping). Showing a language's ability to self-host can prove its sufficiency of features, and by ridding itself of external dependency on other languages, security, robustness, and resillience towards external outages will all be improved.

Yet, many languages, especially esoteric ones, do not possess a self-hosting compiler/interpreter. Specifically, we identified two such languages: Piet and Malbolge.

Piet

Piet is a 2-dimensional language where the instruction pointer traverses a planar codespace (consisting of instrucion pixels, or codels) whilst maintaining only a stack as its runtime memory. Inspired the Dutch abstract artist Piet Mondrian, it tries to prove the concept that artworks can be code as well.

However, due to the difficulty of maintaining arbitrary variable-sized arrays on only one stack (there are not even additional registers), no one has successfully implemented a self-hosting interpreter. Additionally, due to it being a simulation of an instruction's walk on a 2D plane, its speed of interpretation is very slow, making any valid interpreter to be also too slow to be useful. The quickest method to run Piet, currently, is by transpiling to C/C++ before running.

Malboge

Malbolge is another programming language, this time designed to be as hard to program in as possible. It runs on a ternary virtual machine with three pointer registers (including the instruction pointer), encrypts (modifies) its code after all instructions, and its instruction contains a minimal set of useless instructions (all non-I/O, non-halt instructions are non-trivial side-effects on the registers and the memory).

The first valid program was discovered 8-years after creation by brute-force. Although nowadays researchers have discovered weaknesses in its instruction set to do useful things in very convoluted ways, it is still too tedius to implement anything non-trivial, and hence it does not self-host. It is also unknown whether it can self-host, since its runtime memory is fixed-sized (and so is the program it will attempt to self-host), unlike Piet, which is known to be Turing-complete is its stack-size is not limited.

What it does

We provide an external implementation of Malbolge in Piet. That is, we created a working ternary virtual machine to execute Malbolge programs in the form of a piece of artwork.

The Piet program is implemented word-for-word according to the original Malbolge standard, except for the treatment of whitespaces: Malbolge ignores all whitespace characters in its source, whilst we forbid them, because we use SPACE () as a delimiter to separate Malbolge source and standard inputs (into Piet).

We have tested our program against all existing program sources that we could find (there aren't that many), and the results show that they all:

  • Run and halt correctly, or;
  • Run and give the the correct execution (and memory data) for a non-trivial length of time, but did not finish running due to our Piet interpreter being too inefficient, or;
  • We identified usages of undefined behaviour in the original source (such as inconsistent treatments of EOF), which render the original program standard non-compliant, and hence outside the scope of our project.

How we built it

Whilst nearly all Piet programs are implemented by linearly execution, tightly coupling the validity of regions of code with current stack states, we novelly introduce ideas of procedural programming into Piet, emphasising modularity and scoping.

Subroutines

We implemented a top-level subroutine dispatcher, which can transport the instruction pointer to different subroutines based on its call ID, and a secondary dispatcher within each subroutine that sends the instruction pointer to specific locations within the subroutine. This provides a way to "call" "functions" and return to where we left off based on a callee-return policy, and hence allowed us to abstract different core parts of the program into distinct sections of the artwork.

Modularisation provided at least the following benefits:

  • Decrease in artwork size due to decreased redundancy through abstractions;
  • Improved scalability, readability and robustness;
  • Support for data scoping, which means that we could make assumptions about the global stack structure independent of our location in code, improving robustness and ease of implementation.

Metaprogramming

We utilised different levels of metaprogramming throughout the this project:

  • Most of the branching to the top-level dispatcher and branching within subroutine-level were linked programatically using Perl, so we could focus on the logic (and jumps to be handled by label branching);
  • Two subroutines, which handled the encrytion of Malbolge memory before and after execution, were generated using Python. The encrytion itself in the original Malbolge specification was a substitution cipher using random permutations, so our only choice was to hard code the lookup table using stack instructions;
  • Numerical are represented as contiguous colour blocks with size equalling the constants, and many constants are quite large. We implemented a constant optimiser that decreased the size of constants by replacing then with equivalent arithmetic (such as 100 = (2 * 5) times iteself), greatly reducing out code size and efficiency (since constant read time is proportional to the area size).
  • Fixed strings, which are contiguous sequences of numerical constants (chars), are futher optimised programatically, by storing their ASCII differences instead, since we realise that the difference between characters codepoints are mostly less than the codepoints themselves. This also generated code segments that prints strings which we could inject into the artwork for debugging.

Challenges we ran into

We encountered several challenges programatically, many of which we have already described in previous sections. Besides the above, the following things have also wasted us a massive amount of time during developement:

  • Failing to figure out how to do random access into the stack. We eventually figured it out and wrote a subroutine for random access and assignment.
  • Inconsistencies in reference documents. It turns out that both Wikipedia and EsoLang's description of Malbolge is incorrect.
  • Debugging a picture is very hard.
  • Debugging a programming not designed for humans to write, on a picture, is even harder.
  • Efficiency issue in well-known interpreters for Piet. That specific interpreter's execution for instructions increased in the order of cubics (as measured manually using a stopwatch) as the stack size, which made Malbolge program loading unbearably long. Our first version ran for 1 hour before fully loading the Malbolge memory, and then immediately segfaulted.
  • We then switched to a transpiler that generated equivalent C/C++ code, but the transpiler had a bug that is not compiant with the Piet standard, so we had to fix it. We also implemented support for arbitrary sized stacks, which the transpiler did not originally support (but we needed, since Malbolge requires a very big memory).

Accomplishments that we're proud of

  • Finishing the project.
  • Finishing the project and getting enough sleep.
  • Contributions to the Piet community (if there even is one).
  • Mario pixel art.

What's next for Piet Malbolge

Applications

Piet, by design, allows for steganography, which is hiding code in files that doesn't look like code. Specifically, through our modularisation approach, we can very easily spread the code out to different parts of a big image, whilst still being relatively unoticeable (a key restriction is that Piet forbids codels of colours not in the instruction set, which makes most plausible images unappealling).

Further improvements

  • More static optimisations, especially during transpilation to C++.
  • Now that we understand how array management work in Piet stacks, we could implement a high(er) level C-like language that transpiles to valid Piet artworks.
  • We really wanted to add more pixel art to this project, but we all got tired of drawing pixels.

Built With

Share this project:

Updates