Brainfuck tutorial

Learn how to create applications with Branifuck isoteric language

Brainfuck (also known as Brainf*ck or even BF, given its name nature) is an esoteric language, which goal is to "burn your brain" trying to undercover what a program does. However, after learning the concepts of the language, you will see that is actually easy to interpret a Brainfuck application. We will also create some stuff with it easily!

A first look

Before progressing on the tutorial, let's see a simple "Hello World" application:

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

At the end of this tutorial, we will see in details how this code works. However, first things first. You need to know some basics: ASCII table and memory pointers (or arrays, for the sake of simplicity). I recomend you to open two additional browser tabs while you check this tutorial:

Let's begin by testing the previous code on the interpreter and you will see the famous "Hello World" sentence:

Hello World!

How Brainfuck works?

In Brainfuck, as in other many languages, we have variables. These variables are in fact a single memory made of cells or positions. Given this, you can see that a variable is not represented by a name. Instead it is represented by its position. Each position will hold an integer number, which is the equivalent of a character in the ASCII table (know you are understanding why you need it 🙂 ).

Memory:   [ 65 0 89 72 ] 
Position:    ^

Check out this example. We have our memory with 4 positions: first one with value 65, second one with 0, and so on. You are allowed to stay in a single position at a time. By default, you always start in position 0. If it is easier to understand, we can compare it to an array. However, we can only change to the left or right position. All these positions are initialized by zero (0) and you can have an arbitrary number of cells.

Let's see how to alternate between positions and read/set values on this memory.

Brainfuck operators

Brainfuck only contains 8 operators, beloging to well-known characters. Every other character is considered a comment. You can also write your code with as many line breaks as you wish and organize it your way.

Operator C language equiv. Purpose
> ++p (incr. pointer) Changes to the next/right cell in memory
< −−p (decr. pointer) Changes to the previous/left cell in memory
+ ++(*p) Increments the current cell value by one unit
- −−(*p) Decrements the current cell value by one unit
. putchar(p) Outputs the ASCII character corresponding to the value on the current cell
, *p = getchar(p) Reads a character from an input source (eg. keyboard) a stores the corresponding integer in the current cell, according to ASCII table
[ while(*p) { Start of a while loop, using the current cell value as a test condition (true: value != 0; false: 0)
] } Delimits the body of a while loop

