Writing A Compiler In Go

 Acknowledgments....6

Introduction....7

Evolving Monkey....8

The Past and Present....8

The Future....10

Use This Book....11

Compilers & Virtual Machines....13

Compilers....14

Virtual and Real Machines....17

Real Machines....17

What Is a Virtual Machine?....22

Why Build One?....24

Bytecode....26

What We're Going to Do, or: the Duality of VM and Compiler....27

Hello Bytecode!....29

First Instructions....30

Starting With Bytes....31

The Smallest Compiler....35

Bytecode, Disassemble!....40

Back to the Task at Hand....44

Powering On the Machine....46

Adding on the Stack....52

Hooking up the REPL....57

Compiling Expressions....60

Cleaning Up the Stack....60

Infix Expressions....64

Booleans....68

Comparison Operators....72

Prefix Expressions....79

Conditionals....85

Jumps....88

Compiling Conditionals....90

Executing Jumps....102

Welcome Back, Null!....105

Keeping Track of Names....113

The Plan....114

Compiling Bindings....115

Introducing: the Symbol Table....117

Using Symbols in the Compiler....120

Adding Globals to the VM....123

String, Array and Hash....128

String....128

Array....133

Hash....137

Adding the index operator....143

Functions....149

Dipping Our Toes: a Simple Function....149

Representing Functions....149

Opcodes to Execute Functions....151

Compiling Function Literals....153

Compiling Function Calls....166

Functions in the VM....169

A Little Bonus....178

Local Bindings....179

Opcodes for Local Bindings....180

Compiling Locals....183

Implementing Local Bindings in the VM....194

Arguments....202

Compiling Calls With Arguments....203

Resolving References to Arguments....208

Arguments in the VM....210

Built-in Functions....219

Making the Change Easy....220

Making the Change: the Plan....225

A New Scope for Built-in Functions....226

Executing built-in functions....230

Closures....236

The Problem....237

The Plan....238

Everything's a closure....239

Compiling and resolving free variables....249

Creating real closures at run time....260

Recursive Closures....264

Taking Time....276

Resources....280

Feedback....282

Changelog....283

This is the sequel to Writing An Interpreter In Go. We're picking up right where we left off and write a compiler and a virtual machine for Monkey.Runnable and tested code front and center, built from the ground up, step by step — just like before. But this time, we're going to define bytecode, compile Monkey and execute it in our very own virtual machine. It's the next step in Monkey's evolution. It's the sequel to … a programming language.

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 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.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

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