Back to index

A just-in-time compiler for Befunge

Ever since I encountered Befunge I liked how different it is from other programming languages - it's minimal, stack based, 2D and not exactly Turing complete. I've made a game inspired by Befunge (but that's ancient history by now) and now I've written a just-in-time compiler called Befunjit.

Writing an interpreter for Befunge is fairly straight forward. However, interpreters are slow and the next best thing in terms of speed would be a compiler. The problem is that Befunge was deliberately designed to be very hard, if not impossible to compile. As far as I can tell, compiling a Befunge program fully ahead-of-time is indeed impossible because of the p instruction. That doesn't mean that the idea of a compiler should be abandoned completely - we can still write a jit compiler.

The Befunge runtime is composed of the program counter, the stack and stack pointer and the playfield. An interpreter, for every step, reads an instruction at the program counter and then acts upon it. We can see some inefficiencies right away, as a large percentage of the instructions encountered are whitespace, which is a no-op. In fact, let's partition instructions into 2 sets depending on whether they involve the stack or not. The ^<v> and # instructions for instance only affect the program counter; they don't compute anything. Their only purpose is to aid in layouting the program on the playfield.

The " "instruction" doesn't affect the stack in any way either and it doesn't even affect the program counter. All it does is change the way the board is read as it's traversed by the PC. A series of spaces in a straight line don't need to be interpreted one at a time; they can be trivially compressed/encoded as a fast-forward instruction. Any twisted path formed of ^<v>, # or whitespace can be similarly compressed as a teleport instruction. In fact, any path which doesn't consist of instructions with several possible outcomes (_|?) can be optimized and compiled. In Befunjit these are called "static paths" and this is the principle that it is based upon.

The execution of a static path can be thought of as a "jump". After every such "jump" Befunjit checks its cache of compiled static paths, starting from the cell indicated by the PC:

As I mentioned earlier, the p instruction makes compilation challenging. When executed (from a compiled path), p alters the contents of the playfield and invalidates any paths that pass through the affected cell. All these paths are eventually recompiled if and when the PC gets to them. If the current executing path happens to be invalidated then it continues executing only if the affected cell comes before the current p instruction in the path. Otherwise, the compiled code ceases control back to the compiler immediately which in turn has to compile and execute the path starting from the current PC.

This visualizer shows what static paths remain cached after the execution of a program (hover the small arrows).

An eager runtime

The process described above works fine, but it is rather slow due to the high number of context switches. Any path is in fact a new function call. There is a way to get rid of function calls, by compiling the whole program as a single piece of code. This way the whole program is a single function that the JavaScript engine can chew on and optimize.

We can think of Befunjit's execution process described in the previous section as being lazy in that it compiles and executes paths as needed. Compiling the whole program in a great big chunk would therefore be considered a more eager approach. Indeed, Befunjit implements 2 runtimes, both a lazy one and an eager one - each optimized for different scenarios.

The eager runtime is based on the same idea of splitting up the program into static paths as the lazy runtime. The only difference is that the eager runtime collects all paths even if they might not be reached. In addition, the static paths get stitched together using while-loops and break statements. The p instruction is handled differently than in the case of the lazy runtime. Since the whole program is a single clump of code, any modification to a static path would result in a full recompilation. An improvement is to make the eager runtime check if any of the code paths affected by p are reachable from the current point. This ensures that p instructions which do not affect the reachable paths do not trigger a recompilation. Still, this runtime should not be the first choice if your program makes extensive use of the p instruction.