Thorsten Ball - Writing An Interpreter In Go

Thorsten Ball

I want to use these lines to express my gratitude to my wife for supporting me. Shes the reason youre reading this. This book wouldnt exist without her encouragement, faith in me, assistance and her willingness to listen to my mechanical keyboard clacking away at 6am.

Thanks to my friends Christian, Felix and Robin for reviewing early versions of this book and providing me with invaluable feedback, advice and cheers. You improved this book more than you can imagine.

The first sentence of this introduction was supposed to be this one: Interpreters are magical. But one of the earliest reviewers, who wishes to remain anonymous, said that sounds super stupid. Well, Christian, I dont think so! I still think that interpreters are magical! Let me tell you why.

On the surface they look deceptively simple: text goes in and something comes out. They are programs that take other programs as their input and produce something. Simple, right? But the more you think about it, the more fascinating it becomes. Seemingly random characters - letters, numbers and special characters - are fed into the interpreter and suddenly become meaningful. The interpreter gives them meaning! It makes sense out of nonsense. And the computer, a machine thats built on understanding ones and zeroes, now understands and acts upon this weird language we feed into it - thanks to an interpreter that translates this language while reading it.

I kept asking myself: how does this work? And the first time this question began forming in my mind, I already knew that Ill only be satisfied with an answer if I get to it by writing my own interpreter. So I set out to do so.

A lot of books, articles, blog posts and tutorials on interpreters exist. Most of the time, though, they fall into one of two categories. Either they are huge, incredibly heavy on theory and more targeted towards people who already have a vast understanding of the topic, or they are really short, provide just a small introduction to the topic, use external tools as black boxes and only concern themselves with toy interpreters.

One of the main sources of frustration was this latter category of resources, because the interpreters they explain only interpret languages with a really simple syntax. I didnt want to take a shortcut! I truly wanted to understand how interpreters work and that included understanding how lexers and parsers work. Especially with a C-like language and its curly braces and semicolons, where I didnt even know how to start parsing them. The academic textbooks had the answers I was looking for, of course. But rather inaccessible to me, behind their lengthy, theoretical explanations and mathematical notation.

What I wanted was something between the 900 page book on compilers and the blog post that explains how to write a Lisp interpreter in 50 lines of Ruby code.

So I wrote this book, for you and me. This is the book I wish I had. This is a book for people who love to look under the hood. For people that love to learn by understanding how something really works.

In this book were going to write our own interpreter for our own programming language - from scratch. We wont be using any 3rd party tools and libraries. The result wont be production-ready, it wont have the performance of a fully-fledged interpreter and, of course, the language its built to interpret will be missing features. But were going to learn a lot.

Its difficult to make generic statements about interpreters since the variety is so high and none are alike. What can be said is that the one fundamental attribute they all share is that they take source code and evaluate it without producing some visible, intermediate result that can later be executed. Thats in contrast to compilers, which take source code and produce output in another language that the underlying system can understand.

Some interpreters are really small, tiny, and do not even bother with a parsing step. They just interpret the input right away. Look at one of the many Brainfuck interpreters out there to see what I mean.

On the other end of the spectrum are much more elaborate types of interpreters. Highly optimized and using advanced parsing and evaluation techniques. Some of them dont just evaluate their input, but compile it into an internal representation called bytecode and then evaluate this. Even more advanced are JIT interpreters that compile the input just-in-time into native machine code that gets then executed.

But then, in between those two categories, there are interpreters that parse the source code, build an abstract syntax tree (AST) out of it and then evaluate this tree. This type of interpreter is sometimes called tree-walking interpreter, because it walks the AST and interprets it.

What we will be building in this book is such a tree-walking interpreter.

Were going to build our own lexer, our own parser, our own tree representation and our own evaluator. Well see what tokens are, what an abstract syntax tree is, how to build such a tree, how to evaluate it and how to extend our language with new data structures and built-in functions.

Every interpreter is built to interpret a specific programming language. Thats how you implement a programming language. Without a compiler or an interpreter a programming language is nothing more than an idea or a specification.

Were going to parse and evaluate our own language called Monkey. Its a language specifically designed for this book. Its only implementation is the one were going to build in this book - our interpreter.

Expressed as a list of features, Monkey has the following:

• C-like syntax
• variable bindings
• integers and booleans
• arithmetic expressions
• built-in functions
• first-class and higher-order functions
• closures
• a string data structure
• an array data structure
• a hash data structure

Were going to take a detailed look at and implement each of these features in the rest of this book. But for now, lets see what Monkey looks like.

Here is how we bind values to names in Monkey:

Besides integers, booleans and strings, the Monkey interpreter were going to build will also support arrays and hashes. Heres what binding an array of integers to a name looks like:

And here is a hash, where values are associated with keys:

Accessing the elements in arrays and hashes is done with index expressions:

The let statements can also be used to bind functions to names. Heres a small function that adds two numbers:

But Monkey not only supports return statements. Implicit return values are also possible, which means we can leave out the return if we want to:

And calling a function is as easy as youd expect:

A more complex function, such as a fibonacci function that returns the Nth Fibonacci number, might look like this:

Note the recursive calls to fibonacci itself!

Monkey also supports a special type of functions, called higher order functions. These are functions that take other functions as arguments. Here is an example: