Building a Brainfuck Interpreter in Swift

Brainfuck is an esoteric language with no practical uses. Yet with only eight operations, it is still just as capable as languages like C++ or Ruby. In this talk, Sam discusses his experience of building an interpreter for Brainfuck, and wraps up with a few gotchas he learned from trying to do so in Swift.

---

Introduction (0:00)

This talk about Swift, but it is also about this other very esoteric programming language called Brainfuck. Yes, I promise you, it is a real thing. One of the more impractical things I’ve done recently was building an interpreter for Brainfuck.

What is Brainfuck? (0:43)

So, what is Brainfuck? It’s a really cool programming language. No, it’s not useful, but that’s what is fun about it. It’s an utterly useless language, if you want to get anything practical done. But, theoretically speaking, it’s just as powerful as any other programming language. Any program that you can write in C++, Swift, or Ruby, you could write in Brainfuck.

It’s actually one of the smallest languages that fulfills this requirement called being “Turing complete”. Alan Turing is one of the godfathers of computer science, and one of the things that he postulated was the idea of a Turing machine.

A Turing machine is capable of encapsulating a certain set of computations. These are all the computations that you can do in a normal programming language. And, you can do all of them in Brainfuck as well. In that sense, Brainfuck is equivalent to all those other programming languages that we write every day.

Hello World (1:58)

Let’s take a look at a Brainfuck program.

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

This is Hello World. As you can see, it looks like utter nonsense. But it really isn’t — it’s quite elegant, because if you count, there are actually only six different characters used to construct that program. Brainfuck, in total, has eight.

Brainfuck Operations (2:34)

There are eight primitive operations that you can use to compose a Brainfuck program. There’s absolutely nothing superfluous to it. And so, what are those eight things?

