I’m attending GopherCon in New York City this week. I will be giving a lightning talk on Wednesday August 27 based on my blog post about writing a Lua interpreter in Go. If you’re going to be there, come and say hi! For accessibility, I’m publishing the slides ahead of time and including a full transcript of the talk. I’ll update this post to include the recording once it becomes available.

Hi everyone! My name is Roxy Light. If you want to follow along, the slides are available on my blog, which you can find at 256lights.com.

Today I’m going to be talking about how I built a Lua interpreter in Go and why I had a good time with it. I’m not the first person to write a Lua interpreter in Go, and chances are, you probably won’t end up writing one. But I always find it neat to see how Go works for things that aren’t enterprise-y HTTP/RPC servers.

So quickly: why did I do this? Well, I’m writing a build tool called zb. It’s cool, you should check it out.

In zb, I wanted to give users a full scripting language to write their build targets in. Thing is, I needed some custom hooks that existing interpreters didn’t have. Namely, I needed to store dependency information in strings. By doing this, users don’t have to write out an explicit dependency list for their build targets. You might be familiar with this technique if you’ve used Terraform or Nix.

Long story short, I picked Lua. The reference implementation of Lua is written in C and is called “PUC-Rio Lua” after the university that published it. My implementation follows PUC-Rio Lua for some parts, but diverges completely for others.

If you haven’t written an interpreter before, creating one may seem really daunting. Don’t worry, I got you. At a high level, it’s three steps: lexing, parsing, executing. There’s a lot of elbow grease that doesn’t fit in this talk, but you can read my blog post for more of that. I split each of the steps into separate Go packages.

1. Read from an io.Reader and split into words. Think of this like a streaming strings.Fields function.
2. Parse the tokens into bytecode, which is represented as a slice of uint32s.
3. Run that bytecode.

Go’s packages rocked to keep implementation details of each part of this process hidden from the other parts. I can even parse the bytecode without having an interpreter, which is something you can’t do with PUC-Rio Lua.

Let’s zoom into steps 1 and 2.

On the top, we have some Lua source code.

In Step 1 (the lualex package), we split up the source into “tokens”. This is a term of art for words, punctuation, numbers, and string literals. We also strip out comments here.

In Step 2 (the luacode package), we turn the tokens into instructions. Again, these are uint32s under the hood, but in this talk, I’ll show you them in “disassembly”. These instructions mean:

1. Load 42 into “register” 0
2. Add 3 to the value in “register” 0 and store it in “register” 1
3. And finally, if the values weren’t numbers, call the metamethod “__add” (6).

… “wait, values weren’t numbers? What else can they be?" you may be asking.

Let’s talk about Lua’s types. You’ve got:

• nil
• booleans
• numbers
• strings (which remember, we’re adding dependency information to)
• userdata (which is just an opaque Go value)
• tables (which are basically map[value]value, but my implementation makes them ordered)
• Lua functions (which are mostly a list of uint32s, the bytecode!)
• and Go functions

In the PUC-Rio Lua implementation, a value is a complex C union with a lot of branching. What rocks is that in Go, I can just use an interface type and have methods like string conversion on each value type.

Now that we have our bytecode and our data types ready to go, we’re on to Step 3: bytecode execution. In a lightning talk, there isn’t enough time to go into how this works in depth, but if you’re interested, you can go read my blog post.

At a high level, we do a for-loop over the bytecode list and switch on the bottom 7 “op code” bits from the current bytecode. Standard Lua uses about 80 different op codes, so that means 80 different cases in this switch statement! (That’s the elbow grease I was talking about.) Each case does an operation and then moves the “program counter” forward.

Fairly bog-standard code, right?

Nothing that Go helps us with? …

… wrong! Turns out, the Go compiler optimizes this sort of giant switch statement using a technique called jump tables. So I can write this giant switch statement and Go helps make this faster than writing a bunch of individual if statements. Cool!

To recap:

• Go packages made it easy to organize code
• The type system eliminated the need for a lot of the book-keeping code in PUC-Rio Lua
• And the compiler made my code performant without having me jump through hoops

… I feel like I’m missing something.

[Pauses, then looks back at screen.] Oh right!

For such a complicated project, it was critical to be testing frequently, and Go’s testing package helped me spot check all sorts of things along the way. For example, I used the go-cmp package to quickly spot bugs in my parser by comparing my parser’s output with the output from the PUC-Rio Lua parser.

Something else that really helped: Go’s built-in performance tools. I don’t want my users to be waiting on their configuration loading: I want them to get to the build as fast as they can. I wrote a few microbenchmarks and then used the pprof tool to find where I was accidentally allocating memory when I didn’t need to. I absolutely love how easy it is to find out what’s going on in my code without even leaving VSCode. If you haven’t checked out pprof yet, give it a look.

Okay. Go rocks. I’m done gushing now.

Again, my name is Roxy Light, and you can check me out at 256lights.com. If you have any questions, come find me after the lightning talks are over. Thank you so much for listening, and thank you to GopherCon for having me.