Build your own Brainfuck interpreter

Set up

Choose your language and editor, and save the challenge's sample programs as files: the short Hello! program, the test script and the Mandelbrot program from the linked blog post. Before reading the page's answer, try writing a program that prints Hello! yourself.

Works whenThe three sample programs are saved and ready to run, and you can explain how the Hello! program builds each letter in its cells.

REPL and echo

Start an interactive prompt that reads what you type and prints it straight back. Then, when a file name is given, print that file's contents instead.

Works whenA line typed at the prompt comes back unchanged, and running the program on the Hello! file prints the file's text exactly.

Concepts: the read-eval-print loop

Interpreter

Run a program one command at a time on a tape of 30,000 cells set to zero, or a size you can choose. Ignore every character that isn't one of the eight commands, and make the program counter jump to the matching bracket when a loop is skipped or repeated.

Works whenThe Hello! program prints Hello!, the test script prints a readable message, and the Mandelbrot program draws a recognisable Mandelbrot set in text. Timed with its output thrown away, the Mandelbrot run takes tens of seconds at this stage, and that time is your baseline.

Concepts: the machine · fetch, decode, execute · matching brackets and precomputing jump targets · what the spec leaves open

Bytecode compiler

Compile the source into bytecode with one instruction for each command. Leave the comments out, and give every loop instruction the position of its partner, worked out at compile time.

Works whenThe bytecode for each sample program has no comments, one instruction per command, and loop instructions that point at each other, and the programs still behave exactly as before.

Concepts: compiling to bytecode · matching brackets and precomputing jump targets

Virtual machine

Run the bytecode in a virtual machine with its own program counter and data pointer. It reads each opcode and, for loops, its target, then updates the program counter or the current cell.

Works whenEvery earlier program gives the same output as with the step 2 interpreter, and the Mandelbrot program is timed again under the same conditions and compared with the baseline.

Concepts: virtual machines · fetch, decode, execute · measuring speed honestly

Collapse repeated commands

Make the compiler turn a run of the same command into one instruction with a count, such as a single instruction that adds ten in place of ten plus commands, and make the virtual machine carry it out.

Works whenThe Hello! program compiles to about a third as many instructions as it has commands (the page gets 26 from 70), its output is unchanged, and the Mandelbrot program runs much faster than the baseline.

Concepts: peephole optimisation · what the spec leaves open

Replace common patterns

Recognise the loop that subtracts one until its cell is zero, and that loop followed by a move right, and compile each into a single new instruction that the virtual machine supports.

Works whenEvery sample program still gives the same output, and timing shows a clear further speed-up over step 5.

Concepts: peephole optimisation · virtual machines

Going furtherOptional

Count how often each loop runs and turn the most common loop shapes into new instructions. Beyond that, replace the virtual machine with a just-in-time compiler, or emit assembly or a compiler back end's intermediate form instead of bytecode.

Works whenThe Mandelbrot program draws the same picture in a small fraction of the original time, with the page's target under 15 percent of it.

Concepts: measuring speed honestly · peephole optimisation · compiling to bytecode