“The Pragmatic Programmer” book (if you haven’t read it, stop reading this article and do it now!) says that each year we should learn one new programming language.
Even though some may argue that it’s too much effort, we could all agree that it may be a good idea. Choosing a new language to learn is not that easy. We don’t want to dedicate our time to something that we may never use in practice, do we? But perhaps sometimes we should make an exception and learn something just for the fun of it? I’d like to present to you the Brainfuck language. It’s a language which you can learn in a couple of minutes, so there is no problem of investing too much of your time in vain. Also, I can promise that solving any problem with Brainfuck will stimulate your brain (all f*cks are just a bonus ;)). Let’s get started!According to Wikipedia:
Brainfuck is an esoteric programming language created in 1993 by Urban Müller. The language consists of only eight simple commands and an instruction pointer. While it is fully Turing-complete, it is not intended for practical use, but to challenge and amuse programmers.
Imagine an infinitely long ribbon (or tape) composed of cells, each one initialized to 0. There is also a movable data pointer which initially points to the first cell. There are as well two streams of bytes for input and output. Instructions are executed sequentially, one by one. The machine stops after executing the last one.
Command
What it does?
>
move data pointer to the next cell on the right
<
move data pointer to the next cell on the left
increment value of current cell
-
decrement value of current cell
.
output the byte of a currently pointed cell in ASCII code
,
read one byte from stdin and store its value at the current cell
[
if the current cell is 0 then jump to the matching ]
]
jump to the matching [
All characters other than ><+-.,[] are ignored.
Let’s look at a simple example:
,+.
It will be interpreted as follows:
As a result, one character will be read from input and there will be printed the next character from ASCII table.
Before we write some useful (?) programs in Brainfuck, we need an interpreter or a compiler. AFAIK, there is no official one, but it’s not a problem. There are dozens unofficial in the Internet. I can recommend these two:
“Hello World!” should be the first program that we write while learning a new language. However writing it in Brainfuck is a little bit harder than in other languages. We have to start with something easier… Let’s write a program that will print out a single letter “H” on the screen (so exciting :D):
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.
How does it work? It sets the value of current cell to 72 (performing 72 increments) and prints it to the screen using “.” (H has code 72 in ASCII). Now you know what we should do in order to print “Hello World!” on the screen, but before that, we will do small refactoring. Writing all those ’+’ requires too much typing and counting. We can make it shorter by using [ and ] for looping. To set value to 72 we can e. g. make a loop which increases value 7 times by 10. This way we get 70. Adding 2 will make it 72. It looks like this:
++++++++++ # set cell0 to 10
[ # loop until cell0 is 0
- # decrease cell0
> # move data pointer to the right (cell1)
+++++++ # increase cell1 by 7
< # move data pointer to the left (cell0)
]
# loop ends with cell1 set to 70 and data pointer on cell0
> # move data pointer to the right (cell1)
++ # increase by 2
. # print the result
I have included comments to make it clear how everything works. The same program without comments:
++++++++++[->+++++++<]>++.
Isn’t it beautifull? :-)
Going back back to our “Hello World!” program. We could set the value of the first cell to 72 (H) and print it, set the value of the 2nd cell to 101 (e) and print it, set the value of the 3rd cell to 108 and print it and so on. Here is the implementation of this algorithm:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++.>
As I’m not crazy enough to write it sign by sign, I cheated a bit and generated this program with Ruby:
puts "Hello World!".chars.map { |c| c.ord.times.map { "+" }.join + ".>" }.join("\n")`
Yeah, only 1120 bytes to print “Hello World!”… But we can do better! Instead of using new cell for each character, let’s use just one. To print letter “e” (101) we can reuse value in cell0 (72). We can make increase it by one 29 times (101 - 72). And the result is as follows:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
+++++++++++++++++++++++++++++.
+++++++.
.
+++.
-------------------------------------------------------------------------------.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++.
++++++++++++++++++++++++.
+++.
------.
--------.
-------------------------------------------------------------------.
I cheated yet again!:
puts "Hello World!".chars.inject(["", 0]) { |(code, prev), char| [code + "++-"[char.ord - prev <=> 0] * (char.ord - prev).abs + ".\n", char.ord] }[0]`)
We made major progress. 377 bytes instead of 1120 bytes. However there is still room for improvements. I will give you some ideas:
+ and -Here is the version from Wikipedia which uses these ideas:
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
It’s only 106 bytes and it prints new line at the end! Amazing.
Now we are ready to write something more challenging. Let’s write a program which will read a line from input and print it in reverse order. The first problem is to read characters and stop on the new line character. Remember, there is no break, if or other similar statements. We have to use [ and ]. Let’s start with a program that reads all characters from input and puts them in successive cells:
,[>,]
It starts with reading first character and will continue until last , operation returns 0. However, it will loop forever in implementation which returns something other than O for EOF (language doesn’t specify this behavior). So how can we stop on the new line character? Here is the trick:
+[++++++++++>,----------]
We start with cell0 set to 1 to make sure, that our loop is executed at least once. In a loop we increase the value of current cell by 10, move data pointer to the next cell, read one character and decrease its value by 10. This way if there is read a new line character (10 in ASCII), the program will stop in a next iteration, otherwise its value will be restored by adding 10.
After that step, our cells will look like this:
11 C1 C2 C3 0* 0 0
Cn is nth character from input, and * is current data pointer position. Now we have to start moving data pointer to the left, and print all cells until we reach value 11. Here is my take on the task:
+[++++++++++>,----------]<-----------[+++++++++++.<-----------]
I encourage you to analyze it on your own :-).
When I discovered Brainfuck, I thought that it should be treated as pure joke. But now I see it quite differently. Besides challenging your brain, it gives you a new perspective of looking for programming languages. It clearly shows why we program in languages of higher level and why it’s so important to use abstractions and name things properly etc. Brainfuck is also very good to start with if you want to write your own interpreter for it. It is very easy to create as there are only 8 simple commands and no complex parsing.
