What?
I wanted to learn a bit of Go, so I decided to make a Brainfuck interpreter. Brainfuck is an esoteric programming langugage that only has 8 commands. Since Brainfuck is so simple, building an interpreter is a decent way for me to get my toes wet in a new language. I haven’t made one before, so I figured I’d give it a shot.
Digression describing Brainfuck
In case you don’t want to read the Wikipedia page for Brainfuck, I’ll summarize things a bit here. The idea is to make a simple Turing machine. You start with a big tape of cells and a data pointer pointing at the first cell. Then you go through the commands in the program and apply each command to the tape.
The two main commands, + and -, increment or decrement whatever cell the data pointer points to.
I usually call “whatever cell the data pointer points to” the “current” cell.
You can move the data pointer left or right along the tape with < and >.
There are also loops, which use [ and ] to enclose the code you want to loop over.
The closing ] jumps execution back to the matching opening [ unless the current cell is 0.
For example, the loop [-] will decrement the current cell all the way down to 0 and then continue with the rest of the program
Here’s a simple program that moves one cell into another.
Put 2 in the first cell
++
Increment the second cell and decrement the first cell
until we have moved the whole value over
[>+<-]
| 0 | 0 |
^
| 1 | 0 |
^
| 2 | 0 |
^
| 2 | 0 |
^
| 2 | 1 |
^
| 2 | 1 |
^
| 1 | 1 |
^
| 1 | 1 |
^
| 1 | 2 |
^
| 1 | 2 |
^
| 0 | 2 |
^
That’s six of the eight commands.
Almost done!
The last two handle input and output.
The , command reads one byte into the current cell and . outputs the byte in the current cell.
As you can imagine, it’s borderline impossible to write useful code in Brainfuck. But people do a lot of difficult things. Erik Bosman even wrote a program to display the Mandelbrot set.
Actually writing the interpreter
It was pretty easy to get the interpreter working. The only slight challenge was finding the matching bracket for a loop, which is not a difficult problem in the grand scheme of things. Most of the implementations out there focus on the classic programming quiz of checking a full string for any mismatched brackets. That’s similar but not exactly what I wanted to do. I needed to search from one bracket to find the index of the matching bracket.
I made a pretty silly error here. My first attempt reversed the entire program in memory to search backwards instead of just iterating backwards by decrementing an index. That hurt performance so much that I couldn’t run some of the more complicated Brainfuck programs.
I think I did that because I’m used to Python.
In Python, the whole name of the game is using built-in functions as much as possible.
Usually, those functions are way faster than anything I can write in Python because they’re often written in C.
So I think my brain went use reverse() -> oh there's no reverse() -> implement reverse().
Luckily this error was obvious enough that I didn’t need to profile anything to find the bottleneck.
Implementing a Brainfuck interpreter is a common project, so there are a lot of online debuggers for Brainfuck. It felt a bit luxurious to have a answer key like that to work with. I’m glad they exist. This one helped me out a lot. I also used this one a bit and was blown away by the speed. At first I though I must’ve made even more glaring performance errors somewhere, but then I noticed their note.
The code is converted to JavaScript code and then run in a web worker, which speeds up execution at lot.
Maybe I’ll look into compiling Brainfuck to other languages in the future.
One last thing I’ll mention is a little hack I came up with for debugging.
I added an extra $ command to my interpreter that would dump the state.
That way, I could put a $ in existing programs to debug them a bit.
It was kind of neat to be so vertically integrated.
How did I do?
Well, Urban Müller’s original Brainfuck compiler was only 296 bytes. He later got it down to 240 bytes. Let’s see how mine stacks up.
% du -k bf_interpreter
2172 bf_interpreter
% bc
>>> 2172 * 1024
2224128
2.2 megabytes. Oof. They don’t make ’em like they used to.
Learning Go
I don’t think this project really exercised the main features of Go. There isn’t any concurrency in my interpreter, so I didn’t use any goroutines or channels. I didn’t use any dependencies outside the standard library either. I also intentionally avoided web stuff like JSON and HTTP for this first project. I think those are a large part of how people use Go in the real world.
The parts I did use seemed to work pretty well. It was easy to look up any errors I came across, and AI assistants were able to give me decent example code. The assistants would usually give me code to solve a common programming quiz question and then I could adapt that to fit the problem I was actually trying to solve. It’s definitely a step down from Python where the AI assistants know the ins and outs of specific libraries like Pandas, but it got the job done.
One quirk of Brainfuck is that each cell is only one byte. Some of the programs I came across intentionally underflow that byte to wrap around to 255. That would’ve been a pain in Python, but it Just Worked™ in Go.
I really like the packaging system where I can tag a release on GitHub to make it available to anyone else who wants to use it. That’s super convenient. There are probably all sorts of problems with it that I don’t know about, but it was nice as a first experience.
What next?
I have the basic syntax down and can write stuff that at least runs, but there are few things I still don’t really understand about Go.
Just like everyone else, my main stumbling block is error handling.
I tried to make a custom error, but I couldn’t figure out how to actually write a function that returns _, err so that the calling function can do the infamous if err != nil check.
I looked in the standard library for examples, where I happened to see a bunch of errors.New().
That worked fine, so I did that instead.
I don’t know whether that’s a new thing or a deprecated thing or what—it worked so I ran with it.
The directory structure is another mystery that eluded me.
I noticed that a lot of Go projects put their code in a cmd/ directory.
I don’t understand what that does or why you would want to do that.
It didn’t come up in any of the docs or StackOverflow posts I read, so I just didn’t do it.