Why this is a good first interpreter
Brainfuck has eight commands, a single array for memory and no syntax beyond matching brackets. That makes it one of the smallest languages worth implementing, and an interpreter fits in a page. The same structure of tape, program counter and dispatch loop shows up in far bigger projects, so what you learn here carries over to building interpreters of other kinds.
The plan has three parts: find matching brackets in advance, set up the tape and pointers, and run a loop that handles one command at a time.
Step one: match the brackets
When the interpreter reaches a [ whose current cell is zero, it must skip to the matching ]. When it reaches a ] whose cell is nonzero, it must jump back to the matching [. Scanning for the match each time is slow and fiddly, so it is better to compute all pairs once, before running. This uses a stack of positions: push the index at each [, and at each ] pop the index of its partner and record both directions.
If a ] arrives with an empty stack, or the stack is nonempty at the end, the brackets do not balance and the program is rejected before it runs. This is a nice, small appearance of the underflow problem in a different setting.
Step two: the tape and pointers
You need an array of cells, a data pointer, a program counter, and somewhere to collect output. Many implementations use 30,000 byte-sized cells, which is a long-standing convention rather than part of the language. Cell values wrap at 256 in the version below, which is the usual choice, though the dialect differences are worth knowing about.
The complete interpreter
def run(code, data=b""):
jump = {}
stack = []
for i, ch in enumerate(code):
if ch == "[":
stack.append(i)
elif ch == "]":
if not stack:
raise SyntaxError("unmatched ]")
j = stack.pop()
jump[i] = j
jump[j] = i
if stack:
raise SyntaxError("unmatched [")
tape = [0] * 30000
ptr = 0
pc = 0
pos = 0
out = []
while pc < len(code):
ch = code[pc]
if ch == ">":
ptr += 1
if ptr >= len(tape):
raise RuntimeError("pointer past end of tape")
elif ch == "<":
ptr -= 1
if ptr < 0:
raise RuntimeError("pointer before start of tape")
elif ch == "+":
tape[ptr] = (tape[ptr] + 1) % 256
elif ch == "-":
tape[ptr] = (tape[ptr] - 1) % 256
elif ch == ".":
out.append(tape[ptr])
elif ch == ",":
if pos < len(data):
tape[ptr] = data[pos]
pos += 1
else:
tape[ptr] = 0
elif ch == "[" and tape[ptr] == 0:
pc = jump[pc]
elif ch == "]" and tape[ptr] != 0:
pc = jump[pc]
pc += 1
return bytes(out)Calling run("++++++++[>++++++++<-]>+.") returns the single byte 65, which is the letter A.
How it works
The first loop builds the jump table. After that the interpreter ignores anything that is not a command, because none of the if branches match, so comments are free.
The main loop is a standard fetch and dispatch cycle. It reads the character at the program counter, performs the action and moves on. The two bracket cases set the counter to the matching bracket, and then the final increment moves to the instruction after it. Landing on the bracket itself and then stepping past it works because the jump goes to the partner, and the partner does not need to be tested again: jumping forward to ] and then moving on skips the loop, and jumping back to [ and moving on enters the loop body without retesting, which is correct because the cell is known to be nonzero.
Choices to make
- Bounds: The code raises an error when the pointer leaves the tape. Alternatives are wrapping or growing the tape.
- Cell width: The modulus of 256 gives byte cells. Remove the modulus for big integers.
- End of input: The code stores 0. Other interpreters store -1 or leave the cell alone.
- Output: The function returns bytes. A real tool would write each byte as it appears.
These are the same implementation choices that divide dialects.
Testing
A few small programs are enough to build confidence: the one above that prints A, an empty program, a program with nested loops such as the multiplication idiom, and programs with unbalanced brackets that must be rejected. Compare the output with a known-good interpreter if you have one. Good testing habits are covered in the topic on interpreter testing. For input, try a program that echoes one byte: ,. should print whatever it was given.
Speed
This version is slow because it repeats a single command a character at a time. A common improvement is to combine runs of identical commands, so +++++ becomes a single add of 5, and to recognize the clear-cell loop [-] and replace it with an assignment. Both are covered under interpreter performance. A further step is to translate the program into another language, which leads toward a compiler.
Where to go next
Once this works, add a debug mode that prints the tape after each step, or a limit on the number of steps so that runaway loops stop. The second addition is a small reminder of the halting problem: no interpreter can tell in general whether a program will ever finish, so a step limit is the practical answer.