A Brief Introduction to Brainfuck
Basics
Brainfuck is a minimal Turing-complete programming language invented by Urban Müller that consists of only eight commands. These commands operate on an array of bytes (usually 30,000) by moving a pointer along the array & incrementing or decrementing the byte under the pointer as the programmer sees fit. At the start of program execution, all of the bytes in the array are initialized to zero, and the pointer is positioned at the first byte in the array.
Commands
| > | increment the pointer |
| < | decrement the pointer |
| + | increment the byte at the pointer |
| - | decrement the byte at the pointer |
| . | output the character represented by the byte at the pointer |
| , | read in a character & store it in the byte at the pointer |
| [ | execute the code from itself to the matching ] if the byte at the pointer is nonzero; otherwise, the code is skipped |
| ] | go back to the matching [ if the byte at the pointer is nonzero |
All other characters are ignored.
Implementation-Defined Elements
As Müller's description of Brainfuck is not very thorough, a number of aspects of the language are left to its implementors to determine. For example, it is unclear what should happen when incrementing or decrementing a byte beyond its storage capacity or when moving the pointer beyond the end of the array in either direction. Most Brainfuck implementations have the byte or pointer "wrap around," though this behavior should not be relied upon. The length of the array & the size of its elements can also vary between implementations, though most use Urban Müller's original array size of 30,000 cells, and nearly all use 8-bit bytes as the array elements.
A less uniformly implemented detail is how the language handles the end-of-file condition when reading from standard input with ','. Some implementations set the current byte to zero or -1, while others leave the byte unchanged. One should consult the documentation for a specific Brainfuck implementation before trying to make use of EOF or any other variable aspect of the language in a program.
Algorithms
This section lists the Brainfuck code necessary to perform certain calculations with the language, though the exact codes given are not necessarily the only ways that the calculations can be accomplished. Each snippet is accompanied by a summary of the operations that it performs on the segment of the data array that it is applied to, using a notation of my own design. The two sets of values shown for each algorithm represent the values of the consecutive cells that the code operates on both before & after execution. The pointer starts & ends on the first element of the set, and any elements outside of the given set are not affected. In the notation, 'x', 'y', etc. represent arbitrary coder-defined values, and '0' indicates that the appropriate cell either must be or will be equal to zero before or after executing the code, respectively. The final operations performed on the variables are represented as they are in C. Note that all of these code snippets assume that the numeric values involved are feasible under one's Brainfuck implementation.
If one wishes to manipulate elements that are not organized in conformance to the given synopses, one must modify the quantities of '<'s & '>'s appropriately.
Clearing a Value: {x} → {0}
[-]
Moving a Value: {x, 0} → {0, x}
[->+<]
Copying a Value: {x, 0, 0} → {x, x, 0}
[->+>+<<]>>[-<<+>>]<<
Addition: {x, y} → {0, x+y}
[->+<]
Subtraction: {x, y} → {x-y, 0}
>[-<->]<
Multiplication: {x, y, 0, 0} → {0, y, x*y, 0}
[->[->+>+<<]>>[-<<+>>]<<<]
Exponentiation: {x, y, 0, 0, 0} → {x, 0, pow(x, y), 0, 0}
>>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]<
Division: {x, y, 0, 0, 0, 0} → {x/y, x%y, 0, 0, 0, 0}
[>[->+>+<<]>[-<<-[>]>>>[<[-<->]<[>]>>[[-]>>+<]>-<]<<]>>>+<<[-<<+>>]<<<]
>>>>>[-<<<<<+>>>>>]<<<<<
Warning: When y=0, an infinite loop will result.
Psych
As writing a Brainfuck interpreter is incredibly simple, I immediately set out to make one as soon as I learned the basic commands. Pretty soon, I had created Psych, my own Brainfuck interpreter, which you can download here. Psych is currently at version 1.0, and, besides the standard language features, it also allows resizing of the array at runtime, unbuffered input for ',', output in the form of numbers rather than characters, output of a portion of the data array on program termination, source code comments, and running code passed via the command line. You can even use the -h switch to print out a short summary of the Brainfuck commands if, say, you just can't remember which is the input command & which is the output.
Other Resources
<http://www.muppetlabs.com/~breadbox/bf/><http://en.wikipedia.org/wiki/Brainfuck>
<http://esoteric.sange.fi/brainfuck/>