brainfuck
Paradigm(s) imperative
Designed by Urban Müller
Appeared in 1993
Memory system Cell-based
Dimensions one-dimensional
Computational class Turing complete
Major implementations Original, Awib, Optimizing BF interpreter (from the Wayback Machine; retrieved on 19 July 2023)
Influenced by FALSE
P''
Influenced List of derivatives
File extension(s) .b, .bf

Brainfuck

Brainfuck is one of the most famous esoteric programming languages, and has inspired the creation of a host of other languages. Due to the fact that the last half of its name is often considered one of the most offensive words in the English language, it is sometimes referred to as "brainf***", "brainf*ck", "brainfsck", "b****fuck" , "brainf**k", "branflakes", "brainoof", "brainfrick", "bf", etc. This can make it a bit difficult to search for information regarding brainfuck on the web, as the proper name might not be used at all in some articles.

Language overview

Brainfuck operates on an array of memory cells, each initially set to zero. (In the original implementation, the array was 30,000 cells long, but this may not be part of the language specification; different sizes for the array length and cell size give different variants of the language). There is a pointer, initially pointing to the first memory cell. The commands are:

Command Description
> Move the pointer to the right
< Move the pointer to the left
+ Increment the memory cell at the pointer
- Decrement the memory cell at the pointer
. Output the character signified by the cell at the pointer
, Input a character and store it in the cell at the pointer
[ Jump past the matching ] if the cell at the pointer is 0
] Jump back to the matching [ if the cell at the pointer is nonzero

All characters other than ><+-.,[] should be considered comments and ignored. But, see extensions below.

History

Brainfuck was invented by Urban Müller in 1993, in an attempt to make a language for which he could write the smallest possible compiler for the Amiga OS, version 2.0. He managed to write a 240-byte compiler. The language was inspired by FALSE, which had a 1024-byte compiler. Müller chose to name the language brainfuck (with the initial letter in lower case, although it is now often capitalised).

It is not known to what extent Müller was aware of or influenced by Böhm's language P′′ published in 1964, of which brainfuck can be considered a minor variation.

Examples

Hello, World!

This program prints out the words Hello World!:

 1 +++++ +++               Set Cell #0 to 8
 2 [
 3     >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
 4     [                   as the cell will be cleared by the loop
 5         >++             Add 4*2 to Cell #2
 6         >+++            Add 4*3 to Cell #3
 7         >+++            Add 4*3 to Cell #4
 8         >+              Add 4 to Cell #5
 9         <<<<-           Decrement the loop counter in Cell #1
10     ]                   Loop till Cell #1 is zero
11     >+                  Add 1 to Cell #2
12     >+                  Add 1 to Cell #3
13     >-                  Subtract 1 from Cell #4
14     >>+                 Add 1 to Cell #6
15     [<]                 Move back to the first zero cell you find; this will
16                         be Cell #1 which was cleared by the previous loop
17     <-                  Decrement the loop Counter in Cell #0
18 ]                       Loop till Cell #0 is zero
19 
20 The result of this is:
21 Cell No :   0   1   2   3   4   5   6
22 Contents:   0   0  72 104  88  32   8
23 Pointer :   ^
24 
25 >>.                     Cell #2 has value 72 which is 'H'
26 >---.                   Subtract 3 from Cell #3 to get 101 which is 'e'
27 +++++ ++..+++.          Likewise for 'llo' from Cell #3
28 >>.                     Cell #5 is 32 for the space
29 <-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
30 <.                      Cell #3 was set to 'o' from the end of 'Hello'
31 +++.----- -.----- ---.  Cell #3 for 'rl' and 'd'
32 >>+.                    Add 1 to Cell #5 gives us an exclamation point
33 >++.                    And finally a newline from Cell #6

The same program in minimised form: 

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

This is another program that prints out Hello, World! with correct spacing, case and punctuation: 

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

This is a slightly more complex variant that often triggers interpreter bugs. This uses cell values below zero and so doesn't work on unreasonably restrictive, score-computing interpreters. 

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

Short program printing Hello, World! by primo from https://codegolf.stackexchange.com/a/68494/6691. This program needs four cells to the left of the starting point (so standard scoring would give it an adjustment of four instructions and four ticks) and requires wrapping byte sized cells. 

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

Currently, the shortest known program printing Hello, World! is written by KSab from https://codegolf.stackexchange.com/a/163590/59487 (this program needs 5 cells to the left of the starting point): 

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

Move value

This code piece moves the value of the current cell (cell0) two cells to the right (cell2): 

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

With indentation and comments the same code looks like this: 

Code:   Pseudo code:
>>      Move the pointer to cell2
[-]     Set cell2 to 0 
<<      Move the pointer back to cell0
[       While cell0 is not 0
  -       Subtract 1 from cell0
  >>      Move the pointer to cell2
  +       Add 1 to cell2
  <<      Move the pointer back to cell0
]       End while

Cat

A cat program writes its input directly to its output. As there is not a standard way to handle EOF in brainfuck, there are four versions of the program below and a non-termiating one, labelled by how they match common implementations of the interpreter. (see Implementation issues).

EOF returns 0: 

,[.,]

EOF returns -1: 

,+[-.,+]

No change on EOF, or EOF returns 0: 

,[.[-],]

No change on EOF, or EOF returns -1: 

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

Never terminates: 

+[>,.<]

Cell size

This program outputs the cell width of the interpreter: 

Calculate the value 256 and test if it's zero
If the interpreter errors on overflow this is where it'll happen
++++++++[>++++++++<-]>[<++++>-]
+<[>-<
    Not zero so multiply by 256 again to get 65536
    [>++++<-]>[<++++++++>-]<[>++++++++<-]
    +>[>
        # Print "32"
        ++++++++++[>+++++<-]>+.-.[-]<
    <[-]<->] <[>>
        # Print "16"
        +++++++[>+++++++<-]>.+++++.[-]<
<<-]] >[>
    # Print "8"
    ++++++++[>+++++++<-]>.[-]<
<-]<
# Print " bit cells\n"
+++++++++++[>+++>+++++++++>+++++++++>+<<<<-]>-.>-.+++++++.+++++++++++.<.
>>.++.+++++++..<-.>>-.
Clean up used cells
[[-]<]

Looping counter

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

Truth-machine

Without explanation 

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

With explanation 

+++++++++                Add 9 to the first cell
>>,                      Set the input to the third cell
<<[->+++++<]             Multiply the first cell (9) by 5 in the second cell
>+++                     Add 3 to the second cell
[>-<-]                   Subtract the second cell from the third cell
>>+++++[>++++++++++<-]>- Gets the ASCII code for "1"
<<[>>.<<]>>-.            Checks if the input is "1":
                         If it is, move to the output cell, print it, then go back to the start-loop cell to start the loop again
                         Else moves to the output cell decrements it, and print it

Alternate version

This version prints out whatever character the user did input, even if it isn't the digit "1". 

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

Made by: User:RixTheTyrunt

XKCD Random Number

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

With comments: 

+c+h+o+s[e-n> +b+y+ <f]a+i[r-d>i+c+e+ +r<o]l-l+;
Guaranteed to be random.

Quine

A quine is a program that prints itself. This one was written by Erik Bosman, also available at https://copy.sh/brainfuck/prog/quine505.b. 

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

Self-interpreters

Writing a self-interpreter in brainfuck is not a simple task, yet, several self-interpreters have been written throughout the years.

Computational class

When the array is unbounded, or when the array is at least three cells long and can store unbounded values, brainfuck is Turing-complete, meaning that it is in the same computational class as universal Turing machines. This, plus its dearth of commands, makes it a canonical example of a Turing tarpit.

This can be shown in a number of ways and with various restrictions on the brainfuck program and/or interpreter. The following formulations require the array to be unbounded, but allow the value in each cell to be bounded:

Other formulations allow the array to be bounded, but require that the value in each cell be unbounded:

And still others require both the array and the value in each cell to be unbounded:

Algorithms

See Brainfuck algorithms, Brainfuck constants.

Simple instruction examples

Extensions

Some implementations also recognize the following symbols as meaningful: 

# Start debugger (e.g. Print contents of first few memory cells)
! Separate code from input

The debug command # comes from brainfuck's original interpreter, written by Urban Müller. Because brainfuck programs have only one input source, brainfuck interpreters written in brainfuck (or other languages without file I/O) require ! to be able to distinguish a program's code from the input it is intended to process.

As all characters other than ><+-.,[] should be considered comments and ignored, it is normal for an interpreter to have a method of disabling these extensions if required. This disabling may be automatic for '!' based on such things as if there is currently an open loop and/or if the program is being read from the 'standard input'.

As these commands are non-standard some interpreters use different codes for these functions.

Probably the next most frequently implemented extension is a command to comment out the rest of the line, however, experienced brainfuck programmers generally consider this useless mostly due to the existence of the header comments technique.

Conventions

The following summarizes the common conventions for making a brainfuck interpreter or compiler. It can be seen as a general specification for brainfuck, commonly accepted amongst the brainfuck community as a minimal base. It attempts to solve implementation issues by standardizing them.

Memory

Input and Output

Newlines

The input should be "line buffered" until the user enters a newline at which point the program receives the edited line.

Note that most programming platforms and programming languages already do this for you, which might make converting 10s to OS newlines redundant.

EOF

An interpreter should normally either return Zero or leave the cell unchanged on EOF.

The Zero option matches the brainfuck language in that the only conditional in brainfuck is a comparison with zero. Using this form, in theory, allows slightly shorter code. For eight bit cells the "leave the cell untouched" matches the C/Unix read(2) system call in that the character memory will be left unchanged on EOF. For Unix the EOF (or error) condition is signalled by the return value, which is lost with BF. If the interpreter's cells are more than eight bits the "unchanged cell" can safely handle binary data. If the cells are eight bit or the interpreter sets the cells to zero on EOF binary data cannot be handled.

For a brainfuck program this means that ASCII data+EOF should be read using a [-], construct (or similar). Binary input should, probably, be read using a construct of the form [-]-,. This requires that input bytes are in the range 0..255 when the cell size exceeds eight bits.

Note: It is strongly recommended that an interpreter be configurable to all three normal form of EOF (Zero, minus one and unchanged).

Character set

The original brainfuck interpreter used the native character set of the host, ISO8859-1. Most modern brainfuck interpreters do the same, so this means that many current implementations will used UTF-8 as the character set and have access to ANSI control sequences. The majority of brainfuck programs only use ASCII with newlines, but the few that use extended sets follow the UTF-8+Ansi pattern.

GUI and Other I/O

GUI Pong / Simple UNIX Shell

Using a Virtual Machine controlled via stdin/out, here's a Pong implementation and a simple UNIX shell implementation (that actually controls a real filesystem)

Pong Shell

PPM file output

For a more trivial output the PPM, PGM and PPM formats or Netpbm can be generated in a simple format as plain (ASCII) text.

476px-Mandelbrot-mono-bf

Implementation issues

Brainfuck leaves a lot of things up to the implementation to decide, such as array and cell size, and what happens when EOF is read.

Memory and wrapping

The size of the cells and the cell array varies a lot in different implementations. A usual implementation will have either 8bit or 32bit cells with 30000 cells (in the positive direction). For Turing completeness either the number of cells must be unbounded or (at least) three unbounded cells are required, the former is usually assumed.

Urban Müller's compiler used an array of 30000 cells 8bit cells, while the interpreter only allowed 100 (of 5000) to be used. As the compiler was written in assembler there is no indication as to whether the cells are to be assumed to be signed or unsigned and the overflow semantics are of the usual twos complement (or unsigned byte) wrapping form. The interpreter uses signed 8bit characters (-128 to 127 range).

Other interpreters normally use a similar layout, however, some allow cells to the left of the start position or use different allowed ranges of cell values. Some limit the cells to only positive values or other reduced ranges, others allow a larger range including 'floating point' (which would usually be in effect a 53bit integer without wrapping) or even completely unbounded integers.

Note, that it's not possible for a brainfuck program to determine if its integers are officially signed or unsigned unless they are also non-wrapping. If the cells don't wrap then the loops [-] and [+] used after an number in the opposite direction will cause a crash (ie: an exception or a hang). Most optimisers will therefore assume these sequences set a zero even with unbounded integers.

Even with wrapping cells code can be written that depends on the cell size for example Brainfuck bitwidth conversions or the code below (which only works correctly with 8bits). 

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

Newlines

The vast majority of brainfuck programs, following Urban Müller's original example programs, use 10 as newline on both input and output; this is also the convention used by Unix-based operating systems, including Linux and Mac OS X. Some other operating systems use different conventions for newline, and may use different conventions on input and on output, and different conventions in different programming environments (e.g. C versus assembly language). Several solutions to the problem are possible:

A few implementations allow the input to be "raw" and sometimes non-blocking. If the input is in "raw" mode it is not line buffered and key presses are passed to the program immediately. Non-blocking means that if there isn't a character available either immediately or after a short delay (for example 1/10 of a second) the input command will return an EOF indication.

EOF

EOF is a controversial issue. Many implementations return 0, some return -1, and several notable brainfuck programmers suggest that on EOF the memory cell should be left as-is, without modification. In the original distribution the compiler left the cell unchanged, while the interpreter used the EOF from C which, strictly speaking, could be any negative integer, but which usually is -1 (which, in the case of byte-sized cells, ends up as 255).