Writing a code generator for Brainfuck

Martin Ueding

2023-05-02

Code & Zahlen

Last time we have written an interpreter for Brainfuck, this time we are going to start with the code generator.

Writing Brainfuck by hand is very tedious. That's likely where the language got its name from. And in this series of posts I didn't plan on writing my of it myself. Rather I want to write a program that generates the code for me and Brainfuck serves as a sort of assembly language.

Basic building blocks

First we need a few basic building blocks and think of a memory layout. The easiest way to manage variables it to use a stack on the infinite tape. This way we always know where to find a free variable.

In order to implement this, I create a Variable class that remembers the position and a TapeStack class which manages the stack of variables on the tape:

class Variable:
    def __init__(self, position: int) -> None:
        self.position = position


class TapeStack:
    def __init__(self) -> None:
        self._stack = []
        self._position = 0

    def register_variable(self) -> Variable:
        new_position = len(self._stack)
        new_variable = Variable(new_position)
        self._stack.append(new_variable)
        return new_variable

    def unregister_variable(self, variable: Variable) -> None:
        assert self._stack[-1] == variable
        self._stack.pop()

    def seek(self, variable: Variable) -> str:
        result = []
        while variable.position > self._position:
            result.append(">")
            self._position += 1
        while variable.position < self._position:
            result.append("<")
            self._position -= 1
        return "".join(result)

This stack can generate the seek instructions for the tape. It also remembers its position. We can just let the tape seek to any variable which we are intered in. This means that for the code generator we don't have to worry about the tape any more, we can already work with variables that have identity and are therefore entities. This makes building upon that much easier.

Wrapping basic instructions

Next we can wrap the basic instructions of the Brainfuck language. Let us take the increment of the current tape position. In our code generator it will be the increment of a variable. We implement this by asking the tape to seek to the variable and then append the + instruction to it. All generated code is represented as strings, so we can just use the string concatenation with the + operator.

def op_increment(tape: TapeStack, var: Variable) -> str:
    return tape.seek(var) + "+"

The other instructions are wrapped in a similar way:

def op_decrement(tape: TapeStack, var: Variable) -> str:
    return tape.seek(var) + "-"


def op_input(tape: TapeStack, var: Variable) -> str:
    return tape.seek(var) + ","


def op_output(tape: TapeStack, var: Variable) -> str:
    return tape.seek(var) + "."

The while loop is a bit different. For this we make the simplifying restriction that the tape position at for the [ and ] check must be the same. Therefore we have a variable with the condition and have to see to that before we hit either marker. And then we have the body of the loop. This needs to be a callable such that this can implicitly also use the tape to seek to different variables.

def op_while(tape, condition: Variable, body: Callable[[], str]) -> str:
    return tape.seek(condition) + "[" + body() + tape.seek(condition) + "]"

This then lets us think of an actual while loop with a condition stored in a particular variable. As long as variable is non-zero, the loop gets repeated. We need to manipulate that variable in the loop body. But as you can already see, we can think of variables and loops, not of a tape and a state machine!

First set of abstractions

Building these elementary operations we can create a couple more operations. For instance we can have a operation which clears a position on the tape:

def op_clear(tape: TapeStack, var: Variable) -> str:
    return op_while(tape, var, lambda: op_decrement(tape, var))

This is now pretty abstract. We have a while loop that repeats the body as long as the variable var is non-zero. And the loop body is just to decrement that variable.

This clearing allows us to build an if-statement. This is a while loop where we just clear out the condition variable after the loop. And with the abstractions that we already have in place, we can just write it like that:

def op_if(tape, condition: Variable, body: Callable[[], str]) -> str:
    return op_while(tape, condition, lambda: body() + op_clear(tape, condition))

Accumulation uses the while loop and the decrement and increment operations. We can use this for an in-place accumulation and subtraction. Note that changes the accumulator variable but also effectively clears out the summand variable.

def op_accumulate(tape: TapeStack, accumulator: Variable, summand: Variable) -> str:
    return op_while(
        tape,
        summand,
        lambda: (op_decrement(tape, summand) + op_increment(tape, accumulator)),
    )


def op_subtract(tape: TapeStack, accumulator: Variable, summand: Variable) -> str:
    return op_while(
        tape,
        summand,
        lambda: (op_decrement(tape, summand) + op_decrement(tape, accumulator)),
    )

