BrainFuck Programming Language

BrainFuck - An Esoteric Turing-Complete Computer Programming Language

Who Created BrainFuck??
    Brainfuck was created in 1993 by Urban Müller in an attempt to make a language which could be used by the smallest compiler. A small compiler is important for portability on older computers with limited disk space. Despite its small size, Brainfuck is not really intended to be used as a "real" language because of the difficulty in writing and maintaining Brainfuck code. Although it is not professionally used, given enough time and patience, any program could be created using only its 8 instructions (sometimes less - depending on whether or not you chose to uses it I/O commands).

Language Specifications
    According to the original Brainfuck specifications, Brainfuck is supposed to operate on a machine with 30,000 bytes of data. There really isn't any reason to limit yourself to this small amount of memory. Doing so would prevent you from creating many complicated programs and would actually prevent many algorithmic processes from being solved, intentionally breaking the language's Turing Completeness. In theory however, for a computer to be actually be turing-complete it must have unlimited memory, but since this is unrealistic, we can still consider a machine to be turing-complete if it would be so if it had unlimited memory. But, no one has placed a limit to the amount of memory a computer is allowed to have, as was apperntly done to the Brainfuck language.
    To implement the Brainfuck language, whether by emulating on a PC or actually building a brainfuck processor, requires two 1-Dimensional arrays. Once again, according to Brainfuck documentation the elements (cells) of the array should be 1 byte in size, but the Brainfuck instruction set itself does not limit this and cell sizes of greater than one byte could be implemented. One of these arrays contains the Brainfuck program instructions, where each cell contains one instruction. The other array is similar to RAM in a modern computer except the memory cannot be accessed randomly and must be done sequentially from one address to the next. This memory array contains the bytes generated during run-time, similar to storing variables in modern computers. On powerup all of the cells in this array are set to zero. Both of these arrays have a "pointer" which indicates which memory cell is currently be worked on or looked at. Both of these pointers initially point to the first cell in the array, cell 0, on powerup. Often when The Pointer is mentioned, it is referring to the pointer to the memory (where variables are stored) rather than to the program memory. In fact, most of the time no one considers the Program Memory to actually have a pointer, however if you were to build a processor which was designed to understand the Brainfuck language, you would need to have a pointer for this Program Memory as well.

The Instruction Set

