Programming in Brainfuck: Part 0 — Introduction

Wed 20 August 2014 by TWal

This post is part 0 of the "Brainfuck tutorial" series:

  1. Programming in Brainfuck: Part 0 — Introduction
  2. Programming in Brainfuck: Part 1 — Common patterns & conditions
  3. Programming in Brainfuck: Part 2 — Arrays
  4. Programming in Brainfuck: Part 3 — Using a preprocessor

I love brainfuck. I’m amazed by what we can do with only eight instructions. I learned almost everything I know on this language by myself because I didn’t find any tutorial that teach in-depth how to program in brainfuck.

I decided to change this and to make my own tutorial, this first part will teach you the basics of the language.

The eight instructions

Brainfuck is a minimalist and esoteric programming language containing exactly 8 instructions: < > , . + - [ ]. Every other character is a comment.

Hello World!” in brainfuck looks like this:

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

Amazing, isn’t it?

Let me explain what each instruction does.

In brainfuck, we have two “tapes”: the memory tape, and the program tape. You can view them as big arrays with cells. The memory tape holds a number in each cell, usually stored in a byte, so it can go from 0 to 255. Each cell is initialized with 0.

Add and subtract: + and -

The instructions + and - are used to change the number in a cell: + increments this number, - decrements this number.

Consider the following program:

++-+

It will execute like this:

0 0 0 0 0 0                 ++-+
^                           ^
1 0 0 0 0 0                 ++-+
^                            ^
2 0 0 0 0 0                 ++-+
^                             ^
1 0 0 0 0 0                 ++-+
^                              ^
2 0 0 0 0 0                 ++-+
^                               ^

Easy! However changing only one number isn’t very interesting, we need a way to change other cells.

Navigate in the cells: < and >

This is done using the < and > instructions: < goes to the cell to the left, > goes to the cell to the right.

Consider the following program:

++>+<-

It will execute like this:

0 0 0 0 0 0                 ++>+<-
^                           ^
1 0 0 0 0 0                 ++>+<-
^                            ^
2 0 0 0 0 0                 ++>+<-
^                             ^
2 0 0 0 0 0                 ++>+<-
  ^                            ^
2 1 0 0 0 0                 ++>+<-
  ^                             ^
2 1 0 0 0 0                 ++>+<-
^                                ^
1 1 0 0 0 0                 ++>+<-
^                                 ^

Loops: [ and ]

In brainfuck, loops are done with the [ and ] instructions. When executing a [, if the current cell is 0, it will jump to the corresponding ], otherwise it will go inside the loop. When executing a ], if the current cell is 0, it will go to the next instructions, otherwise, it will jump to the corresponding [. It can be seen as: “While the current cell is not 0, execute the code inside [ and ].

Consider the following program:

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

It will execute like this: (since you are now familiar with + - < >, I won’t execute them step by step)

0 0 0 0 0 0                 +++[>++<-]>+<[++[-<]-[>-]]
^                           ^
3 0 0 0 0 0                 +++[>++<-]>+<[++[-<]-[>-]]
^                              ^
The current cell is different from 0, we go inside the loop

2 2 0 0 0 0                 +++[>++<-]>+<[++[-<]-[>-]]
^                                    ^
The current cell is still different from 0, we go to the start of the loop

1 4 0 0 0 0                 +++[>++<-]>+<[++[-<]-[>-]]
^                                    ^
Again...

0 6 0 0 0 0                 +++[>++<-]>+<[++[-<]-[>-]]
^                                    ^
The current cell is 0, we can go outside

0 7 0 0 0 0                 +++[>++<-]>+<[++[-<]-[>-]]
^                                        ^
The current cell is 0, we do not enter in the loop

0 7 0 0 0 0                 +++[>++<-]>+<[++[-<]-[>-]]
^                                                     ^

Input and output: , and .

The last two instructions are , and .: , is used to read a character from the user, . is user to print a character to the user.

The character-encoding used is ASCII, you can find various ASCII tables on the internet. For example, if a cell contains the number 97 and the instruction executed is ., it will print “a”. If the instruction executed is , and the user type “a”, then the cell will contain the number 97.

What happens when we are executing , and there is no more input to read? This is interpreter-dependant. There are mostly 3 different behaviors: put 0 in the cell or put 255 in the cell or don’t change the value in the cell.

Let’s make a program that prints “abcabcabcabcabc”! The ASCII code for “a” is 97, the ASCII code for “b” is 98 and the ASCII code for “c” is 99. Using the instruction + - . we can do it easily:

++++++++++++++++++++ 20
++++++++++++++++++++ 40
++++++++++++++++++++ 60
++++++++++++++++++++ 80
+++++++++++++++++    97 this is the value for "a"
.+.+.--                 print "abc" and reset the cell to 97
.+.+.--                 again
.+.+.--                 again
.+.+.--                 again
.+.+.--                 done

Loops

The previous code is highly unoptimized, we can do better using loops.

In brainfuck, a common pattern is: “execute these instructions n times”.

For n = 5, it looks like this:

+++++       insert 5 in the current cell (the "counter cell")
[           start the loop
    ???     (insert instructions here that ends on the counter cell)
    -       decrease the counter by one
]
Here the counter's cell contains 0 and the instructions in the loop have been executed 5 times

We know that 97 = 12*8 + 1. By adding 12 to a cell 8 times, and then adding 1, we will have the number 97 in it.

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

It will execute like this:

0 0 0 0 0                 ++++++++[>++++++++++++<-]>+
^                         ^
8 0 0 0 0                 ++++++++[>++++++++++++<-]>+
^                                 ^
7 12 0 0 0                ++++++++[>++++++++++++<-]>+
^                                                 ^
6 24 0 0 0                ++++++++[>++++++++++++<-]>+
^                                                 ^
[...]

0 96 0 0 0                ++++++++[>++++++++++++<-]>+
^                                                 ^
0 97 0 0 0                ++++++++[>++++++++++++<-]>+
  ^                                                  ^

Our little program that prints “abcabcabcabcabc” can be shortened:

++++++++[>++++++++++++<-]>+     the current cell now contains "a"
.+.+.--                         print "abc" and reset the cell to 97
.+.+.--                         again
.+.+.--                         again
.+.+.--                         again
.+.+.--                         done

There is still a repetition we can remove using a loop:

++++++++[>++++++++++++<-]>+     the current cell now contains "a"
< +++++                         put 5 in the counter
[
    >.+.+.--                    print "abc" and reset the cell to 97
    <-                          go back to the counter and decrease it by one
]

Without the comments, it looks like this:

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

As you can see, that’s a lot shorter than our previous attempt.

You should now be able to see how the “Hello World!” program works. It is made of two parts:

setup some values using the multiplication trick
++++++++++[>+++++++>++++++++++>+++>+<<<<-]

print the message
>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

That’s all! You are now able to make simple programs that print messages, and know how to make simple loops.

In the next parts, we will see how to make conditions and how to use arrays: in short, how to make real programs using brainfuck.

Exercises

Practice makes perfect!

Here is an exercise you can do to sharpen your new skills: make a program that prints Brainfuck with a new line at the end (its ASCII code is 10).

Then, modify your code to print:

Brainfuck
Brainfuck
Brainfuck
Brainfuck
Brainfuck
Brainfuck
Brainfuck
Brainfuck
Brainfuck
Brainfuck

Use a loop!

The solutions of these exercises will be in the next part.