Monday, May 14, 2012

Some brainfuck tutorial

So, to make up for my absence, I thought I'd start something I've been wanting to do for a while:  a brainfuck tutorial, just so that it's there on the interwebz for those who need it.

So, what is brainfuck?  It's a programming language; a very simple, hair-pulling language.  It currently holds the record (at 200 bytes or less) for the smallest compilers.  It's a textbook example of a Turing tarpit; that is, a Turing-complete (that is, it can do anything a computer can do) language that is still impractical.

If you want to get started with it, my recommendation for a compiler is the IDE Visual Brainfuck.  With that, let's begin the brain damage.

The language itself is straightforward enough:  there are eight operators, each taking zero arguments (<>+-,.[]).  That's it; all other characters are ignored by most compilers.  Now, imagine a literal Turing machine, represented by a strip of tape and a data pointer.  At the start of each program, memory is allocated for 30,000 bytes of type char, and a data pointer is set to point at the 0th one.

The < and > commands move the data pointer (in C, you can think of it as using pointer arithmetic such as ptr-- or ptr++ to increment or decrement the location of the pointer).  The + and - commands increment or decrement the byte currently at the pointer (think of it as dereferencing the pointer).  The , and . commands input and output the current byte as an ASCII char.  The [ and ] commands are used as while loops; basically, at the end of each loop, the program checks whether the current byte is zero.  If it is, it moves on; else it repeats the loop.

So, those are the commands, but I'm sure the reader will benefit from a more concrete example..  So, what can we do with these commands?  (Technically, anything that can be done on a Turing machine, but let's start simple.)  Remember the "Hello, world!" program from my first post:

This might look messy, but it's not bad once we decompose it.  First, notice that
there are no instances of the , command, because this program doesn't accept any
input.  Now, take a look at the ten + commands at the top.  This increments the
current byte (byte 0) by ten.  Then a while loop begins; since the current byte
isn't zero, it performs the loop.  It moves the pointer to the right (to byte 1),
and increments it by seven.  It then moves the pointer to the byte 2, and increments
it by ten.  It similarly increments bytes 3 and 4 by three and 1.  It then moves the
pointer back to byte 0 and decrements it.  So, at the end of the first loop, we have:

Byte 0:  9
Byte 1:  7
Byte 2:  10
Byte 3:  3
Byte 4:  1
Since the pointer is currently at byte 0, which is not equal to zero, the loop continues.
It should be easy for the reader to convince himself that the program does exactly the same
thing nine more times, until byte 0 reaches zero.  So, at that point, we have:
Byte 0:  0
Byte 1:  70
Byte 2:  100
Byte 3:  30
Byte 4:  10
From here, it gets much simpler.  The next four commands move the pointer to byte 1,
increment it by two, and print it out.  At this point, byte 1 contains the value 72.
Looking this value up in our handy-dandy ASCII tables, this corresponds to the
character 'H' as desired.  The other characters are printed out similarly by moving to
the byte closest in value to the desired one, and changing it to the desired value to
be printed.
As an exercise for the reader:  without looking up the correct answer in an ASCII table,
what are the other values of the bytes printed by this Hello, world! program?
P.S.  Note how incredibly compact this program is.  This is the main advantage to brainfuck,
but it's not enough of an advantage for it to be practical. 

No comments:

Post a Comment

Anything which is both a known logical fallacy and a personal insult will be mercilessly mocked all the way to fictional hell, and anything which is one or the other will be relentlessly rebuked. I am an unconditional proponent of free speech, and as such open debate is always welcome. This means that disemvowelling and temporary suspension will only be used when commenters have shown that they are nothing more than flamers. Commenters will only be banned completely when they post information that can actively harm another individual, such as docs. Anonymous comments are disallowed to weed out cowardly flamers who hide behind anonymity. If you play nice, this may change in the future :-)