Brainfuck

Brainfuck is a minimalistic computer programming language created by Urban Müller around 1993. The name has been variously euphemized.

Language design

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 commands. Version 2 of the original compiler, written for the Amiga, is only 240 bytes in size. He was inspired by False, another esoteric programming language, whose compiler has a size of 1024 bytes.

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

As the name suggests, brainfuck programs tend to be difficult to comprehend, and the language is certainly not suitable for practical use. Nonetheless, like any Turing-complete language, brainfuck is theoretically capable of computing any known computable function or simulating any other computational model, if given an unlimited memory store.

Commands

The eight language commands, each consisting of a single character, are the following:

(Alternatively, either the [ command or the ] command may instead be translated as an unconditional jump to the corresponding ] or [ command; this will produce the same behavior from every brainfuck program, but the programs will run more slowly.)

Brainfuck programs can be translated into C using the following substitutions, assuming ptr is of type unsigned char* and has been initialized to point to an array of zeroed bytes:

Examples

Hello World!

The following program prints "Hello World!" and a newline to the screen:

++++++++++
[
   >+++++++>++++++++++>+++>+<<<<-
] The initial loop to set up useful values in the array
>++. print 'H'
>+. print 'e'
+++++++. 'l'
. 'l'
+++. 'o'
>++. space
<<+++++++++++++++. 'W'
>. 'o'
+++. 'r'
------. 'l'
--------. 'd'
>+. '!'
>. newline

For readability, this code has been spread across many lines and comments have been added. Brainfuck treats all characters but +-<>[],. as comments so no special syntax for a comment is needed.

The loop at the first line effectively sets the initial values for the array: a[1] = 70 (close to 72, the ASCII code for the character 'H'), a[2] = 100 (close to 101 or 'e'), a[3] = 30 (close to 32, the code for space) and a[4] = 10 (newline). The loop works by multiplying the value of a[0], 10, by 7, 10, 3, and 1, saving the results in other cells. After the loop is finished, a[0] is zero. >++. then moves the pointer to a[1] which holds 70, adds two to it (producing 72 which is the ASCII character code of a capital H), and outputs it.

The next line moves the array pointer to a[2] and adds one to it, producing 101, a lower-case 'e', which is then output.

As 'l' happens to be the seventh letter after 'e', to output 'll' we add another seven (+++++++) to a[2] and output the result twice.

'o' is the third letter after 'l', so we increment a[2] three more times and output the result.

The rest of the program goes on in the same way. For the space and capital letters, different array cells are selected and incremented or decremented as needed.

Trivial

Simple loop

,[.,]

A continuous loop that takes text input from the keyboard and echoes it to the screen. Note that this assumes the cell is set to 0 when a ',' command is executed after the end of input (sometimes called end-of-file or "EOF"); implementations vary on this point. For implementations that set the cell to -1 on EOF, or leave the cell's value unchanged, this program would be written ",+[-.,+]" or ",[.[-],]" respectively.

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 implementations use 10 for return.) If the user hits 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.

Copying a byte

(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.)

Brainfuck does not include any operation for copying bytes. This must be done with the looping construct and arithmetical operators. Moving a byte is simple enough; moving the value of [0] to [1] can be done as follows:

[->+<]

However, this resets the value of [0] to 0. We can restore the value of [0] after copying by taking advantage of the ability to copy a value to two places at once. To copy the value of [0] to both [1] and [2] is simple:

[->+>+<<]

We can take advantage of this to restore the value of [0]. Therefore, we can nondestructively copy [0] to [1] (using [2] as scratch space) as follows:

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

Non-trivial

Addition

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

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

4+3

7

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 [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.

Languages based on brainfuck

Because brainfuck is so simple, it is easy to make other programming languages based on it:

• Doublefuck has an additional array and eight additional instructions which perform brainfuck-identical operations on the second array. They are, in order: "^", "v", "/", "\", ":", ";", "{", and "}".
• PATH (and SNUSP) are combinations of brainfuck with Befunge, a language which represents instructions as symbols in two-dimensional space.
• Brainfork is a multi-threaded version of brainfuck with an additional "Y" instruction to fork the current thread.
• THRAT uses two instructions to access brainfuck instructions on an opcode table.
• L00P has an implicit loop, removes the "[" and "]" looping instructions and adds ten others.
• Ook! reformats brainfuck's commands as combinations of "Ook." "Ook!" and "Ook?".
• COW reformats brainfuck's commands as various capitalisations of the word "Moo".
• Spoon uses a Huffman coded set of brainfuck's instructions.
• l33t adds networking capabilities. (Very loosely based).
• Aura
• F*ckF*ck uses profanity as commands.
• Boolfuck uses bits instead of bytes.

External links

• Brian Raiter, Muppetlabs. Brainfuck: An Eight-Instruction Turing-Complete Programming Language is a concise informational page with comments on portability.
• Panu Kalliokoski. The Brainfuck Archive has many brainfuck programs and implementations.
• Frans Faase. Brainf*** is written from a mathematician's angle and has Turing-completeness proofs.
• Daniel Cristofani. some brainfuck fluff has a complete brainfuck reference, plus programs and implementations.
• Jeffry Johnston. BF programs, including Basic compiler and assembler
• A Brainfuck tutorial in English and French.

Implementations

Software

• Acme::Brainfuck, a Perl module that permits brainfuck programs to be embedded in Perl.
• Brainfuck interpreter with integrated debugger (IDE) for Windows
• Brainfuck interpreter with compiler (IDE) for Windows
• Brainfuck.Net
• Also Written In Brainfuck (awib) is a brainfuck compiler written in brainfuck for Linux on i386.
• The download page with Blue Fern, a brainfuck IDE
• BrainPhuck is a PHP class featuring an optmizing parser, executor, debugger, PHP translator, and x86 compiler for brainfuck
• Stefan Partusch, Brainfucked a small broken open source compiler with syntax checking and code optimization for DOS and Windows.

Hardware

• Robert Östling. Brainfuck computer.
• Clifford Wolf. The Brainf*ck CPU and other brainfuck-related projects
• A Brainfuck Computer With a Brainfuck CPU

[[is:Heilari<eth>lun]]