A few weeks ago, I started at the Recurse Center with the goal of scrubbing away the “magic” behind various software concepts. Of these concepts, Interpreters and Compilers were the first on my agenda.
At my previous employer, my team was responsible for internal tooling and SRE work; a lot of the core infrastructure pieces we worked with were built in Go (Nomad, Consul, Vault, Prometheus). In order to gain better visibility and understanding of these tools, I began picking up the Go Programming Language. During this time, I stumbled upon an excellent book called “Building an Interpreter in Go”. This presented a great opportunity to extend my Go knowledge as well as scrub away the magic behind programming languages.
What features were implemented?
The Interpreter is for a language called Monkey, a C-like language which looks familiar to Javascript and supports:
- Integers, Strings, Arrays, Maps and Function data types
- Statements
- Expressions
- Prefix and Infix operators
- Conditionals
- Recursion
- Variable Bindings
- First Class and Higher Order Functions
How do Interpreters work?
- The Interpreter is fed a text input string, this is the file we want to run.
- The Lexer breaks up this program string into the language’s smallest components, tokens.
- The Parser crawls a few tokens at a time and figures out what sort of statements/expressions are being formed. Along the way, the parser validates the rules of the language and returns an AST (Abstract Syntax Tree).
- The Evaluator is fed the AST and proceeds to “walk” the tree from the first to last statement. These statements in the AST are broken down sufficently that we can natively execute them in Go.
How’d it go?
I finished up the tree walking interpreter within my first few weeks of RC. With a stronger foundation to fall back on, I feel much more comfortable learning new languages or working with unfamiliar ones. Overall, this was a great learning experience and it was a blast implementing all of these different concepts. The book sparked my interest enough that I picked up the sequel “Building a Compiler in Go” which replaces the evaluator backend for a Bytecode Compiler and Virtual Machine.
Notes
- A helpful insight: a language’s grammar rules are often displayed publicly either in it’s design documents, documentation or within it’s Git repository. These documents are a powerful tool for understanding how a particular language can be written and manipulated to create it’s various idioms. Go, Java, Python, and Javascript examples.