INTRUCTION SYMBOL	SYMBOL NAME (IN CASE YOU CAN'T SEE)	FUNCTION
+	PLUS	Increment the value at the Pointer.
-	MINUS	Decrement the value at the Pointer
>	GREATER THAN	Move the pointer forward
<	LESS THAN	Move the pointer backward
[	OPEN SQUARE BRACE	Jump forward to the instruction after the corresponding `]` if the value at the pointer is zero.
]	CLOSE SQUARE BRACE	Jump backward to the instruction after the corresponding `[` if the value at the pointer is not zero.
.	PERIOD	Output the value at the pointer.
,	COMMA	Put value of input (keyboard or other type of input device) into the cell at the pointer.

Programming in Brainfuck
    Before beginning to program in Brainfuck, first be warned that Brainfuck is a difficult language to program in, as its name probably suggests. Even though it only has 8 instructions that are easy to memorize, it still takes some skill to create a program in Brainfuck. Since relatively simple programs and simple tasks take a relatively large amount of time and thought to create in Brainfuck, it is not used professionally. However, it is still theoretically possible, although not easy, to create any program with this language, given enough memory. It is recommened that you have prior programming knowledge before reading ahead, however you may be able to proceed without it. Understanding this language will give you an idea of how other computers could be built as well and how computers in general operate, although modern computers are much more optimized and may have several hundred or thousands of instructions to perform complex operations in a single setp. Brainfuck, having only 8 instructions, does extremely simple functions each step, which is why it requires many steps before a simple function can be performed.
    Lets begin by examining a small program written in Brainfuck.

    I've used spaces between the symbols to make them easier to see, the spaces would not normally be included when writting a program. However, a good interpreter of Brainfuck should disregard and symbol which is not part of the language. Therefore, when adding comments to your code, no special character is required.

+ + + + + [ . - ]
    Even with understanding of the instructions of Brainfuck, this simple program may still be hard to understand. We will evaluate it on instruction at a time to figure out what it does.

    The start of the program is a series of five " + ". Because The Pointer starts off at the 0 cell / first cell in the array, these 5 pluses increment the value of The Pointer by one, five times, for a total increase in value of five!

\/ + + + + + [ . - ]	This is the Program, which is stored as an array with as many entries as necessary to hold the program. This program only requires 9 instruction or 9 cells of program memory. The \/ above the first instruction marks the instruction currently being considered by the computer.
\/ 0 0 0 0 0 0 0 0 0	This is the free memory of the machine, all initially zero when powered up. The pointer here is often referred to as The Pointer and initially points to the first memory location in the array.

Since the first instruction in the program is " + " the computer "increments the value at The Pointer." To follow what has just happened, here is the state which would follow the execution of the first instruction in the program...

\/ + + + + + [ . - ]	The first instruction has already been executed. The computer automatically selects the next instruction to be executed.
\/ 1 0 0 0 0 0 0 0 0	The + command has raised the value at The Pointer by one, but The Pointer has not moved and remains still pointing to the first cell in the array.

As you can see, Brainfuck performs very simple instructions. Here is the result after executing the first five + instructions...

\/ + + + + + [ . - ]	The first five instructions have been executed. The computer now is ready to execute the [ instruction which we have not discussed yet.
\/ 5 0 0 0 0 0 0 0 0	The Pointer has still not moved since neither a > or a < has been executed yet. Since five + instruction have been executed the value at The Pointer has been raised by 1 five times.

The next instruction to be executed is the [ command which is one of the more complicated ones to follow, but it still is rather simple. In this case, since the value of at The Pointer is not zero, the [ command does nothing and is simply a waste of time, but in cannot be removed since when the value at the pointer is zero it will perform an important function.

\/ + + + + + [ . - ]	Since the value at The Pointer was not zero (it was five) this instruction did not perform a function. If the value at The Pointer had been a zero the computer would have skipped passed the cooresponding ]. In this particular example, such an action would cause an end of program since there are no more instructions passed that point.
\/ 5 0 0 0 0 0 0 0 0	No change was performed on this array.

The .instruction simple outputs the value at The Pointer. In this case since The Pointer is pointing to the first cell in the array which has a value of five, the number 5 would be displayed. Exactly how this is done depends on how you decide to implement the machine. Often people use a cell size of 1 byte (8-bits) and use the ASCII encoding. In my example I have decided to only deal with numeric values (0-255) for 8-bits. If there were an actual computer running this program you might have this 8-bit value be output on 8 pins leading from the Brainfuck processor. Alternatively, if you were emulating this system on an existing desktop computer you may decide to have the value printed to the screen. Also, for ease of programming you may wish to implement 16-bit registers to directly perform functions on numbers between 0-65535.

\/ + + + + + [ . - ]	The execution of the . command displayed the value at The Pointer, in this case 5. This is the first output from the machine to the user.
\/ 5 0 0 0 0 0 0 0 0	No change was performed on this array.

The - command is opposite of the + command. Here, executing the - instruction decreases the value at The Pointer by 1, making it a 4. The state so far can be observed below.

\/ + + + + + [ . - ]	The computer is now ready to execute the last instruction in the program.
\/ 4 0 0 0 0 0 0 0 0	The value at The Pointer was lowered by one from executing the - command.

Now, there is one instruction remaing in the program, but is it really the end of the program? At first glance, one may think so, but consider what the function of the ] instruction is. Jump backward to the instruction after the corresponding [ if the value at the pointer is not zero. Since the The Pointer is clearly not pointing to a value of zero the machine jumps back to the instruction right after the cooresponding [

\/ + + + + + [ . - ]	Since the value at The Pointer was not zero the computer moved the program pointer back to the instruction after the cooresponding [ command.
\/ 4 0 0 0 0 0 0 0 0	No changed was performed on this array.

    If this program were continued it would continue to loopbetween these two brackets, the [ and ] instructions, eventually lowering the value at The Pointer to zero, in which case the program would end because there would be no more instructions afterward.
    Looking at only the output displayed by this machine using this program and ignoring the inner details of the processor, we could say the the result of this machine was the following:
    5
    4
    3
    2
    1
<<END OF PROGRAM>>

    NOTE: The reason a 0 was not displayed before the end of the program was because the - command was used after the . command. Had they been reverse an output like this could have been achieved...
    4
    3
    2
    1
    0

YOU ARE AT: Brainfuck - PART 1

BACK: ESOTERIC LANGUAGES

NEXT: BRAINFUCK - PART 2

Coming Soon:

How to create a Brainfuck simulator on your computer
How to program a microncontroller to act like a Brainfuck processor
How to build a Brainfuck processor

>>HOME:

>>OTHER CATEGORIES: