Why I Wrote a Book About Interpreters

30 Nov 2016

Last week I’ve self-published my first book called “Writing An Interpreter In Go”, which you can get at interpreterbook.com. I want to tell you a little bit about why I chose to write this particular book.

Sometimes I jokingly call the summer of 2015 my “Summer Of Lisp”. But, honestly, I’m only half joking when I say this. It really was a great and Lispy summer programming-wise: I was working through the final chapters of Structure And Interpretation Of Computer Programs (SICP), which I began studying at the beginning of that year, was totally fascinated by Lisp, enamored by Scheme and also starting to learn Clojure by working through the fantastic The Joy Of Clojure.

SICP had an immense impact on me. It’s a wonderful book, full of elegant code and ideas; it hearkens “to a programming life that if true, would be an absolute blast to live in”. Especially the fourth chapter made a lasting impression. In this chapter, Abelson and Sussmann show the reader how to implement the so called “meta-circular evaluator” - a Lisp interpreter in Lisp. “Mesmerized” is probably the word I’d use to describe myself while reading this chapter.

The code for the meta-circular evaluator is elegant and simple. Around 400 lines of Scheme, stripped down to the essentials and doing exactly what they are supposed to. It’s a beautiful piece of software. I asked a friend to design a poster for me, containing only the source code for the meta-circular interpreter, beautifully formatted. That poster hung next to my office desk for over a year.

But soon I discovered why it’s only 400 lines. The code presented in the book skips the implementation of an entire component - the parser. Huh. But how does a parser work then? I was stumped. I really wanted to know how that parser works. And I almost never want to skip anything I don’t know yet. I really want to know how things work, at least in a rough sense. Black boxes and skipping things always leave me wanting to dig deeper.

In that same summer I also read Steve Yegge’s “Rich Programmer Food”, in which he argues what a worthwhile goal it is to learn about and to understand compilers. Let me quote my favorite passage:

That’s why you need to learn how [compilers] work. That’s why you, yes you personally, need to write one.

[…]

You’ll be able to fix that dang syntax highlighting.

You’ll be able to write that doc extractor.

You’ll be able to fix the broken indentation in Eclipse.

You won’t have to wait for your tools to catch up.

You might even stop bragging about how smart your tools are, how amazing it is that they can understand your code […]

You’ll be able to jump in and help fix all those problems with your favorite language.

That blog post flipped a switch. Determined as if there was some kind of weird challenge I said to a friend of mine: “I’m going to write a compiler”. I believe, I was gazing into the distance while saying this. “Alright”, he said rather unimpressed, “do it.”

Without having taken a compiler course in college or even having a computer science degree I set out to write a compiler. The first goal, I determined, is to get a foot in the door and write an interpreter. Interpreters are closely related to compilers, but easier to understand and to build for beginners. But most importantly, this time there would be no skipping of anything. This interpreter will be built from scratch!

What I found was that a lot of resources for interpreters or compilers are either incredibly heavy on theory or barely scratching the surface. It’s either the dragon book or a blog post about a 50 line Lisp interpreter. The complete theory with code in the appendix or an introduction and overview with black boxes.

Every piece of writing helped though. Slowly but surely I was completing work on my interpreter. The tiny tutorials, the slightly longer blog posts and the heavy compiler books - I could find something useful in all of them.

Nevertheless I was getting frustrated. There needs to be a book, that … One day, I said to the same friend, who earlier so enthusiastically encouraged me to write a compiler:

“You know what… I’d love to write a book about interpreters. A book that shows you everything you need to know to build an interpreter from scratch, including your own lexer, your own parser and your own evaluation step. No skipping of anything!”

Somehow this turned into me giving myself a motivational speech.

“And with tests too!”, I continued, “Yeah! Code and tests front and center! Not like in these other books, where the code is an unreadable mess that you can’t get to compile or run on your system. And you don’t need to be well versed in mathematical notation either! It should be a book any programmer can read and understand.”

It’s entirely possible that I was banging my fist on the table at this point. Calmly, my friend said: “Sounds like a good idea. Do it.”

And here we are, 11 month later, and “Writing An Interpreter In Go” is available to the public. It has around 200 pages and presents the complete and working interpreter for the Monkey programming language, including the lexer, the parser, the evaluator and also including tests. No black boxes, no 3rd party tools and no skipping of anything. Nearly every page contains a piece of code. I’m really proud of this book.