Brainfuck Explained

The model: a tape and a pointer

Brainfuck is a very small language built around a simple machine. Memory is a long row of cells, called the tape. Each cell holds a number, and every cell starts at zero. A data pointer sits on one cell at a time. A separate instruction pointer walks through the program text from left to right, executing one character per step.

Implementations differ in details such as how many cells the tape has, how large each cell value can be, and what happens when a value goes past its limit. A common convention is cells holding a single byte, with wraparound, but the language is loosely specified, so programs that depend on these choices may behave differently on different interpreters.

Any character that is not one of the eight commands is typically ignored, which means you can write plain-text notes in between the commands.

The eight commands

That is the full language. There are no variables with names, no functions and no numbers in the source; everything is built from these eight symbols.

How loops work

The brackets are the only control flow. Together they form a “while the current cell is not zero” loop. When execution reaches [ and the cell is zero, it skips the entire block. When it reaches ] and the cell is not zero, it goes back to the start of the block.

The key habit is that a loop usually decrements the cell it tests. Otherwise the cell never reaches zero and the program runs forever.

A traced example

This short program prints the capital letter A, whose character code is 65:

++++++++[>++++++++<-]>+.

Reading it in pieces:

1. ++++++++ sets cell 0 to 8.
2. [>++++++++<-] is a loop. Each pass moves to cell 1, adds 8, moves back to cell 0 and subtracts 1. The loop runs 8 times, so cell 1 ends at 8 times 8, which is 64. When the loop ends, cell 0 is zero.
3. > moves to cell 1.
4. + raises it from 64 to 65.
5. . outputs the character with code 65, which is A.

This multiply-with-a-loop trick is the basis of many Brainfuck programs, since typing 65 plus signs would be tedious. Reusable idioms like this one are often called common Brainfuck patterns.

Why it is hard to use

Brainfuck makes ordinary tasks laborious. To add two numbers you must write a loop that moves one value into another cell by cell. To print text you must build each character code by hand. You also have to track where the pointer is at all times, because nothing in the code tells you. The result is that programs are long, repetitive and difficult to read, which is part of the point.

Despite this, the language is considered Turing complete if you assume unlimited tape, which is why people use it to illustrate Turing completeness. Real interpreters have finite memory, a difference explained in the discussion of infinite memory versus real machines.

How it differs from a grid language

Brainfuck’s execution is linear. The instruction pointer only moves forward through the text, except when a bracket sends it back or past a loop. The data lives on a one-dimensional tape.

Befunge takes a different approach. Its program is laid out on a two-dimensional grid, and the instruction pointer can travel right, left, up or down, with instructions that change its direction. Data goes on a stack instead of a tape. A fuller comparison between these memory approaches is in the discussion of tape versus grid designs, but the short version is this: Brainfuck asks you to think about where the data pointer is, while Befunge asks you to think about where the program pointer is heading.

Trying it yourself

A Brainfuck interpreter is short enough that many people write one as a first project. Running a few tiny programs and tracing them by hand is one of the best ways to understand the model. Start with programs that only use +, > and ., then add a simple loop.