Brainfuck

Müller designed Brainfuck with the goal of implementing the smallest possible compiler, inspired by the 1024-byte compiler for the FALSE programming language. Müller's original compiler was implemented in Motorola 68000 assembly on the Amiga and compiled to a binary with a size of 296 bytes. He uploaded the first Brainfuck compiler to Aminet in 1993. The program came with a "Readme" file, which briefly described the language, and challenged the reader "Who can program anything useful with it? :)". Müller also included an interpreter and some examples. A second version of the compiler used only 240 bytes. == Language design ==

The language consists of eight commands. A Brainfuck program is a sequence of these commands. The commands are executed sequentially, with some exceptions: an instruction pointer begins at the first command, and each command it points to is executed, after which it normally moves forward to the next command. The program terminates when the instruction pointer moves past the last command. In the canonical abstract machine model for Brainfuck, a program operates on a one-dimensional tape of memory cells indexed from zero and unbounded to the right. Each cell contains an 8-bit unsigned integer (0–255) and is initialized to zero. Arithmetic on cells wraps modulo 256, so incrementing 255 produces 0 and decrementing 0 produces 255. A data pointer (initialized to point to the leftmost byte of the array) indicates the current cell on the tape and can move left or right. Moving left from the first cell (index 0) is undefined. The language provides eight commands that modify the tape, move the pointer, perform input/output (using the ASCII character encoding) or control loops. The eight language commands each consist of a single character: Notes • The much older language P′′ already featured three of these commands, >, [, and ], denoting them R, (, and ) instead, while the fourth P′′ command, denoted λ, combined + and [ … ] can be nested arbitrarily and all brackets must be properly matched, making the set of valid programs a context-free language. Many practical implementations allocate a finite array of cells (commonly at least 30 000 bytes) and use 8‑bit cells with wraparound, although neither the exact cell count nor wraparound behavior is required by all interpreters. • In implementations with 8-bit unsigned cells and arithmetic wrapping at 256, one of the + or - instructions is redundant. Incrementing a cell by one is equivalent to decrementing it 255 times in succession, and decrementing by one is equivalent to incrementing it 255 times in succession. Accordingly, either the + instruction may be expressed as -^{255}, or the - instruction as +^{255}.{{Efn|H^{k} \; \rightarrow \; \underbrace{H H \dots H}_{k \text{ times}} defines repeated application of an instruction.}} Brainfuck programs are usually difficult to comprehend. This is partly because any mildly complex task requires a long sequence of commands and partly because the program's text gives no direct indications of the program's state. These, as well as Brainfuck's inefficiency and its limited input/output capabilities, are some of the reasons it is not used for serious programming. Nonetheless, like any Turing-complete language, Brainfuck is theoretically capable of computing any computable function or simulating any other computational model if given access to an unlimited amount of memory and time. A variety of Brainfuck programs have been written. Although Brainfuck programs, especially complicated ones, are difficult to write, it is quite trivial to write an interpreter for Brainfuck in a more typical language such as C due to its simplicity. Brainfuck interpreters written in the Brainfuck language itself also exist. == Examples ==

Hello World! The following program prints "Hello World!" and a newline to the screen. Note that brainfuck uses ASCII for letters. [ This program prints "Hello World!" and a newline to the screen; its length is 106 active command characters. [It is not the shortest.] This loop is an "initial comment loop", a simple way of adding a comment to a BF program such that you don't have to worry about any command characters. Any ".", ",", "+", "-", "" characters are simply ignored, the "[" and "]" characters just have to be balanced. This loop and the commands it contains are ignored because the current cell defaults to a value of 0; the 0 value causes this loop to be skipped. ] ++++++++ Set Cell #0 to 8 [ >++++ Add 4 to Cell #1; this will always set Cell #1 to 4 [ as the cell will be cleared by the loop >++ Add 2 to Cell #2 >+++ Add 3 to Cell #3 >+++ Add 3 to Cell #4 >+ Add 1 to Cell #5 + Add 1 to Cell #2 >+ Add 1 to Cell #3 >- Subtract 1 from Cell #4 >>+ Add 1 to Cell #6 [>. Cell #2 has value 72 which is 'H' >---. Subtract 3 from Cell #3 to get 101 which is 'e' +++++++..+++. Likewise for 'llo' from Cell #3 >>. Cell #5 is 32 for the space >+. Add 1 to Cell #5 gives us an exclamation point >++. And finally a newline from Cell #6 For readability, this code has been spread across many lines, and blanks and comments have been added. Brainfuck ignores all characters except the eight commands +-<>[],. so no special syntax for comments is needed (as long as the comments do not contain the command characters). The code could just as well have been written as: ++++++++[>++++[>++>+++>+++>++>+>->>+[>.>---.+++++++..+++.>>.>+.>++.Another example of 'Hello World' code is presented here. This version highlights the complexity of the language. For example, after printing 'e', it is necessary to increment cell #3 to switch to the letter 'l'. Displaying the second 'l' requires no further modifications, as cell 3 already contains 'l'. Adding two values As a first, simple example, the following code snippet will add the current cell's value to the next cell: Each time the loop is executed, the current cell is decremented, the data pointer moves to the right, that next cell is incremented, and the data pointer moves left again. This sequence is repeated until the starting cell is 0. [->+ This can be incorporated into a simple addition program as follows: c0_{\text{final}} = \big((2 \bmod 256) + (5 \bmod 256)\big) \bmod 256 = 7 \bmod 256 = 7 ++ Cell c0 = 2 > +++++ Cell c1 = 5 [ Start your loops with your cell pointer on the loop counter (c1 in our case) - Subtract 1 from c1 ] End your loops with the cell pointer on the loop counter At this point our program has added 5 to 2 leaving 7 in c0 and 0 in c1 but we cannot output this value to the terminal since it is not ASCII encoded To display the ASCII character "7" we must add 48 to the value 7 We use a loop to compute 48 = 6 * 8 ++++ ++++ c1 = 8 and this will be our loop counter again [ - Subtract 1 from c1 ] ROT13 This program enciphers its input with the ROT13 cipher. To do this, it must map characters A-M (ASCII 65–77) to N-Z (78–90), and vice versa. Also it must map a-m (97–109) to n-z (110–122) and vice versa. It must map all other characters to themselves; it reads characters one at a time and outputs their enciphered equivalents until it reads an EOF (here assumed to be represented as either -1 or "no change"), at which point the program terminates. -,+[ Read first character and start outer character reading loop -[ Skip forward if character is 0 >>++++[>+++++++++>+>-[>>>] Increase copy and remainder / reduce divisor / Normal case: skip forward +>+>] Special case: move remainder back to divisor and increase quotient >>[-]+ End skip loop; zero former divisor and reuse space for a flag >--[-[+++[-]-[>+>>] Reduce divisor; Normal case: increase remainder >[+[-]>+>>] Special case: increase remainder / move it back to divisor / increase quotient >[-] Add remainder back to divisor to get a useful 13 >[ Skip forward if quotient was 0 -[ Decrement quotient and skip forward if quotient was 1 -> Zero quotient and divisor if quotient was 2 ]>-]>> Zero divisor and subtract 13 from copy if quotient was 1 ]>-] Zero divisor and add 13 to copy if quotient was 0 ] End outer skip loop (jump to here if ((character minus 1)/32) was not 2 or 3) == Simulation of abiogenesis ==

In 2024, a Google research project used a slightly modified 10-command version of Brainfuck with separate read and write pointers and addition of pointer transfer commands as the basis of an artificial digital environment. In this environment, they found that replicators arose naturally and competed with each other for domination of the environment. == See also ==