Crafting Interpreters

Citation

Nystrom, R. (2021). Crafting Interpreters. Genever Benning. Free official edition: https://craftinginterpreters.com/

Chapter Summary

Chapter 1: Introduction

The introduction sets out the book's promise: two complete interpreters for one small language, Lox, with every line of code shown and explained, and less theory than other books. Nystrom argues that "little languages" are everywhere, that building one is demanding programming practice, and that the subject is not reserved for wizards. He explains the book's devices (code snippets that say exactly where to insert them, asides, end-of-chapter challenges and design notes), why he writes everything by hand instead of using Lex and Yacc, and why the first interpreter is in Java and the second in C.

Chapter 2: A Map of the Territory

This chapter surveys how language implementations are built, following a program through scanning, parsing, static analysis, intermediate representations, optimization, code generation, virtual machines and runtimes. It then describes shortcuts such as single-pass compilers, tree-walk interpreters, transpilers and just-in-time compilation, and argues that the line between "compiler" and "interpreter" is blurry, so the book is about both.

Chapter 3: The Lox Language

An informal tour of the language to be implemented: a dynamically typed, garbage-collected scripting language with C-like syntax, Booleans, numbers, strings and nil, the usual operators, variables, control flow, first-class functions with closures, and classes with single inheritance. A section explains why Lox uses classes rather than prototypes. The design note compares languages built on expressions with those that separate expressions from statements.

Chapter 4: Scanning

Part II begins jlox, the tree-walk interpreter in Java. This chapter sets up the interpreter framework (running a file or a REPL, reporting errors) and writes a hand-coded scanner that turns source text into tokens, covering single- and two-character operators, string and number literals, and keywords versus identifiers via "maximal munch". A short section links the lexical grammar to regular languages without going deeply into automata.

Chapters 5–6: Representing Code; Parsing Expressions

Chapter 5 introduces context-free grammars and writes the grammar for Lox expressions, then generates the syntax-tree classes with a small metaprogram. It discusses the "expression problem" and introduces the Visitor pattern, used to write a simple tree printer. Chapter 6 resolves ambiguity with precedence and associativity rules, builds a recursive-descent parser for expressions, and adds syntax-error reporting with panic-mode recovery and synchronization.

Chapter 7: Evaluating Expressions

The interpreter now evaluates expression trees, representing Lox values as Java objects. The chapter defines truthiness, implements unary and binary operators, and adds runtime type errors with useful reporting. Its design note weighs static against dynamic typing.

Chapters 8–9: Statements and State; Control Flow

Chapter 8 adds statements, global variables, assignment and block scope, implemented with a chain of environments that supports nesting and shadowing. Chapter 9 adds if, short-circuiting and/or, while and for (the last by desugaring into while), after a brief detour into Turing machines and Turing completeness.

Chapter 10: Functions

User-defined functions arrive: call expressions with arity checks, a native clock() function, function declarations and function objects, return (implemented by unwinding the Java stack with an exception) and local functions that close over their environment.

Chapter 11: Resolving and Binding

A subtle bug appears when closures meet mutable environments, so the chapter adds a static resolver pass that computes, before execution, exactly which scope each variable reference points to. This is the book's introduction to semantic analysis, and the same pass reports errors such as returning from top-level code.

Chapters 12–13: Classes; Inheritance

Chapter 12 implements class declarations, instances, fields (get and set expressions), methods, this and initializers; its design note compares classes with prototypes. Chapter 13 adds single inheritance and super calls, completing jlox, which the part introduction describes as fewer than two thousand lines of Java.

Chapters 14–15: Chunks of Bytecode; A Virtual Machine

Part III starts again in C to build clox. Chapter 14 explains why bytecode is chosen over walking the AST (poor memory locality) or native code (complexity and lack of portability), and builds chunks of instructions as dynamic arrays, a disassembler, a constant pool and line information. Chapter 15 writes the virtual machine's dispatch loop and value stack and turns it into a calculator; its design note discusses register-based bytecode.

Chapters 16–17: Scanning on Demand; Compiling Expressions

Chapter 16 writes a scanner that produces tokens only when asked and recognizes keywords with a trie-like state machine. Chapter 17 writes a single-pass compiler that emits bytecode directly, using a Pratt parser in which each token type has prefix and infix parsing functions and a precedence level.

Chapters 18–19: Types of Values; Strings

