Analysis of the Programming Language Brainf*ck

    In the early 1990's, Urban Müller wanted to create a unique programming language. Instead of focusing on goals such as performance, readability, portability, and the like, he focused on an entirely different goal. A goal, in fact, that had probably never been set for any language. He wanted to create a language which could be compiled with the smallest compiler possible. Also, the language had to be Turing complete, meaning the language had to be powerful enough to calculate all possible functions. Thus, if a language is Turing complete, any program in existence today could be written in the given language.
    Müller succeeded in his task in 1993 with the generation of Brainf*ck. Brainf*ck is a Turing complete language that has only eight instructions. There are no objects, no classes, no methods, no variables, and no functions. In fact, nearly all of the normal language constructs are gone. However, these facets allow Brainf*ck to have the smallest compiler ever written: 172 bytes for the Amiga OS 2.0

    Brainf*ck has only eight instruction. The instructions are as follows:
 

Instruction	C Equivalent	Description
<	p++;	Increment the pointer.
>	p--;	Decrement the pointer.
+	a[p]++;	Increment the byte at the pointer.
-	a[p]--;	Decrement the byte at the pointer.
.	putchar(a[p]);	Output the byte at the pointer.
,	a[p]=getchar();	Input a byte and store it in the byte at the pointer.
[	while(a[p]) {	Start loop: Execute delimited code until the byte at the pointer equals zero.
]	}	End loop: Jump back to the matching "[".
#	NA	This is not a part of the language, but a debugging command available in most implementations.

    The variable "p" represents a pointer where p = 0 at the start of every program, and a[p] represents the byte at the pointer. Only ASCII characters represented by the byte the pointer points to are recognized. You are given an array of 30000 bytes and a pointer that can be moved within the array. You can increment or decrement, by one, the byte at the pointer, as well as input or output any byte at the pointer. When the pointer equals zero, the program ends.
    Obviously, this is an imperative language. The information stored at various memory locations are changed with a step-by-step execution of the statements. In fact, Brainf*ck closely resembles an assembly language with its direct manipulation of memory contents.
 

    Here's a "Hello World!" program written in Brainf*ck:

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

    Readability

    Obviously, this program is completely unreadable as nothing about the program is apparent from casual inspection. Of course, readability was not a goal for Brainf*ck.

    Writeability

   Brainf*ck is as easy to write as it is hard to read. This is because there are only eight, single character commands to remember, and no command is redundant.

    Verifiability
            Again, Brainf*ck shines in this aspect. Since the most complicated component
        of Brainf*ck is the "while" loop and since most Brainf*ck programs are, by
        nature, small, verifiability of a program is usually achievable. The proof of the
        "while" loop depends upon determining the invariant, the condition by which the
        loop executes. There is only one invariant. It's the part of the array pointed to by
        the pointer. That invariant must be non-zero for the loop to execute. If it
        is zero when the loop condition is checked, the loop ends.

    Ease of Translation

    Since the language has an extremely regular structure, translation of the language into an executable is quite simple. In fact, this was the main objective of the language, and is verified by the fact that the compiler is only 172 bytes long. Also, there are many other compilers and interpreters available for Brainf*ck, a mark of its easy translatability. There are even many programs that translate Brainf*ck into other programming languages such as C, C++, Java, and Perl

    Lack of Ambiguity

    There is no ambiguity in Brainf*ck. The eight unique symbols have eight unique meanings with no possibility of change.

    Orthogonality

    Since nearly every instruction can be combined with every other instruction in any order, Brainf*ck is orthogonal. The only non-orthogonal instruction is the symbol "]" which must be paired up with the symbol "[".

    Support for Abstraction

    There is simply no support for abstraction. There are no abstract data structures. The eight instructions are all the programmer has and all the programmer will ever have.

    Portability

    Since Brainf*ck manipulates the memory of a machine directly, portability is a problem. For instance, Brainf*ck assumes the existence of a 30000 byte array. What if the machine can't provide that array? Then Brainf*ck can not be used. Also, there is no standardization of Brainf*ck.

    Here's a Brainf*ck program, written by the author of this article, that asks the user to enter his/her name and then displays that name backwards.

Leave a0 equal to zero
>

We're now pointing at a1
Set a1 equal to E
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Print out 'E'
.

Print out 'nter your name: '  all at a1
+++++++++++++++++++++++++++++++++++++++++.
++++++.
---------------.
+++++++++++++.

We'll make a2 a space and reuse it later
>++++++++++++++++++++++++++++++++.

Now go back to a1 and display the rest
'your'
<+++++++.
----------.
++++++.
---.

The space
>.<

'name: '
----.
-------------.
++++++++++++.
--------.
-------------------------------------------.
>.<

Get the user's name
Put each character in a5 and up
Ends when we read a new line character  - ASCII code 10
Thus the 10 minus symbols turn the new line character into null
>>>+[>,----------]

Display a new line character
++++++++++.

Print out the name in reverse
The loop stops when it encounters the 0 at a4
<[++++++++++.<]

End program with pointer at a0 = 0
[<]
 

This is the entire program without comments (as is custom):
>+++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++.++++++++++++++
+++++++++++++++++++++++++++.++++++.-------------
--.+++++++++++++.>++++++++++++++++++++++++++
++++++.<+++++++.----------.++++++.---.>.<----.----------
---.++++++++++++.--------.-----------------------------------
--------.>.<>>>+[>,----------]++++++++++.<[+++++++++
+.<][<]
 

    I'm really not sure what to make of Brainf*ck. One would never want to use Brainf*ck for any serious application. At first glance, Brainf*ck appears to be a replacement for Assembly language, but the entire reason for Assembly's existence is the absolute control it provides over a machine. Brainf*ck does not provide that level of control. At the same time, it lacks everything needed to replace any higher level language. Thus, Brainf*ck falls short there as well.
    Even though Brainf*ck seems to be an inferior language, I still had a great deal of fun writing the above program. There's just something beautifully simple about programming with eight instructions and no anomalies or exceptions. It stretches and exercises the brain a bit.
    I believe Brainf*ck could make an excellent teaching language, perhaps even as a primer to proper Assembly language. The student could get a very general feel for registers and pointer manipulation with Brainf*ck and then dive into serious Assembly language.

Brainf***. http://home.wxs.nl/~faase009/Ha_BF.html (Jan 23, 2001).

CHAOS COMPUTER CLUB COLOGNE.
   http://koeln.ccc.de/projekte/brainfuck/index-e.html (Jan. 24, 2001).

Green, Austin. Brainf*ck. Index of /~acm/helloworld. http://www.LaTech.edu/~acm/helloworld/brainfck.html (Jan 27, 2001).

Programming in Brainfuck. http://cydathria.com/bf/brainfuck.html. (Jan 27, 2001).

Raiter, Brian. Brainfuck: An Eight-Instruction Turing-Complete Programming
   Language. Muppetlabs. http://www.muppetlabs.com/~breadbox/bf/ (Jan 24, 2001).

Urban Mueller. README. http://www.nvg.ntnu.no/amiga/source/div/brainfuck.readme (Jan 23, 2001).