Writing a Brainfuck compiler in Java

Brainfuck is probably the only programming language in the world that lives up to its name, I’ve always been intrigued about how it works but never felt confident enough to dive deeper.

After starting to read this brilliantly written blog post by Thorsten Ball everything seemed to click into place. The language, while difficult to read, isn’t that complicated when you scratch under the surface.

In fact, it all felt very familiar, a few years ago I wrote an emulator for the Gameboy Color, which was fun, but a lot bigger than the 8 bit machine that Brainfuck runs on.

So after reading about half of Thorsten’s post I set to work on implementing the basics, which didn’t take long and was soon up and able to run the simplest of Brainfuck applications, hello world

$ cat helloworld.b
++++++++[>++++[>++>+++>+++>+<<
<<-]>+>+>->>+[<]<-]>>.>---.+++
++++..+++.>>.<-.<.+++.------.-
-------.>>+.>++.
$ java -jar target/bf.jar helloworld.b
Hello World! 

The most interesting aspect of the blog post happened later on, when the author begins to introduce the idea of creating a compiler for the Brainfuck code and apply some simple optimisations to make programs run faster.

• Fold chains of the same instructions into one (e.g. ++++ becomes +4)
• Make loops determine their jump points up front without having to recalculate this every time

I decided not to cheat and look at what the author had implemented, and went away and did this myself. We only diverged on the way I did the second optimisation around loops, my version does a first pass through the code to translate the tokens into Operation objects and fold chained instructions, then goes through on a second pass to determine the loop jump points if they haven’t been set already.

private void optimiseJumps(List<Operation> operations) throws CompileException {
    int instructionPointer = 0;
    while (instructionPointer < operations.size()) {
        Operation operation = operations.get(instructionPointer);

        switch (operation.instruction) {
            case JUMP_IF_ZERO:
                if (operation.argument == MIN_VALUE) {
                    int endLoopPos = findEndOfLoop(instructionPointer, operations);
                    operations.set(instructionPointer, new Operation(operation.instruction, endLoopPos));
                }
                break;
            case JUMP_IF_NOT_ZERO:
                if (operation.argument == MIN_VALUE) {
                    int startLoopPos = findStartOfLoop(instructionPointer, operations);
                    operations.set(instructionPointer, new Operation(operation.instruction, startLoopPos));
                }
                break;
        }
        instructionPointer++;
    }
}

His version is more efficient as he does it all in one pass, but I like my initial stab at the problem.

Writing this was hugely rewarding and seeing the mandlebrot program go from 55 seconds before optimisations, down to 15 seconds was really cool and has given me a taste to start learning properly how compilers and optimisations work.

Running mandlebrot.b in less than 15 seconds

You can find my implementation here, I decided to write it properly with unit tests, and used some sample programs written by Daniel b Cristofani to verify my implementation, which was great as they highlighted some bugs in my code.

Maybe at some point in the future I’ll look into further optimisations that can be applied, but for now this has been a fun little weekend project.