Chapter 18 represents dynamically typed values as tagged unions in C, adding Booleans and nil with type checks and runtime errors. Chapter 19 introduces heap-allocated objects with a shared header ("struct inheritance"), implements strings and concatenation, and keeps a list of all objects so they can be freed; the design note discusses string encodings.

Chapter 20: Hash Tables

A full chapter builds a hash table from scratch: buckets and load factor, separate chaining versus open addressing, the FNV-1a hash function, linear probing, resizing, deletion with tombstones, and string interning, which lets clox compare strings by pointer.

Chapters 21–23: Global Variables; Local Variables; Jumping Back and Forth

These chapters add statements and globals (stored in the hash table), block-scoped locals that live in stack slots resolved at compile time, and control flow compiled to conditional and unconditional jumps using backpatching. The design note revisits the debate over goto.

Chapters 24–25: Calls and Functions; Closures

Chapter 24, which the author calls a beast, adds function objects, call frames, a stack of compilers for nested functions, argument binding, runtime stack traces and native functions. Chapter 25 implements closures with upvalues that start "open" (pointing into the stack) and are "closed" (moved to the heap) when a variable goes out of scope.

Chapter 26: Garbage Collection

The VM gets a mark-sweep garbage collector. The chapter defines reachability and roots, uses the tricolour abstraction with a gray-object worklist, treats the string table as weak references, discusses when to collect (latency versus throughput and a self-adjusting heap threshold), and shows how to find GC bugs with a stress-testing mode.

Chapters 27–29: Classes and Instances; Methods and Initializers; Superclasses

The object model is rebuilt in C across three chapters: class and instance objects, fields, methods and bound methods, this, initializers, and an optimized invoke instruction that makes method calls several times faster. Chapter 29 adds inheritance by copying methods down into the subclass and implements super calls, completing the virtual machine.

Chapter 30: Optimization

The last chapter measures and improves performance. It discusses benchmarks and profiling, replaces a modulo in hash-table probing with a bit mask, and implements NaN boxing to pack every value into 64 bits, reporting a roughly 10% overall gain for the latter. It closes with suggestions for further study, including compiler-optimization textbooks and formal programming-language theory.

Appendices I–II: Lox Grammar; Generated Syntax Tree Classes

The appendices collect the complete Lox grammar in one place and list the Java syntax-tree classes generated by the metaprogram from Chapter 5.

Key Concepts

Chapters 1–3: Welcome

• Tree-walk interpreter versus bytecode VM: the two implementation strategies the book builds in turn, trading simplicity for speed.
• Lox: a small, dynamically typed, garbage-collected language with closures and classes, designed to be implemented twice.

Chapters 4–6: Scanning and Parsing in jlox

• Token and lexeme: a lexeme is the raw substring; a token adds its type, literal value and line.
• Visitor pattern: a way to add operations over a fixed set of syntax-tree classes without editing each class.
• Panic-mode recovery: after a syntax error, skip tokens to a likely statement boundary so parsing can continue and report more errors.

Chapters 7–11: Evaluation, State and Functions

• Environment: a mapping from names to values, chained to an enclosing environment to model nested scopes.
• Desugaring: implementing a convenient construct (such as for) by translating it into simpler ones (while).
• Closure: a function value that keeps the environment in which it was declared.
• Resolver: a static pass that binds each variable use to its declaration before execution.

Chapters 12–13: Classes and Inheritance

• Bound method: a method value packaged with the instance it was accessed from, so this works later.
• Superclass call: super.method() looks up a method starting from the superclass of the class containing the call.

Chapters 14–19: Bytecode, VM and Values

• Bytecode chunk: a compact, linear array of instructions plus constants and line numbers.
• Pratt parser: a precedence-climbing parser driven by a table of prefix and infix functions per token type.
• Tagged union: a C struct that stores a type tag alongside a union of possible payloads, used for dynamic values.

Chapters 20–25: Hash Tables, Variables and Calls

• Open addressing with tombstones: storing entries directly in the bucket array and marking deleted slots so probe sequences stay intact.
• String interning: keeping one copy of each distinct string so equality becomes pointer comparison.
• Upvalue: the VM's indirection for a captured variable, open while it lives on the stack and closed once moved to the heap.

Chapters 26–30: Garbage Collection, Objects and Optimization

