Why grid languages are a good first project
An interpreter is a program that reads another program and carries out its instructions directly. Writing one is a classic way to learn how languages actually work, and small esoteric languages make the job manageable. Their instruction sets are tiny, their rules fit on a page, and there is no parser to write in the usual sense: every character is already an instruction.
Befunge and its relatives are especially friendly because the whole language is a loop that reads one cell, does one thing and moves. This guide uses that family as the running example, but the stages apply to almost any small language. Each stage below can be built and checked before you start the next one, which keeps bugs from piling up.
Stage 1: Decide what you are implementing
Before writing code, pick a target and write down its rules. For a Befunge interpreter the common choices are the original Befunge-93 rules or the broader Funge-98 specification. The Befunge-93 limits are small and clear: a fixed-size playfield, a single stack and one instruction pointer. Funge-98 adds more features, so it is a larger project.
Starting with the smaller language is usually wise. Settle questions such as how large the grid is, what size of integer the stack holds, and what should happen on odd situations like an empty stack or a missing input character. Writing these answers in a short notes file saves arguments with yourself later.
Stage 2: Load the program into a grid
The program arrives as a text file, and the interpreter must turn it into a two-dimensional structure. That means splitting lines, padding short rows with spaces so every row has the same width, and deciding what to do with tabs, carriage returns and characters outside plain ASCII. This is a small stage but a surprisingly common source of off-by-one bugs, so it gets its own treatment in the article on loading a program file into a grid.
A related decision is how to store the cells. A simple array of arrays works for a fixed grid; maps and sparse storage suit grids that can grow. The trade-offs are covered in the discussion of the playfield data structure.
Stage 3: Model the machine state
The state of a running program is small. In a typical Befunge-style interpreter it consists of:
- the grid of cells
- the pointer position (x and y)
- the pointer direction (a pair of steps, one per axis)
- the program stack
- a flag for whether string mode is on
- the output so far, and a handle on input
Keep these together in one place, such as a class or a record. Having one object that holds all of the state makes later work much easier, especially trace output, tests and any attempt to run several pointers.
Stage 4: Write the core loop
The heart of the interpreter is a loop that reads the current cell, performs the matching action, and moves the pointer one step in its current direction. At the edge of the grid the pointer wraps around, which gives a toroidal playfield. Getting the wrap right, for both negative and positive movement, is worth testing on its own.
Start with only a few instructions: the four direction arrows, the stop instruction, and perhaps a way to print one character. Once a pointer can walk across a grid and halt, the skeleton is working. The details of this loop are the subject of the article on the fetch and execute loop.
Stage 5: Add instructions in groups
Add the rest of the instruction set in related groups rather than one at a time in random order:
- Number pushing and stack manipulation (duplicate, swap, discard).
- Arithmetic (add, subtract, multiply, divide, remainder).
- Comparison and branching (the horizontal and vertical conditionals).
- Output of numbers and characters.
- Input of numbers and characters.
- Reading and writing grid cells, which makes programs able to change themselves.
After each group, run a few tiny programs. Two groups deserve particular care. Arithmetic hides edge cases such as division by zero, negative remainders and overflow, which the article on arithmetic edge cases walks through. Stack operations raise the question of what to do on stack underflow, and the answer should be decided once and applied everywhere.
Stage 6: Handle input and output properly
Output is usually easy: collect characters or print them as they come. Input is trickier. You must decide whether to read a line at a time or a character at a time, what a number read looks like, and what the program sees when input runs out. These choices change how interactive programs feel, and they are discussed in the piece on input and output in an interpreter.
Stage 7: Build tools to see what is happening
Early on you will often wonder why a program did not do what you expected. A trace that prints each step, with the pointer position, the current cell and the stack, answers most such questions. Building a trace visualizer is less work than it sounds and pays for itself quickly. It also doubles as a learning aid, since it automates the same process as tracing by hand.
Stage 8: Test as you go
Write a ladder of very small programs, each isolating one instruction, and keep them in a folder with the expected output beside each one. Run the whole set after every change. Interpreter testing is mostly about catching regressions: it is easy to break wrap-around while fixing division. The details are in the article on testing an interpreter with small programs.
Stage 9: Only then, consider speed
A straightforward interpreter is usually fast enough for the programs people write for fun. If you do want speed, measure first. Precomputing jumps, caching decoded cells and avoiding repeated work in the inner loop are typical improvements, and they are covered under interpreter performance. A different route entirely is a grid compiler, which translates the program into another language. Both come after correctness.
Common traps across all stages
- Mixing up the row and column order when indexing the grid.
- Forgetting that a program can change its own cells, so any cached decoding must be invalidated.
- Assuming a behavior is standard when the language definition says something different.
- Writing a long program as the first test. Small programs fail in small, readable ways.
A finished interpreter is rarely a single heroic effort. It is usually a dozen small steps, each one checked, with notes about the choices that were made along the way.