Writing A Compiler In Go

It's the sequel to … a programming language

Buy the first part for $29

Writing A Compiler In Go is the sequel to Writing An Interpreter In Go. It starts right where the first one stopped, with a fully-working, fully-tested Monkey interpreter in hand, connecting both books seamlessly, ready to build a compiler and a virtual machine for Monkey.

In this book, we use the codebase (included in the book!) from the first part and extend it. We take the lexer, the parser, the AST, the REPL and the object system and use them to build a new, faster implementation of Monkey, right next to the tree-walking evaluator we built in the first book.

The approach is unchanged, too. Working, tested code is the focus, we build everything from scratch, do baby steps, write tests firsts, use no 3rd-party-libraries and see and understand how all the pieces fit together.

It's a continuation in prose and in code.

Do you need to read the first part before this one? If you're okay with treating the code from the first book as a black box, then no. But that's not what these books are about; they're about opening up black boxes, looking inside and shining a light. You'll have the best understanding of where we're going in this book, if you know where we started.

Learn how to write a compiler and a virtual machine

Our main goal in in this book is to evolve Monkey. We change its architecture and turn it into a bytecode compiler and virtual machine.

We'll take the lexer, the parser, the AST and the object system we wrote in the first book and use them to build our own Monkey compiler and virtual machine … from scratch! We'll build them side-by-side so that we'll always have a running system we can steadily evolve.

Read a sample

What we end up with is not only much closer to the programming languages we use every day, giving us a better understanding of how they work, but also 3x faster. And that's without explicitly aiming for performance.

Here's what we'll do:

• We define our own bytecode instructions, specifying their operands and their encoding. Along the way, we also build a mini-disassembler for them.
• We write a compiler that takes in a Monkey AST and turns it into bytecode by emitting instructions
• At the same time we build a stack-based virtual machine that executes the bytecode in its main loop

View table of contents

We'll learn a lot about computers, how they work, what machine code and opcodes are, what the stack is and how to work with stack pointers and frame pointers, what it means to define a calling convention, and much more.

We also

• build a symbol table and a constant pool
• do stack arithmetic
• generate jump instructions
• build frames into our VM to execute functions with local bindings and arguments!
• add built-in functions to the VM
• get real closures working in the virtual machine and learn why closure-compilation is so tricky

The Monkey Programming Language

The implementation of Monkey we build in this book is markedly different from the tree-walking interpreter we built in Writing An Interpreter In Go, but Monkey stays the same.

At the end, Monkey will still look and work like this:

// Integers & arithmetic expressions
let version = 1 + (50 / 2) - (8 * 3);

// Strings
let name = "The Monkey programming language";

// Booleans
let isMonkeyFastNow = true;

// Arrays & Hashes
let people = [{"name": "Anna", "age": 24}, {"name": "Bob", "age": 99}];

// Functions
let getName = fn(person) { person["name"]; };
getName(people[0]); // => "Anna"
getName(people[1]); // => "Bob"

And it will still support recursive functions, conditionals, implicit and explicit returning of values:

let fibonacci = fn(x) {
  if (x == 0) {
    0
  } else {
    if (x == 1) {
      return 1;
    } else {
      fibonacci(x - 1) + fibonacci(x - 2);
    }
  }
};

The crown-jewel we'll build into our new Monkey implementation are closures:

// `newAdder` returns a closure that makes use of the free variables `a` and `b`:
let newAdder = fn(a, b) {
    fn(c) { a + b + c };
};
// This constructs a new `adder` function:
let adder = newAdder(1, 2);

adder(8); // => 11

Yes, we'll compile all of that to bytecode and execute it in a stack-based virtual machine. That not only works, but is also tremendous fun to build.

What readers are saying about this book:

"This is a very polished pair of books that together give a steady path to follow for learning some of the real techniques that are used to implement programming languages. They're both well above average for their depth, technical clarity, and accessibility. I've been recommending them to everyone I work with who wants to get involved in compilers."

Chris Seaton (@ChrisGSeaton)
Researcher at Shopify, PhD in Ruby, Founder of Truffle Ruby

"Thorsten has a wonderful gift — as you read his books, you'll feel as though you've discovered compilers, all on your own! As a self-taught engineer without a CS degree, I found myself led on a journey of learning, driven by the nuggets of 'why' that Thorsten shares alongside code.

I've recommended these books to many, and I won't hesitate to continue. Compilers, interpreters and programming languages may seem esoteric, but if you look closely, they're everywhere. The Monkey language is my go-to project whenever I learn a new programming language. There's no better way to take a new language through its paces!"

Lauren Tan (@potetotes)
Software Engineer

"Longing for implementing a compiler, but lacking the guidance? Then this book is for you. Thorsten offers invaluable mentorship for tackling the multiple challenges that arise when writing a single-pass compiler and a virtual machine to execute the resulting code, in a pragmatic and test-driven approach. After going over this book, you'll certainly feel inspired to go further, such as extending the compiler with code transformations of your own."

Ricardo Nabinger Sanchez (@rnsanchez)
Performance Engineer at Taghos Tecnologia

"Making is understanding. The book carefully teaches us how VM-backed interpreters work, while building our own compiler and virtual machine. Written in a TDD style, a step-by-step manner and with a humane tone. I've enjoyed the wonderful journey!"

Yoji Shidara (@darashi)
Programmer, English/Japanese Translator of Writing An Interpreter In Go

"I think that it's one of the best self-published books on the market I've ever read, not only in Go area, but whole technical market."

Bart Smykla (@bartsmykla)
Open Source engineer at VMWare

