Brainfuck

Brainfuck is a minimalist computer programming language created by Urban Müller around 1993. The language is sometimes referred to as brainf*ck, brainf***, or just BF in polite company.

Müller's goal was to create a simple Turing complete programming language which could be implemented with the smallest possible compiler. The language consists of eight statements. Version 2 of the original compiler (http://wuarchive.wustl.edu/pub/aminet/dev/lang/brainfuck-2.lha), written for the Amiga, was 240 bytes in size.

As the name suggests, brainfuck programs tend to be difficult to comprehend, perhaps so much so as to drive the programmer insane. However, the Turing machine, and therefore brainfuck, can accomplish any computing task. Disregarding the apparent difficulty in programming certain tasks in brainfuck, it is certainly possible to do so.

The language is based on a simple machine model consisting, besides the program, of an array of bytes initialized to zero, a pointer into the array (initialized to point to the first byte of the array), and two streams of bytes for input and output.

The eight language statements, each consisting of a single letter, are the following:

(Alternately, ] may be taken to mean "jump back to the corresponding [". This is briefer, but less symmetrical and time-efficient. Both versions produce equivalent behavior from every brainfuck program.)

(A third equivalent version, little considered, is: [ means "jump forward to the corresponding ]", and ] means "jump back to the statement after the corresponding [ if the byte at the pointer is nonzero".)

Brainfuck programs can be transliterated into C using the following substitutions, assuming ptr is of type char*:

Examples

Hello World!

A program which prints "Hello World!" to the screen is:

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

Zero current location

 [-]

Character I/O

 ,.

Take one character from the keyboard and output it to the screen.

Simple loop

 ,[.,]

A continuous loop that takes keyboard input and echoes it to the screen. Note that this assumes 0 to signal the end of input; implementations vary on this point. Versions for -1 and "no change" are ",+[-.,+]" and ",[.[-],]".

Pointer manipulation

 >,[.>,]

A version of the last one that also saves all the input in the array for future use, by moving the pointer each time.

Add

 [->+<]

This adds the current location (destructively, it is left at zero) to the next location.

Conditional statements

 ,----------[----------------------.,----------]

This will take lowercase input from the keyboard and make it uppercase. To exit, press the enter key.

First, we input the first character using the , and immediately subtract 10 from it. (Most, but not all, brainfuck programs use 10 for return.) If the user hit enter, the loop command ([) will jump past the end of the loop, because we will have set the first byte to zero. If the character input was not a 10, we boldly assume it was a lowercase letter, and enter the loop, wherein we subtract another 22 from it, for a total of 32, which is the difference between an ASCII lowercase letter and the corresponding uppercase letter.

Next we output it. Now we input the next character, and again subtract 10. If this character was a linefeed, we exit the loop; otherwise, we go back to the start of the loop, subtract another 22, output, and so on. When we exit the loop, the program terminates, as there are no more commands.

Addition

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

This program adds two single-digit numbers and displays the result correctly if it too has only one digit:

 4+3

 
 7

(Now things start to get a bit more complicated. We may as well refer to the bytes in the array as [0], [1], [2], and so on.)

The first number is input in [0], and 48 is subtracted from it to correct it (the ASCII codes for the digits 0-9 are 48-57). This is done by putting a 6 in [1] and using a loop to subtract 8 from [0] that many times. (This is a common method of adding or subtracting large numbers.) Next, the plus sign is input in [1]; then the second number is input, overwriting the plus sign.

The next loop [<+>-] does the real work, moving the second number onto the first, adding them together and zeroing [1]. Each time through, it adds one to [0] and subtracts one from [1]; so by the time [1] is zeroed, as many have been added to [0] as have been removed from [1]. Now a return is input in [1]. (We're not error-checking the input at all.)

Then the pointer is moved back to the [0], which is then output. ([0] is now a + (b + 48), since we didn't correct b; which is identical to (a + b) + 48, which is what we want.) Now the pointer is moved to [1], which holds the return that was input; it is now output, and we're done.

Multiplication

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

Like the previous, but does multiplication, not addition.

The first number is input in the [0], the asterisk and then the second number are input in [1], and both numbers are corrected by having 48 subtracted.

Now we enter the main multiplication loop. The basic idea is that each time through it we subtract one from [0] and add [1] to the running total kept in [2]. In particular: the first inner loop moves [1] onto both [2] and [3], while zeroing [1]. (This is the basic way to duplicate a number.) The next inner loop moves [3] back into [1], zeroing [3]. Then one is subtracted from [0], and the outer loop is ended. On exiting this loop, [0] is zero, [1] still has the second number in it, and [2] has the product of the two numbers. (Had we cared about keeping the first number, we could have added one to [4] each time through the outer loop, then moved the value from [4] back to [0] afterward.)

Now we add 48 to the product, input a return in [3], output the ASCIIfied product, and then output the return we just stored.

Commentary

Note that since each array location is specified as being a byte here, the - command is superfluous and could be replaced by 255 + commands. Similarly, if the element array were finite and circular, < could be replaced by 29,999 > commands. Each of these modifications would reduce the language to only seven commands. However, both modifications together would sacrifice Turing-completeness, because it would limit the number of possible memory states to a finite number. (It is precisely for this reason that even a modern PC is strictly speaking not entirely Turing-complete.)

See also: Esoteric programming language

External links

• Brian Raiter, Muppetlabs. Brainfuck: An Eight-Instruction Turing-Complete Programming Language (http://www.muppetlabs.com/~breadbox/bf/). This site includes a brainfuck quine.
• Panu Kalliokoski. The Brainfuck Archive (http://esoteric.sange.fi/Brainfuck/) has many brainfuck programs, quines, and implementations.
• Cat's Eye Technologies. Brainfuck (http://www.catseye.mb.ca/esoteric/bf/)
• Frans Faase. BF is Turing Complete (http://home.planet.nl/~faase009/Ha_bf_Turing)