• Tricolour mark-sweep: white, gray and black sets that track which objects are unvisited, pending or fully traced.
• NaN boxing: encoding non-number values inside the unused bit patterns of IEEE 754 NaNs so every value fits in 64 bits.
• Profiling before optimizing: measuring with benchmarks and a profiler to find real hotspots instead of guessing.

Critical Analysis

Strengths

• Complete, runnable code at every step. Every line of both interpreters appears in the text, each snippet names the file and function where it goes, and the chapters are ordered so the program runs after each one. Readers end with two working implementations rather than fragments.
• Two implementations of one language. Building Lox twice lets the book contrast designs directly: environments versus stack slots, Java's garbage collector versus a hand-written one, a recursive-descent AST builder versus a single-pass Pratt compiler. Part III's chapter openings repeatedly explain what jlox took for granted.
• Engineering depth beyond parsing. Chapters on hash tables, closures with upvalues, garbage collection and NaN boxing cover runtime topics that many introductory compiler texts skip, with measurements and trade-offs explained (for example cache locality as the reason to leave the AST).
• Challenges and design notes. The challenges push beyond the chapter (adding break, anonymous functions, BETA-style inheritance, a switch statement), and the design notes on topics such as implicit semicolons, static versus dynamic typing and "novelty budgets" bring in language-design judgement.

Limitations

• Light on theory by design. Regular languages, grammars and parsing are introduced only as far as needed; LL and LR theory, parser generators, type systems and formal semantics are absent. Students who need these for a compilers exam need a second text.
• Dynamic, interpreted target only. Lox has no static types, and clox compiles to its own bytecode, not machine code, so register allocation, instruction selection and static type checking are not covered.
• Two languages assumed. Readers need working Java for Part II and confident C, including pointers and manual memory management, for Part III; the author says outright to learn C first if necessary.
• Long and incremental. The step-by-step snippet style means the full book is long, and the code is written for clarity on the page rather than as production style, as the author notes.

Where It Fits in the Course

In this course list, Crafting Interpreters and Douglas Thain's Introduction to Compilers and Language Design are the two introductory books, and they cover different ground. Nystrom writes every phase by hand for a dynamic language and goes deep into runtime implementation (closures, garbage collection, a bytecode VM), while Thain covers grammar theory, Flex and Bison, static type checking and generating X86 or ARM assembly. Reading Nystrom first gives an intuitive feel for how a language works end to end; Thain then supplies the formal parsing material and native code generation that Nystrom leaves out.

The fuller books in the course, Cooper and Torczon's Engineering a Compiler and Aho, Lam, Sethi and Ullman's Compilers: Principles, Techniques, and Tools, are generally described as comprehensive treatments of compiler theory and optimization; Nystrom's own closing chapter recommends Cooper and Torczon as a next step for compile-time optimization. Pierce's Types and Programming Languages is the place for the formal type theory that this book deliberately avoids.

How to Use This Book

The book is aimed at programmers meeting language implementation for the first time. No compiler background is needed, but readers should be comfortable programming: a minimal subset of Java is used in Part II, and Part III assumes solid C.

The intended way to use it is to type in the code chapter by chapter and keep each interpreter running, as the snippets are designed for. Part I (Chapters 1–3) can be read quickly. Part II (Chapters 4–13) is the core for understanding scanning, parsing, evaluation, scope and closures; Chapter 11 on resolving is short but important. Part III (Chapters 14–30) is longer and more demanding; Chapters 24–26 (calls, closures and garbage collection) are the most demanding and repay the effort. A shorter course can stop after Part II, or follow Part III through Chapter 26 and treat the object-oriented chapters and Chapter 30 as optional.

Attempt at least some challenges in each chapter, but in a copy of the code, since later chapters assume the unmodified interpreter. The design notes can be read on their own for language-design discussion. The book's website hosts the full text, and the source code for jlox and clox is released under the MIT licence, which is useful for checking your own implementation.

Edition and Sources

This guide is based on the free web edition of Crafting Interpreters at https://craftinginterpreters.com/ (text © 2015–2020 Robert Nystrom; print edition 2021). It draws on the table of contents, the part introductions, Chapter 1 in full, and for all 30 chapters the opening sections, every section heading, the challenges and the design notes, with Sections 14.1 (why bytecode) and 30.3–30.4 (NaN boxing and "Where to Next") read in full, plus both appendices.