Brainfuck Tutorial: Part 1

One of our previous blog posts introduced Brainfuck! Programs written in this minimalistic language can be highly unreadable! It can be fun though to put your intelligence to use to create something with these simple instructions. This article is the first part of a tutorial series showing you how this language works and how to write programs in this.

The whole language of Brainfuck comprises of just 8 characters, each with it’s own implicit meaning. Whitespaces are ignored, and can be freely used to improve readability (what’s that?!). In fact, any character apart from these 8 are just ignored! The 8 characters that make up a Brainfuck program are: + – < > . , [ ] .

Before a Brainfuck program can run, a buffer is created and filled with zeros, and a pointer is set up to point to the first byte of the buffer. The rest of the program then is all about either making changes to the pointer, or making changes to the content (byte) pointed by the pointer, or looping or I/O.

The first commands to learn are:

Armed with this information, we will write our first program to print “A” on the standard output. We use the fact that the ASCII code for “A” is 65, that the pointer is pointing to the first byte of the buffer, and the value of this byte is initially 0. We use the “+” command to increment this value to 65, and then use the “.” command to print the character.

Program #1: To print “A”

The program can be rewritten without comments as:

Let us now modify the program to print “ABCD”. After we print “A”, we need to increment the current byte and print it in order to get “B”, and repeat the procedure similarly to get “C” and “D”.

Program #2: To print “ABCD”

The program can be rewritten without comments as:

This was pretty long! We can make the program shorter if we know and use a few more commands:

65 can Mathematically be written in a variety of ways:
1.5*13
2. 13*5
3. 8*8+1
4. 10*7-5
5. 4*4*4+1

We will try out each of the above permutations:

Program #3: To print “A” using the fact that 65 = 5*13
We will load 5 into the cell 0 and add 13 to cell 1 as many times as the count in cell 0. Each time we add 13 to cell 1, we will go back to cell 0 and decrement it, repeating the process till the contents of cell 0 reaches 0, at which point the contents of cell 1 should have become 65.

The program as a continuous stream of characters is:

Isn’t this far shorter than the first version?

Program #4: To print “A” using the fact that 65 = 13*5
We will load 13 into the cell 0 and add 5 to cell 1 as many times as the count in cell 0. Each time we add 5 to cell 1, we will go back to cell 0 and decrement it, repeating the process till the contents of cell 0 reaches 0, at which point the contents of cell 1 should have become 65.

The program as a continuous stream of characters is:

Program #5: To print “A” using the fact that 65 = 8*8+1
We will load 8 into the cell 0 and add 8 to cell 1 as many times as the count in cell 0. Each time we add 8 to cell 1, we will go back to cell 0 and decrement it, repeating the process till the contents of cell 0 reaches 0, at which point the contents of cell 1 should have become 64. We finally add 1 to make to 65.

The program as a continuous stream of characters is:

Program #6: To print “A” using the fact that 65 = 10*7-5
We will load 10 into the cell 0 and add 7 to cell 1 as many times as the count in cell 0. Each time we add 7 to cell 1, we will go back to cell 0 and decrement it, repeating the process till the contents of cell 0 reaches 0, at which point the contents of cell 1 should have become 70. We finally subtract 5 to make it 65.

The program as a continuous stream of characters is:

++++++++++[>+++++++<-]>—–.

Program #7: To print “A” using the fact that 65 = 4*4*4+1
We will load 4 into the cell 0 and start a loop. We will load 4 into cell 1 and start another loop. We will add 4 to cell 2 in this innermost loop. After setting all loops correctly, we will get 64 in cell 2, to which we add 1 to get 65.

The program as a continuous stream of characters is:

We’ll now print 2 characters – “Hi” – using the same technique. The ASCII code for “H” is 72 and for “i” is 105.

Program #8: To print “Hi” using the fact that 72=10*7+2 and 105=10*10+5.
We will load 10 into the cell 0 and add 7 to cell 1 as many times as the count in cell 0. Each time we add 7 to cell 1, we will go back to cell 0 and decrement it, repeating the process till the contents of cell 0 reaches 0, at which point the contents of cell 1 should have become 70. We finally add 2 to make it 72 and print it.

We return to cell 0 (which has become 0). We will load 10 into the cell 0 and add 10 to cell 2 as many times as the count in cell 0. Each time we add 10 to cell 2, we will go back to cell 0 and decrement it, repeating the process till the contents of cell 0 reaches 0, at which point the contents of cell 2 should have become 100. We finally add 5 to make it 105 and print it.

The program as a continuous stream of characters is:

However, the program can be shortened by using the fact that both require an outer loop running 10 times!

Program #9: To print “Hi” using the fact that 72=10*7+2 and 105=10*10+5 using a common loop for multiplication with 10.
We will load 10 into the cell 0 and enter the loop. We add 7 to cell 1 as many times as the count in cell 0, go to cell 2 and add 10 to it the same number of times. Each time we add 7 to cell 1 and 10 to cell 2, we will go back to cell 0 and decrement it, repeating the process till the contents of cell 0 reaches 0, at which point the contents of cell 1 should have become 70 and cell 2 should have become 100. We finally add 2 to cell 1, make it 72 and print it, and add 5 to cell 2, make it 105 and print it.

The program as a continuous stream of characters is:

Now that we’ve got a hang of things, let’s see how to write a program to print “Hello World!”.

Program #10: To print “Hello World!”
We first analyze the ASCII codes:

In order to prevent generating all codes individually, we decide to generate a few “base” codes and “derive” the rest by small additions or subtractions. Thus, we can generate:
1. 32 for the space (32=8*4) and derive “!” from it
2. 72 for “H” and derive “W” from it by adding 15 (72=8*4*2+8)
3. 96 to derive all other lowercase alphabets from it (96=8*4*3)

This is how we plan to use the cells:
0: Will hold 8 for the outer loop count
1: Will hold 4 for the inner loop count
2: Will store 32 at the end by adding 1 in each iteration (8*4*1=32)
3: Will store 72 at the end by adding 2 in each iteration (8*4*2=64), and adding 1 in each outer iteration (+8)
4: Will store 96 at the end by adding 3 in each iteration (8*4*3=96)

And now, the entire program as a single string:

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