The Hungry Hacker's Explanation of Everything

Home » Code

An elegant programming language: Brainfuck

15 December 2000 No Comment

This article is a re-print from DoJ Issue #10.

This text is supposed to explain the brainfuck language and its elegance. I hope to wake your interest in esoteric programming languages, such as intercal, dis, malbolge and befunge.

I will continue to use the word ‘brainfuck‘ and not something like ‘brainf*ck’. If you are too sensitive to stand foul language, then please ignore this article, though I would find that extremely ridiculous.

What is brainfuck?

Brainfuck is a programming language with only 8 commands, each one symbol, that is Turing-complete. It was originally implemented and designed for Amiga OS 2.0 by Urban Mueller.

A brainfuck program has an array of 30000 elements (lets call it A for simplicity), all with an initial value of 0 and a pointer (we’ll call it P) pointing to the first element of A.

Commands

As previously mentioned, brainfuck only uses 8 commands. These are: ‘+’, ‘-‘, ‘>’, ‘<‘, ‘[‘, ‘]’, ‘.’, ‘,’. In case that was unreadable: +-><[].,

Let’s examine them more closely, what does each one of them do?

  • the ‘+’ command increments the element of A currently pointed at by P
  • the ‘-‘ command decrements the element of A currently pointed at by P
  • the ‘>’ command increments P
  • the ‘<‘ command decrements P
  • the ‘[‘ command starts a loop, which is looped until the element of A currently pointed at by P is 0.
  • the ‘]’ command ends the execution block of a previously started loop.
  • the ‘.’ command prints out the ascii character of the element of A currently pointed at by P.
  • the ‘,’ command reads a character and saves its ascii value to the element of A currently pointed at by P.

It may be easier to understand this in comparison to the C language.

Command | C-Equivalent --------+------------- + | a[p]++ - | a[p]-- > | p++ < | p-- [ | while(a[p]) { ] | } . | putchar(a[p]) , | a[p] = getchar()

Taking apart the ‘hello world’ program

Let’s take a look at the original brainfuck code of the ‘hello world’ program first:

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

We know that a ‘.’ will print out a character, so we can assume that >+++++++++[<++++++++>-]<. prints ‘H’. The ascii value of ‘H’ is 72, so how do we get 72 into a[p] without writing 72 ‘+’s? We run a loop. So, first we set P to 1 and then a[1] to 9. Now we go into a loop. In the body of the loop we decrement P and add 8 to a[0]. Then we increment P again and subtract one from a[1].

At the beginning we have a[0] = 0 and a[1] = 9. After going through the loop the first time, we have a[0] = 8 and a[1] = 8. After going through the loop the second time, we have a[0] = 16 and a[1] = 7. This continues 9 times, so what this results in, basically is a[0] = 9 * 8.

Let’s take a look at ‘[-]’ now. So, what does this do and how does it work?

Assuming a[p] = 5, what would ‘while(a[p]) a[p]–;’ do? It would loop until a[p] is 0 … that’s it. It’s a simple way to reset a[p].

To help you understand how this works, here’s the code in C:

/* Begin C code */ #include <stdio.h> long a[30000]; int p = 0; int main(void) { /* Print 'H' */ p++; /* > */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ while(a[p]) { /* [ */ p--; /* < */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ p++; /* > */ a[p]--; /* - */ } /* ] */ p--; /* < */ putchar(a[p]); /* . */ /* Print 'e' */ p++; /* > */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ while(a[p]) { /* [ */ p--; /* < */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ p++; /* > */ a[p]--; /* - */ } /* ] */ p--; /* < */ a[p]++; /* + */ putchar(a[p]); /* . */ /* Print 'l' */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ putchar(a[p]); /* . */ /* Print 'l' */ putchar(a[p]); /* . */ /* Print 'o' */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ putchar(a[p]); /* . */ /* Print ' ' */ while(a[p]) { /* [ */ a[p]--; /* - */ } /* ] */ p++; /* > */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ while(a[p]) { /* [ */ p--; /* < */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ p++; /* > */ a[p]--; /* - */ } /* ] */ p--; /* < */ putchar(a[p]); /* . */ /* Print 'W' */ p++; /* > */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ while(a[p]) { /* [ */ p--; /* < */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ p++; /* > */ a[p]--; /* - */ } /* ] */ p--; /* < */ putchar(a[p]); /* . */ /* Print 'o' */ p++; /* > */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ while(a[p]) { /* [ */ p--; /* < */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ p++; /* > */ a[p]--; /* - */ } /* ] */ p--; /* < */ putchar(a[p]); /* . */ /* Print 'r' */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ putchar(a[p]); /* . */ /* Print 'l' */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ putchar(a[p]); /* . */ /* Print 'd' */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ a[p]--; /* - */ putchar(a[p]); /* . */ /* Print '!' */ while(a[p]) { /* [ */ a[p]--; /* - */ } /* ] */ p++; /* > */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ while(a[p]) { /* [ */ p--; /* < */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ p++; /* > */ a[p]--; /* - */ } /* ] */ p--; /* < */ a[p]++; /* + */ putchar(a[p]); /* . */ /* Newline */ while(a[p]) { /* [ */ a[p]--; /* - */ } /* ] */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ a[p]++; /* + */ putchar(a[p]); /* . */ return 0; } /* End C code */

Notes on efficiency in brainfuck

If you’re aiming for efficiency, brainfuck is definitely not the programming language you’ll want to use. To make brainfuck code as efficient as possible, you should translate it to C using, for example, bfc, which optimizes the code. Then you should definitely compile the C code with optimization flags ofyour compiler, eg. -O2 for gcc. It will still probably be faster to just write int main(void) { printf(“Hello World!\n”); return 0; }though 🙂

Also, obviously it will be faster to just decrement a[p] by 3 instead of using [-] and then setting up the value again, just 3 less, when you for example just printed ‘m’ and now wish to print ‘j’.

Running through a loop less often will probably be faster, so instead of having’>++++++++[<++++>-]’ you should use ‘>++++[<++++++++>-]’, though I must admit Ihaven’t timed these possibilities or tested results.

Last program

Note: I wrote this brainfuck program rather quickly so it may not be the mostefficient or shortest way to write it … this is left as an exercise for thereader (as substitute for my laziness) :)Well, here it is:

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

What is so elegant about brainfuck?

Brainfuck just simply is the most elegant programming language around. It only has 8 commands, only 6 being necessary for it to be turing-complete. If you don’t find that makes it elegant … well, that’s your opinion then, I suppose. Many people enjoy writing their own interpreters and/or compilers/translaters to other programming languages for brainfuck. Brainfuck is just a lot of fun and it’s a lifetime experience coding programs in it 🙂

Also you can impress colleagues by the cryptic look of its code.

Well, that’s it for this article … hope you enjoyed it.

Resources

Markus Kliegl <markus.kliegl@t-online.de>, December 2000

Leave your response!

Add your comment below, or trackback from your own site. You can also subscribe to these comments via RSS.

Be nice. Keep it clean. Stay on topic. No spam.

You can use these tags:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

This is a Gravatar-enabled weblog. To get your own globally-recognized-avatar, please register at Gravatar. Note: By filling out this comment form or emailing us you are signifying that you have read and agree to the terms laid out on the Contact Us page.