Brainfuck

Analysis and Assesment of Gateway Process (1983)
US Army Operational Group

Brainfuck is a programming language design using a . It is conceptually simple — almost entirely minimal, in fact — https://en.wikipedia.org/wiki/Counter_machine

syntax

Brainfuck syntax uses eight single-character tokens. These matching one-to-one with the language's instructions, the meaning of which follows in semantics. As a generative grammar,

<program>	=	ε
	\|	<program>+
	\|	<program>-
	\|	<program><
	\|	<program>>
	\|	<program>[
	\|	<program>]
	\|	<program>.
	\|	<program>,

Starting from empty, ε, a Brainfuck program +><- is generated ε, +, +>, +><, +><-.

semantics

The behavior of a Brainfuck program is modeled in two pieces, closely linked: a data model, and an instruction model orchestrating the data.

data

Data is modeled as a sequence of memory cells, each storing an integer. The sequence extends infinitely in both directions, each cell initially containing a zero.

	0	0	0	0	0
			↑

Only a single data cell is ever in use, a data pointer (rendered ↑) remembers which.

instruction

The instruction model is a finite sequence of Brainfuck tokens: this is a Brainfuck program.

+	[	>	+	<	-	]	.
↑

Similarly to the data tape, a single instruction is in use, an instruction pointer, initially at the first instruction, remembers which.

runtime

	data	instruction
`+`	the data under the data pointer is incremented	the instruction pointer advances
`-`	the data under the data pointer is decremented	the instruction pointer advances
`<`	the data pointer shifts to the left	the instruction pointer advances
`>`	the data pointer shift to the right	the instruction pointer advances
`[`	if the data under the data pointer is zero	the instruction pointer advances past its matching `]`
`]`		the instruction pointer advances back to its matching `[`
`.`	the data under the data pointer is output	the instruction pointer advances
`+`	the data under the data pointer takes an input	the instruction pointer advances

theory

Brainfuck is particularly close to a fundamental theoretical model of computation, the Turing Machine.

implementation notes

syntax

As a consequence of a small set of single-character tokens, comments are included simply by skipping non-tokens.

+++[~*~a commented embedded in program text~*~>++>+<<-]

For improved syntax handling, a parser of Brainfuck syntax may catch and flag programs with the meaningless use of un-matched [ ].

There is not a singular authoritative source for semantics, but a large diversity of Brainfucks; the presentation here avoids common refinements ammenable to practical implementation in place of a simple symbolic representation. Common variations include

picking a useful format for the input/output instructions ,/., e.g. ASCII.
memory cells using underlying machine memory cells, e.g. in place of unbounded integers, an 8-bit computer using 8-bit cells with wrapping arithmetic.
data pointer as machine memory cell or machine pointer, e.g. a (neccessarily finite) data tape with counted cells, > incrementing and < decrementing the pointer.
exceptions or runtime errors, e.g. if < or > run outside a finite data memory, or if - underflows unsigned memory cells.

further

While diverse, the Brainfucks considered might still be considered classical. Further variations exist: adding operators,

references

Brainfuck constants esolangs wiki. Web-based interpreter and single-step visual debugger minond.xys. An unofficial Brianfuck standard muppetlabs.com.