Learning to Appreciate Brainf**k

Recognizing the brilliance of this joke programming language

Brainf**k overview

Brainfuck is a minimal programming language, and I truly mean “minimal”. It’s technically Turing complete, but nobody in their right mind would use it to build actual software. It’s more like a mathematical exercise, one that causes tons of frustration while being more brilliant that it first appears.

It was created in 1993 by Urban Müller, who wanted to create a language with the smallest possible compiler (partly because he was working with the ancient Amiga 2.0 operating system).

As a consequence, it’s possible to write an entire brainfuck compiler in just 170 bytes

Not megabytes.

Not kilobytes.

…just regular bytes.

/* The world's smallest Brainfuck interpreter in C, by Kang Seonghoon
 * http://j.mearie.org/post/1181041789/brainfuck-interpreter-in-2-lines-of-c */
s[99],*r=s,*d,c;main(a,b){char*v=1[d=b];for(;c=*v++%93;)for(b=c&2,b=c%7?a&&(c&17
?c&1?(*r+=b-1):(r+=b-1):syscall(4-!b,b,r,1),0):v;b&&c|a**r;v=d)main(!c,&a);d=v;}

source

And all brainfuck programs essentially do the same thing: provie a 30K 8-bit array to be modified with 8 different characters.

How does Brainf**k work?

A Brainf**k program starts with a 30,000 byte array. All values start out as 0 (8-bit integers), and then it provides a movable pointer with which you can use eight different commands:

  • Use < & > to move the pointer to the left or right one position, respectively
  • Use + & - to increment or decrement the value of the cell at the pointer by 1
  • Use . to print the value at the current pointer
  • Use , to accept an input and store it at the current pointer
  • Use brakcets [ & ] to create a while loop.

No variables, functions, or classes.

Brainf**k in action

Delete your operating system and install amigaOS (alternatively if you’re too impatient for that you can use any of the various online intrpreters like this one)

Create a file ending in .bf. Any characters not among the eight commands listed above will be ignored, so you can just use them as comments.

If you wanted to create a program to print out a message you would need to set
the array values to the corresponding numbers from the ASCII table

For example we can increment the first cell times
enter a loop with an opening bracket
and the loop will increment that cell 4 times
then move one cell to the right
then decrement 3 times
then move back to the left
and then close the loop
This will continue until the original cell goes back to 0 and then will exit
After this the program will move once cell to the right and decrememnt once
before printing the first character: B

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

and then we can continue onto the other characters

-[--->+<]>--. i
++++++. o
---. l
+++. o
--------. g
+[--->+<]>+. y
-[---->+<]>++. (space)
---[----->++<]>. r
+++. u
---------. l
-------. e
[--->+<]>----. s

And yes this entire block of both code and text will run in
a brainfuck interpreter
(as long as you do not use any of the above symbols as
actual punctuation in your comments)

Now I know what you’re thinking: “This seems like an intentionally difficult language just for the sake of bragging rights.”

You’re probably not wrong about that being one of the reasons this was built.

However, remember when I mentioned that this language is Turing complete? That doesn’t do this language justice. This vulgarly-named language is probably the closest thing out there to Alan Turing’s original vision of a Turing machine. The only real difference is that Brainfuck’s memory is limited to just 30,000 cells (instead of the infinite amount of memory that a Turing machine has). With this in mind, it’s more akin to a finite state machine than a Turing machine.

Still, beyond the slight differences between a true Turing machine and Brainfuck, we can use this language to get an intuitive grasp of the limitations of a Turing machine as mathematical model.

For example, good luck trying to model different kinds of computational complexity with a Turing machine. Modern stored-program computers are more akin to a DIFFERENT kind of abstract computer: The random access stored program (RASP). Like the Turing Machine, RASP stores programs in memory, but unlike the Turing Machine, RASP make use of indirect addressing. This allows the program to address any register in the register-sequence. This opens the door for computational optimizations only possible with these memory indices (that a Turing machine cannot access).

Another glaring issue is that Turing machines don’t handle concurrency very well. For example, there is a bound on the size of integer that can be computed by an always-halting nondetermisitic Turing machine starting on a blank tape. By constrast, there are always-halting concurrent systems with no inputs that can compute an intger of unbounded size. Given how well many modern computers can handle concurrency, it’s clear there are limits to the Universal Turing machine as a mathematical abstraction. As a biologist, I can tell you it would be foolish to try and model a system like the brain with a Turing machine model.

So if there’s a lesson to be taken from Brainfuck, it’s that perhaps we need to calm down about Turing machines.


Cited as:

@article{mcateer2013appbf,
    title = "Learning to Appreciate Brainf**k",
    author = "McAteer, Matthew",
    journal = "matthewmcateer.me",
    year = "2013",
    url = "https://matthewmcateer.me/blog/learning-to-appreciate-brainf/"
}

If you notice mistakes and errors in this post, don’t hesitate to contact me at [contact at matthewmcateer dot me] and I will be very happy to correct them right away! Alternatily, you can follow me on Twitter and reach out to me there.

See you in the next post 😄

I write about AI, Biotech, and a bunch of other topics. Subscribe to get new posts by email!


This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

At least this isn't a full-screen popup

That'd be more annoying. Anyways, subscribe to my newsletter to get new posts by email! I write about AI, Biotech, and a bunch of other topics.


This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.