Abuse filter log

Abuse Filter navigation (Home | Recent filter changes | Examine past edits | Abuse log)
Jump to navigation Jump to search
Details for log entry 7,070

19:40, 9 April 2018: Alpha-ketoacid (talk | contribs) triggered filter 9, performing the action "edit" on Brainfuck. Actions taken: Warn; Filter description: require new users to introduce themselves (examine)

Changes made in edit

   
 
===Memory and wrapping===
 
===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.
+
The size of the cells and the cell array varies a lot in different implementations. A usual implementation will have 30000, either 8- or 32-bit 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).
+
Urban Müller's compiler used an array of 30000 8-bit 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.
 
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.
 
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#Multiple_conversions|Brainfuck bitwidth conversions]] or the code below (which only works correctly with 8bits).
+
Even with wrapping cells code can be written that depends on the cell size for example [[Brainfuck_bitwidth_conversions#Multiple_conversions|Brainfuck bitwidth conversions]] or the code below (which only works correctly with 8 bits).
   
 
<font color="#c000c0">+</font><font color="#804000">[[</font><font color="#c000c0">-</font><font color="#008000">&gt;</font><font color="#804000">]</font><font color="#c000c0">-</font><font color="#804000">[</font><font color="#c000c0">-</font><font color="#008000">&lt;</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c000c0">-</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;&lt;</font><font color="#c000c0">++</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">++</font><font color="#c00000">.</font>
 
<font color="#c000c0">+</font><font color="#804000">[[</font><font color="#c000c0">-</font><font color="#008000">&gt;</font><font color="#804000">]</font><font color="#c000c0">-</font><font color="#804000">[</font><font color="#c000c0">-</font><font color="#008000">&lt;</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c000c0">-</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;&lt;</font><font color="#c000c0">++</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">++</font><font color="#c00000">.</font>

Action parameters

VariableValue
Whether or not the edit is marked as minor (no longer in use) (minor_edit)
false
Edit count of the user (user_editcount)
0
Name of the user account (user_name)
'Alpha-ketoacid'
Age of the user account (user_age)
733
Page ID (page_id)
961
Page namespace (page_namespace)
0
Page title (without namespace) (page_title)
'Brainfuck'
Full page title (page_prefixedtitle)
'Brainfuck'
Action (action)
'edit'
Edit summary/reason (summary)
'/* Memory and wrapping */ '
Old content model (old_content_model)
'wikitext'
New content model (new_content_model)
'wikitext'
Old page wikitext, before the edit (old_wikitext)
'{{featured language}} {{infobox proglang |name=brainfuck |paradigms=imperative |author=[[Urban Müller]] |year=[[:Category:1993|1993]] |memsys=tape-based |dimensions=one-dimensional |class=[[:Category:Turing complete|Turing complete]] |majorimpl=[http://main.aminet.net/dev/lang/brainfuck-2.lha Original], [http://code.google.com/p/awib/ Awib], [http://mazonka.com/brainf/ Optimizing BF interpreter] |influence=[[P%27%27]] |influenced=[[:Category:Brainfuck derivatives|List of derivatives]] <!-- should there be the actual list and not just a link? --><!-- NO! --> |files=<code>.b</code> }} :''The title of this article may well be '''brainfuck''', due to typically being lowercased except, often, at the start of a sentence.'' '''Brainfuck''' is the most famous [[esoteric programming language]], 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, or BF. 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, also referred to as the [[tape]], each initially set to zero. There is a [[pointer]], initially pointing to the first memory cell. The commands are: {| class="wikitable" !Command !Description |- | style="text-align:center"| <code>&gt;</code> |Move the pointer to the right |- | style="text-align:center"| <code>&lt;</code> |Move the pointer to the left |- | style="text-align:center"| <code><nowiki>+</nowiki></code> |Increment the memory cell under the pointer |- | style="text-align:center"| <code><nowiki>-</nowiki></code> |Decrement the memory cell under the pointer |- | style="text-align:center"| <code>.</code> |Output the character signified by the cell at the pointer |- | style="text-align:center"| <code>,</code> |Input a character and store it in the cell at the pointer |- | style="text-align:center"| <code>[</code> |Jump past the matching <code>]</code> if the cell under the pointer is 0 |- | style="text-align:center"| <code>]</code> |Jump back to the matching <code>[</code> if the cell under the pointer is nonzero |} All characters other than <code>&gt;&lt;+-.,[]</code> should be considered comments and ignored. But, see extensions below. ==History== Brainfuck was invented by [[Urban Müller]] in [[:Category:1993|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%27%27]] published in 1964, of which brainfuck can be considered a minor variation. ==Examples== ===[[Hello, World!]]=== This program prints out the words ''Hello World!'': <div style="border: 1px solid #ddd;padding:1em;background-color:#f9f9f9;font-family: monospace,Courier;"> <font color="#a52a2a">&nbsp;1&nbsp;</font><font color="#ff00ff">+++++</font>&nbsp;<font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Set Cell #0 to 8</font><br> <font color="#a52a2a">&nbsp;2&nbsp;</font><font color="#a52a2a"><b>[</b></font><br> <font color="#a52a2a">&nbsp;3&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4 to Cell #1; this will always set Cell #1 to 4</font><br> <font color="#a52a2a">&nbsp;4&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>[</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">as the cell will be cleared by the loop</font><br> <font color="#a52a2a">&nbsp;5&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*2 to Cell #2</font><br> <font color="#a52a2a">&nbsp;6&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*3 to Cell #3</font><br> <font color="#a52a2a">&nbsp;7&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*3 to Cell #4</font><br> <font color="#a52a2a">&nbsp;8&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4 to Cell #5</font><br> <font color="#a52a2a">&nbsp;9&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&lt;&lt;&lt;&lt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Decrement the loop counter in Cell #1</font><br> <font color="#a52a2a">10&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Loop till Cell #1 is zero</font><br> <font color="#a52a2a">11&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #2</font><br> <font color="#a52a2a">12&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #3</font><br> <font color="#a52a2a">13&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 1 from Cell #4</font><br> <font color="#a52a2a">14&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #6</font><br> <font color="#a52a2a">15&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Move back to the first zero cell you find; this will</font><br> <font color="#a52a2a">16&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">be Cell #1 which was cleared by the previous loop</font><br> <font color="#a52a2a">17&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Decrement the loop Counter in Cell #0</font><br> <font color="#a52a2a">18&nbsp;</font><font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Loop till Cell #0 is zero</font><br> <font color="#a52a2a">19&nbsp;</font><br> <font color="#a52a2a">20&nbsp;</font><font color="#0000ff">The result of this is:</font><br> <font color="#a52a2a">21&nbsp;</font><font color="#0000ff">Cell No :&nbsp;&nbsp; 0&nbsp;&nbsp; 1&nbsp;&nbsp; 2&nbsp;&nbsp; 3&nbsp;&nbsp; 4&nbsp;&nbsp; 5&nbsp;&nbsp; 6</font><br> <font color="#a52a2a">22&nbsp;</font><font color="#0000ff">Contents:&nbsp;&nbsp; 0&nbsp;&nbsp; 0&nbsp;&nbsp;72 104&nbsp;&nbsp;88&nbsp;&nbsp;32&nbsp;&nbsp; 8</font><br> <font color="#a52a2a">23&nbsp;</font><font color="#0000ff">Pointer :&nbsp;&nbsp; ^</font><br> <font color="#a52a2a">24&nbsp;</font><br> <font color="#a52a2a">25&nbsp;</font><font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #2 has value 72 which is 'H'</font><br> <font color="#a52a2a">26&nbsp;</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">---</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 3 from Cell #3 to get 101 which is 'e'</font><br> <font color="#a52a2a">27&nbsp;</font><font color="#ff00ff">+++++</font>&nbsp;<font color="#ff00ff">++</font><font color="#6a5acd">..</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Likewise for 'llo' from Cell #3</font><br> <font color="#a52a2a">28&nbsp;</font><font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #5 is 32 for the space</font><br> <font color="#a52a2a">29&nbsp;</font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">-</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 1 from Cell #4 for 87 to give a 'W'</font><br> <font color="#a52a2a">30&nbsp;</font><font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #3 was set to 'o' from the end of 'Hello'</font><br> <font color="#a52a2a">31&nbsp;</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font><font color="#ff00ff">-----</font>&nbsp;<font color="#ff00ff">-</font><font color="#6a5acd">.</font><font color="#ff00ff">-----</font>&nbsp;<font color="#ff00ff">---</font><font color="#6a5acd">.</font>&nbsp;&nbsp;<font color="#0000ff">Cell #3 for 'rl' and 'd'</font><br> <font color="#a52a2a">32&nbsp;</font><font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#ff00ff">+</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #5 gives us an exclamation point</font><br> <font color="#a52a2a">33&nbsp;</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">And finally a newline from Cell #6</font><br> </div> The same program in minimised form: ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. This is a slightly more complex variant that often triggers interpreter bugs. This uses cell values below zero and so doesn't work on [http://www.hevanet.com/cristofd/brainfuck/ fascist, score-computing interpreters]. >++++++++[-<+++++++++>]<.>>+>-[+]++>++>+++[>[->+++<<+++>]<<]>-----.>-> +++..+++.>-.<<+[>[+>+]>>]<--------------.>>.+++.------.--------.>+.>+. Short program printing Hello, World! by primo from http://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. --<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+. ===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, labelled by how they match common implementations of the interpreter. (see [[#Implementation issues | Implementation issues]]). '''EOF returns 0:''' ,[.,] '''EOF returns -1:''' ,+[-.,+] '''No change on EOF, or EOF returns 0:''' ,[.[-],] '''No change on EOF, or EOF returns -1:''' ,+[-.[-]-,+] ===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. [[-]<] ==Self-interpreters== Writing a self-interpreter in brainfuck is not a simple task, yet, several self-interpreters have been written throughout the years. * [http://www.iwriteiam.nl/Ha_bf_inter.html by Frans Faase] - Perhaps the first one. * [http://www.iwriteiam.nl/Ha_vs_bf_inter.html by NYYRIKKI] * [http://www.brain------------------------------------------------------fuck.com/programs/kbfi.b by Keymaker] - Designed in the strictest 8-bit, non-wrapping, EOF = no change (EOF 0 works too) environment. The program emulates unbound cell size for cells (the program +[+] is valid and never ends) -- not really a brainfuck feature but it's there anyway -- and of course all the brainfuck programs written for the 8-bit non-wrapping environment work as supposed to. Supports infinite/unbound number of cells and nested loops. * [http://www.hevanet.com/cristofd/brainfuck/dbfi.b by Daniel B Cristofani] - The shortest; see also [[dbfi]] * [http://homepages.xnet.co.nz/~clive/eigenratios/cgbfi2.b by Clive Gifford] - The fastest * [https://github.com/ludamad/bf-self-interpreter by Adam Domurad] - Interprets Brainfuck code from the input until a %, then reads remaining input as input for the interpreted program. Comments are allowed, and up to 256-depth nested loops ==Computational class== Brainfuck is [[Turing-complete]], meaning that it is in the same [[computational class]] as [[universal Turing machine]]s. This, plus its dearth of commands, makes it a canonical example of a [[Turing tarpit]]. This can be shown in a number of ways. The following formulations require the tape to be [[unbounded]], but allow the value in each cell to be bounded: * Daniel B Cristofani's [http://www.hevanet.com/cristofd/brainfuck/utm.b implementation of a universal Turing machine in brainfuck] provides a proof by [[Computational_class#Simulation|simulation]]. * Fairly trivial [[Computational_class#Reduction|reductions]] can also be drawn between brainfuck and [[P%27%27]], which has been formally shown to be Turing-complete. * [[User:Keymaker]] [[Brainfuck minus -|has shown that]] brainfuck is Turing-complete even if you can only adjust cells by incrementing 0s to 1s. Other formulations allow the tape to be bounded, but require that the value in each cell be unbounded: * Frans Faase gives a procedure for translating 5-register Universal Register Machines into brainfuck programs using five cells [http://www.iwriteiam.nl/Ha_bf_Turing.html ]. * [[Ørjan Johansen]] has made a conversion from iterated [[Collatz function]]s to 3-cell brainfuck [[Collatz_function#Reduction_to_3-cell_brainfuck|(see that page for details)]]. And still others require both the tape and the value in each cell to be unbounded: * Frans Faase gives [http://www.iwriteiam.nl/Ha_bf_Turing.html a procedure for transforming Turing machines into brainfuck programs] which constitutes a proof by translation. ==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#Multiple_conversions|Brainfuck bitwidth conversions]] or the code below (which only works correctly with 8bits). <font color="#c000c0">+</font><font color="#804000">[[</font><font color="#c000c0">-</font><font color="#008000">&gt;</font><font color="#804000">]</font><font color="#c000c0">-</font><font color="#804000">[</font><font color="#c000c0">-</font><font color="#008000">&lt;</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c000c0">-</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;&lt;</font><font color="#c000c0">++</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">++</font><font color="#c00000">.</font> ===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: * Write brainfuck programs to accept multiple linefeed conventions. (Possible, though clunky, on input; not generally possible on output.) * Write many versions of each brainfuck program, one for each programming environment. (Possible, but very unpleasant.) * Forget portability and write programs for whatever implementation you are using. (A fairly common approach. May make it hard to share programs if your interpreter doesn't use 10 as newline.) * Write brainfuck interpreters and compilers to translate newline to 10 on input, and 10 to newline on output, in environments where that is not already the case. (Easy and helpful, but often overlooked. Also, may break the few brainfuck programs that do binary i/o; so newline translation should ideally be able to be turned off with a switch.) * Instead of having the user hit the "Enter" key, expect the user to do something else to give a 10 to the interpreter; e.g., the user can feed the input from a file which uses 10s to end the lines, rather than from the keyboard. Send the output to a file too. (Possible but clunky.) 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). ==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=== * Memory should normally consist of 8 bit cells, a very fast compiler may use 32bit or larger cells. Floating point cells are strongly discouraged as are cells that are not a power of two in size. "Bignum" cells are allowed but should be an option. * Memory should wrap on overflow and underflow. (This also includes the <code>[-]</code> function with "bignum" cells). * Negative memory addresses should NOT be assumed to exist, however, an interpreter may provide some. (An optimising interpreter my be forced to) * Memory should consist of at least 30000 cells, some existing brainfuck programs do need more so this should be configurable or unbounded. ===Newlines=== The input should be "line buffered" until the user enters a newline at which point the program receives the edited line. * OS newlines should be converted to 10 for input. * 10s should be converted to OS newlines for output. Note that most programming platforms and programming languages already do this for you, which might make converting 10s to OS newlines redundant. ===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. ===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 <code>[-],</code> construct (or similar). Binary input should, probably, be read using a construct of the form <code>[-]-,</code>. 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). ==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 <code>&gt;&lt;+-.,[]</code> 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 [[Brainfuck algorithms#Header comment|header comments technique]]. ==Algorithms== See [[Brainfuck algorithms]], [[Brainfuck constants]]. ==Related languages== See also [[Brainfuck extensions]]. In publishing the formal programming language [[P%27%27]] in 1964, Corrado Böhm used six symbols ''precisely'' equivalent to the brainfuck commands <code>+</code>, <code>-</code>, <code>&lt;</code>, <code>&gt;</code>, <code>[</code>, and <code>]</code>, and provided an explicit program for each of the basic functions that together serve to compute any partial recursive function. (So in a very real sense, the first "brainfuck" programs appear in Bohm's 1964 paper.) Many people at various times have tried to extend brainfuck to make it easier to program in, but such efforts have been compared to trying to make a luxury car by gluing parts onto a skateboard. <!-- maybe it was dbc who said this initially. --> <!-- I said something similar to that, only "bolting" not "gluing", and "pickup truck" not "luxury car". -DBC. --> Other people have been interested in variations of the language for theoretical purposes, pedagogical applications, etc. The sheer proliferation of languages equivalent to and derived from brainfuck led Chris Pressey to dub it "the [[wikipedia:twelve-bar blues|twelve-bar blues]] of esolang". Some of the more interesting variants: * [[pbrain]] is a brainfuck extension that supports procedures. * [[cbrain]] is a derivative of pbrain as implemented in pbrain.c, adding integers and operators. * [[RUM]] stands for "bRainfUck iMproved." and adds procedures, strings and repetition. * [[Toadskin]] is a brainfuck variant that supports procedures, but uses a stack instead of a tape. * [[Brainfork]] adds a Y command to fork the current thread. * [[Fm]] edits a string on alphabet {0,1,...,m-1} (m >= 2). * [[FRAK]] assemble instructions to brainfuck code. * [[FukYorBrane]] and [[BF Joust]] pit two Brainfuck-like programs against each other, as in Core War (see [[Redcode]]). * [[Smallfuck]] operates only on bits and has no input- or output-commands. * [[Bitter]] one-bit memory cells, four commands, equivalent to [[Smallfuck]] under certain circumstances * [[Spoon]] uses a Huffman coded set of instructions corresponding to Brainfuck's commands. * [[BrainDuino]] BF port on [http://en.wikipedia.org/wiki/Arduino Arduino] HW platform (based on Atmel's ATMega). Extended by two special I/O operations and special overflow protection. * [[Puzzlang]] turns every program into an exercise in patience and logic puzzle skills. The lone X operator becomes any of brainfuck's instructions, depending on the surrounding characters. * [[Alarm Clock Radio]] throws away the instructions to decrement the memory pointer or memory value. * [[Portal]] and [[Portal 2]] allows code-level pointer manipulation and theoretically implements the Wang-B Machine. * [[tbf]] is a language that can be compiled to Brainfuck. It includes variables, strings, macros and improved loops. * [[Grin]] adds more efficient arithmetic functions to Brainfuck. * [[tinyBF]] and its variant [[RISBF]] are brainfuck equivalents with only 4 opcodes. * [[Mindscrew]] could be considered an extension of pbrain which adds a separate tape for storing procedures. * [[Grawlix]] adds stack operations, decimal I/O, another loop structure, functions, multiply/divide by two Some other funny variants: * [[Ook!]] works exactly like brainfuck, except the syntax is in Orangutan. * [[Blub]] is the same for fish. * [[Matisse]] uses colors to merge brainfuck codes and program comments. * [[Brainloller]] has the same commands as brainfuck, except they're read from a png image. * [[COW]] is like Ook!, except with a bovine syntax. * [[Pi]] obfuscates Brainfuck instructions in random errors in pi digits. Some languages inspired by brainfuck, but with more major differences: * [[Aura]] requires data to be stored in the code space. * [[PATH]] and [[SNUSP]] attempt to combine brainfuck with [[Befunge]]. * [[Wierd]] arose out of an earlier attempt to combine brainfuck with Befunge. ==See also== * [[EsoInterpreters]], featuring several brainfuck interpreters written in other esoteric languages * [[BFBASIC]], a Basic to brainfuck compiler * [[C2BF]], a partially implemented C to brainfuck compiler * [[Binary lambda calculus]], featuring an 829 bit (under 104 bytes) Brainfuck interpreter * [[Brainfuck algorithms]] * [[Brainfuck constants]] * [[Brainfuck bitwidth conversions]] * [[BF instruction minimalization]] * [[Brainfuck code generation]] * [[Brainfuck implementations]] * [[BFO]], the first known brainfuck to brainfuck optimizer and compressor * [[:Category:Brainfuck]], a collection of brainfuck related articles on this wiki * [[:Category:Brainfuck derivatives]], languages based on brainfuck * [[Brainfuck minus -]], showing that ordinary brainfuck without the '-' instruction and cell range of 0-1 (without cell-wrapping!) is still Turing-complete ==External resources== * [http://www.muppetlabs.com/~breadbox/bf/ Brian Raiter's site] contains a summary, an informal standards guide, and a couple of interesting programs. * [http://www.iwriteiam.nl/Ha_BF.html Frans Faase's site] includes a proof that brainfuck is Turing-complete. * [http://www.hevanet.com/cristofd/brainfuck/ some brainfuck fluff] contains many interesting programs, a solid interpreter, and suggestions for programmers and implementors, among other things. * [http://esoteric.sange.fi/brainfuck/ The Brainfuck Archive] has a large selection of programs, implementations and utilities. * [http://sourceforge.net/forum/forum.php?forum_id=201037 Brainfuck Golf] is a contest with the goal of writing a shortest program to do a certain task; see [[golf]]. * [http://www.brain------------------------------------------------------fuck.com/ brain------------------------------------------------------fuck.com] features some interesting brainfuck programs. * [http://alx2002.free.fr/esoterism/brainfuck/brainfuck_en.html brainfuck tutorial] * [http://jonripley.com/brainfuck/executable.html Making executable BF programs], contains information on how to make executable brainfuck programs. * {{wayback|20111031121638|http://jonripley.com/i-fiction/games/LostKingdomBF.html|The Lost Kingdom}}, an adventure game in 2 megabytes of BF code generated with [[BFBASIC]]. ** The above [http://rdebath.github.io/LostKingdom/ converted to Javascript]. * [http://www.cs.cmu.edu/~dst/DeCSS/Gallery/css-brainfuck.txt Brainfuck CSS descrambler] (with comments), from the [http://www.cs.cmu.edu/~dst/DeCSS/Gallery/ Gallery of CSS Descramblers]. * [https://github.com/graue/esofiles/tree/master/brainfuck/ Brainfuck] in [[the Esoteric File Archive]], including [https://github.com/graue/esofiles/tree/master/brainfuck/impl/ implementations], [https://github.com/graue/esofiles/tree/master/brainfuck/src/ programs] and [https://github.com/graue/esofiles/tree/master/brainfuck/util/ utilities]. * [http://www.49-6-dev.net/takingovertheworlden.htm Taking-] and [http://www.49-6-dev.net/ftotwen.htm Finally Taking Over The World] are games written by hand in brainfuck. * [http://esoteric.sange.fi/ENSI/bf-implementors-epistle.html The Epistle to the Implementors] * [http://esosc.mroman.ch/ESOSC-2014-A2.TXT ESOSC-2014-A2: Normalized Brainfuck] ===Notable implementations=== For a complete list, see [[brainfuck implementations]]. * [http://main.aminet.net/dev/lang/brainfuck-2.lha Original distribution by Urban Müller] from the [http://www.aminet.net AmiNet] archive. Includes interpreter and compiler for the Amiga. The interpreter can be compiled with [http://gcc.gnu.org/ gcc] by removing line 43, which says ''chkabort();''. The associated [http://main.aminet.net/dev/lang/brainfuck-2.readme readme file] might also have some historical interest. * [http://code.google.com/p/awib/ Also Written In Brainfuck (Awib)] is an optimizing brainfuck compiler written in brainfuck, generates various conversions including i386 executable code for Linux. * [http://esotope-bfc.googlecode.com/ Esotope Brainfuck compiler] is an optimizing Brainfuck-to-C compiler written in Python, with well optimised code. * [https://www.vanheusden.com/misc/blog/2016-05-19_brainfuck_cobol_compiler.php Brainfuck] compiler/translator to COBOL or C. ====Interpreters in plain C==== * [http://sree.kotay.com/2013/02/implementing-brainfuck.html bffsree] is a optimizing interpreter that claims to be fastest in class. (No source code) * [http://mazonka.com/brainf/ Optimizing BF interpreter] is a very fast C interpreter, fastest in its class. <!-- * [http://swapped.cc/bf/ Moderately-optimizing BF interpreter] is a portable C interpreter, second fastest in its class. --> ====JIT Interpreters==== * [https://savannah.nongnu.org/projects/libbf libbf] is a very fast JIT interpreter, still very fast ten years later. * [https://github.com/rdebath/Brainfuck/tree/master/tritium Tritium] is a optimizing interpreter that claims to be fastest in all classes. (including plain C) * [https://github.com/Wilfred/bfc Wilfred bfc] is a fast interpreter written in [https://www.rust-lang.org/en-US/ Rust] using [http://llvm.org/ LLVM]. ====Hardware implementations==== * [http://www.clifford.at/bfcpu/bfcpu.html The Brainf*ck CPU Project] is a VHDL implementation of a brainfuck CPU * [http://grapsus.net/74/ Brainfuck on 74 series logic IC's ] [[Category:Turing tarpits]] [[Category:Low-level]] [[Category:Cell-based]] [[Category:Implemented]] [[Category:Languages]] [[Category:Brainfuck]] [[Category:1993]] [[Category:Turing complete]]'
New page wikitext, after the edit (new_wikitext)
'{{featured language}} {{infobox proglang |name=brainfuck |paradigms=imperative |author=[[Urban Müller]] |year=[[:Category:1993|1993]] |memsys=tape-based |dimensions=one-dimensional |class=[[:Category:Turing complete|Turing complete]] |majorimpl=[http://main.aminet.net/dev/lang/brainfuck-2.lha Original], [http://code.google.com/p/awib/ Awib], [http://mazonka.com/brainf/ Optimizing BF interpreter] |influence=[[P%27%27]] |influenced=[[:Category:Brainfuck derivatives|List of derivatives]] <!-- should there be the actual list and not just a link? --><!-- NO! --> |files=<code>.b</code> }} :''The title of this article may well be '''brainfuck''', due to typically being lowercased except, often, at the start of a sentence.'' '''Brainfuck''' is the most famous [[esoteric programming language]], 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, or BF. 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, also referred to as the [[tape]], each initially set to zero. There is a [[pointer]], initially pointing to the first memory cell. The commands are: {| class="wikitable" !Command !Description |- | style="text-align:center"| <code>&gt;</code> |Move the pointer to the right |- | style="text-align:center"| <code>&lt;</code> |Move the pointer to the left |- | style="text-align:center"| <code><nowiki>+</nowiki></code> |Increment the memory cell under the pointer |- | style="text-align:center"| <code><nowiki>-</nowiki></code> |Decrement the memory cell under the pointer |- | style="text-align:center"| <code>.</code> |Output the character signified by the cell at the pointer |- | style="text-align:center"| <code>,</code> |Input a character and store it in the cell at the pointer |- | style="text-align:center"| <code>[</code> |Jump past the matching <code>]</code> if the cell under the pointer is 0 |- | style="text-align:center"| <code>]</code> |Jump back to the matching <code>[</code> if the cell under the pointer is nonzero |} All characters other than <code>&gt;&lt;+-.,[]</code> should be considered comments and ignored. But, see extensions below. ==History== Brainfuck was invented by [[Urban Müller]] in [[:Category:1993|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%27%27]] published in 1964, of which brainfuck can be considered a minor variation. ==Examples== ===[[Hello, World!]]=== This program prints out the words ''Hello World!'': <div style="border: 1px solid #ddd;padding:1em;background-color:#f9f9f9;font-family: monospace,Courier;"> <font color="#a52a2a">&nbsp;1&nbsp;</font><font color="#ff00ff">+++++</font>&nbsp;<font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Set Cell #0 to 8</font><br> <font color="#a52a2a">&nbsp;2&nbsp;</font><font color="#a52a2a"><b>[</b></font><br> <font color="#a52a2a">&nbsp;3&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4 to Cell #1; this will always set Cell #1 to 4</font><br> <font color="#a52a2a">&nbsp;4&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>[</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">as the cell will be cleared by the loop</font><br> <font color="#a52a2a">&nbsp;5&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*2 to Cell #2</font><br> <font color="#a52a2a">&nbsp;6&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*3 to Cell #3</font><br> <font color="#a52a2a">&nbsp;7&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*3 to Cell #4</font><br> <font color="#a52a2a">&nbsp;8&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4 to Cell #5</font><br> <font color="#a52a2a">&nbsp;9&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&lt;&lt;&lt;&lt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Decrement the loop counter in Cell #1</font><br> <font color="#a52a2a">10&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Loop till Cell #1 is zero</font><br> <font color="#a52a2a">11&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #2</font><br> <font color="#a52a2a">12&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #3</font><br> <font color="#a52a2a">13&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 1 from Cell #4</font><br> <font color="#a52a2a">14&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #6</font><br> <font color="#a52a2a">15&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Move back to the first zero cell you find; this will</font><br> <font color="#a52a2a">16&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">be Cell #1 which was cleared by the previous loop</font><br> <font color="#a52a2a">17&nbsp;</font>&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Decrement the loop Counter in Cell #0</font><br> <font color="#a52a2a">18&nbsp;</font><font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Loop till Cell #0 is zero</font><br> <font color="#a52a2a">19&nbsp;</font><br> <font color="#a52a2a">20&nbsp;</font><font color="#0000ff">The result of this is:</font><br> <font color="#a52a2a">21&nbsp;</font><font color="#0000ff">Cell No :&nbsp;&nbsp; 0&nbsp;&nbsp; 1&nbsp;&nbsp; 2&nbsp;&nbsp; 3&nbsp;&nbsp; 4&nbsp;&nbsp; 5&nbsp;&nbsp; 6</font><br> <font color="#a52a2a">22&nbsp;</font><font color="#0000ff">Contents:&nbsp;&nbsp; 0&nbsp;&nbsp; 0&nbsp;&nbsp;72 104&nbsp;&nbsp;88&nbsp;&nbsp;32&nbsp;&nbsp; 8</font><br> <font color="#a52a2a">23&nbsp;</font><font color="#0000ff">Pointer :&nbsp;&nbsp; ^</font><br> <font color="#a52a2a">24&nbsp;</font><br> <font color="#a52a2a">25&nbsp;</font><font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #2 has value 72 which is 'H'</font><br> <font color="#a52a2a">26&nbsp;</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">---</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 3 from Cell #3 to get 101 which is 'e'</font><br> <font color="#a52a2a">27&nbsp;</font><font color="#ff00ff">+++++</font>&nbsp;<font color="#ff00ff">++</font><font color="#6a5acd">..</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Likewise for 'llo' from Cell #3</font><br> <font color="#a52a2a">28&nbsp;</font><font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #5 is 32 for the space</font><br> <font color="#a52a2a">29&nbsp;</font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">-</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 1 from Cell #4 for 87 to give a 'W'</font><br> <font color="#a52a2a">30&nbsp;</font><font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #3 was set to 'o' from the end of 'Hello'</font><br> <font color="#a52a2a">31&nbsp;</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font><font color="#ff00ff">-----</font>&nbsp;<font color="#ff00ff">-</font><font color="#6a5acd">.</font><font color="#ff00ff">-----</font>&nbsp;<font color="#ff00ff">---</font><font color="#6a5acd">.</font>&nbsp;&nbsp;<font color="#0000ff">Cell #3 for 'rl' and 'd'</font><br> <font color="#a52a2a">32&nbsp;</font><font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#ff00ff">+</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #5 gives us an exclamation point</font><br> <font color="#a52a2a">33&nbsp;</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">And finally a newline from Cell #6</font><br> </div> The same program in minimised form: ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. This is a slightly more complex variant that often triggers interpreter bugs. This uses cell values below zero and so doesn't work on [http://www.hevanet.com/cristofd/brainfuck/ fascist, score-computing interpreters]. >++++++++[-<+++++++++>]<.>>+>-[+]++>++>+++[>[->+++<<+++>]<<]>-----.>-> +++..+++.>-.<<+[>[+>+]>>]<--------------.>>.+++.------.--------.>+.>+. Short program printing Hello, World! by primo from http://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. --<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+. ===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, labelled by how they match common implementations of the interpreter. (see [[#Implementation issues | Implementation issues]]). '''EOF returns 0:''' ,[.,] '''EOF returns -1:''' ,+[-.,+] '''No change on EOF, or EOF returns 0:''' ,[.[-],] '''No change on EOF, or EOF returns -1:''' ,+[-.[-]-,+] ===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. [[-]<] ==Self-interpreters== Writing a self-interpreter in brainfuck is not a simple task, yet, several self-interpreters have been written throughout the years. * [http://www.iwriteiam.nl/Ha_bf_inter.html by Frans Faase] - Perhaps the first one. * [http://www.iwriteiam.nl/Ha_vs_bf_inter.html by NYYRIKKI] * [http://www.brain------------------------------------------------------fuck.com/programs/kbfi.b by Keymaker] - Designed in the strictest 8-bit, non-wrapping, EOF = no change (EOF 0 works too) environment. The program emulates unbound cell size for cells (the program +[+] is valid and never ends) -- not really a brainfuck feature but it's there anyway -- and of course all the brainfuck programs written for the 8-bit non-wrapping environment work as supposed to. Supports infinite/unbound number of cells and nested loops. * [http://www.hevanet.com/cristofd/brainfuck/dbfi.b by Daniel B Cristofani] - The shortest; see also [[dbfi]] * [http://homepages.xnet.co.nz/~clive/eigenratios/cgbfi2.b by Clive Gifford] - The fastest * [https://github.com/ludamad/bf-self-interpreter by Adam Domurad] - Interprets Brainfuck code from the input until a %, then reads remaining input as input for the interpreted program. Comments are allowed, and up to 256-depth nested loops ==Computational class== Brainfuck is [[Turing-complete]], meaning that it is in the same [[computational class]] as [[universal Turing machine]]s. This, plus its dearth of commands, makes it a canonical example of a [[Turing tarpit]]. This can be shown in a number of ways. The following formulations require the tape to be [[unbounded]], but allow the value in each cell to be bounded: * Daniel B Cristofani's [http://www.hevanet.com/cristofd/brainfuck/utm.b implementation of a universal Turing machine in brainfuck] provides a proof by [[Computational_class#Simulation|simulation]]. * Fairly trivial [[Computational_class#Reduction|reductions]] can also be drawn between brainfuck and [[P%27%27]], which has been formally shown to be Turing-complete. * [[User:Keymaker]] [[Brainfuck minus -|has shown that]] brainfuck is Turing-complete even if you can only adjust cells by incrementing 0s to 1s. Other formulations allow the tape to be bounded, but require that the value in each cell be unbounded: * Frans Faase gives a procedure for translating 5-register Universal Register Machines into brainfuck programs using five cells [http://www.iwriteiam.nl/Ha_bf_Turing.html ]. * [[Ørjan Johansen]] has made a conversion from iterated [[Collatz function]]s to 3-cell brainfuck [[Collatz_function#Reduction_to_3-cell_brainfuck|(see that page for details)]]. And still others require both the tape and the value in each cell to be unbounded: * Frans Faase gives [http://www.iwriteiam.nl/Ha_bf_Turing.html a procedure for transforming Turing machines into brainfuck programs] which constitutes a proof by translation. ==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 30000, either 8- or 32-bit 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 8-bit 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#Multiple_conversions|Brainfuck bitwidth conversions]] or the code below (which only works correctly with 8 bits). <font color="#c000c0">+</font><font color="#804000">[[</font><font color="#c000c0">-</font><font color="#008000">&gt;</font><font color="#804000">]</font><font color="#c000c0">-</font><font color="#804000">[</font><font color="#c000c0">-</font><font color="#008000">&lt;</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c000c0">-</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;&lt;</font><font color="#c000c0">++</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">++</font><font color="#c00000">.</font> ===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: * Write brainfuck programs to accept multiple linefeed conventions. (Possible, though clunky, on input; not generally possible on output.) * Write many versions of each brainfuck program, one for each programming environment. (Possible, but very unpleasant.) * Forget portability and write programs for whatever implementation you are using. (A fairly common approach. May make it hard to share programs if your interpreter doesn't use 10 as newline.) * Write brainfuck interpreters and compilers to translate newline to 10 on input, and 10 to newline on output, in environments where that is not already the case. (Easy and helpful, but often overlooked. Also, may break the few brainfuck programs that do binary i/o; so newline translation should ideally be able to be turned off with a switch.) * Instead of having the user hit the "Enter" key, expect the user to do something else to give a 10 to the interpreter; e.g., the user can feed the input from a file which uses 10s to end the lines, rather than from the keyboard. Send the output to a file too. (Possible but clunky.) 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). ==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=== * Memory should normally consist of 8 bit cells, a very fast compiler may use 32bit or larger cells. Floating point cells are strongly discouraged as are cells that are not a power of two in size. "Bignum" cells are allowed but should be an option. * Memory should wrap on overflow and underflow. (This also includes the <code>[-]</code> function with "bignum" cells). * Negative memory addresses should NOT be assumed to exist, however, an interpreter may provide some. (An optimising interpreter my be forced to) * Memory should consist of at least 30000 cells, some existing brainfuck programs do need more so this should be configurable or unbounded. ===Newlines=== The input should be "line buffered" until the user enters a newline at which point the program receives the edited line. * OS newlines should be converted to 10 for input. * 10s should be converted to OS newlines for output. Note that most programming platforms and programming languages already do this for you, which might make converting 10s to OS newlines redundant. ===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. ===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 <code>[-],</code> construct (or similar). Binary input should, probably, be read using a construct of the form <code>[-]-,</code>. 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). ==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 <code>&gt;&lt;+-.,[]</code> 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 [[Brainfuck algorithms#Header comment|header comments technique]]. ==Algorithms== See [[Brainfuck algorithms]], [[Brainfuck constants]]. ==Related languages== See also [[Brainfuck extensions]]. In publishing the formal programming language [[P%27%27]] in 1964, Corrado Böhm used six symbols ''precisely'' equivalent to the brainfuck commands <code>+</code>, <code>-</code>, <code>&lt;</code>, <code>&gt;</code>, <code>[</code>, and <code>]</code>, and provided an explicit program for each of the basic functions that together serve to compute any partial recursive function. (So in a very real sense, the first "brainfuck" programs appear in Bohm's 1964 paper.) Many people at various times have tried to extend brainfuck to make it easier to program in, but such efforts have been compared to trying to make a luxury car by gluing parts onto a skateboard. <!-- maybe it was dbc who said this initially. --> <!-- I said something similar to that, only "bolting" not "gluing", and "pickup truck" not "luxury car". -DBC. --> Other people have been interested in variations of the language for theoretical purposes, pedagogical applications, etc. The sheer proliferation of languages equivalent to and derived from brainfuck led Chris Pressey to dub it "the [[wikipedia:twelve-bar blues|twelve-bar blues]] of esolang". Some of the more interesting variants: * [[pbrain]] is a brainfuck extension that supports procedures. * [[cbrain]] is a derivative of pbrain as implemented in pbrain.c, adding integers and operators. * [[RUM]] stands for "bRainfUck iMproved." and adds procedures, strings and repetition. * [[Toadskin]] is a brainfuck variant that supports procedures, but uses a stack instead of a tape. * [[Brainfork]] adds a Y command to fork the current thread. * [[Fm]] edits a string on alphabet {0,1,...,m-1} (m >= 2). * [[FRAK]] assemble instructions to brainfuck code. * [[FukYorBrane]] and [[BF Joust]] pit two Brainfuck-like programs against each other, as in Core War (see [[Redcode]]). * [[Smallfuck]] operates only on bits and has no input- or output-commands. * [[Bitter]] one-bit memory cells, four commands, equivalent to [[Smallfuck]] under certain circumstances * [[Spoon]] uses a Huffman coded set of instructions corresponding to Brainfuck's commands. * [[BrainDuino]] BF port on [http://en.wikipedia.org/wiki/Arduino Arduino] HW platform (based on Atmel's ATMega). Extended by two special I/O operations and special overflow protection. * [[Puzzlang]] turns every program into an exercise in patience and logic puzzle skills. The lone X operator becomes any of brainfuck's instructions, depending on the surrounding characters. * [[Alarm Clock Radio]] throws away the instructions to decrement the memory pointer or memory value. * [[Portal]] and [[Portal 2]] allows code-level pointer manipulation and theoretically implements the Wang-B Machine. * [[tbf]] is a language that can be compiled to Brainfuck. It includes variables, strings, macros and improved loops. * [[Grin]] adds more efficient arithmetic functions to Brainfuck. * [[tinyBF]] and its variant [[RISBF]] are brainfuck equivalents with only 4 opcodes. * [[Mindscrew]] could be considered an extension of pbrain which adds a separate tape for storing procedures. * [[Grawlix]] adds stack operations, decimal I/O, another loop structure, functions, multiply/divide by two Some other funny variants: * [[Ook!]] works exactly like brainfuck, except the syntax is in Orangutan. * [[Blub]] is the same for fish. * [[Matisse]] uses colors to merge brainfuck codes and program comments. * [[Brainloller]] has the same commands as brainfuck, except they're read from a png image. * [[COW]] is like Ook!, except with a bovine syntax. * [[Pi]] obfuscates Brainfuck instructions in random errors in pi digits. Some languages inspired by brainfuck, but with more major differences: * [[Aura]] requires data to be stored in the code space. * [[PATH]] and [[SNUSP]] attempt to combine brainfuck with [[Befunge]]. * [[Wierd]] arose out of an earlier attempt to combine brainfuck with Befunge. ==See also== * [[EsoInterpreters]], featuring several brainfuck interpreters written in other esoteric languages * [[BFBASIC]], a Basic to brainfuck compiler * [[C2BF]], a partially implemented C to brainfuck compiler * [[Binary lambda calculus]], featuring an 829 bit (under 104 bytes) Brainfuck interpreter * [[Brainfuck algorithms]] * [[Brainfuck constants]] * [[Brainfuck bitwidth conversions]] * [[BF instruction minimalization]] * [[Brainfuck code generation]] * [[Brainfuck implementations]] * [[BFO]], the first known brainfuck to brainfuck optimizer and compressor * [[:Category:Brainfuck]], a collection of brainfuck related articles on this wiki * [[:Category:Brainfuck derivatives]], languages based on brainfuck * [[Brainfuck minus -]], showing that ordinary brainfuck without the '-' instruction and cell range of 0-1 (without cell-wrapping!) is still Turing-complete ==External resources== * [http://www.muppetlabs.com/~breadbox/bf/ Brian Raiter's site] contains a summary, an informal standards guide, and a couple of interesting programs. * [http://www.iwriteiam.nl/Ha_BF.html Frans Faase's site] includes a proof that brainfuck is Turing-complete. * [http://www.hevanet.com/cristofd/brainfuck/ some brainfuck fluff] contains many interesting programs, a solid interpreter, and suggestions for programmers and implementors, among other things. * [http://esoteric.sange.fi/brainfuck/ The Brainfuck Archive] has a large selection of programs, implementations and utilities. * [http://sourceforge.net/forum/forum.php?forum_id=201037 Brainfuck Golf] is a contest with the goal of writing a shortest program to do a certain task; see [[golf]]. * [http://www.brain------------------------------------------------------fuck.com/ brain------------------------------------------------------fuck.com] features some interesting brainfuck programs. * [http://alx2002.free.fr/esoterism/brainfuck/brainfuck_en.html brainfuck tutorial] * [http://jonripley.com/brainfuck/executable.html Making executable BF programs], contains information on how to make executable brainfuck programs. * {{wayback|20111031121638|http://jonripley.com/i-fiction/games/LostKingdomBF.html|The Lost Kingdom}}, an adventure game in 2 megabytes of BF code generated with [[BFBASIC]]. ** The above [http://rdebath.github.io/LostKingdom/ converted to Javascript]. * [http://www.cs.cmu.edu/~dst/DeCSS/Gallery/css-brainfuck.txt Brainfuck CSS descrambler] (with comments), from the [http://www.cs.cmu.edu/~dst/DeCSS/Gallery/ Gallery of CSS Descramblers]. * [https://github.com/graue/esofiles/tree/master/brainfuck/ Brainfuck] in [[the Esoteric File Archive]], including [https://github.com/graue/esofiles/tree/master/brainfuck/impl/ implementations], [https://github.com/graue/esofiles/tree/master/brainfuck/src/ programs] and [https://github.com/graue/esofiles/tree/master/brainfuck/util/ utilities]. * [http://www.49-6-dev.net/takingovertheworlden.htm Taking-] and [http://www.49-6-dev.net/ftotwen.htm Finally Taking Over The World] are games written by hand in brainfuck. * [http://esoteric.sange.fi/ENSI/bf-implementors-epistle.html The Epistle to the Implementors] * [http://esosc.mroman.ch/ESOSC-2014-A2.TXT ESOSC-2014-A2: Normalized Brainfuck] ===Notable implementations=== For a complete list, see [[brainfuck implementations]]. * [http://main.aminet.net/dev/lang/brainfuck-2.lha Original distribution by Urban Müller] from the [http://www.aminet.net AmiNet] archive. Includes interpreter and compiler for the Amiga. The interpreter can be compiled with [http://gcc.gnu.org/ gcc] by removing line 43, which says ''chkabort();''. The associated [http://main.aminet.net/dev/lang/brainfuck-2.readme readme file] might also have some historical interest. * [http://code.google.com/p/awib/ Also Written In Brainfuck (Awib)] is an optimizing brainfuck compiler written in brainfuck, generates various conversions including i386 executable code for Linux. * [http://esotope-bfc.googlecode.com/ Esotope Brainfuck compiler] is an optimizing Brainfuck-to-C compiler written in Python, with well optimised code. * [https://www.vanheusden.com/misc/blog/2016-05-19_brainfuck_cobol_compiler.php Brainfuck] compiler/translator to COBOL or C. ====Interpreters in plain C==== * [http://sree.kotay.com/2013/02/implementing-brainfuck.html bffsree] is a optimizing interpreter that claims to be fastest in class. (No source code) * [http://mazonka.com/brainf/ Optimizing BF interpreter] is a very fast C interpreter, fastest in its class. <!-- * [http://swapped.cc/bf/ Moderately-optimizing BF interpreter] is a portable C interpreter, second fastest in its class. --> ====JIT Interpreters==== * [https://savannah.nongnu.org/projects/libbf libbf] is a very fast JIT interpreter, still very fast ten years later. * [https://github.com/rdebath/Brainfuck/tree/master/tritium Tritium] is a optimizing interpreter that claims to be fastest in all classes. (including plain C) * [https://github.com/Wilfred/bfc Wilfred bfc] is a fast interpreter written in [https://www.rust-lang.org/en-US/ Rust] using [http://llvm.org/ LLVM]. ====Hardware implementations==== * [http://www.clifford.at/bfcpu/bfcpu.html The Brainf*ck CPU Project] is a VHDL implementation of a brainfuck CPU * [http://grapsus.net/74/ Brainfuck on 74 series logic IC's ] [[Category:Turing tarpits]] [[Category:Low-level]] [[Category:Cell-based]] [[Category:Implemented]] [[Category:Languages]] [[Category:Brainfuck]] [[Category:1993]] [[Category:Turing complete]]'
Unified diff of changes made by edit (edit_diff)
'@@ -200,7 +200,7 @@ ===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. +The size of the cells and the cell array varies a lot in different implementations. A usual implementation will have 30000, either 8- or 32-bit 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). +Urban Müller's compiler used an array of 30000 8-bit 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. @@ -208,5 +208,5 @@ 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#Multiple_conversions|Brainfuck bitwidth conversions]] or the code below (which only works correctly with 8bits). +Even with wrapping cells code can be written that depends on the cell size for example [[Brainfuck_bitwidth_conversions#Multiple_conversions|Brainfuck bitwidth conversions]] or the code below (which only works correctly with 8 bits). <font color="#c000c0">+</font><font color="#804000">[[</font><font color="#c000c0">-</font><font color="#008000">&gt;</font><font color="#804000">]</font><font color="#c000c0">-</font><font color="#804000">[</font><font color="#c000c0">-</font><font color="#008000">&lt;</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c000c0">-</font><font color="#804000">]</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&gt;</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;&gt;&gt;</font><font color="#c000c0">-</font><font color="#c00000">.</font><font color="#008000">&lt;&lt;&lt;&lt;&lt;</font><font color="#c000c0">++</font><font color="#c00000">.</font><font color="#008000">&gt;&gt;</font><font color="#c000c0">++</font><font color="#c00000">.</font> '
New page size (new_size)
36666
Old page size (old_size)
36681
Lines added in edit (added_lines)
[ 0 => 'The size of the cells and the cell array varies a lot in different implementations. A usual implementation will have 30000, either 8- or 32-bit 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.', 1 => 'Urban Müller's compiler used an array of 30000 8-bit 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).', 2 => 'Even with wrapping cells code can be written that depends on the cell size for example [[Brainfuck_bitwidth_conversions#Multiple_conversions|Brainfuck bitwidth conversions]] or the code below (which only works correctly with 8 bits).' ]
Unix timestamp of change (timestamp)
1523302849