Müller's Brainfuck

Implementation of programming language Brainfuck

This is a classic implementation of Brainfuck, written by its author Urban Müller. The distribution includes a compiler for Amiga OS, an interpreter written in C and several examples.

Examples:

Hello, World!:

Example for versions EsCo 0.511 (Brainfuck), Müller's Brainfuck 2.0

There are lots of ways to say “Hello, World!” in Brainfuck. Here is the simplest one: use only one memory cell, and change its value to ASCII-code of each letter in row. Each line of the example prints one letter. 

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
+++++++++++++++++++++++++++++.
+++++++.
.
+++.
-------------------------------------------------------------------.
------------.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++.
++++++++++++++++++++++++.
+++.
------.
--------.
-------------------------------------------------------------------.

Hello, World!:

Example for versions EsCo 0.511 (Brainfuck), Müller's Brainfuck 2.0

In this example we use three memory cells — first for uppercase letters ‘H’ and ‘W’, second for lowercase letters and third for special characters ‘,’, ‘ ‘ and ‘!’ — and three index cells to shorten the notation of ASCII-codes changes. The memory used looks like this:

(index cell 1) (uppercase letters cell) (index cell 2) (lowercase letters cell) (index cell 3) (special characters cell) 

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

Fibonacci numbers:

Example for versions EsCo 0.511 (Brainfuck), Müller's Brainfuck 2.0

This example uses iterative definition of Fibonacci numbers. A high-level description of what it does is: store two last numbers in variables c4 and c5 (initially c4=0, c5=1), print the number stored in c5 (this operation takes the major part of the code), calculate next number (c6 = c5+c4), and move the numbers sequence one number back (c4 = c5, c5 = c6). A low-level description is given in the comments, notation “cXvY” meaning that after execution of the commands in the line the data pointer is at cell X, and the value at this cell is Y. A total of 12 memory cells is used.

This example uses one minor cheat: classic Brainfuck interpreter uses byte variables to store values of memory cells, so Fibonacci numbers 14 through 16 will cause overflow. Writing long arithmetics in Brainfuck is a bit of overkill, so in this example we assume that memory cells can store integer values. 

++++++++++++++++++++++++++++++++++++++++++++		c1v44 : ASCII code of comma
>++++++++++++++++++++++++++++++++			c2v32 : ASCII code of space
>++++++++++++++++					c3v11 : quantity of numbers to be calculated
>							c4v0  : zeroth Fibonacci number (will not be printed)
>+							c5v1  : first Fibonacci number
<<							c3    : loop counter
[							block : loop to print (i)th number and calculate next one
>>							c5    : the number to be printed

							block : divide c5 by 10 (preserve c5)
>							c6v0  : service zero
>++++++++++						c7v10 : divisor
<<							c5    : back to dividend
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]			c5v0  : divmod algo; results in 0 n d_n%d n%d n/d
>[<+>-]							c5    : move dividend back to c5 and clear c6
>[-]							c7v0  : clear c7

>>							block : c9 can have two digits; divide it by ten again
>++++++++++						c10v10: divisor
<							c9    : back to dividend
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]				c9v0  : another divmod algo; results in 0 d_n%d n%d n/d
>[-]							c10v0 : clear c10
>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]c12v0 : print nonzero n/d (first digit) and clear c12
<[++++++++++++++++++++++++++++++++++++++++++++++++.[-]] c11v0 : print nonzero n%d (second digit) and clear c11

<<<++++++++++++++++++++++++++++++++++++++++++++++++.[-]	c8v0  : print any n%d (last digit) and clear c8
<<<<<<<.>.                                              c1c2  : print comma and space
							block : actually calculate next Fibonacci in c6
>>[>>+<<-]						c4v0  : move c4 to c6 (don't need to preserve it)
>[>+<<+>-]						c5v0  : move c5 to c6 and c4 (need to preserve it)
>[<+>-]							c6v0  : move c6 with sum to c5
<<<-							c3    : decrement loop counter
]
<<++...							c1    : output three dots

Factorial:

Example for versions EsCo 0.511 (Brainfuck), Müller's Brainfuck 2.0

This example uses iterative definition of factorial. Last calculated factorial is stored in variable c6 and on each step it is multiplied by next number (stored in c5). A low-level description is given in the comments, notation “cXvY” meaning that after execution of the commands in the line the data pointer is at cell X, and the value at this cell is Y. A total of 13 memory cells is used.

This example uses one minor cheat: classic Brainfuck interpreter uses byte variables to store values of memory cells, so 6! and further will cause overflow. Writing long arithmetics in Brainfuck is a bit of overkill, so in this example we assume that memory cells can store integer values. Besides, factorial length grows fast along with execution time of Brainfuck program, so the above code is limited to calculating and printing first 7 factorials. 

+++++++++++++++++++++++++++++++++			c1v33 : ASCII code of !
>++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++				c2v61 : ASCII code of =
>++++++++++						c3v10 : ASCII code of EOL
>+++++++						c4v7  : quantity of numbers to be calculated
>							c5v0  : current number (one digit)
>+							c6v1  : current value of factorial (up to three digits)
<<							c4    : loop counter
[							block : loop to print one line and calculate next
>++++++++++++++++++++++++++++++++++++++++++++++++.	c5    : print current number
------------------------------------------------	c5    : back from ASCII to number
<<<<.-.>.<.+						c1    : print !_=_

>>>>>							block : print c6 (preserve it)
>							c7v0  : service zero
>++++++++++						c8v10 : divizor
<<							c6    : back to dividend
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]			c6v0  : divmod algo borrowed from esolangs; results in 0 n d_n%d n%d n/d
>[<+>-]							c6    : move dividend back to c6 and clear c7
>[-]							c8v0  : clear c8

>>							block : c10 can have two digits; divide it by ten again
>++++++++++						c11v10: divizor
<							c10   : back to dividend
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]				c10v0 : another divmod algo borrowed from esolangs; results in 0 d_n%d n%d n/d
>[-]							c11v0 : clear c11
>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]c13v0 : print nonzero n/d (first digit) and clear c13
<[++++++++++++++++++++++++++++++++++++++++++++++++.[-]] c12v0 : print nonzero n%d (second digit) and clear c12
<<<++++++++++++++++++++++++++++++++++++++++++++++++.[-]	c9v0  : print any n%d (last digit) and clear c9

<<<<<<.							c3    : EOL
>>+							c5    : increment current number
							block : multiply c6 by c5 (don't preserve c6)
>[>>+<<-]						c6v0  : move c6 to c8
>>							c8v0  : repeat c8 times
[
<<<[>+>+<<-]						c5v0  : move c5 to c6 and c7
>>[<<+>>-]						c7v0  : move c7 back to c5
>-
]
<<<<-							c4    : decrement loop counter
]