Editing Brainfuck

{{short description|Esoteric, minimalist programming language}}
{{distinguish|Brain Fuck Scheduler|Mindfuck (disambiguation){{!}}Mindfuck|GRM. Brainfuck}}
{{Multiple issues|
{{Unreliable sources|date=April 2023}}
{{More citations needed|date=April 2023}}
}}
{{Infobox programming language
| name = Brainfuck
| file_ext = .b, .bf
| paradigm = [[Esoteric programming language|Esoteric]], [[Imperative programming|imperative]], [[Structured programming|structured]]
| released = September 1993
| designer = Urban Müller
| typing = Typeless
| influenced_by = [[P′′]], [[Esoteric programming language#FALSE|FALSE]]
| influenced = [[Malbolge]]
}}
'''Brainfuck''' is an [[esoteric programming language]] created in 1993 by Swiss student Urban Müller.<ref>{{Cite journal|last=Easter|first=Brandee|date=2020-04-02|title=Fully Human, Fully Machine: Rhetorics of Digital Disembodiment in Programming|journal=Rhetoric Review|volume=39|issue=2|pages=202–215|doi=10.1080/07350198.2020.1727096|s2cid=219665562|issn=0735-0198}}</ref> Designed to be extremely minimalistic, the language consists of only eight simple commands, a [[data pointer]], and an [[instruction pointer]].<ref>{{Cite journal |last=Temkin |first=Daniel |date=2017-09-01 |title=Language without code: intentionally unusable, uncomputable, or conceptual programming languages |url=https://revistas.ucp.pt/index.php/jsta/article/view/7297 |journal=Journal of Science and Technology of the Arts |language=en |volume=9 |issue=3 |pages=83–91 |doi=10.7559/citarj.v9i3.432 |issn=2183-0088 |access-date=2024-02-11 |archive-date=2024-07-09 |archive-url=https://web.archive.org/web/20240709135000/https://revistas.ucp.pt/index.php/jsta/article/view/7297 |url-status=live }}</ref>

Brainfuck is an example of a so-called [[Turing tarpit]]: it can be used to write any program, but it is not practical to do so because it provides so little abstraction that the programs get very long or complicated. While Brainfuck is fully [[Turing completeness|Turing-complete]], it is not intended for practical use but to challenge and amuse [[programmers]].<ref>Haupt, Michael. "Implementing Brainfuck in COLA."</ref><ref>Cox, Geoff, and Alex McLean. "Not Just for Fun." Bloomsbury Academic, 2014. 157-173.</ref> Brainfuck requires one to break down commands into small and simple instructions.

The language takes its name from the slang term ''[[:wikt:brainfuck|brainfuck]]'', which refers to things so complicated or unusual that they exceed the limits of one's understanding, as it was not meant or made for designing actual software but to challenge the boundaries of [[computer programming]].

Because the language's name contains [[profanity]], many substitutes are used, such as brainfsck, branflakes, brainoof, brainfrick, BrainF, and BF.<ref>{{Cite web |title=brainfuck - Esolang |url=https://esolangs.org/wiki/Brainfuck |access-date=2024-02-07 |website=esolangs.org |archive-date=2018-10-23 |archive-url=https://web.archive.org/web/20181023084337/https://esolangs.org/wiki/Brainfuck |url-status=live }}</ref>

== History ==
Müller designed Brainfuck with the goal of implementing the smallest possible [[compiler]],<ref>{{cite web |url=https://muppetlabs.com/~breadbox/bf/ |title=The Brainfuck Programming Language |publisher=Muppetlabs.com |access-date=2023-04-30 |archive-date=2023-05-03 |archive-url=https://web.archive.org/web/20230503224855/http://www.muppetlabs.com/~breadbox/bf/ |url-status=live }}</ref> inspired by the 1024-[[byte]] compiler for the [[Esoteric programming language#FALSE|FALSE programming language]].<ref>{{cite web |url=https://strlen.com/false-language/ |title=The FALSE Programming Language &mdash; Wouter van Oortmerssen |publisher=Strlen.com |date=2013-08-03 |access-date=2023-04-30 |archive-date=2023-04-30 |archive-url=https://web.archive.org/web/20230430025341/https://strlen.com/false-language/ |url-status=live }}</ref><ref>{{cite AV media | url = https://www.youtube.com/watch?v=gjm9irBs96U&t=8722s | title = Tamedia TX 2017 - Livestream Werdino | date = 13 June 2017 | access-date = 30 August 2024 | archive-date = 11 August 2023 | archive-url = https://web.archive.org/web/20230811071142/https://www.youtube.com/watch?v=gjm9irBs96U&t=8722s | url-status = live }}</ref> Müller's original compiler was implemented in [[Motorola 68000]] [[Assembly language|assembly]] on the [[Amiga]] and compiled to a [[Binary file|binary]] with a size of 296 bytes. He uploaded the first Brainfuck compiler to [[Aminet]] in 1993. The program came with a [[README|"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.<ref>{{cite web |url=https://aminet.net/package.php?package=dev/lang/brainfuck-2.lha |title=Aminet - dev/lang/brainfuck-2.lha |publisher=Aminet |access-date=2023-04-30 |archive-date=2023-04-30 |archive-url=https://web.archive.org/web/20230430025339/https://aminet.net/package.php?package=dev/lang/brainfuck-2.lha |url-status=live }}</ref>

== Language design ==
The language consists of eight [[command (computing)|commands]]. A brainfuck program is a sequence of these commands, possibly interspersed with other characters (which are ignored). The commands are executed sequentially, with some exceptions: an [[Program counter|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.

The brainfuck language uses a simple machine model consisting of the program and instruction pointer, as well as a one-dimensional array of at least 30,000 [[byte]] cells initialized to zero; a movable [[pointer (computer programming)|data pointer]] (initialized to point to the leftmost byte of the array); and two streams of bytes for input and output (most often connected to a keyboard and a monitor respectively, and using the [[ASCII]] character encoding).

The eight language commands each consist of a single character:

{| class="wikitable"
|-
! style="text-align:center;" | Character
! align="left" | Instruction Performed
|-
|style="text-align:center"|<code>&gt;</code>
| Increment the [[pointer (computer programming)|data pointer]] by one (to point to the next cell to the right).
|-
|style="text-align:center"|<code>&lt;</code>
| Decrement the data pointer by one (to point to the next cell to the left).
|-
|style="text-align:center"|<code>+</code>
| Increment the byte at the data pointer by one.
|-
|style="text-align:center"|<code>-</code>
| Decrement the byte at the data pointer by one.
|-
|style="text-align:center"|<code>.</code>
| Output the byte at the data pointer.
|-
|style="text-align:center"|<code>,</code>
| Accept one byte of input, storing its value in the byte at the data pointer.
|-
|style="text-align:center"|<code>[</code>
| If the byte at the data pointer is zero, then instead of moving the [[Program Counter|instruction pointer]] forward to the next command, [[Branch (computer science)|jump]] it ''forward'' to the command after the ''matching'' <code>]</code> command.
|-
|style="text-align:center"|<code>]</code>
| If the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it ''back'' to the command after the ''matching'' <code>[</code> command.{{Efn|Alternatively, the <code>]</code> command may instead be translated as an unconditional jump ''to'' the corresponding <code>[</code> command, or vice versa; programs will behave the same but will run more slowly, due to unnecessary double searching.}}
|}

<code>[</code> and <code>]</code> match as parentheses usually do: each <code>[</code> matches exactly one <code>]</code> and vice versa, the <code>[</code> comes first, and there can be no unmatched <code>[</code> or <code>]</code> between the two.

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 (computer science)|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.<ref>{{cite web |url=https://iwriteiam.nl/Ha_bf_Turing.html |title=BF is Turing-complete |publisher=Iwriteiam.nl |access-date=2023-04-30 |archive-date=2023-05-23 |archive-url=https://web.archive.org/web/20230523075731/http://www.iwriteiam.nl/Ha_bf_Turing.html |url-status=live }}</ref> A variety of Brainfuck programs have been written.<ref>{{cite web |url=https://sange.fi/esoteric/brainfuck/bf-source/prog/ |title=Index of /esoteric/brainfuck/bf-source/prog |publisher=sange.fi |date=2002-01-22 |access-date=2023-04-30 |archive-date=2023-04-30 |archive-url=https://web.archive.org/web/20230430025341/https://sange.fi/esoteric/brainfuck/bf-source/prog/ |url-status=live }}</ref> 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.<ref>{{cite web |url=https://iwriteiam.nl/Ha_bf_inter.html |title=BF interpreter written in BF |publisher=Iwriteiam.nl |access-date=2023-04-30 |archive-date=2024-09-22 |archive-url=https://web.archive.org/web/20240922070535/https://iwriteiam.nl/Ha_bf_inter.html |url-status=live }}</ref><ref>{{cite web |url=https://www.brainfuck.org/dbfi.b |title=brainfuck interpreter |publisher=Daniel B. Cristofani |access-date=2024-06-19 |archive-date=2024-09-22 |archive-url=https://web.archive.org/web/20240922070413/https://www.brainfuck.org/dbfi.b |url-status=live }}</ref>

== Examples ==
=== 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.

<syntaxhighlight lang="bf">
[->+<]
</syntaxhighlight>

This can be incorporated into a simple addition program as follows:

<syntaxhighlight lang="bf">
++       Cell c0 = 2
> +++++  Cell c1 = 5

[        Start your loops with your cell pointer on the loop counter (c1 in our case)
< +      Add 1 to c0
> -      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
[
< +++ +++  Add 6 to c0
> -        Subtract 1 from c1
]
< .        Print out c0 which has the value 55 which translates to "7"!
</syntaxhighlight>

=== Hello World! ===
The following program prints [[Hello world program|"Hello World!"]] and a newline to the screen:

<syntaxhighlight lang="bf">
[ 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 ".", ",", "+", "-", "<" and ">" 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
        <<<<-           Decrement the loop counter in Cell #1
    ]                   Loop until Cell #1 is zero; number of iterations is 4
    >+                  Add 1 to Cell #2
    >+                  Add 1 to Cell #3
    >-                  Subtract 1 from Cell #4
    >>+                 Add 1 to Cell #6
    [<]                 Move back to the first zero cell you find; this will
                        be Cell #1 which was cleared by the previous loop
    <-                  Decrement the loop Counter in Cell #0
]                       Loop until Cell #0 is zero; number of iterations is 8

The result of this is:
Cell no :   0   1   2   3   4   5   6
Contents:   0   0  72 104  88  32   8
Pointer :   ^

>>.                     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
<-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
<.                      Cell #3 was set to 'o' from the end of 'Hello'
+++.------.--------.    Cell #3 for 'rl' and 'd'
>>+.                    Add 1 to Cell #5 gives us an exclamation point
>++.                    And finally a newline from Cell #6
</syntaxhighlight>

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 <code>+-<>[],.</code> 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:
<syntaxhighlight lang="bf">++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.</syntaxhighlight>

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

<syntaxhighlight lang="bf">
-,+[                         Read first character and start outer character reading loop
    -[                       Skip forward if character is 0
        >>++++[>++++++++<-]  Set up divisor (32) for division loop
                               (MEMORY LAYOUT: dividend copy remainder divisor quotient zero zero)
        <+<-[                Set up dividend (x minus 1) and enter division loop
            >+>+>-[>>>]      Increase copy and remainder / reduce divisor / Normal case: skip forward
            <[[>+<-]>>+>]    Special case: move remainder back to divisor and increase quotient
            <<<<<-           Decrement dividend
        ]                    End division loop
    ]>>>[-]+                 End skip loop; zero former divisor and reuse space for a flag
    >--[-[<->+++[-]]]<[         Zero that flag unless quotient was 2 or 3; zero quotient; check flag
        ++++++++++++<[       If flag then set up divisor (13) for second division loop
                               (MEMORY LAYOUT: zero copy dividend divisor remainder quotient zero zero)
            >-[>+>>]         Reduce divisor; Normal case: increase remainder
            >[+[<+>-]>+>>]   Special case: increase remainder / move it back to divisor / increase quotient
            <<<<<-           Decrease dividend
        ]                    End division loop
        >>[<+>-]             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)
    <[-]                     Clear remainder from first division if second division was skipped
    <.[-]                    Output ROT13ed character from copy and clear it
    <-,+                     Read next character
]                            End character reading loop
</syntaxhighlight>

=== Simulation of abiogenesis ===
In 2024, a Google research project used a slightly modified 10-command version of Brainfuck 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.<ref>{{cite arXiv
	| author-link = 
	| date = 2024
	| title = Computational Life: How Well-formed, Self-replicating Programs Emerge from Simple Interaction
	| eprint = 2406.19108
	| class = cs.NE
| author1 = Blaise Agüera y Arcas
	| last2 = Alakuijala
	| first2 = Jyrki
	| last3 = Evans
	| first3 = James
	| last4 = Laurie
	| first4 = Ben
	| last5 = Mordvintsev
	| first5 = Alexander
	| last6 = Niklasson
	| first6 = Eyvind
	| last7 = Randazzo
	| first7 = Ettore
	| last8 = Versari
	| first8 = Luca
	}}</ref>

== See also ==
* [[JSFuck]] – an esoteric subset of the [[JavaScript]] programming language with a very limited set of characters

== Notes ==
{{Notelist}}

== References ==
{{Reflist|30em}}

== External links ==
* {{Official website|https://brainfuck.org/}}

{{Esoteric programming languages|state=expanded}}

[[Category:Non-English-based programming languages]]
[[Category:Esoteric programming languages]]
[[Category:Programming languages created in 1993]]