Brainfuck (from now on BF) turns 30 this year. This puts it in the same league as Python (32), Java (28) and Haskell (33). I remember the first time I had heard about BF. It was in my college dorm while talking to my roommate. I was pre-med at the time, and had only the faintest idea about programming. So when I first laid eyes on its syntax I hadn’t the faintest idea why someone would ever subject themselves to it. Now many years later I’m a programmer in my own right, and I find myself writing about a programming language I once balked at. Funny how life happens that way 😉.

A brief BF history 📖

BF is based off of the P double prime language, an impressive language in its own right, holding the title of “the first GOTO-less imperative structured programming language to be proven Turing-complete”. BF was invented by a Swiss physics student named Urban Müller in 1993. He uploaded it to Aminet

the worlds largest repository of Amiga related software and files, a website he had become the steward over a year earlier. In the readme Urban issued a cheeky challenge

Who can program anything useful with it? :)

The readme contained the description of the language. There were 8 pieces of syntax in the language + - > < [ ] . , The description for each symbol said

1. + Increment the value of the cell by 1

2. - Decrement the value of the cell by 1

3. > Move the pointer to the next cell to the right

4. < Move the pointer to the next cell to the left

5. . Output the ASCII character corresponding to the value of the current cell

6. , Input a character and store its ASCII value in the current cell

7. [ If the value of the cell is zero, jump to the corresponding ] character

8. ] if the value of the current cell is non-zero, jump back to the corresponding [

With how obtuse BF’s syntax is, it’s understandable to believe that it’s impossible to do anything in it. But while it is technically possible to do anything in it given infinite memory, it also falls under what Alan Perlis would describe as a Turing tarpit

.

Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.

But giving up before we’ve even started wouldn’t be any fun. So let’s see how we can actually use the language to write something!

How do I actually use this? 🤔

There are many different types of BF implementations but we will go with a simple one. You can imagine every BF program starting with an array containing a single element initialized to zero. The array is zero indexed. I’ve represented the starting state of a BF program below.

  *
[ 0 ] 

Also imagine the ‘*’ above the 0 as a pointer to the 0 value. This just tells the program at what index in the array the program is operating on. In fact let’s just call the pointer the index to make it easier. The array has a few rules

1. It can grow in size

2. The values inside the array can be increased to a maximum of 255. If a cell is already at 255, and is increased by one with ‘+’ it will overflow down to 0.

3. The value in a cell can be decreased to a minimum of 0. If a cell is at 0 and is decreased by one with ‘-’ it will underflow back up to 255.

In the below example we have an array with 3 values in it, and we are currently at index 1 (the value 100).

      *
[ 0  100 200] 

That means if a BF interpreter hits another ‘+’ the value at index one will be increased by one, which means the value 100 will go to 101. If instead the BF interpreter hits ‘>’ it will instead increment the index by one. Meaning that our asterisk ‘*’ will move over the 200. And if instead it hits ‘<‘ it will be pushed back over the 0.

That covers the ‘+’ ‘-’ ‘<‘ and ‘>’ but what about ‘[‘, ‘]’, ‘.’, and ‘,’? ‘,’ Allows the user to input a single character. That character is then converted to its ANSI representation and stored in the cell at the current index. Using our example from above if the next value ourinterpreter hits is a ‘,’ it will ask for a single character. If we give it the letter ‘A’ then the value 65 will be stored where the value of 100 used to be (since the index is at 1).

      *
[ 0   65  200] 

If the interpreter then hits a ‘.’ it will then print the character to the user. In this case the letter ‘A’ will be printed (the letter representation of 65). How do we know what values corresponds to what letters? We consult a chart! Since we are working within the bounds of the ASCII character set in this example, I’ll just show an ASCII chart to save space. The first 127 characters are the same in ASCII and ANSI.

If you look at the chart above you will see how we got 65 for ‘A’.

Now for ‘[‘, ‘]’,. These are how we do loops in BF. If instead of ‘A’ we wanted to print ‘%’ we could write this BF program.

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

Which would increment our value in the array to [25] before printing the value. That is a lot of ‘+’ for one character. If instead of ‘%’ I wanted ‘Z’ I’d have to type ‘+’ 90 times. That’s too much! Instead we can use a loop like the one below.

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

We already know what ‘+’ does, it increments the cell at the current index. In this case our array will look like this by the time we hit ‘[‘.

  *
[ 9 ] 

Since the value in the cell is 9 and not 0 ‘[‘ does nothing and we move to ‘>’. ‘>’ pushes us to index 1 of the array. Since there was nothing in the array at index 1 before we hit the ‘>’ we add a 0 at index 1 of the array. We then increment that 0 10 times with the ‘+’ inside of the loop. So we now have an array that looks like this…

      *
[ 9   10 ] 

‘<‘ pushes us back to index 0 which is 9 and ‘-’ subtracts 9 by 1 giving us 8 in the first slot of the array. Our array now looks like this

  *
[ 8   10 ] 

We then jump back to our ‘[‘ from our ‘]’. It does this because the value at the current index is 8 which is not zero, so it brings us back to the matching ‘[‘. We then loop again. We don’t do anything when we hit ‘[‘ because ‘[‘ checks if our cell at the current index is 0 and it is not. We then shift our index over to the cell with 10 because of the ‘>’ and increment the values up again by 10. At the end of the next iteration of the loop our cells look like this

 *
[7 20 ]

As you can probably see this loop will repeat itself dropping the value in the first cell from 7, to 6, 5, 4 all the way down to 0. Giving us this by the end.

 *
[0 90 ]

Once the first value in the array is 0, our ‘[‘ will jump to the matching ‘]’. ‘]’ checks and sees that our value is zero at the current index, and moves on to the next instruction. Our next instruction is ‘>’ which pushes our index over 90. Then we hit ‘.’ which prints the letter associated with the value of ‘90’ which is ‘Z’.

Now that you understand the basics of BrainFuck writing an interpreter should be simple. Here is a more complicated example to challenge you.

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

To see a working one in written in Pharo (a derivative of Smalltalk) you can go here.

Is this useful 🤨?

Surprisingly yes… While the syntax is obtuse the mechanics are pretty simple. This makes implementing a BF interpreter a great project for novice programmers. It’s one that I personally use when trying to learn a new programming language as it doesn’t require any external libraries, has simple logic that is easy to test using built in testing libraries, and doesn’t take too long to implement.

It’s also a great introduction to stack machines. And if you ever want to do some Assembly, will make understanding register allocations easier. Also if you want to get really fancy you can even implement BF optimizers. Notice how if you have a cell that is at 255 you can overflow down to 0. Or if you are at 0 you can underflow back up to 255. This could be leveraged to get at numbers on the extreme ends of the character set faster than looping, incrementing or decrementing.

BF has nerdsniped

many a programmer. And some have taken the language to its limits. From creating a BF interpreter that supports Linux syscalls

to solving the advent of code in BF

it continues to be a language that allows us to flex our creativity. In an age were there is increased pressure to spend time on things that are productive, or turn our hobbies into side hustles, programming does not escape that pressure. But I'm glad something like BF exists and that people still use it. Sometimes it's fun to create something silly and then do something equally absurd with it with no expectation that it will ever "be" anything. So Happy Birthday BF and here's to 30 more 🥂

Call To Action 📣

If you made it this far thanks for reading! I’m still new here and trying to find my voice. If you liked this article please consider liking and subscribing. And if you haven’t why not check out another article of mine!

Share

Share Deus In Machina

Links⚓