The Discordant Opposition Journal Issue 10 - File 19
An elegant programming language: Brainfuck
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 fowl 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 of your 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 I haven't timed these possibilities or tested results.
Last program
Note: I wrote this brainfuck program rather quickly so it may not be the most efficient or shortest way to write it ... this is left as an exercise for the reader (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
- http://www.catseye.mb.ca/esoteric/bf/ the current brainfuck site
- http://freshmeat.net has various brainfuck compilers/interpreters
- http://www.muppetlabs.com/~breadbox/bf/ a great site about brainfuck
- http://home.wxs.nl/~faase009/Ha_bf_Turing.html brainfuck in relation to turing-completeness and URM.
- http://obiwan.uvi.edu/computing/turing/ture.htm paper on the turing machine
- http://www.ionet.net/~timtroyr/funhouse/beer/beer_a_c.html#brainfuck 99 bottles of beer on the wall in brainfuck
- http://cydathria.com/bf/brainfuck.html Guide on programming in brainfuck
Markus Kliegl <markus.kliegl@t-online.de>, December 2000
Comments