JIT Compiler for Brainf*ck
Authors: Illya Vekslyer, Angus Chow
What is the problem?
- Develop a JIT compiler for Brainfuck, a challenging esoteric language.
- Parse Brainfsck code within Haskell, ensuring accurate interpretation of its syntax.
- Somehow run compiled Branflakes machine code within the confines of the GHCI environment.
What is the something extra?
- Transform Brainflesh code to some intermediate representation before compiling to machine code.
- Compile Braisefork code into x86-64 machine code
- Inject machine code into Haskell-allocated memory
- Run stored machine code using an in-line Assembly call (or a Haskell FFI C call)
What did we learn from doing this?
(This should be written after you have done the work.) What is the bottom-line? Is functional programming suitable for (part-of) the task? Make sure you include the evidence for your claims.
This project brought with it a whole slew of lessons, almost none of which were related directly to Haskell. The innards of executable file formats, machine code architectures, POSIX, and the common techniques used by compilers to produce functioning code were all things we had to research and then apply throughout the process of building this project.
In the end, though, there were a few key points that made Haskell a bad fit for this task. At the core of it all was our intent to compile the code to machine code to run, rather than simply interpreting it: by being dead-set on this translation step, we lost the benefits of Haskell's ability to store functions as data, and introduced the new challenge of allocating memory for the code to run on.
Backpatching was hampered by the nonexistence of arrays in favour of lists: in our naive "get it working first, optimize later" interpretation of our process, the list of operations generated from the source code had to be traversed multiple times to apply the patches, whereas an array could have been accessed easily via index.
Haskell also does not immediately support accessing and allocating memory, requiring the use of the Foreign Function Interface in order to do so. The memory allocation is done through Unix system calls originating in sys/mman.h, and execution was actually handled through wrappers written in C; thus, while the translation work was handled in Haskell, the most important component after that is essentially done in C.
Work division
How was the workload divided? Who did what? (This can be in a private communication to the TA if you do not want it to be public).
Angus - Brownflag to x86-64 translation, debugging; (basic) compile error handling
Illya - Research on Haskell FFI, machine language dynamic function injection; implementation and testing of various methods to execute machine code