Aah Brainfuck…

Brainfuck is possibly my new favorite language. Brainfuck is an esoteric programming language that consists of just eight instructions. It’s sort of like hardcore assembly in a sense. I’ve been into Brainfuck for a long time but I recently started learning how to actually write code in Brainfuck; I want to write a language that compiles to Brainfuck and maybe a VM of sorts. We shall see.

But in this article I want to cover the basics of Brainfuck and how we can write code in Brainfuck.

The Basics

Brainfuck is an incredibly minimalistic language in syntax and functionality. Brainfuck can be thought of as a simple CPU. It contains an instruction pointer (where we are in the Brainfuck code) and a data pointer. The data pointer is used to read and write memory. Memory is typically assumed to be unsigned bytes (although implementations vary). In everything I do, I work under the assumption of unsigned eight-bit integer values for memory cells and an instruction and data pointer of any sufficient size.

Then we have the eight instructions (the instruction pointer is implicit):

>      dp++
<      dp--
+      mem[dp]++
-      mem[dp]--
,      mem[dp] = readchar()
.      putchar(mem[dp])
[      if(mem[dp] == 0) ip = address of matching ] + 1
]      if(mem[dp] != 0) ip = address of matching [ + 1

Now, let’s start by taking a look at a simple program and disecting how it works:

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

This program, when run, prints Hello.

++++++++++

memory layout before:   0 0
                        ^

memory layout after:   10 0
                        ^


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

memory layout before:  10  0
                        ^

memory layout after:    0 70
                        ^ 

A [ ] pair is sort of like an if statement combined with a while loop whose condition can change at runtime. They can be used to clear a cell: [-]; this works by looping on the cell and decrementing it as such:

while(mem[dp]) {
    mem[dp]--
}

So, if we want to multiply two cells we can use a loop which clears the first number and increments the second cell by some multiple.

++                                
[                                 
    >                                 
    +++                               
    <                             
    -                             
]                                 

Pseudocode:

mem[dp] += 2
while(mem[dp]) {
    dp++
    mem[dp] += 3
    dp--
    mem[dp] -= 1
}

That is everything you need to understand the Hello program.

Common Operations

When writing Brainfuck code, there are some patterns that tend to come up; lots of the same algorithms.

Say we have a value in the first cell and we want to move it to the second cell:

+++

memory layout before: 0 0
                      ^

memory layout after:  3 0
                      ^


[>+<-]

memory layout before: 3 0
                      ^

memory layout after:  0 3
                      ^

Notice that this algorithm moves the value in the first to the second cell and clears the first cell.

Now say we want to copy the value in the first cell the the second cell, without clearing the first cell. To do this we move the value from the first cell to the second cell and to another temporary cell simultaneously. We then move the value in the temporary cell back to the first cell.

+++

memory layout before: 0 0
                      ^

memory layout after:  3 0
                      ^


[>+>+<<-]

memory layout before: 3 0 0
                      ^

memory layout after:  0 3 3
                      ^


>>[<<+>>-]

memory layout before: 0 3 3
                      ^

memory layout after:  3 3 0
                          ^ 

Control Flow

Control Flow in Brainfuck is surprisingy rich. We tend to treat 0 as false and 1 as true, but it is possibly to use any non-zero number to represent true.

Therefore, if statements are fairly trivial:

[
    [-]
    ...
]

It is assumed that the data pointer starts on the cell that is the condition of the if statement. If it is non-zero, we set it to zero and run whatever code is in the if statement’s body. The clear can be a - instead if it is assumed that true is always represented as 1. The clearing can happen at the beginning or the end of the if statement as long as the correct cell is cleared.

This concept can be extended to for loops or while loops trivially:

++++
[
    -
    ...
]

That code will run its body four times in this case.

Additionally, Brainfuck’s control flow is somewhat unique in that the condition can actually change since it is simply checking a value in memory at the data pointer, and the data pointer can change. For example:

+++
[
    >
    ...     
]

In this example the condition starts at the first cell but changes to the second cell. When the condition changes, an unbalanced loop is created. These can be useful:

+>++>+<<

memory layout before: 0 0 0 0
                      ^

memory layout after:  1 2 1 0
                      ^

Now say we want to find the next clear cell:

[>]          

memory layout before: 1 2 1 0
                      ^

memory layout after:  1 2 1 0
                            ^

The problem with unbalanced loops such as this is that, if you’re not careful, you can easily lose track of where the data pointer is. They are useful and sometimes necessary however, so just make sure you know what you’re doing when using them.

Boolean Operations

Say we want to check if the first cell is non-zero and then write that as a boolean value encoded as 0 or 1 in the second cell:

+++

memory layout before: 0 0
                      ^

memory layout after:  3 0
                      ^

[
    [-]
    >+<
]

memory layout before: 3 0
                      ^

memory layout after:  0 1
                        ^

Now how about boolean or?

+

memory layout before: 0 0 0
                      ^

memory layout after:  1 0 0
                      ^

[
    [-]
    >+<
]

memory layout before: 1 0 0
                      ^

memory layout after:  0 1 0
                      ^

>
[
    [-]
    >+<
]

memory layout before: 0 1 0
                      ^

memory layout after:  0 0 1
                        ^

How about boolean and?

+>+<

memory layout before: 0 0 0
                      ^

memory layout after:  1 1 0
                      ^

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

memory layout before: 1 1 0
                      ^

memory layout after:  0 0 1
                        ^

As you can see, writing basic operations is Brainfuck is actually pretty simple and intuitive once you get into the right mindset. That said, once you want to do arrays, things get difficult, but, I digress.

Making it Easier

Writing Brainfuck code by hand is crucial for understanding the fundamentals of computing in such a restrained environment, and is needed to implement the most primitive operations, but, what can we do to make it easier to build more complex, higher-level software?
In the next post we will look at one possibility: using Lua as a “macro language” or “preprocessor” to aid writing Brainfuck code. We’ll also take a look at some more simple operations such as numeric comparison. And, if not in the next post, in the one after it, we will finally figure out a scheme for implementing arrays; it’s not as easy as you might think.

That’s all for now.

Part 2