Interpreting versus compiling
An interpreter reads the grid while the program runs. A compiler reads it once, ahead of time, and writes out a program in another language that does the same work. For a grid language the second approach is appealing for two reasons: the resulting program can run quickly in a host language such as C, and the exercise teaches you what the grid program really means once the geometry is stripped away.
It is also harder than it looks. A grid program is a graph drawn on a plane, and the compiler’s job is to recover that graph and write it out as ordinary statements.
Think in paths, not cells
At runtime the pointer visits cells one at a time, but most of those visits are boring: the pointer moves in a straight line through instructions that do not change direction. A run of such cells can be treated as a single block, a short stretch of straight code that always runs from start to end.
Blocks end where the pointer’s path can change:
- a direction-changing instruction such as an arrow
- a conditional that picks between two directions
- a random-direction instruction with several outcomes
- the stop instruction
- a point that other paths can enter from elsewhere
Each block starts with a label and ends with a jump to another label, a two-way branch or a halt. That is the same shape as the basic blocks used in conventional compilers.
State must be tracked per direction
A cell is not enough to name a place in the program. The same cell can be reached heading east and later heading north, and from there the pointer may behave differently. So the compiler’s key identifier is a pair: position plus direction.
The process looks like this:
- Start with the pointer at the top left heading east.
- Follow the path, emitting the code for each instruction, until a block ends.
- For each place the path may continue, record a new pair (position and direction) to explore.
- Skip any pair already compiled, and emit a jump to its label instead.
- Stop when no unexplored pairs remain.
Wrap-around is applied during this exploration, just like in an interpreter, which is why the toroidal playfield matters to a compiler too.
Code for the stack and instructions
Most instructions translate directly. Number pushes become pushes onto a stack in the target language, arithmetic pops two values and pushes a result, and output instructions call the target’s print function. The target program usually still needs an explicit stack, so a compiler to Python or C includes a small stack structure in its output. The edge cases discussed in arithmetic edge cases, such as division by zero and negative remainders, must be reproduced in the generated code, or the compiled program will behave differently from the interpreted one.
A tiny example of the idea in Python-like output might look like this for a block that pushes 2 and 3, adds them and prints the result:
def block_0():
stack.append(2)
stack.append(3)
b = pop(); a = pop()
stack.append(a + b)
print(pop(), end="")
return "halt"The block returns the name of the next block, and a small driver function calls blocks in a loop until it gets “halt”. In C you would use labeled statements and goto, or a loop around a switch.
String mode
String mode needs care because its meaning depends on the path. Between two quote characters, every cell is pushed as data instead of run as code. The compiler can track this while walking: when it enters string mode, it emits pushes until the closing quote. A path that enters string mode and comes back in a different state needs to be recorded as a different state, so the exploration key may grow to include this flag.
The hard part: programs that change themselves
Everything above assumes the grid does not change. If the program uses write instructions to alter cells, the compiler cannot simply follow the paths it sees at the start. Self-modifying code can create new instructions that did not exist at compile time, and a cell read might fetch an instruction that was stored earlier by the program.
Practical choices:
- Refuse to compile programs that contain write instructions, and say so.
- Compile only the parts that cannot be affected, and fall back to an interpreter for the rest.
- Include a small interpreter in the generated program and use the compiled form just as an optimization.
For a hobby project, the first choice is perfectly reasonable. Reads that treat the grid as data storage, not code, are easier: if you can prove that writes never land on cells that are executed, you can place those data cells in an ordinary array in the generated program.
Some questions about grid programs cannot be settled by analysis at all, in the same way that undecidable properties arise throughout the theory. A compiler therefore has to be conservative: when it cannot tell, it assumes the worst.
Random and concurrent features
A random-direction instruction becomes a call to the target language’s random number function followed by a multi-way branch. Features such as concurrent pointers are much more work, since the compiled form must interleave several flows, so most small compilers leave them out.
Is it worth it?
A compiler is more work than an interpreter, and the benefit is mostly speed. If speed is the aim, try the cheaper steps first, as outlined in the article on making an interpreter faster. Still, the project has a real learning value. It forces you to treat the program as a graph, find the real structure, and consider how one language can be expressed in another, a theme explored more generally in language translation. Test the compiler by comparing its output with the interpreter on the same set of small programs; any difference points to a bug in one of them.