Brainfuck
This document may be distributed freely if unchanged.If anything in this tutorial is incorrect then let me know.
Contents
- Prologue
- The operators
- Data, pointers & bytes
- Legend of notations
- Brainfuck interpreter
- Your first steps
- '[' and ']'
- Dividing
- Moving & copying
- If then
- Logical ports
- Signatures
- Just something extra
- Epilogue
Prologue
Brainfuck is a so-called esoteric programming language, meaning it's "intentionally unusual" (Chris Pressey). Brainfuck was invented by Urban Müller, whose goal was to create the smallest possible compiler. The second version of this compiler was 240 bytes in size (compiled ASM)! Urban Müller also wrote an interpreter in C:
char m[9999],*n[99],*r=m,*p=m+5000,**s=n,d,c;main(){for(read(0,r,4000);c=*r;
r++)c-']'||(d>1||(r=*p?*s:(--s,r)),!d||d--),c-'['||d++||(*++s=r),d||(*p+=c==
'+',*p-=c=='-',p+=c=='>',p-=c=='<',c-'.'||write(2,p,1),c-','||read(2,p,1));}
A few years later, an even smaller compiler was made by Raiter, but this time
in binary form. It was 171 bytes in size and ran under Linux. There was a
compiler for DOS as well, which was 136 bytes in size!While brainfuck is a very restrictive language (only 8 operators can be used, no variable names, etc.), it's still Turing Complete, i.e. any computational task can be performed.
The operators
Brainfuck only has 8 operators that are all written as a single character, but despite its restrictiveness, any program that can be written in pure C can be written in brainfuck too.The 8 operators are: +-<>[].,
- + increase byte under pointer
- - decrease byte under pointer
- > increase pointer
- < decrease pointer
- [ start a loop if byte under pointer is not 0
- ] return to matching [
- . print byte under pointer to standard output (often screen)
- , read input from standard input (often keyboard) to byte under pointer
Data, pointers & bytes
To store and read data, an array of 30,000 bytes is used. This array is like an array of cells, where each cell represents a byte:
[0] [3] [1] [24] [123] [2] [1] [5] [3] [8]
^
Above are the first 10 bytes, the pointer points to byte 2.
Initially, all bytes are set to 0 and the pointer points to the first byte:
[0] [0] [0] [0] [0] [0] [0] [0] [0] [0] ^From now on, I'll refer to bytes as pn (pointer-n) and to its value as vn (value-n). So when I write p2v5 I mean that the pointer points to byte 2 and that byte 2 has a value of 5:
[ ] [5] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
^
The values of the other bytes are not displayed, because they aren't known,
I only mentioned p2v5, so other values are unknown.
For further notations, see LEGEND OF NOTATIONS (below).
Since the array consists of bytes, the maximum value a pointer can have is
255. If p1v255 is increased by 1 it'll become p1v0. Likewise, if p1v0 is
decreased by 1 it'll become p1v255.
Legend of notations
| p3 | pointer 3, value unknown |
| v25 | last mentioned pointer has value 25 |
| p2v5 | pointer 2 has a value of 5 |
| p1v/3 | pointer 1's value is increased by 3 |
| p5v\2 | pointer 5's value is decreased by 2 |
| p8v!0 | pointer 8 has a non-zero value |
| p6v!13 | pointer 6 has a value that is not 13 |
Instead of + and -, / and \ are used, since +'s and -'s shouldn't be used in comments (the interpreter will not ignore them!) This notation is useful when a byte's value is unknown, but its value is changed anyway.
Mnemonic: / leads upwards=increasing and \ leads downwards=decreasing.
N.B.: pointer = byte = position in array
Brainfuck interpreter
Before you start programming, you should make sure you have a brainfuck Interpreter. A brainfuck Interpreter executes your code and takes care of input and output. My interpreter can be downloaded from the previous page, or you can write your own!N.B.: brainfuck source code can contain non-brainfuck characters like ;(*:=1!@#$ since the interpreter will just ignore them. Therefore, my examples can be copied to the interpreter with comments. However, some people have added their own operators to the original brainfuck language, like # (statusdump IIRC). My interpreter will ignore these characters, but some other interpreters might not!
Your first steps
Let's start with the following program ("Hello World" will come later):
, ;reads character from standard input to byte
under pointer
. ;print byte under pointer to screen
Now let's start manipulating the input:
, ;read character + ;increase byte . ;print byteSo, if input was 'e', then the output will be 'f'. Next, let's change a lowercase letter to an uppercase letter:
, ;read character ---------------- ---------------- ;decrease byte by 32 . ;print byteThe ASCII value of a lowercase letter is always 32 higher than its matching uppercase letter, so to print an uppercase letter, the value read from input has to be decreased by 32. Next two letters are read, one is stored in p1 and the other in p2:
, ;read character and store it in p1 > ;move pointer to p2 (second byte) , ;read character and store it in p2 < ;move pointer back to p1 (first byte) . ;print p1 (first byte) > ;move pointer to p2 . ;print p2 (second byte)
'[' and ']'
Now that you know how to work with +-<>,. Let's switch over to '[' and ']'. '[' and ']' basically act as a loop, while the byte under pointer has a non-zero value the loop gets executed.
++++ ;p1v4
[ ;execute loop if p1 has non-zero value
- ;decrease p1; p1v3 p1v2 p1v1 and p1v0
] ;look for matching counterpart
;p1v0
With these brackets a multiplication can be performed:
++++ ;p1v4 [ ;enter loop > ;p2 +++ ;p2v/3 < ;p1 - ;p1v\1 ] ;end loop > ;p2v12First, p1v4. When the loop is entered, p2v/3, and p1v\1. This pattern is repeated until p1v0, so the loop is gone through four times. p2 is increased by 3 4 times, so eventually p2v12. Voilà, you've multiplied 4 and 3.
And finally, the moment you've all been waiting for, "Hello World!" This one requires a little introduction though. In brainfuck, output is given as text, and not as a number (value):
+++++++++++ ;p1v11 [>++++++++++<-]>+. ;p1v111; display 'o'p2v111, and since 'o' has value 111, 'o' is displayed. Likewise, any other letter can be displayed. An ASCII chart can be found here:
http://www.jelks.nu/XML/ASCIIchart.html
Hello World!
++++++++[>+++++++++<-]>.;p1v0 p2v72 72=H <+++++[>++++++<-]>-. ;p1v0 p2v101 101=e +++++++.. ;p2v108 108=l +++. ;p2v111 111=o <++++++++[>>++++<<-]>>. ;p1v0 p3v32 32=<space> <<++++[>------<-]>. ;p2v87 87=W <++++[>++++++<-]>. ;p2v111 111=o +++. ;p2v114 114=r ------. ;p2v108 108=l --------. ;p2v100 100=d >+. ;p3v33 33=!I hope you now understand why "Hello World" shouldn't be your first brainfuck program, it's way too difficult.
Dividing
You already know how to add, subtract and multiply, so dividing remains. The following program divides 15 by 3:+++++++++++++++ ;p1v15 [ ;loop >+<--- ;p2v/1 p1v\3 ] ;end of loopDuring every loop 3 gets subtracted from 15, and eventually p1v0. The answer (15/3=5) is stored in p2.
There is however one problem regarding division: the result must be an integer, i.e. not a fraction. Here is why: if you would try to divide 15 by 6, then during every loop 6 would be subtracted from 15, resulting in 15, 9, 3, -3=253! The result will never be 0, so the program will get stuck in an infinite loop. Notice that this is not a limitation of brainfuck as a language, but of this particular method in general.
Update 2012-05-24: Paweł Łakomski pointed me to a solution that does not require the remainder to be 0:
,>,>++++++[-<--------<-------->>] <<[ >[->+>+<<] >[-<<- [>]>>>[<[>>>-<<<[-]]>>]<<] >>>+ <<[-<<+>>] <<<] >[-]>>>>[-<<<<<+>>>>>] <<<<++++++[-<++++++++>]<.
Moving & copying
Use the following program to move data from one cell to another:[ ;loop >+<- ;p2v/1 p1v\1 ]Say, p1v5. The loop will be executed five times, p2v5, and p1v0. You can also use this construction to multiply a byte with a fixed amount:
[ ;loop >+++<- ;p2v/3 p1v\1 ]Say, p1v5. The loop will be executed five times, and p2v15. But if you want p1 to be multiplied to itself, you'll have to move p2 to p1 afterwards.
N.B.: Make sure that p2v0 so that p2 will indeed get the value you want it to get. If p2 already has a non-zero value then something like this might happen:
>+++< ;p2v3 p1 +++++ ;p1v5 [ >+++<- ;p2v/3 p1v\1 ]Instead of p2v15, p2v18 will apply, which is not 3 * 5. To prevent this, you should empty the byte first:
> ;p2 [ ;loop - ;execute loop until byte is empty ] ;exit loopOr, in short, [-]
Copying is almost like moving, but to copy p1 to p2, an extra byte is needed as workspace. First, p1 is moved to p3, where p3 is the workspace:
[>>+<<-] ;move p1 to p3Now p3 is moved to p2 and p1:
>> ;p3 [ <+ ;p2v/1 <+ ;p1v/1 >> ;p3 - ;p3v\1 ]Voilà, p1 is copied to p2, and p3 is emptied.
N.B.: always make sure that at the beginning of a loop the pointer points to the same byte as at the end, because after reaching ']' the interpreter will return to the matching '[', and the loop might be executed again. The pointer should then point to the same byte as at the start of the previous loop. (Notice that this is a beginner's rule of thumb, when you're an advanced brainfuck-programmer, you might want to ignore this rule (and you should too ;).)
Next is a program that reads two numbers from keyboard and multiplies them:
>, ;input p2 >++++++[<-------->-] ;p2v\48 input 0 has value 48 , ;input p3 >++++++[<-------->-] ;p3v\48 input 5 has value 53 << ;p2 [ ;loop >[>>+<<-]>>[<+<+>>-]< ;copy p3 to p4 [<<<+>>>-]<< ;move p4 to p1 - ;p2v\1 ] < ;p1
If then
A programming language is nothing without IF-THEN-constructions. Luckily, IF-THEN-constructions can be made in brainfuck, using [ and ]. A [ ]-loop is only entered _IF_ the value under pointer has a non-zero value:[ ;enter loop if p1 has non-zero value >++++++++ ;p2v8 [>+++++++++<-] ;p3v72 >. ;display p3 << ;p1 [-] ;p1v0 so that the loop only gets executed once ]Say, p1v3, the loop is entered and 'H' (value 48h=72d) is displayed. But if p1v0, the loop will not be entered and nothing is displayed, so only IF p1 has a non-zero value the loop gets executed.
N.B.: p1v0 after the loop, so if you want to use the value again, you should have backed it up (by copying) in another byte.
It's nice to be able to display something if a byte is not 0, but it would be even nicer to display something if a byte has a certain value, including 0! To do this, first, the value of the byte has to be reduced by number you want to compare it with. Let's test p1 to see if its value is 64:
, ;read input ---------------- ---------------- ;p1v\64 ---------------- ----------------If p1 was v64, then now p1v0. If you program a loop that displays something right now, it would only be entered if p1v!0, but you want the exact opposite. Therefore, a so-called NOT-port can be used, and p2 is a temporary byte. Change p2 to p2v1:
>[-]+< ;p2v1 p1Next you program a loop that does nothing more than empty p2, but only if p1v!0:
[ ;enter loop if p1v!0 > ;p2 [-] ;p2v0 < ;p1 [-] ;p1v0 so you can exit the loop ]The above loop is the NOT-port: if p1v0 then p2v1 and if p1v!0 then p2v0. As you can see, p2v1 if p1 was v64, but p2v0 if p1 was v!64. Next, the part that displays something:
> ;p2 [ ;enter loop if p2v!0 and p1 was v64 >++++++++ ;p3v8 [>++++++++<-] ;p4v64 >. ;display '@' << ;p2 [-] ;p2v0 so you can exit the loop ]The '@' is only displayed if p1 was v64, so you've just programmed your first real IF-construction! The program as a whole:
, ;read input ---------------- ---------------- ;p1v\64 you can change this value to anything ---------------- you want; 64 is the value you compare ---------------- p1 with >[-]+< ;p2v1 p1 [ ;enter loop if p1v!0 > ;p2 [-] ;p2v0 < ;p1 [-] ;p1v0 so you can exit the loop ] > ;p2 [ ;enter loop if p1 was v64 >++++++++ ;p3v8 [>++++++++<-] ;p4v64 >. ;display '@' << ;p2 [-] ;p2v0 so the loop gets executed only once ]Now it's also really easy to check whether a byte has a value other than e.g. 64:
, ;read input ---------------- ---------------- ;p1v\64 ---------------- ---------------- [ ;enter loop if p1 was v!64 >++++++++ ;p2v8 [>++++++++<-] ;p3v64 >. ;display '@' << ;p1 [-] ;p1v0 so you can exit the loop ]Besides IF-THEN-constructions, it is also possible to create IF-THEN-ELSE- constructions:
, ;read input ---------------- ---------------- ;p1v\64 ---------------- ---------------- >>>+<<< ;p4v1 since p1 through p3 are used [ ;enter loop if p1 was v!64 \ >+++++++++++++ ;p2v13 | [>++++++<-] ;p3v78 | >. ;display 'N' | ELSE part >- ;p4v0 | <<< ;p1 | [-] ;p1v0 so you can exit the loop / ] >>> ;p4 [ ;enter loop if p4v1 and p1 was v64 \ << ;p2 | ++++++++ ;p2v8 | [>++++++++<-] ;p3v64 | IF part >. ;display '@' | > ;p4 | [-] ;p4v0 so you can exit the loop / ]If the input was an '@' (value 40h=64d), an '@' will be displayed, otherwise a 'N' (Not) will be displayed.
Logical ports
Although there are twelve (some might argue twenty, whatever logical ports), only AND, OR, XOR and NOT will be discussed here.For those unfamiliar with logical ports, here's a short introduction: A logical port is an information manipulator. AND, OR and XOR ports receive two inputs, while a NOT port receives only one input. The output of a logical port is either 0 or 1, depending on the value(s) of the input(s). 0 is called 'false', and !0 (non-zero) is called 'true'.
- An AND port will only give 1 as output if both input1 AND input2 are true, i.e. have non-zero values, the output will be 0 in all other cases, e.g. input1 = true (!0) and input2 = false (0).
- An OR port will give 1 as output if input1 OR input2 OR both are true, the only case in which the output is 0 is when both inputs are 0. This port is called an Inclusive OR, or just OR.
- A XOR port will give 1 as output if input1 or input2 is true, but not if both are true. The output will be 0 if both inputs are true or both inputs are non-true. This port is called an eXclusive OR, or XOR.
- A NOT port will give 1 as output if input1 is false, and 0 as output if input1 is true.
AND: OR: XOR: NOT: IN1 0 0 1 1 IN1 0 0 1 1 IN1 0 0 1 1 IN1 0 1 IN2 0 1 0 1 IN2 0 1 0 1 IN2 0 1 0 1 -------- ------------ ------------ ------------ OUT 1 0 OUT 0 0 0 1 OUT 0 1 1 1 OUT 0 1 1 0Anyway, back to brainfuck...
AND:
Output is 1 if both inputs are true. p1 is output, p2 and p3 are inputs:
[-] ;p1v0 > ;p2 [ ;enter loop if p2 is true > ;p3 [ ;enter loop if p3 is also true <<+>> ;p1v1 [-] ;empty p3 ] < ;empty p2 [-] ] < ;p1p1v1 only if p2v!0 AND p3v!0, else p1v0
OR:
Output is 1 if at least one input is true. p1 is output, p2 and p3 are inputs, p4 is temporary byte:
[-] ;p1v0 > ;p2 [>>+<<[-]] ;p4v/1 if p2v!0 > ;p3 [>+<[-]] ;p4v/1 if p3v!0 > ;p4 [<<<+>>>[-]] ;p1v1 if p4v!0p1v1 only if p2v!0 OR p3v!0, else p1v0. The last line is necessary to make sure p1v1 and not p1v2 (if both inputs are true).
XOR:
Output should only be 1 if sum of inputs is 1. p1 is output, p2 and p3 are inputs, p4 is temporary byte:
[-] ;p1v0 >>>[-]<< ;p4v0 p2 [>>+<<[-]] ;p4v/1 > ;p3 [>+<[-]] ;p4v/1 >- ;p4v\1 p4v0 if XOR is true <<<+>>> ;p1v1 p4 [<<<->>>[-]] ;p1v\1 <<< ;p1p1v1 only if p2v!0 XOR p3v!0, else p1v0
NOT:
Output should be 1 if input is 0. p1 is output, p2 is input:
[-]+ ;p1v1 >[<->[-]]< ;p1v0 if p2v!0p1v1 only if p2v!0
Of course, you can also combine these ports to create ports such as IN1 AND NOT(IN2), or IN1 NAND IN2.
Signatures
If you're all crazy about brainfuck or just like it really much, you can try to make your own sig that has a 'hidden' brainfuck message in it. Below is mine (try compiling it, but don't feel offended :)++++++++++[>+++++++++>+++>+++++>+++++++++++<<<<-]>-.>++>---->+.++++++.> | Nieko Maatjes | nieko.m @ gmx.net | www.nieko.net | | Improve your Internet-behaviour | | www.nieko.net/misc_learn.php | <<<<++++++++.>>>---.<<<++++.>.......<-.>>>+++.--------.<<<--.>>.[-]<[-]
Just something extra
As something extra, I'll show you one of the most difficult brainfuck programs I've written so far. This program displays whether your input is even or odd. Say, input is '@' (value 40h=64d), then the output will be '@'s value is even.'
++++++++++[>+++++++<-]>-.<+
+++++++[>+++++<-]>+.++++++.
<+++[>-----<-]>.<+++[>++++<
-]>+.<++++++++[>>++++<<-]>> display 'Enter input: '
.<---------.+++++.++.+++++.
-.<++++[>>++++++<<-]>>++.<<
++++[>>------<<-]>>--.
>,.<<<+++++++++++++.---.[-] p4vINPUT chr$(13) chr$(10)
>>>.<+++++++.<-.>-------.<
+++.<++++[>-----<-]>-.+++++
++++++.+++++++++.<++++[>--- display '@'s value is'
-<-]>.>.<++++.++++++++++.>.
<[-]>>[<<+>>-]<[-] p4 moved to p2; p3v0; only p2v!0
<<+ don't stop until p1v0; p1
[
>[>>+<<-]>>[<+<+>>-]< p2 copied to p3; p3
>[-]+< p4v1
[>-< [-] ] p4v1 if p3v!0; p3v0 to exit loop
>[ if p4v1 then p3 was v0 and loop will be entered
p3v0 and p4v0 so they can be used to print text
<++++++++++ p3v10
[>++++++++++<-]>. p3v101='e' \
<++++++[>+++<-]>-. p3v118='v' | display 'even'
<++++++[>---<-]>+. p3v101='e' |
+++++++++. p3v110='n' /
<<<[-]>>> p1v0 so that main loop is closed
[-] exit loop
]
<<[>>+<<-]>>[<+<+>>-]<- p2 copied to p3; p3v\1
>[-]+< p4v1
[>-< [-] ] p4v1 if p3 was v!!; p3v0 to exit loop
>[ if p4v1 then p3 was v0 and loop will be entered
p3v0 and p4v0 so they can be used to print text
<+++++++++++ p3v11
[>++++++++++<-]>. p3v111='o' \ display 'odd'
-----------.. p3v100='d' /
<<<[-]>>> p1v0 so that main loop is closed
[-] exit loop
]
<<--< p2v\2; p1
]
>[-]<
++++++[>++++++++<-]>--. display a dot
Or, without comments:
++++++++++[>+++++++<-]>-.<++++++++[>+++++<-]>+.++++++.<+++[>-----<-]>.<+++ [>++++<-]>+.<++++++++[>>++++<<-]>>.<---------.+++++.++.+++++.-.<++++[>>+++ +++<<-]>>++.<<++++[>>------<<-]>>--.>,.<<<+++++++++++++.---.[-]>>>.<++++++ +.<-.>-------.<+++.<++++[>-----<-]>-.+++++++++++.+++++++++.<++++[>----<-]> .>.<++++.++++++++++.>.<[-]>>[<<+>>-]<[-]<<+[>[>>+<<-]>>[<+<+>>-]<>[-]+<[>- <[-]]>[<++++++++++[>++++++++++<-]>.<++++++[>+++<-]>-.<++++++[>---<-]>+.+++ ++++++.<<<[-]>>>[-]]<<[>>+<<-]>>[<+<+>>-]<->[-]+<[>-<[-]]>[<+++++++++++[>+ +++++++++<-]>.-----------..<<<[-]>>>[-]]<<--<]>[-]<++++++[>++++++++<-]>--.
Epilogue
Credits go to:Frans Faase for showing how to use IF-THEN-statements
Erdal Karaca for writing a real good tutorial (albeit in German)
Eelco Lempsink for introducing me to the language
Daniel Cristofani for giving lots of suggestions to improve this tutorial
Paweł Łakomski for the link to division with non-zero remainders
http://home.planet.nl/~faase009/Ha_BF.html (english)
http://home.t-online.de/home/erdalkaraca/html/bf2.htm (german)
Copyright © 2002 Nieko Maatjes