Brainfuck tutorial

Brainfuck (also known as Brainf*ck or even BF, given its polemic name) 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 understand a Brainfuck application. We will also create some stuff with it easily!

A first look

Before continuing with the tutorial, let’s see a simple “Hello World” application:

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

Later we will see in detail 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 recommend you to open two additional browser tabs while you check this tutorial:

• ASCII table reference: https://asciitable.com/ (or another website you like)
• To run the examples present in the tutorial and test code, you can use the Brainfuck Interpreter by Project Nayuki.

Let’s begin by testing the previous code on the Brainfuck interpreter and you will see the famous “Hello World” sentence:

Hello World!

How Brainfuck works?

Brainfuck, as other many languages, have variables. These variables are represented by 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 (and know you are understanding why you need it :) ).

Memory:   [ 65 2 89 72 ] 
Position:    ^

Check this example. We have our memory with 4 positions: first one with value 65, second one with 2, and so on. You are allowed to stay in a single position at a time. By default, a Brainfuck program starts at 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, belonging 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.

(Source: https://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 lifecycle of the application, meaning a change at a given cell will be stored and available further on the execution. The idea of a Brainfuck program is to store values on this memory to retrieve them later. Let’s now take a look at a new example:

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

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 corresponds to the “A” character in ASCII. 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 our “A” appear in the “Result” box.

Alternating between cells

Until now we have seen how to manage a single cell in the memory. But as you may expect, we will need more cells to create more aspiring 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 memory position to the next cell, and the < (lesser) operator which changes this position to the previous one.

This application now makes use of two cells. Making a similar analysis as we did at 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:    ^

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 memory pointer to the next position. So now we have two known 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) operator. 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 to go back to the previous position and display its contents 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

Writing + (plus) operators is boring. Fortunately Brainfuck has a repetition structure: the while loop. Let’s take advantage of it to reduce the code size. As on other languages, a while loop repeats its body instructions 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 position which will act as test operation for our loop. Let’s say we want the loop to repeat exactly 3 times: we start by putting the value 3 on the test position. Then we can use other positions for our repeating logic and when done, go back to the test position to decrement the 3, updating the position’s value to 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 we need to check how this works. Let’s break it down.

Our goal is still to put the value 65 in the first position. 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 (test position) 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 the logic of lines 2 and 3 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:

And that’s how we optimize our code, syntactically 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, outside the loop.

You may also notice that inside the loop we have to take care of the test position value (4th line on the example), otherwise we may run into an infinite loop.

The Hello World analysis

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

++++++++++              # acumulate 10 on test position
[
  >+++++++              # increment 7 on second position
  >++++++++++           # increment 10 on third position
  >+++                  # increment 3 on third position
  <<<-                  # decrement test position (loop control)
]                       

# memory after the loop: (0 70 100 30)

>++.                    # 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

So far 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 behavior 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 curent cell. Then, it decrements the value, outputs it, increments the value, outputs it again, and do this again. The goal of the application is to display the previous, actual 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)
2. 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 letters with distance with maximum of 9 and assume the first letter is always before (lexicographically) the second letter)

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 some suggested 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 whose 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 double-linked lists we get two advantages:

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

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

1 byte per cell (byte data type)
Array with 30000 cells => 30000 bytes, around 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, around 270 KBytes

I created a small Brainfuck interpretor in C language that puts this idea into practice. You can check the code on my Github.

Notes and references

Thank you for reaching until here, and I hope you found the tutorial useful. However, I suggest you to keep learning more about the language. Try continuing the research on the links below. You will find more example applications, more details on the interpreters work and how to create you own.

• Brainfuck Interpreter
• Javascript Brainfuck Interpreter / Debugger
• brainfuck – Wikipdia
• Brainfuck - Esolang
• The Brainfuck Programming Language
• More Brainfuck examples

If you happen to create an interesting application and want to share it with me, be my guest! I will be happy to take a look or test it during my free time.