Arithmetic operations

The next operations are going to be functions in the sense that they don't destroy their arguments. This will make it much easier to compose them. But as we have seen above, the accumulation destroys the argument. We therefore need a copy function.

And let me show the test case that I use for developing these functions. It builds a program with an input, the operation of interest, an output. Then it feeds that into a state machine together with an input. We expect that it has copied the element to the destination.

def test_copy() -> None:
    tape = TapeStack()
    source = tape.register_variable()
    destination = tape.register_variable()
    code = (
        op_input(tape, source)
        + fn_copy(tape, destination, source)
        + op_output(tape, destination)
    )
    assert StateMachine(code, [2]).run() == [2]

We can then write a copy function. It is a bit involved because we only have the destructive operations available for now. We create a temporary variable. The tape is set up in a way that it will guarantee us a free variable slot. We don't know whether it has been used before, so we better clear it.

def fn_copy(tape: TapeStack, destination: Variable, source: Variable) -> str:
    temp = tape.register_variable()
    code = (
        op_clear(tape, temp)
        + op_clear(tape, destination)
        + op_while(
            tape,
            source,
            lambda: (
                op_decrement(tape, source)
                + op_increment(tape, destination)
                + op_increment(tape, temp)
            ),
        )
        + op_accumulate(tape, source, temp)
    )
    tape.unregister_variable(temp)
    return code

This duplicates the variable from the source to destination and temp, but destroys the source. We then move the temporary variable back to the source and therefore have a perfect copy.

Using this copy operation we can then copy the inputs of each operation and make sure that the inputs are unchanged. This effectively makes for a pass-by-value. The plus function needs to make a copy of the left and right summand and then accumulates them onto the result variable.

def fn_plus(tape: TapeStack, result: Variable, left: Variable, right: Variable) -> str:
    left_copy = tape.register_variable()
    right_copy = tape.register_variable()
    code = (
        fn_copy(tape, left_copy, left)
        + fn_copy(tape, right_copy, right)
        + op_clear(tape, result)
        + op_accumulate(tape, result, left_copy)
        + op_accumulate(tape, result, right_copy)
    )
    tape.unregister_variable(right_copy)
    tape.unregister_variable(left_copy)
    return code

The minus function is the same, it just uses a subtraction. This requires that the left >= right holds, and there is no check for that.

def fn_minus(tape: TapeStack, result: Variable, left: Variable, right: Variable) -> str:
    left_copy = tape.register_variable()
    right_copy = tape.register_variable()
    code = (
        fn_copy(tape, left_copy, left)
        + fn_copy(tape, right_copy, right)
        + op_clear(tape, result)
        + op_accumulate(tape, result, left_copy)
        + op_subtract(tape, result, right_copy)
    )
    tape.unregister_variable(right_copy)
    tape.unregister_variable(left_copy)
    return code

Multiplication is a bit more involved. We need to have a loop and then copy and accumulate the right side as often as the left side says.

def fn_multiply(
    tape: TapeStack, result: Variable, left: Variable, right: Variable
) -> str:
    temp = tape.register_variable()
    left_copy = tape.register_variable()
    right_copy = tape.register_variable()
    code = (
        fn_copy(tape, left_copy, left)
        + fn_copy(tape, right_copy, right)
        + op_clear(tape, temp)
        + op_while(
            tape,
            left_copy,
            lambda: (
                op_decrement(tape, left_copy)
                + fn_copy(tape, temp, right_copy)
                + op_accumulate(tape, result, temp)
            ),
        )
    )
    tape.unregister_variable(right_copy)
    tape.unregister_variable(left_copy)
    tape.unregister_variable(temp)
    return code

With this we have three of the four elementary arithmetic operations. For division we still need a bit more, we need comparison operations. And for these we need logical operations.

Logical operations

A not function is not that easy, actually. It takes a couple of hoops to jump through. The copy and clear are just boilerplate code. As we only have an if for positive conditions but not the else, we need to construct it. We set the result to 1. But if the input was greater or equal than zero, we zero out the result again. If the input was zero, we skip over the zeroing out. This way gives us a not operation.

