Brainfuck

From Esolang
Revision as of 12:51, 11 August 2006 by Rune (talk | contribs) (→‎History: links)
Jump to navigation Jump to search

Brainfuck is probably the most famous of the esoteric programming languages, and has inspired the creation of a host of other languages. Due to the fact that the last half of its name is often considered one of the most offensive words in the English language, it is sometimes referred to as brainf***, brainf*ck 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:

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

History

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

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

Examples

Hello, world!

This program prints out the words Hello World!: 

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

Move value

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

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

Without indentation and comments the same code looks like this: 

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

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 three versions of the program below, one for each of the most common implementations (see Implementation issues).

EOF returns 0: 

,[.,]

EOF returns -1: 

,+[-.,+]

No change on EOF: 

,[.[-],]

Computational class

The brainfuck language is Turing-complete, meaning that it is in the same computational class as universal Turing machines. This, plus its dearth of commands, makes it a canonical example of a Turing tarpit.

This can be shown in a number of ways. The following formulations require the tape to be unbounded, but allow the value in each cell to be bounded:

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 Minsky machines into brainfuck programs (at the link below).

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

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

The size of the cell array varies a lot in different implementations. The original compiler used an array of 30000 cells, while the later interpreter used only 5000.

The original implementation used bytes (0-255, wrapping around) for the memory cells. Most implementations do likewise, but some have been known to allow negative numbers or use bignums, allowing a memory cell to hold an arbitrarily large number.

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

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

Extensions

Some implementations also recognize the following symbols as meaningful: 

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

All characters other than ><+-.,[]#! are generally considered comments and ignored.

Algorithms

See Brainfuck algorithms, Brainfuck constants.

Related languages

In publishing the formal programming language P'' in 1964, Corrado Böhm used six symbols precisely equivalent to the brainfuck commands +, -, <, >, [, and ], 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. Other people have been interested in variations of the language for theoretical purposes, pedagogical applications, etc. Some of the more interesting variants:

  • Brainfork adds a Y command to fork the current thread.
  • Fm edits a string on alphabet {0,1,...,m-1} (m >= 2).
  • FukYorBrane pits two Brainfuck-like programs against each other, as in CoreWars.
  • Smallfuck operates only on bits and has no input- or output-commands.
  • Spoon uses a Huffman coded set of instructions corresponding to Brainfuck's commands.

Some of the less interesting variants:

  • Ook! works exactly like brainfuck, except the syntax is in Orangutan.
  • 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.
  • Brainloller has the same commands as brainfuck, except they're read from a png image.

See also

External resources

Gallery of CSS Descramblers with comments.

Implementations

Hardware

Retrieved from "https://esolangs.org/w/index.php?title=Brainfuck&oldid=5758"