"Finally, a compiler book that you don't have to fight each and every page to get through! Other books burden the reader with so many details and subtleties that you'll never make progress. But if you want to make an actual compiler, read this. I'll definitely be recommending this to my students."

Austin Henley (@austinzhenley)
Assistant Professor, Department of Electrical Engineering & Computer Science, University of Tennessee

"If you are scared of Dragons but want to understand how compilers work, this book is for you. Not only does it make a daunting subject approachable but it also make it fun and enjoyable."

Franck JEANNIN (@frje)
Founder DataNuage

"The Monkey books are everything I've ever wanted in programming books, but could never find until now. They are a real labor of love and it shows on every page. The books are fun to read and showcase the Go programming language, but what makes them extraordinary is the fact that they're completely focused on giving the reader an accessible, conceptual understanding of the implementation of interpreters and compilers. It's hard to overstate just how rare yet extremely valuable that focus on understanding is in an educational book."

Brandon Ramos
Product Owner/Developer

"Just awesome books. If we had books like this on other subjects (search engines, DB systems), I think developers would have less fear of contributing to large open source projects. - Thank you @thorstenball. This is already paying off in my DB internals course."

Evance Soumaoro (@evanxg852000)
Software Engineer | System Programming Enthusiast

What readers said about the first book:

"Compilers was the most surprisingly useful university course I ever took. Learning to write a parser and runtime for a toy language helps take away a lot of "magic" in various parts of computer science. I recommend any engineer who isn't familiar with lexers, parsers, and evaluators to read Thorsten's book."

Mitchell Hashimoto (@mitchellh)
Founder of HashiCorp

"Thorsten took a topic that is usually very dry and CS heavy and made it accessible and easy to understand. After reading this book I felt confident enough to write Plush, the templating language I’ve always wanted in Go! If you have yet to read Thorsten's book, I can't recommend it enough. Please go and buy it!"

Mark Bates (@markbates)
Creator of gobuffalo.io

"Great book. I loved it because everything is built by hand, so you get to think about all the details, and it does so in a gradual way, which is didactic. The implementation itself is also nice and simple 🙌"

Xavier Noria (@fxn)
Everlasting student, Rails Core Team, Ruby Hero, Freelance, Live lover

"This book demystifies and makes the topic of interpreters approachable and fun. Don't be surprised if you become a better Go programmer after working your way through it."

Johnny Boursiquot (@jboursiquot)
Go Programmer, @BaltimoreGolang Organizer, @GolangBridge Core Member

"Thorsten's writing style is fun and easy to understand with detailed explanations and even better code. Even if you've written an interpreter before, this book is a great refresher. I picked it up as a project to learn Rust, translating the example Go code into Rust as I read through. Lexers, parsers, and interpreters are such a fundamental part of CS, these skills are valuable to more than just programmers implementing programming languages. As a project for picking up a new language, this book is perfect because it only requires the standard library and has extensive test driven development, which means you get quick feedback as you go along. I highly recommend it for programmers wanting to learn more about lexers, parsers, and interpreters or Go programmers picking up a new language looking for a project to learn through."

Paul Dix (@pauldix)
CTO of InfluxDB

FAQ

• Do I need to read the first book, Writing An Interpreter In Go, before this one?

  The short answer: Yes.

  The slightly longer version is this: Writing A Compiler In Go is the sequel to Writing An Interpreter In Go and starts right where the other one stopped. It also uses the code from the first book — the lexer, the parser, the AST, the object system — and extends it.

  If you're okay with treating the code as a black box, then no, you don't need to start with the first book. But that's not what I recommend or what these books are about; they're about opening up black boxes, looking inside and shining a light. You'll have the best understanding of where we're going in this book, if you know where we started.

• Can I buy a bundle of the eBook and the paperback?

  I'm sorry to say it, but no, I cannot bundle eBooks with paperbacks. It's not that I don't want to (I do!) but I can't. The eBooks are sold and distributed through Gumroad, where I have a lot of influence on the process, but the paperback editions are being printed, sold and shipped by Amazon and I don't have many options there. I can't tell Amazon to bundle digital files with the paperback. Sorry!

• I found a typo/mistake/error in the book. What now?

  Take a look at the changelog to see whether I've already fixed it. If I haven't or you're not sure I have, please send me an email to me @ thorstenball.com — I really appreciate it!

• The books are too expensive for me. Can you help me out?

  Sure, just send me a picture! I'm always fascinated by new places and love seeing where people live, so here's my proposal.

  You go outside, take a picture of where you live and send it to me to me @ thorstenball.com. Tell me what you feel comfortable paying for the book(s) and we'll make that happen.

About the author

Hello there! My name is Thorsten Ball. I'm a writer and programmer living in Aschaffenburg, Germany. In my professional life as a software developer, I build web applications and platforms. I have deployed Ruby, JavaScript, Go and C code to production systems.

In my spare time, though, I like to do what I call recreational programming, where I dig deep into various topics and their codebases, taking them apart, recreating them in my own code, trying to peel away layers of what seems like magic, hoping to come out the other end with a better understanding of what it is that I do when I program.

For the last few years, the two topics that kept my attention are systems programming and programming languages: interpreters, compilers, virtual machines, JIT compilers, assembly language – I can't get enough of it.

Writing an interpreter from scratch and writing a book about that has been one of the most wonderful and satisfying things I ever did as a programmer. It has been so much fun, in fact, that I couldn't stop doing it, which is why you're looking at the next book.

You can follow @thorstenball on Twitter to know what I'm up to. If you want to know more about me, visit my blog and website or take a look at my GitHub profile.

Any questions?

If you have any questions, send me an email. I promise, you'll make my day. I love getting email from you: me @ thorstenball.com