(Source: http://www.muppetlabs.com/~breadbox/bf/)

Basic manipulation

AS we have seen, the memory is composed of cells. These cells hold its state for the entire lifeloop of the application, meaning a change in on cell will be avaible further on the execution. The idea of a Brainfuck program is to store values on this memory to retrieve them later. Example time:

++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
+++++
.

Use Brainfuck Interpreter to test this code. Copy the above text to the "Code" box, hit the "Load" button to initialize the state machine and finally hit "Run" button. You should see the following output:

A

A bunch of characters to display a single one 🙂 . Let's see the start memory state for this application:

Memory:   [ 0 ] 
Position:   ^

If you take a look at ASCII table you will notice that "A" character (upper-case) corresponds to integer 65. If you recall the Operators table above, you may see that + (plus) operator means "increment the current cell value by one unit" (+1). On the code, we have 6 rows with 10 + (plus) operators followed by 5 more of these, giving a total of 65 + (plus) operators. So, as you may now expect, we have the value 65 in the first cell:

Memory:   [ 65 ] 
Position:    ^

We have our 65 value, which correponds to the "A" character. But the value is still in memory, so we need to display it on the screen. The last line contains a single . (dot) operator which is used to print the current cell value to the display. This little dot it what makes appear an "A" on the "Result" box.

Alternating between cells

Until now we have seen how to manage a single cell in the memory. But it is likely you will need more cells in your future applications. So let's take a look on how to use multiple positions:

++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++.
>
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
+++++++++.
<.

Run this application on the Brainfuck Interpreter. You should be presented with the following output:

LOL

The application is similar to the previous example (a bunch of + (plus) operators), however this time you may notice two new operators: > (greater) operator, which changes to the next cell, and the < (lesser) operator which does the oposite. This application now makes use of two cells. Making a similar analysis as in the previous example, we are putting the value 76 on the first cell with the first 8 lines of code, which corresponds to the "L" character (upper-case) as per ASCII table:

Memory:   [ 76 ] 
Position:    ^

Next, still on the 8th line, we print the "L" to the screen with . (dot) operator. On the 9th line, we find the > (greater) operator, which will move the current pointer to the next position. So now we have two cells in the memory:

Memory:   [ 76 0 ] 
Position:      ^

The goal now is to create the "O" character, which ASCII code is 79. Like the "L" character, we will store the value 79 on this second cell and display it. Like before, we call as many as + (plus) operators as we need to put the value on the cell and then display with the . (dot) opetator. The output so far:

LO

And the memory at the moment:

Memory:   [ 76 79 ] 
Position:       ^

We're just missing the last "L" character to get the "LOL" expression. We could use a bunch of 76 + (plus) operators like we did previously, however you may recall we already have this value in memory, specifically on the first position. So, we can simply using the < (lesser) operator ti change to the previous cell and display it with the . (dot) operator. This is done in the last code line. Our memory ends being like this:

Memory:   [ 76 79 ] 
Position:    ^

And our output will be:

LOL

Using loops

You may also noticed that Brainfuck has a repetition struture: the while loop. Let's take advantage of it to recude the code size and having those ugly bunch of + (plus) operators. I while loop, the body instructions are executed while the test operation is true. In Brainfuck we don't have booleans so we assume these facts:

  • True: current cell holds a value different from zero
  • False: current cell holds zero value

To use a loop, we will need to chose a cell which will act as test operation for our loop. Let's say we want our loop to repeat exactly 3 times: we start by putting the value 3 on some cell and we could use other cells for our repeating logic and decrement the 3 to have a 2, and so on until reaching 0, which will stop the loop execution.

Let's review the improved version that displays a single "A" character, this time using the while loop:

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

Output:

A

We saved a few operators already, but now you may be puzzled with the source. Let's break it down.

Our goal is still to put the value 65 in the first cell. The first line puts the value 6 which, will act as a test operation for our while loop. Then, the second line will start the loop body. Third line contains the operator to change to next cell, followed by 11 + (plus) operators. The fourth line goes back to the first cell and decrements its value. Next line tells it is the end of the loop body.

We start by putting the value 6 on the first cell. Then, when entering the loop body, we change to second cell and put value 10. And finally, we return to the first cell, which will now have the value 5. Now, the program will return to the third line, because the current cell value (5) holds a thruty value. So we repeat: go to second cell, increment by another 11 and return to the previous cell to decrement it by one. So now we have value 4 on first cell.

So, what's the point? This loop will repeat until first cell holds a falsy value (zero). We're using the second cell to accumulate the value 66 (6 × 11), which is close to 65. The following table summarizes how the loop iterations affected the memory:

Iteration First cell Second cell
Before loop 6 0
After 1st iteration 5 11
After 2nd iteration 4 22
After 3rd iteration 3 33
After 4th iteration 2 44
After 5th iteration 1 55
After 6th iteration (loop ends) 0 66

And that's how we optimize our code, syntatically speaking. With loops we build the value on a cell as close as we can. In this case, we could also had the exact 65 value by putting value 5 on first cell and incrementing 13 times on the second (5 × 13 = 65), avoiding to incrementing/decrementing the remaining, as we do on the last line.

The Hello World analysis

We now have enough knowledge to understand the very first program we've in this tutorial: the Hello World. Let's see it again, this time with proper formatting and comments to understand what't going on:

++++++++++
[
  >+++++++
  >++++++++++
  >+++
  <<<-
]
>++.                    # Output H
>+.                     # Output e
+++++++..               # Output l (twice)
+++.                    # Output o
>++.                    # Output a space
<<+++++++++++++++.      # Output W
>.                      # Output again the o
+++.                    # Output r
------.                 # Output l
--------.               # Output d
>+.                     # Output exclamation mark

By using multiple cells and doing approximations with the values we already have in memory, we can minimze our Brainfuck applications and make it more concise.

Receiving input

We've seen 7 of the 8 Brainfuck operators. We're just missing the , (comma) operator, responsible for reading values from a data source. This operator reads a character at a time and stores the equivalent integer according to the ASCII table in the current cell. Its behaviour is dependent on the compiler/interpreter you are using: the values can be read from a file, keyboard, command line arguments, or even a textbox on a webpage.

There is nothing much to say about this operator, so let's dig straight into a simple example:

,-.+.+.

This Brainfuck code starts by reading a character from the input and store in the first cell. Then, it decrements the value from the first cell, outputs its value, increments the value, outputs it, and do this again. The goal of the application is to display the previous, same and next character received as input (alphabetical order).

For example, if you run this program on the Brainfuck Interpreter and add a single character on the "Input" box (let's day, D), the program will give you the following output:

CDE

Time to practice

To enrich this tutorial, I added two easy exercises for you to solve and check if you're ready to create your own applications.

  1. Create an application that prints the whole alphabet from A to Z (upper-case), print a line break (\n) and print on the line below the numbers from 9 to 0 (hint: use loops; you can also decrement values on the loop condition)
    1. Create an application that accepts two characters as a argument, and store each one as cell values. Now print the distance between letters (eg: for input AC the result should be 2; for input DM the result should be 9) (hint: to simplify consider only letter with distance with maximum of 9 and assume the first is in lower position that the second)

The idea is for you to try solving these exercises with the help of this tutorial and some research. Although I believe you can do it after some research, I will leave here the exercise solutions if you are completely lost or want to compare with your own solution.

Extending the Brainfuck language

In the original Brainfuck model you could only expand cells to the right form the initial one and the memory was limited to 30000 bytes (30 KBytes). There are some alternative proposals which goal is to overcome these limitations.

Virtually infinite cells without expansion limit

The original memory model of Brainfuck consists of an array to store the values. This brings the previously mentioned disadvantages.

We can however suppress these limits by using some more memory. If we use doubly-linked lists we win two advantages:

  • The memory is expansible no matter the direction, that is, you can always go to the previous/next cell
  • There is no limit on how many cells we can use (virtually)

The down side of this solution: you need more memory to hold the values on your cells. For example, if we use the C language and a 32 bits machine, in order to create an arrat we need this amount of memory:

1 byte per cell (byte data type)
Array with 30000 cells => 30000 bytes, 30 KBytes

With the linked list solution, we use up to 9 times more memory to replicate the original implementation:

1 cell structure
-> Value (byte data type) = 1 byte
-> Pointer to previous cell = 4 bytes
-> Pointer to next cell = 4 bytes
Array with 30000 cells => 30000 * (1 + 4 + 4) = 270000 bytes = 270 KBytes

I created a small Brainfuck interpretor in C language that puts this idea into practice. You can check the code on Github: https://github.com/leplastic/brainfuck-interpreter

Notes and references

To conclude this Brainfuck tutorial, I suggest you to continue the research on the links below. You will find more example applications, more details on the interpreters work and how to create you own.