1. > : Move data pointer one cell to the right
2. < : Move data pointer one cell to the left
3. + : Increment the value at the data pointer
4. - : Decrement the value at the data pointer
5. . : Print out the value at the data pointer (as ASCII)
6. , : Accept a byte of input and store it as the value at the data pointer
7. [ : Jump to the matching ] unless the value at the data pointer is 0
8. ] : Jump backwards to the matching [ unless the value at the data pointer is not 0

That’s actually all you need to express any valid program. Although there is no guarantee that writing such a program won’t be a horrifically painful process, there’s a very good reason that, for instance, Realm is not written in Brainfuck. That would be a nightmare. It would also probably be several tens of millions of lines of code. I’ve described this entire programming language on one slide. It’s a piece of cake, right?

Interpreter (3:48)

One of the first things you do, if you’re a nerd like me, is you write what’s called a “transpiler” for Brainfuck. You take that Hello World code and you translate it into another programming language: Brainfuck in, C out. That’s really easy. But, that’s just textual substitution, and for some reason, I decided not to stop there. I went to build a full-blown interpreter for Brainfuck in Swift.

What is an interpreter? It’s exactly what it sounds like. You feed it in some code, and it interprets it, translating it on the fly into operations in the host language, which for us, will be Swift. What does that mean in practice?

This means that every one of those instructions that we encounter while running our program will cause our interpreter to branch and execute a bit of native code. Then we read in the next instruction, and do that over and over and over again.

Virtual Machine (4:59)

We do this in the context of a virtual machine. Our virtual machine encapsulates state. This will be the entire state of our program as we run it. If you want to, you can think of it as the entire computer. It’s internally driven, so it’s not being poked at from the outside. Once our program is inside the virtual machine, it just runs on its own. It’s single use, so after we’ve run our program, the virtual machine will be “dirtied” with the state from that run.

What’s the interface to our VM? We need to feed it in a string, it does some stuff, and then, we can tell it to run, and it will run that program. If we think back to those eight primitive operations, we operate on stuff in Brainfuck through a whole big buffer of data and a pointer into that data. That’s it. So, we have a bunch of data. And because this is Swift, it’s all going to be unsafe. We have a pointer into that data which starts off at the very beginning. Then, we add in an array of the commands that our VM knows how to run, which will look like this:

class VM {
    init?(program: String)
    func run()
    var data: UnsafeMutablePointer<UInt8>
    var dataPointer: Int = 0
    let commands: [Command]
}

VM Commands (6:38)

Think back to the commands mentioned earlier: we can increment the data pointer, we can decrement it, we can increment what’s pointed to by it, decrement that, we can output things, we can input things, we can start a loop, and we can end a loop.

Wikipedia actually has a really cool chart showing you exactly how you’d translate a Brainfuck program into C. That chart would take up fewer characters than this paragraph.

Naïve approach (7:23)

What’s the naïve approach to actually running our interpreter once we’ve parsed out those commands?

public func run() {
    while instructionPointer != program.endIndex {
        if let command = Command(rawValue: String(program[instructionPointer])) {
            command.execute(self)
        }
        instructionPointer++
    }
}

Well, while we’re not at the end of the program, we grab a command off the offset from our instruction pointer, and we execute that command in the context of our VM. We bump the instruction pointer, and we run that over and over and over again. Keep in mind that there can be loops in this.

It turns out that that is super slow. This is because the beginning and end of a loop, those two commands have an arbitrary linear complexity. Every time you go to end a loop, you have to scan back to find the start of the loop.

That gets really slow, especially when you’re doing it over and over and over again. And, of course, we have extra layers of indirection. So, for each command that we’re executing, we’re calling a bunch of Swift functions. Yes, Swift is fast, but there’s still overhead to function calls. We’re doing a bunch of work every time that we don’t necessarily have to be doing. How do we make our interpreter faster?

Threading (Not That Kind) (9:23)

We do something called “threading”. A threaded interpreter is characterized by the fact that it pre-computes all of the conditional jobs in it. Instead of each time that we hit the start or end of the loop and scanning through to find the jump target, we’ll figure that all out ahead of time, because that doesn’t change while our program is running. We can validate our program before running it instead of while running it.

If we have an ill-formed program, which, in the case of Brainfuck, can only happen when you don’t have balance, left and right brackets. We can tell that ahead of time, as opposed to accepting invalid input, and then things just blowing up. This is pretty much the entirety of what building the threaded interpreter looks like:

var index = 0
var pairs = [Int]()
for command in commands {
    switch command {
        case .LoopStart(_):
            pairs.append(index)
        case .LoopEnd(let endBox):
    if pairs.count == 0 {
        fatalError("invalid program")
    }
    let start = pairs.removeLast()
    switch commands[start] {
        case .LoopStart(let startBox):
            startBox.val = index
        endBox.val = start
        default:
            fatalError("invalid program")
    }
    default: ()
    }
    index++
}
if pairs.count != 0 {
    fatalError("invalid program")
}

I substituted in fatal errors for actual error handling, but the idea remains the same. So, we go through, we iterate through all the different commands that we have. Normal commands, we can leave alone. But “loop start” and “loop end” commands we have to balance.

And we do so, basically, by treating these jump targets as a stack. As soon as we hit a loopStart, we push something onto the stack. When we hit a loopEnd, we pop that top loop start off the top of the stack, and match the two up. If ever there are no matching pairs of brackets, we say, “Okay, that’s an error, it’s an invalid program”. We can do this because we know that each left bracket needs to be balanced with a right bracket.

So, we maintain a stack of jump targets that are left brackets. Every time we see a left bracket, we push something onto the stack. Every time we see a right bracket, we pop it off the stack. We match up the indices. This gives us some sort of input validation, but it’s not great. We can either say, “Yes, this is a valid program,” or “Fatal error, no, this is invalid.”

If you’re used to actually writing production code, this might seem unacceptable, and rightly so. Real compilers and interpreters add a whole bunch of complexity to be able to do proper error handling, and be able to give you error messages and not segfault every time you try…

Oh, wait, they do sometimes segfault every time you try to compile something. That’s sort of the bare bones of building a Brainfuck interpreter. What would be the next steps?

Next Steps (12:41)

Of course, all we really care about is speed. The easiest thing to make our program faster will be roll up the adjacent commands. Let’s say we see increments and decrements next to each other. Well, we can combine them: no need to always increment by one, decrement by one. Addition works just like normal, so if you have +1+1+1+1, we could combine that into just being +4. Same thing when we’re moving the data pointer. That would be a nice speed up, but the really big thing would be getting rid of the need to run Swift code.

Interpreters Are Slow (13:43)

Well, it turns out that all interpreters are slow. That whole interpretation part of being an interpreter, it takes time. You’ve got a function call for each command, possibly multiple. You’ve got branches inside those function calls. And, you basically pay continuous penalties for the niceties of developing a normal programming language for every command while your program is running.

Imagine that instead of running a program that just outputs Hello World — which is going to be fast no matter what — imagine we were trying to write something that runs for a long time. Well, maybe we want to pay a bigger penalty up front and have our program run faster for the next hour or the next year, as it’s running on a server.

And finally, there’s an overhead to running stuff in a host language. With Swift, mainly ref-counting is a pain. I ran into a bunch of issues with the compiler not being able to provide ref-counting calls. I experienced about 30% of execution time being spent retaining and releasing the single VM object, which is pretty painful.

Let’s not write an interpreter. Let’s use compiled code, because compiled code is fast. And even better, because of course, we want to do something in Swift, let’s compile it just in time.

JIT (15:32)

That would mean that we can keep the niceties of being able to say, “Okay, here’s my command line.” That takes the program, you feed it in, and it just runs it. No need to invoke a compiler which produces an executeable. Just-in-time compilers are really cool. They’re commonly referred to as “JIT” compilers. How would I theoretically go about building a JIT compiler for anything in Swift?

Step one: you start off by allocating a whole bunch of space to place your program. Step two: you make it writable. Step three: you write machine opcodes into that space. If you think that trying to get the Swift compiler to agree that your program is valid is hard, imagine having to write out Hex opcodes by hand. This is how you build a compiler. It’s painful.

Then you protect that space; you make it executable. Already, we’re unable to do this on, let’s say, iOS, because Apple doesn’t let us mark arbitrary pages as executable. And then, we do this casting magic because Swift doesn’t play nicely with function pointers. And then we call it, and just no.

Swift Gotchas (17:32)

What are some of the “gotchas” of trying to do this all in Swift? Number one, as I already mentioned, ARC. ARC is pretty great. I love ARC. It’s not meant for this. For performance critical code that you’re hitting potentially tens or hundreds of thousands of times or millions of times, you want it to be fast, and you don’t want any overhead that, as the developer, you know is unncessary.

Swift strings — they’re great in that Swift strings are unicode aware. They know about characters versus code points versus extended graphing clusters. All that’s wonderful, but it does make dealing with them, let’s say for the purposes of interpreting code, to be rather difficult. Another is the need to use unsafe mutable pointers everywhere if we again, want to avoid memory overhead. C arrays are wonderful, and Swift just kind of makes it a bit harder to use them.

The other one is mutability. One of the nice things about when I was building up the threaded interpreter is that I built up these commands, and then I started filling in more information on them as I went through. Swift enums don’t like this, so I bowed my head in shame and wrote a little class called Mutable Box, which is exacftly what it sounds like. It’s a class that has a single variable. And it’s variable, so it’s mutable.

Trapping arithmetic, as I went around trying to run some of the Brainfuck programs that I found around on GitHub, they were all segfaulting as I ran them. And that was not very much fun. Well, it turns out that’s because most people who have written Brainfuck programs are running them in Brainfuck interpreters written in C, and C does not have trapping arithmetic by default. That means that you can overflow from 255 to zero. You can underflow from zero to 255. We’re talking about unsigned bytes. Swift kind of makes it a bit annoying. You can’t just say i++ because that will trap.

Finally, bounds checking. I did not handle this in my interpreter, so you, in theory, could write a malicious Brainfuck program that will try and write beyond the bounds of the data buffer that I have set up. There are, in theory, ways around checking this. We could validate it at runtime; that would be slow. We could put guard pages before and after to make sure that we’re not overwriting any of the user’s data. But, in the end, building this interpreter in Swift was pretty fun, and also pretty painful.

Languages like C and C++ are meant to allow programmers to say, “Listen, I know what I’m doing.” And that’s an ability you kind of want when you’re building something really low-level. You’re trying to optimize for performance when you know a lot more context about what’s going to be happening than the compiler does.

Open Source (21:40)

The interpreter I wrote is open source: it’s on my GitHub here. The code is not excellent and it has no test whatsoever, but it’s there. [Sam gives a short demonstration of his interpreter.]

Q&A (22:35)

Q: Sam, you said that this was difficult. Why would you do such a thing?

Sam: I built this entirely for fun. As I started off by saying, anything Brainfuck-related is entirely impractical. There is absolutely no use to what I wrote, other than the fact that I wrote an interpreter for a Turing complete language, which is kind of cool. And, at least for me, I do this as kind of a stepping stone to being able to write much more complicated pieces of software that do roughly the same thing. Which is, you take a bit of text in, and you run a program from it.

Q: What would you say is a better language to build an interpreter or compiler like this, if you had to do it for real?

Sam: So, one of the first projects I ever tried to do in Swift (this was when Swift 1.0 was still in beta) is I stayed up late on a Sunday night, and I tried building a scheme interpreter in pre-1.0 Swift. This did not go over very well. But, schemes are one of my favorite family of languages. They’re very simple and almost practical. Schemes are the dominant family of LISP languages. And so, you have a lot more complexity in them, but you can actually start to write programs that a normal person can understand.

Q: Would you recommend building something that is a bit simpler,like a parser, in Swift, at this stage? Except for cases where you need a lot of performance, would you think it’s also inappropriate for similar or unrelated reasons?

Sam: Building this was one of the “gotchas” I touched upon, but dealing with string manipulation in Swift right now is a bit of a challenge. It’s not straightforward, because you have strings. A string has a UTF-8 view, a UTF-16 view, and a character view. You have to know which of those you want to use, which of them is going to be more performant, and which of them is going to work as expected. I think that’s still kind of a sore spot for the language. Nothing that couldn’t be fixed by someone who’s a bit more experienced with parsing and with unicode, sitting down and writing a little abstraction layer over it. But, for now, I’d recommend against using Swift to do that, unless Swift is already your go-to language.