Writing a Befunge Interpreter

Why Befunge is a friendly first interpreter project

Most programming languages need a parser, a syntax tree and some kind of compiler or evaluator before anything runs. Befunge skips nearly all of that. Every instruction is a single character, there is no grammar to speak of, and the program is just a rectangle of text. A working Befunge interpreter can be written in an afternoon, which makes it a popular exercise.

This article describes the overall structure. It is not a full specification, and details such as grid size or how edge cases behave vary between implementations. Treat it as a map of the territory, then check the rules of the variant you want to support.

The four parts

Every interpreter for this family of languages has the same four moving parts:

• the grid (often called the playfield), which holds the program and doubles as data storage
• the instruction pointer, which has a position and a direction
• the stack of integers
• the main loop, which repeats one step until the program ends

Everything else is detail layered on top of these.

Loading the grid

First, read the source text and place each character in a two-dimensional array. Classic Befunge-93 is generally described as an 80 by 25 grid, and shorter lines are padded with spaces. Funge-98 style grids are conceptually unbounded, which changes how you store them. The tradeoffs of arrays versus sparse maps are covered in the discussion of the playfield data structure, and the practical details of reading files are covered under program loading.

For a fixed-size interpreter, the loading code is only a few lines. Any characters beyond the grid size are typically ignored, and missing cells are filled with spaces.

The instruction pointer

The pointer needs four numbers: an x position, a y position, and a direction expressed as a horizontal and vertical step. Moving right is a step of (1, 0), moving down is (0, 1), and so on. Starting at the top-left cell moving right is the usual convention.

After each instruction, the pointer advances by its step. When it runs off an edge, it wraps around to the opposite side. This is the behavior behind a toroidal playfield, and in code it is usually a modulo operation on each coordinate. Direction instructions simply replace the step values. How the pointer turns is explored further in the discussion of pointer direction.

The stack

The stack is a plain list of integers. Instructions push values, pop values, or both. One decision every implementer faces is what to do when an instruction needs a value and the stack is empty. In Befunge the traditional answer is that popping an empty stack yields zero, which is much more forgiving than raising an error. Other designs treat it as a fault. See the notes on stack underflow for why this choice matters when you compare outputs between interpreters.

Another early decision is integer size. Some implementations use the host language’s native integers, and others restrict values to a fixed width. Programs that depend on overflow behavior are rare, but they exist, and they are one reason the arithmetic edge cases deserve attention.

The main loop

The loop is short. Read the character under the pointer, act on it, move the pointer, repeat. A skeleton makes this concrete. The following Python sketch supports only a few instructions and is meant to show the shape, not to be complete:

import sys

def run(source, width=80, height=25):
    grid = [[" "] * width for _ in range(height)]
    for y, line in enumerate(source.split("\n")[:height]):
        for x, ch in enumerate(line[:width]):
            grid[y][x] = ch

    x, y = 0, 0
    dx, dy = 1, 0
    stack = []
    string_mode = False

    def pop():
        return stack.pop() if stack else 0

    while True:
        ch = grid[y][x]
        if string_mode:
            if ch == '"':
                string_mode = False
            else:
                stack.append(ord(ch))
        elif ch == "@":
            return
        elif ch == '"':
            string_mode = True
        elif ch.isdigit():
            stack.append(int(ch))
        elif ch == "+":
            b, a = pop(), pop()
            stack.append(a + b)
        elif ch == ".":
            sys.stdout.write(str(pop()) + " ")
        elif ch == ",":
            sys.stdout.write(chr(pop()))
        elif ch == ">":
            dx, dy = 1, 0
        elif ch == "<":
            dx, dy = -1, 0
        elif ch == "^":
            dx, dy = 0, -1
        elif ch == "v":
            dx, dy = 0, 1
        x = (x + dx) % width
        y = (y + dy) % height

Running this on the one-line program 55+.@ pushes two fives, adds them, prints 10 and stops. Spaces and unknown characters fall through every branch and do nothing, which matches the usual rule that a space is a no-op.

Notice that string mode is a flag checked first. While it is on, every character except the closing quote is pushed as its character code. That detail is easy to forget and it is the source of many confusing bugs; the techniques for string mode show how programs use it.

What to add next

Once the skeleton runs, grow it in small steps:

1. Add the remaining arithmetic and stack operations, being careful with division and modulo by zero.
2. Add the conditional instructions that choose a direction based on the top of the stack, which is where conditional branching begins to matter.
3. Add the get and put instructions, which read and write grid cells and make self-modifying code possible.
4. Add input and a random direction instruction.
5. Add a way to dump the state each step, so you can watch the program think.

That last item pays off quickly. An interpreter that can print the position, character and stack at every step is also the foundation of a trace visualizer, and it makes the fetch and execute cycle, often described as the execution loop, much easier to reason about.

Testing and trust

Interpreters are easy to get subtly wrong, and the errors are often invisible until a larger program misbehaves. Keep a folder of small programs with known output, run them after every change, and compare against another implementation when you can. Ideas for this are collected under interpreter testing. Start with tiny programs that exercise one instruction each, then move to the classics such as Hello World and a countdown.

Choosing a scope

Decide early which variant you are targeting. A Befunge-93 interpreter is small and well bounded. Supporting Funge-98 adds more directions, multiple pointers and a stack of stacks, which turns a weekend project into a longer one. Neither is wrong, but mixing them half-way tends to produce an interpreter that satisfies neither set of programs. Pick one, make it solid, and extend it only when you have tests that tell you nothing else broke.