def fn_not(tape: TapeStack, result: Variable, condition: Variable) -> str:
    condition_copy = tape.register_variable()
    code = (
        fn_copy(tape, condition_copy, condition)
        + op_clear(tape, result)
        + op_increment(tape, result)
        + op_if(tape, condition_copy, lambda: op_clear(tape, result))
    )
    tape.unregister_variable(condition_copy)
    return code

Similarly we can construct the logical and. This actually needs to if conditions to get it done.

def fn_and(tape: TapeStack, result: Variable, left: Variable, right: Variable) -> str:
    left_copy = tape.register_variable()
    right_copy = tape.register_variable()
    code = (
        fn_copy(tape, left_copy, left)
        + fn_copy(tape, right_copy, right)
        + op_clear(tape, result)
        + op_if(
            tape,
            left_copy,
            lambda: op_if(tape, right_copy, lambda: op_increment(tape, result)),
        )
    )
    tape.unregister_variable(right_copy)
    tape.unregister_variable(left_copy)
    return code

The logical or is a bit easier. We count the non-zero elements. And if that count is non-zero, we set the result to 1 to indicate true.

def fn_or(tape: TapeStack, result: Variable, left: Variable, right: Variable) -> str:
    left_copy = tape.register_variable()
    right_copy = tape.register_variable()
    result_copy = tape.register_variable()
    code = (
        fn_copy(tape, left_copy, left)
        + fn_copy(tape, right_copy, right)
        + op_clear(tape, result)
        + op_clear(tape, result_copy)
        + op_if(tape, left_copy, lambda: op_increment(tape, result_copy))
        + op_if(tape, right_copy, lambda: op_increment(tape, result_copy))
        + op_if(tape, result_copy, lambda: op_increment(tape, result))
    )
    tape.unregister_variable(result_copy)
    tape.unregister_variable(right_copy)
    tape.unregister_variable(left_copy)
    return code

This is pretty cumbersome, but it allows us to build more complicated things with that.

Arithmetic comparison operators

In order to construct the operation left < right, I need to be able to get one of them to zero. I choose to write an operation which takes two numbers and subtracts one from each while both are non-zero. This way I will subtract the smaller number from both, making one zero and the other the difference between them.

def op_subtract_smaller(tape: TapeStack, left: Variable, right: Variable) -> str:
    temp_and = tape.register_variable()
    cond = lambda: fn_and(tape, temp_and, left, right)
    code = cond() + op_while(
        tape,
        temp_and,
        lambda: (op_decrement(tape, left) + op_decrement(tape, right) + cond()),
    )
    tape.unregister_variable(temp_and)
    return code

Using that I can write a less operation that uses the above operation. It then checks that the first number is zero and that the second number is non-zero.

def fn_less(tape: TapeStack, result: Variable, left: Variable, right: Variable) -> str:
    left_copy = tape.register_variable()
    right_copy = tape.register_variable()
    not_left = tape.register_variable()
    code = (
        fn_copy(tape, left_copy, left)
        + fn_copy(tape, right_copy, right)
        + op_clear(tape, result)
        + op_subtract_smaller(tape, left_copy, right_copy)
        + fn_not(tape, not_left, left_copy)
        + fn_and(tape, result, not_left, right_copy)
    )
    tape.unregister_variable(not_left)
    tape.unregister_variable(right_copy)
    tape.unregister_variable(left_copy)
    return code

Similarly one can construct left <= right, the comparison at the end is just slightly different.

def fn_less_equals(
    tape: TapeStack, result: Variable, left: Variable, right: Variable
) -> str:
    left_copy = tape.register_variable()
    right_copy = tape.register_variable()
    code = (
        fn_copy(tape, left_copy, left)
        + fn_copy(tape, right_copy, right)
        + op_clear(tape, result)
        + op_subtract_smaller(tape, left_copy, right_copy)
        + fn_not(tape, result, left_copy)
    )
    tape.unregister_variable(right_copy)
    tape.unregister_variable(left_copy)
    return code

The additional operations left > right and left >= right are then trivial to construct from the other ones:

def fn_greater(
    tape: TapeStack, result: Variable, left: Variable, right: Variable
) -> str:
    return fn_less(tape, result, right, left)


def fn_greater_equals(
    tape: TapeStack, result: Variable, left: Variable, right: Variable
) -> str:
    return fn_less_equals(tape, result, right, left)

Phew, that is a lot of code for basic operations. This is what they mean with “Turing tarpit”, where everything is possible, but useful things are not easy.

Division with remainder

Either way, we now have everything in place to write the division. This is going to be hard, so I write the test first. I have two numbers as divident and divisor as input and expect quotient and remainder as output.

def test_divide() -> None:
    tape = TapeStack()
    quotient = tape.register_variable()
    remainder = tape.register_variable()
    dividend = tape.register_variable()
    divisor = tape.register_variable()
    code = (
        op_input(tape, dividend)
        + op_input(tape, divisor)
        + fn_divide(tape, quotient, remainder, dividend, divisor)
        + op_output(tape, quotient)
        + op_output(tape, remainder)
    )
    assert StateMachine(code, [0, 1]).run() == [0, 0]
    assert StateMachine(code, [1, 1]).run() == [1, 0]
    assert StateMachine(code, [2, 1]).run() == [2, 0]
    assert StateMachine(code, [1, 2]).run() == [0, 1]
    assert StateMachine(code, [10, 3]).run() == [3, 1]
    assert StateMachine(code, [10, 5]).run() == [2, 0]

The division is not that hard with all these building blocks. Identifying the building blocks was the hard part. We subtract the divisor from the dividend as long as the divisor is greater or equal the divisor. For every subtraction we increment the quotient by one. What is left of the dividend is the remainder.

def fn_divide(
    tape: TapeStack,
    quotient: Variable,
    remainder: Variable,
    dividend: Variable,
    divisor: Variable,
) -> str:
    has_remainder = tape.register_variable()

    def condition():
        return fn_greater_equals(tape, has_remainder, remainder, divisor)

    code = (
        fn_copy(tape, remainder, dividend)
        + op_clear(tape, quotient)
        + condition()
        + op_while(
            tape,
            has_remainder,
            lambda: (
                fn_minus(tape, remainder, remainder, divisor)
                + op_increment(tape, quotient)
                + condition()
            ),
        )
    )
    tape.unregister_variable(has_remainder)
    return code

And this works, the generated code is just really long.

A realistic application

Let us now take Project Euler Solution 1: Multiples of 3 or 5, which is the following Python code:

def solution_naive() -> int:
    sum_of_multiples = 0
    for i in range(1000):
        if i % 3 == 0 or i % 5 == 0:
            sum_of_multiples += i
    return sum_of_multiples

This is a rather simple function and just a few lines of code. I need to express this in the operations and functions that we have defined above. This is the code that builds the expression:

def test_euler_1() -> None:
    tape = TapeStack()
    result = tape.register_variable()
    divisor_1 = tape.register_variable()
    divisor_2 = tape.register_variable()
    ceiling = tape.register_variable()

    quotient = tape.register_variable()
    remainder = tape.register_variable()
    is_divisible_by_3 = tape.register_variable()
    is_divisible_by_5 = tape.register_variable()
    is_divisible_by_either = tape.register_variable()

    def loop_body() -> str:
        return (
            fn_divide(tape, quotient, remainder, ceiling, divisor_1)
            + fn_not(tape, is_divisible_by_3, remainder)
            + fn_divide(tape, quotient, remainder, ceiling, divisor_2)
            + fn_not(tape, is_divisible_by_5, remainder)
            + fn_or(tape, is_divisible_by_either, is_divisible_by_3, is_divisible_by_5)
            + op_if(
                tape,
                is_divisible_by_either,
                lambda: fn_plus(tape, result, result, ceiling),
            )
            + op_decrement(tape, ceiling)
        )

    code = (
        op_input(tape, divisor_1)
        + op_input(tape, divisor_2)
        + op_input(tape, ceiling)
        + op_decrement(tape, ceiling)
        + op_while(tape, ceiling, loop_body)
        + op_output(tape, result)
    )

    assert StateMachine(code, [3, 5, 10]).run() == [23]

The generated Brainfuck code is the following. I have just wrapped it to have 70 characters per column, it is pretty impossible to read the structure from that even if it is indented nicely.

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

This is just a total mess. But it works for the numbers to 1000 and produces the correct result. Letting it compute it to a million just doesn't finish. My Python interpreter is inefficient and there are so many extra steps involed in the lengthy computation. However, it does work. And that was my goal.

We have seen how to write a code generator that can generate Brainfuck code for a state machine with reasonable abstraction.