Crafting Interpreters

BSCS students taking a Compilers, Programming Languages, or Language Implementation elective course can read the complete textbook “Crafting Interpreters” by Robert Nystrom, free from its official source. It’s a 30-chapter, project-based book that teaches how programming languages are actually implemented by building two complete, working interpreters for the same language, Lox: jlox, a tree-walking interpreter in Java, and clox, a much faster bytecode virtual machine in C.

This edition works through the full pipeline of language implementation twice, at two different levels of abstraction — scanning, parsing, evaluation, functions, closures, and classes in Part II’s jlox, and then bytecode compilation, a stack-based virtual machine, a hash table and garbage collector built from scratch, and real performance optimization in Part III’s clox — making it a uniquely hands-on companion for anyone who wants to understand compilers and interpreters by actually building them rather than only studying the theory.

Book Overview

Chapter List

Chapter 1: Introduction

Difficulty: Beginner · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: why build an interpreter, the book’s two-interpreter plan, tree-walk vs. bytecode

This opening chapter sets up the whole book: readers will build two complete interpreters for the same language, Lox — a simple tree-walking interpreter in Java (jlox) in Part II, and a much faster bytecode virtual machine in C (clox) in Part III. The chapter makes the case for building real, working interpreters from scratch rather than only studying theory, argues that understanding how languages are implemented makes anyone a better programmer, and previews the hands-on, incremental style the rest of the book follows, with runnable code at every step.

Key Points:

• The book builds two complete interpreters for the same toy language, Lox: jlox (tree-walking, in Java) and clox (bytecode virtual machine, in C).
• Building both a slow, simple interpreter and a fast, complex one lets the book teach both the concepts and the performance trade-offs behind them.
• The book is deliberately hands-on — every chapter produces runnable, working code, not just pseudocode or theory.
• No prior compilers coursework is assumed; the book is written to be approachable to any programmer curious about how languages work under the hood.
• Lox itself is a small, dynamically typed scripting language designed specifically to be simple enough to fully implement in this book, while still being expressive enough to matter.

Memory Tip: Keep the book’s two-part structure in mind throughout: everything in Part II (jlox) gets reimplemented, faster and lower-level, in Part III (clox) — so a concept learned once often gets revisited from a completely different angle later.

Common Mistake: Assuming the two interpreters are unrelated exercises rather than two implementations of the exact same language, Lox — the payoff of the book comes precisely from comparing how the same language features are implemented the simple way (jlox) versus the fast way (clox).

Important Questions:

• Q1. Why does the book build two separate interpreters for the same language instead of just one? Building jlox (a simple tree-walking interpreter in Java) first teaches the core concepts of interpretation clearly, without the added complexity of low-level performance concerns. Building clox (a bytecode virtual machine in C) afterward, for the exact same language, then lets the book show how a production-quality language implementation trades simplicity for speed — the comparison between the two is itself one of the book’s main teaching tools.
• Q2. What is Lox, and why was it designed specifically for this book? Lox is a small, dynamically typed scripting language with C-like syntax, designed by the author specifically to be simple enough to be fully implemented, twice, within the scope of one book, while still including enough real features — closures, classes, inheritance — to make implementing it genuinely instructive rather than trivial.

Chapter 2: A Map of the Territory

Difficulty: Beginner · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: interpreter pipeline stages, compilers vs. interpreters, tree-walk vs. bytecode vs. JIT vs. transpiling

Before writing any code, this chapter gives readers a map of the whole field: the stages a language implementation typically passes through — scanning, parsing, static analysis, intermediate representations, optimization, and code generation — and the major families of ways to actually execute the result, from tree-walking interpreters through bytecode virtual machines to just-in-time compilers and transpilers. It equips readers with the vocabulary and mental model needed to understand where jlox and clox, the book’s two interpreters, sit within this larger landscape.

Key Points:

• A typical language implementation pipeline runs: scanning (lexing) → parsing → static analysis → intermediate representation → optimization → code generation → execution.
• “Compiler” and “interpreter” are not mutually exclusive labels — many real systems (including clox, built later in this book) are both a compiler (source to bytecode) and an interpreter (running that bytecode).
• Tree-walking interpreters execute a program by directly traversing its abstract syntax tree, which is simple to build but relatively slow — this is the strategy behind jlox.
• Bytecode virtual machines compile source into a compact, simplified instruction set and then execute that with a dedicated interpreter loop, trading implementation complexity for real speed — this is the strategy behind clox.
• Just-in-time (JIT) compilation and ahead-of-time (AOT) compilation to native machine code sit further along the performance spectrum, at the cost of significantly more implementation complexity than either of the book’s two interpreters.
• Transpilers, which translate source code in one language into source code in another, are presented as a distinct fourth strategy alongside tree-walking, bytecode, and native compilation.

Practice Tip: Sketch the six-stage pipeline (scan, parse, analyze, IR, optimize, generate) from memory after reading this chapter — every remaining chapter in the book fits into exactly one or two of these stages, and knowing which stage you’re in makes it much easier to follow the code.

Common Mistake: Treating “interpreter” and “compiler” as opposites — the chapter is explicit that many real systems are properly described as both, and clox, built later in the book, compiles Lox source to bytecode and then interprets that bytecode.

Important Questions:

• Q1. What is the difference between a tree-walking interpreter and a bytecode virtual machine, and which strategy does each of the book’s two interpreters use? A tree-walking interpreter executes a program by directly traversing and evaluating its abstract syntax tree at run time, which is simple to implement but comparatively slow — this is jlox, the book’s Part II interpreter. A bytecode virtual machine instead compiles the syntax tree down into a compact set of simple instructions ahead of time, then runs those instructions with a fast, dedicated execution loop — this is clox, the book’s Part III interpreter.
• Q2. Why does the book say a single system can be both a compiler and an interpreter? “Compiler” describes a system that translates source code from one representation into another (such as bytecode), while “interpreter” describes a system that directly executes a program. clox does both: it compiles Lox source code into bytecode, and then its virtual machine interprets that bytecode — so it is accurately described as a compiler feeding an interpreter, not purely one or the other.

Chapter 3: The Lox Language

Difficulty: Beginner · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: Lox syntax and semantics overview, data types, expressions, statements, functions, classes

This chapter introduces the complete surface of the Lox language that jlox and clox will spend the rest of the book implementing: its dynamic typing and small set of built-in data types (booleans, numbers, strings, nil), its C-family expression syntax, statements and variable declarations, control flow, functions and closures, and its single-inheritance class system. Rather than a formal specification, it works as a hands-on tour of the language from a user’s point of view, so that later implementation chapters can be understood against a concrete picture of the target behavior.

Key Points:

• Lox is dynamically typed, with a small set of built-in types: Booleans, numbers (all floating-point), strings, and nil.
• Lox’s expression and statement syntax deliberately follows the C/Java family closely, to keep the language itself familiar so attention can stay on the implementation.
• Variables are declared with var, and Lox uses lexical (static) scoping, resolved via nested block scopes.
• Functions are first-class values in Lox and support closures — they can capture variables from their enclosing scope and be passed around like any other value.
• Lox has a single-inheritance class system with methods, instance fields (assigned dynamically), a special this reference, and superclass method calls via super.

Memory Tip: Keep a copy of this chapter’s example programs handy while reading later chapters — every later feature (closures, classes, inheritance) is one that’s already been shown running correctly here, so it’s a ready-made test suite for jlox and clox as they’re built.

Common Mistake: Skimming this chapter because it “doesn’t involve writing an interpreter yet” — every later chapter assumes familiarity with the exact behavior specified here, and mismatches between what a reader assumes Lox does and what it actually does are a common source of confusion in later implementation chapters.

Important Questions:

• Q1. What kind of type system does Lox have, and what built-in data types does it provide? Lox is dynamically typed — types are checked at run time, not compile time, and a variable can hold a value of any type at different points in a program. It provides four built-in data types: Booleans (true/false), numbers (all represented as double-precision floating point, with no separate integer type), strings, and nil (the absence of a value).
• Q2. How does Lox handle scoping and closures, and why does this matter for later chapters? Lox uses lexical (static) scoping with nested block scopes, and functions are first-class values that can capture (close over) variables from enclosing scopes, forming closures. This matters because correctly implementing closures turns out to be one of the more subtle challenges in the book — it resurfaces explicitly in chapter 11 (Resolving and Binding) for jlox and chapter 25 (Closures) for clox.

Chapter 4: Scanning

Difficulty: Beginner · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: lexical analysis, tokens and lexemes, regular languages, hand-written scanner

The first real implementation chapter builds a scanner (lexer) for jlox: the component that turns raw Lox source text into a flat sequence of tokens — keywords, identifiers, literals, operators, and punctuation. It works through the theory of regular languages just enough to explain why a scanner can be a simple, single-pass, character-by-character loop, then builds that loop by hand in Java, handling multi-character tokens, string and number literals, comments, and reporting syntax errors without stopping the whole scan.

Key Points:

• A scanner (lexer) turns a flat stream of source characters into a flat stream of tokens, each tagged with a type, its lexeme text, and its source location.
• Lexical grammars are regular languages, which is why scanning can be done with a simple, linear, single-pass loop rather than anything recursive.
• The scanner must handle maximal munch: always consuming the longest possible lexeme at each point (e.g., preferring <= over < followed by =).
• String and number literals require special-cased scanning logic to consume an entire literal (handling escapes, decimal points, etc.) as one token.
• Good error handling in a scanner reports a bad character and keeps scanning, rather than aborting on the very first lexical error — so a user sees all lexical errors in one run, not just the first.

Practice Tip: Trace through maximal munch by hand on an ambiguous case like != versus separately scanning ! and = — understanding why the scanner must always try to match the longest valid lexeme first prevents a whole class of scanning bugs.

Common Mistake: Having the scanner throw an exception and stop on the first invalid character — the chapter explicitly designs error handling to report the bad token and keep going, so the user sees every lexical error in one pass instead of having to fix and rerun one error at a time.

Important Questions:

• Q1. What is a scanner responsible for, and why is a simple linear loop sufficient to implement one? A scanner reads raw source text and groups its characters into tokens — keywords, identifiers, numbers, strings, operators, and punctuation — discarding whitespace and comments along the way. A simple linear, single-pass loop is sufficient because lexical grammars (the rules for what counts as a valid token) are regular languages, which by definition can be recognized without needing recursion or backtracking.
• Q2. What is “maximal munch,” and why does the scanner need it? Maximal munch is the rule that, when multiple different tokens could match starting at the current position, the scanner always chooses the longest one — for example, scanning != as a single not-equal token rather than as ! followed separately by =. Without this rule, the scanner would produce ambiguous or incorrect token sequences for any multi-character operator.

Chapter 5: Representing Code

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: context-free grammars, Backus-Naur Form, abstract syntax trees, the Visitor pattern

This chapter introduces the tools needed to represent Lox’s grammar and, from it, the tree structures that will hold parsed programs. It covers context-free grammars and a compact notation for writing them, then shows how each grammar rule for expressions maps onto a Java class representing that kind of expression node, forming the abstract syntax tree (AST). Because different parts of jlox (the interpreter, a pretty-printer, and later a resolver) all need to operate on these same AST node classes without cluttering them, the chapter introduces the Visitor design pattern as the solution and uses a small code-generation script to produce the resulting boilerplate automatically.

Key Points:

• A context-free grammar, written in a compact BNF-like notation, formally defines which sequences of tokens form valid Lox expressions.
• Each production rule in the expression grammar corresponds to one Java class (Binary, Unary, Literal, Grouping, etc.), together forming the abstract syntax tree (AST) representation of a parsed expression.
• The Visitor design pattern lets new operations (like evaluating, printing, or resolving an expression) be added over a fixed set of AST classes without modifying those classes themselves.
• A small standalone code-generation script is used to mechanically generate the repetitive AST class definitions and their Visitor boilerplate, rather than hand-writing all of it.
• This chapter’s AST classes for expressions are the shared data structure that every later jlox chapter — the parser, the interpreter, and the resolver — operates on.

Memory Tip: Whenever a later jlox chapter adds a new kind of AST node, come back to this chapter’s code-generation script as the template — every new expression or statement type follows exactly the same generate-a-class-plus-a-Visitor-method pattern established here.

Common Mistake: Trying to add new operations on the AST (like a new kind of analysis pass) by editing every AST node class directly — the whole point of the Visitor pattern introduced here is to let new operations be added as new Visitor implementations instead, without touching the node classes.

Important Questions:

• Q1. Why does the book use the Visitor design pattern for the AST classes instead of putting behavior directly on each node class? Different parts of jlox (interpreting, pretty-printing, and later resolving) each need to define different behavior for every AST node type, and object-oriented languages like Java make it easy to add new node subclasses but awkward to add new operations across an existing class hierarchy. The Visitor pattern inverts this: it makes it easy to add a whole new operation (as a new Visitor class) across all existing node types at once, which is exactly the kind of extension this book needs repeatedly.
• Q2. What problem does the small code-generation script in this chapter solve? Defining every AST node class (Binary, Unary, Literal, Grouping, and later many statement types) by hand, along with its required Visitor-pattern boilerplate, would mean writing a large amount of repetitive, mechanical, easy-to-get-wrong code. The script instead takes a compact description of each node type’s fields and generates the full Java class definitions automatically, keeping the AST definitions both correct and easy to extend as new node types are added in later chapters.

Chapter 6: Parsing Expressions

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: recursive descent parsing, operator precedence and associativity, syntax error handling

With tokens from the scanner and AST classes from the previous chapter in hand, this chapter builds a recursive descent parser for Lox expressions — a technique where each grammar rule becomes a corresponding parsing method, and precedence is encoded directly in how those methods call each other. It works through how to express operator precedence and associativity (for arithmetic, comparison, equality, and unary operators) purely through the grammar’s structure, and introduces a simple panic-mode error-recovery scheme so that one syntax error doesn’t prevent the parser from finding others in the same file.

Key Points:

• Recursive descent parsing translates each grammar rule directly into a method, with each method calling the methods for higher-precedence rules — making the parser’s structure mirror the grammar’s structure exactly.
• Operator precedence and associativity are expressed entirely through how the grammar (and thus the parser methods) are layered, rather than through any separate precedence table.
• The parser builds AST nodes (from the previous chapter) bottom-up as it recognizes each grammar rule, producing a complete expression tree by the time parsing finishes.
• Panic-mode error recovery lets the parser, after reporting a syntax error, skip tokens until it reaches a likely statement boundary and keep parsing, so multiple syntax errors can be reported from a single parse.
• This chapter parses only expressions; full statement parsing (and syntax errors that span statements) is deferred to chapter 8.

Practice Tip: Draw the precedence hierarchy (equality → comparison → term → factor → unary → primary) as a stack of boxes, each calling into the one below — recursive descent parsing becomes far more intuitive once precedence is seen as “depth in this stack” rather than as an abstract numeric rule.

Common Mistake: Assuming a separate operator-precedence table is required to parse expressions correctly — in recursive descent parsing, precedence is instead encoded implicitly in the order that parsing methods for each grammar rule call one another, which is precisely the technique this chapter teaches.

Important Questions:

• Q1. How does recursive descent parsing encode operator precedence without an explicit precedence table? Each precedence level in the grammar (equality, comparison, term, factor, unary, primary) gets its own parsing method, and each method calls the method for the next-higher-precedence level before trying to match its own operators. This layered structure of method calls means higher-precedence expressions are always parsed first and bound more tightly, without needing any separate lookup table — precedence is implicit in the call structure of the parser itself.
• Q2. What is panic-mode error recovery, and why does the parser need it? When the parser hits a token it can’t make sense of, panic-mode recovery reports the syntax error and then discards tokens until it reaches a point that’s likely to be the start of a new statement (such as after a semicolon), rather than aborting the entire parse immediately. This matters because without it, a single syntax error early in a file would stop the parser from finding and reporting any other, unrelated errors later in the same file.

Chapter 7: Evaluating Expressions

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: tree-walk evaluation, Lox’s type system and truthiness, runtime errors

This chapter turns jlox’s parser into an actual interpreter by giving the AST’s Visitor interface a real implementation: one that evaluates each kind of expression node down to a runtime Lox value. It works through how Java values represent each Lox type, how Lox defines truthiness and equality, how binary and unary operators are evaluated (with type checking), and how runtime type errors are reported as Lox-level runtime errors distinct from the syntax errors handled in earlier chapters. By the end, jlox can correctly evaluate any single Lox expression.

Key Points:

• The Interpreter class implements the Visitor interface from chapter 5, giving each AST node type a corresponding “how to evaluate this” method — this is the essence of a tree-walking interpreter.
• Lox’s runtime values are represented directly as Java objects: Lox numbers as Java Doubles, strings as Java Strings, Booleans as Java Booleans, and nil as Java null.
• Lox defines truthiness explicitly: false and nil are falsey, and every other value (including 0 and empty strings) is truthy — a specific design choice the interpreter must implement exactly.
• Binary and unary operators perform their own run-time type checking (e.g., + requires two numbers or two strings), raising a Lox runtime error rather than crashing the Java interpreter on a type mismatch.
• Runtime errors are distinguished from syntax errors: they can only be detected while actually executing an expression, not while parsing it, and are reported with a Lox-specific runtime exception.

Memory Tip: Memorize Lox’s exact truthiness rule — only false and nil are falsey, everything else (including 0, “”, and any object) is truthy — since this differs from several other languages’ conventions and is tested repeatedly in later control-flow chapters.

Common Mistake: Confusing a syntax error (caught while parsing, before any code runs) with a runtime error (caught while evaluating, such as calling + on a number and a Boolean) — the chapter treats these as fundamentally different categories, handled by different mechanisms at different stages of jlox’s pipeline.

Important Questions:

• Q1. How does the tree-walking Interpreter class relate to the Visitor pattern introduced in chapter 5? The Interpreter class is one concrete implementation of the Visitor interface defined back in chapter 5 — it provides a visit method for every AST node type (Binary, Unary, Literal, Grouping, etc.) that, instead of printing or resolving, actually evaluates that node down to a runtime Lox value, recursively evaluating any child expressions first. This is exactly what makes it a tree-walking interpreter: evaluation happens by walking the AST directly.
• Q2. What is Lox’s truthiness rule, and why does it matter that it’s defined explicitly? In Lox, only the value false and the value nil are considered falsey; every other value, including the number 0 and the empty string, is considered truthy. This is defined explicitly because different languages make different choices here (some treat 0 or empty strings as falsey too), so the interpreter’s implementation of truthiness must match this specific, chosen rule exactly for conditional expressions and control flow to behave correctly.

Chapter 8: Statements and State

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: statements vs. expressions, variable declarations, environments, scope

This chapter extends jlox from evaluating single expressions to running whole programs, made of statements. It adds a parallel statement grammar and AST alongside the expression grammar from earlier chapters, introduces variable declaration and assignment, and builds the Environment class — a chain of nested maps from variable names to values — that implements Lox’s scoping rules. By the end of the chapter, jlox can run multi-statement programs with variables, print statements, and properly nested block scopes.

Key Points:

• Lox’s grammar splits cleanly into two parallel hierarchies — expressions (which produce a value) and statements (which produce an effect) — each with its own AST classes and Visitor interface.
• The Environment class stores variable bindings as a chain of nested maps, one per scope, with each environment holding a reference to its enclosing environment.
• Variable lookup and assignment walk outward through this chain of environments until a binding is found, which is exactly how lexical scoping is implemented at runtime.
• Block statements ({ … }) create a new child environment for their duration, so variables declared inside a block are automatically discarded when the block ends.
• Lox treats redeclaring a variable in the same scope as legal (unlike many statically typed languages), a specific design choice the interpreter must implement deliberately, not accidentally forbid.

Practice Tip: Trace a small nested-block example by hand, drawing each Environment as a box with a pointer to its enclosing box — seeing the chain of environments as literal linked boxes makes variable shadowing and scope lookup far more concrete than reading the code alone.

Common Mistake: Implementing variable scope with a single flat map instead of a chain of nested Environment objects — a flat map cannot correctly support shadowing (an inner-scope variable temporarily hiding an outer one) or the automatic cleanup of variables when a block ends, both of which the chain-of-environments design handles naturally.

Important Questions:

• Q1. How does jlox implement lexical scoping using the Environment class? Each scope (the global scope, and each block) gets its own Environment object, which is a map from variable names to values plus a reference to the environment of the immediately enclosing scope. Looking up or assigning a variable starts in the current environment and, if the name isn’t found there, walks outward through each enclosing environment in turn until it finds a match or runs out of environments, which is exactly how nested lexical scopes are meant to behave.
• Q2. Why does the interpreter need a separate statement grammar and AST, in addition to the expression grammar from earlier chapters? Expressions produce a value (like 1 + 2), while statements produce an effect (like declaring a variable or printing a value) and don’t themselves evaluate to anything usable. Because these are fundamentally different kinds of syntax with different roles in a program, the chapter gives them a separate grammar, separate AST node classes, and a separate Visitor interface, mirroring exactly how the expression AST was built back in chapter 5.

Chapter 9: Control Flow

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: if/else statements, logical operators and short-circuiting, while and for loops

This chapter gives jlox real control flow: if/else statements, logical and/or operators with proper short-circuit evaluation, and while and for loops. Rather than adding for loops as a wholly separate feature, the chapter shows the classic technique of desugaring: parsing for loop syntax and then rewriting it, purely inside the parser, into an equivalent while loop wrapped in a block — meaning the interpreter itself never needs to know for loops exist at all.

Key Points:

• if statements and the ternary-like logical operators are implemented as new statement/expression AST node types, following the same Visitor-based pattern established in earlier chapters.
• Logical and and or are implemented with proper short-circuit evaluation: the right operand is only evaluated if the left operand’s truthiness doesn’t already determine the result.
• while loops are implemented directly, re-evaluating their condition and body via the tree-walking interpreter on each iteration.
• for loops are implemented via desugaring: the parser rewrites for loop syntax into an equivalent combination of a block, an initializer, a while loop, and an increment — producing an ordinary while-loop AST with no new interpreter logic required.
• Desugaring is presented as a general technique: implementing a convenience feature purely at the syntax level, in terms of features the interpreter already supports, avoids duplicating interpreter logic.

Memory Tip: When reading the for loop desugaring code, mentally rewrite a for (init; cond; incr) body loop as { init; while (cond) { body; incr; } } by hand first — the parser code will then read as a direct, mechanical translation of exactly that rewrite.

Common Mistake: Implementing for loops as a completely separate execution path in the interpreter, duplicating the while loop’s logic — the chapter’s whole point with desugaring is that for loops need no new interpreter code at all once the parser rewrites them into an equivalent while loop.

Important Questions:

• Q1. What does it mean for Lox’s and and or operators to be “short-circuiting,” and why does this require special handling in the interpreter rather than being an ordinary binary operator? Short-circuiting means the right-hand operand of and or or is not evaluated at all if the left-hand operand’s truthiness already determines the overall result (e.g., false and anything is false without evaluating “anything”). This requires special handling because ordinary binary operators in jlox always evaluate both operands before combining them; and/or instead need their own AST node type whose evaluation logic conditionally skips evaluating the right operand.
• Q2. What is “desugaring,” and how does the chapter use it to implement for loops? Desugaring means implementing one piece of syntax entirely in terms of another, more fundamental piece of syntax the interpreter already supports, rather than adding new interpreter logic for it. The chapter’s parser, upon seeing a for loop, builds an AST that is exactly equivalent to a block containing the initializer followed by a while loop (whose body ends with the increment) — so the tree-walking interpreter, which already knows how to run while loops and blocks, can run for loops without any new code of its own.

Chapter 10: Functions

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: function declarations and calls, native functions, closures, returning via exceptions

This chapter adds functions to jlox: function declarations, function call expressions, native (built-in) functions implemented directly in Java, and user-defined Lox functions that correctly capture closures over their enclosing scope. Because Java has no native support for a non-local return-from-anywhere-in-a-function-body control flow, the chapter uses a clever, pragmatic technique: implementing Lox’s return statement by throwing and catching a special Java exception, unwinding the tree-walk back to the point where the function was called.

Key Points:

• User-defined Lox functions are represented internally as LoxFunction objects, which wrap the function’s declaration AST together with the environment active at the point the function was declared — this captured environment is exactly what makes closures work.
• Native functions (like a built-in clock() for timing) are implemented directly in Java by implementing the same LoxCallable interface that user-defined functions implement, letting both be called uniformly.
• A function call creates a new environment, whose enclosing environment is the closure captured at declaration time (not the environment at the call site) — this is what gives Lox correct lexical, rather than dynamic, scoping for functions.
• Lox’s return statement is implemented by throwing a special Return exception carrying the return value, caught at the point the function was originally invoked, since Java has no built-in mechanism for a tree-walking interpreter to unwind arbitrarily deep recursive evaluation.
• Because each function call creates a fresh environment, recursive functions work correctly — each active call has its own separate set of local variable bindings.

Practice Tip: When a function is declared, note exactly which environment gets captured as its closure — it’s the environment active at the point of declaration, not the (different, and not-yet-existing) environment that will exist later when the function is called.

Common Mistake: Assuming a function call’s new environment should be based on the environment at the call site — Lox uses lexical scoping, so a function’s new environment must instead be based on the environment where the function was declared (its closure), which is exactly what makes closures behave predictably regardless of where a function happens to be called from.

Important Questions:

• Q1. How does jlox use Java exceptions to implement Lox’s return statement, and why is this necessary? When a Lox return statement is evaluated, jlox throws a special Return exception carrying the value to return; this exception propagates up through the tree-walking evaluation of the function body until it’s caught at the exact point where the function call itself is being evaluated, which then produces the returned value as the result of the call. This is necessary because a tree-walking interpreter evaluates a function body by recursively calling Java methods for each nested statement, and Java has no built-in way to “jump out” of that arbitrarily deep nested call structure except through its own exception-unwinding mechanism.
• Q2. What makes closures work correctly in jlox, and why does it matter that a function captures its environment at declaration time rather than at call time? Each LoxFunction stores a reference to the environment that was active at the moment the function was declared; when the function is later called, its new local environment’s enclosing environment is set to this captured one, not to whatever environment happens to be active at the call site. This matters because it’s exactly what gives Lox correct lexical scoping: a function always sees the variables that were in scope where it was written, regardless of where or when it’s later called from — which is the defining behavior of a closure.

Chapter 11: Resolving and Binding

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: static scope resolution pass, fixing dynamic-scope bugs in closures

This chapter fixes a subtle bug in jlox’s environment-chain-based scoping: because variable lookup walks the environment chain at run time, certain programs involving closures and variable shadowing can resolve a variable reference to the wrong binding, in effect behaving like dynamic rather than lexical scope in edge cases. The fix is a separate static analysis pass, the Resolver, which walks the AST once before execution and calculates exactly how many scopes “up” each variable reference should resolve to, storing that information for the interpreter to use directly at run time instead of searching.

Key Points:

• The bug being fixed is that jlox’s run-time environment-chain lookup can, in specific cases involving closures, resolve a variable name to a different binding than the one lexically closest to it, violating Lox’s intended lexical scoping.
• The Resolver is a separate tree-walking pass (implemented, like the Interpreter, as a Visitor over the same AST) that runs once after parsing and before execution, without actually evaluating anything.
• For every variable reference, the Resolver calculates the number of scopes between that reference and the scope where the variable was declared, and records this distance.
• At run time, the interpreter uses this precomputed distance to jump directly to the correct environment in the chain, instead of searching outward scope by scope and potentially finding the wrong binding.
• The Resolver also does double duty as a place to catch certain static errors, like using a variable in its own initializer or returning from top-level code, before the program ever runs.

Memory Tip: Think of the Resolver as running a “dry” version of the interpreter — it walks the exact same AST with the exact same Visitor pattern as the real Interpreter, but instead of computing values, it computes distances; keeping this parallel in mind makes the Resolver’s code much easier to follow.

Common Mistake: Assuming static scope resolution is an optional performance optimization rather than a correctness fix — the chapter is explicit that without the Resolver, jlox has a genuine scoping bug in certain closure-plus-shadowing cases, not just suboptimal performance.

Important Questions:

• Q1. What specific bug does the Resolver in this chapter fix, and why does pure run-time environment-chain lookup cause it? Without the Resolver, a variable reference is looked up at run time by walking outward through whatever environment chain happens to be active at that moment, which can differ from the environment chain that was lexically in scope when the reference was written — in specific cases involving closures and variable shadowing, this can cause a reference to resolve to the wrong variable binding, effectively behaving like dynamic scope instead of the lexical scope Lox is supposed to have.
• Q2. How does the Resolver fix this bug, and what does it compute for each variable reference? The Resolver performs a separate static analysis pass over the AST, before any code runs, that calculates — for every variable reference — the exact number of enclosing scopes between that reference and the scope in which the variable was declared. The real interpreter then uses this precomputed number directly to jump straight to the correct environment at run time, rather than searching outward and risking landing on the wrong binding.

Chapter 12: Classes

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: class declarations, instances, properties, methods, this

This chapter adds object-oriented programming to jlox: class declarations, instances created by calling a class like a function, dynamically assignable instance properties, methods looked up on the class, and the this keyword for methods to refer back to the instance they were called on. It works through how method lookup and this-binding are implemented by treating a bound method as essentially a closure over its instance, reusing the same LoxFunction and environment machinery built in chapter 10 rather than inventing anything new.

Key Points:

• A LoxClass object represents a class definition, holding its name and its map of method declarations; a LoxInstance object represents one instance, holding a reference to its class and its own map of instance fields.
• Classes are callable, just like functions — calling a class creates and returns a new LoxInstance, reusing the same LoxCallable interface introduced for functions in chapter 10.
• Instance fields are added dynamically by simple assignment (instance.field = value) rather than being declared up front, matching Lox’s overall dynamically typed design.
• Method lookup checks the instance’s own fields first, then falls back to looking up a method on the instance’s class if no matching field is found.
• this is implemented by binding each method to its calling instance at lookup time, effectively creating a new closure-like environment where this is predefined — reusing the same closure mechanism built for regular functions rather than adding special-case logic.

Practice Tip: Notice that “binding” a method to this uses exactly the same closure technique from chapter 10, just with a new environment whose only variable is this — seeing object-oriented method binding as “just another closure” is the chapter’s central insight.

Common Mistake: Treating classes and their instances as requiring an entirely new evaluation mechanism — the chapter deliberately reuses existing machinery (LoxCallable for calling classes, closures for binding this on methods) rather than inventing a parallel object system from scratch.

Important Questions:

• Q1. How does jlox implement ‘this’ inside a method, given that Java has no built-in equivalent for a tree-walking interpreter? When a method is looked up on an instance, jlox creates a new environment whose enclosing environment is the method’s original closure, and binds the name this to the instance in that new environment — effectively producing a “bound method” that behaves exactly like the closures already built in chapter 10, just with this predefined as a variable. This lets the existing closure and environment machinery handle this without needing any new, special-cased evaluation logic.
• Q2. How does calling a class to create an instance reuse machinery already built for functions? LoxClass implements the same LoxCallable interface that LoxFunction implements, so calling a class (e.g., Bagel()) goes through the exact same call-dispatch code path as calling a function, just with LoxClass’s call() method creating and returning a new LoxInstance instead of running a function body. This reuse means the interpreter’s core call-handling logic, introduced in chapter 10, needs no changes at all to also support instantiating classes.

Chapter 13: Inheritance

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part I & II (tree-walk interpreter, jlox in Java) · Key topics: superclasses, method inheritance, super calls

The final chapter of Part II adds single inheritance to Lox’s class system: a class can declare a superclass, inherit its methods, override them, and call the overridden superclass version explicitly via super. The chapter shows how method lookup is extended to walk up the superclass chain when a method isn’t found on the instance’s own class, and how super calls are resolved not from the calling instance’s actual class but from the specific class where the super expression appears in the source — a subtlety that the Resolver from chapter 11 is extended to handle correctly.

Key Points:

• A LoxClass now optionally stores a reference to its superclass, forming a single-inheritance chain rather than a tree of multiple inheritance.
• Method lookup, when a method isn’t found on a class, walks up the chain of superclasses until it either finds a match or runs out of superclasses.
• super expressions must resolve to a method starting the search from the superclass of the class where the super expression is lexically written, not from the runtime class of the calling instance — which is why the Resolver from chapter 11 has to track this explicitly rather than the interpreter guessing it at run time.
• Because it needs to know where in the superclass chain to start searching, a super expression is resolved by the Resolver to a specific distance and an explicit reference to the correct superclass, similar in spirit to how ordinary variable references were resolved in chapter 11.
• This chapter completes jlox, the book’s Part II tree-walking interpreter, which by this point fully implements the entire Lox language described back in chapter 3.

Memory Tip: Keep clear that super always means “start the method search at the superclass of the class where this code is written,” not “the superclass of whatever the actual instance turns out to be” — conflating these two is the single most common source of confusion when implementing super.

Common Mistake: Resolving a super call based on the calling instance’s actual runtime class rather than the class in which the super expression is lexically written — these can differ in a multi-level inheritance chain, and getting this wrong produces infinite loops or the wrong method being called.

Important Questions:

• Q1. How does method lookup change once classes can have a superclass? When a method isn’t found directly on an instance’s own class, lookup now walks up the chain of superclasses (rather than immediately failing), checking each superclass’s own methods in turn until either a match is found or the chain of superclasses is exhausted, at which point an undefined-property runtime error is reported.
• Q2. Why must a super expression be resolved relative to the class in which it’s written, rather than the calling instance’s actual runtime class? If class C extends B extends A, and a method in B calls super.method(), that call should search starting from A (B’s own superclass) — regardless of whether the actual instance the method is running on is a B or some further subclass of C. Resolving it any other way (such as starting from the instance’s actual runtime class) would produce infinite recursion or incorrect method selection whenever inheritance is more than one level deep, which is why the Resolver from chapter 11 is extended to compute this explicitly ahead of time.

Chapter 14: Chunks of Bytecode

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: bytecode as an intermediate representation, dynamic arrays, constant pools, a disassembler

Part III begins the book’s second interpreter, clox, written in C for real speed. This chapter introduces bytecode as an intermediate representation — a compact, linear instruction encoding, much simpler than an AST for a computer to execute quickly — and builds the Chunk data structure: a dynamic array holding a sequence of bytecode instructions plus an associated constant pool for literal values. It also builds a small disassembler, which turns raw bytecode back into human-readable text, an essential debugging tool for everything that follows in Part III.

Key Points:

• Bytecode is a dense, linear sequence of simple instructions (opcodes plus operands), which is far cheaper for a computer to decode and execute than repeatedly walking a tree structure, motivating the switch away from jlox’s AST-walking design.
• A Chunk is implemented as a manually managed dynamic array in C, growing its backing memory (via realloc) as more bytecode is appended, since C has no built-in growable array type.
• Literal constant values (like numbers) are stored separately in each Chunk’s constant pool, referenced from the bytecode stream by index, rather than embedded directly in the instruction stream.
• A disassembler function walks a Chunk’s bytecode and prints each instruction in a readable text format, which becomes an essential debugging tool for every later clox chapter.
• This chapter deliberately writes only the data structures for representing bytecode, with no compiler or execution logic yet — those are built in the following two chapters.

Practice Tip: Run the disassembler on every new opcode added in later chapters as soon as it’s introduced — being able to see clox’s bytecode in readable text form is, by the author’s own framing, the single most useful debugging habit for the rest of Part III.

Common Mistake: Underestimating how much manual memory management this chapter (and the rest of Part III) requires compared to jlox — C has no garbage collector and no built-in growable arrays, so the dynamic array in this chapter has to manually track capacity, count, and reallocation, a pattern that recurs throughout clox.

Important Questions:

• Q1. Why does the book switch from an AST-walking design (jlox) to a bytecode-based design (clox) in Part III? Walking a tree structure, as jlox does, requires following pointers all over memory and repeatedly dispatching on node type at run time, which is relatively slow. Bytecode instead flattens a program into a dense, linear sequence of simple instructions that can be decoded and executed much more efficiently, which is exactly the performance trade-off this book set out in chapter 1 to demonstrate by building both kinds of interpreter.
• Q2. What is a Chunk, and what two things does it store? A Chunk is clox’s core data structure for representing a piece of compiled bytecode: it stores the actual sequence of bytecode instructions (opcodes and their operands) as a dynamic array, and it also stores a separate constant pool — another dynamic array holding literal values (like numbers) that instructions reference by index rather than embedding directly inline.

Chapter 15: A Virtual Machine

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: the VM execution loop, stack-based architecture, arithmetic instructions

This chapter builds the actual virtual machine that executes the bytecode Chunks from the previous chapter: a stack-based VM with a central fetch-decode-execute loop that reads one instruction at a time and acts on it. It introduces clox’s value stack, used to hold intermediate results during expression evaluation, and implements the first working instructions: constants, negation, and the four arithmetic operators, giving clox its first ability to actually run compiled bytecode and produce a result, even before a real compiler exists to produce that bytecode.

Key Points:

• The VM’s core is a tight loop that repeatedly reads the next opcode from the current Chunk, dispatches on it (typically via a switch statement), and executes the corresponding action — the classic fetch-decode-execute cycle.
• clox is a stack-based VM: instructions like addition pop their operands off a value stack and push their result back onto it, rather than referring to named registers.
• The value stack is implemented, like the Chunk’s bytecode array, as a manually managed array in C, with push and pop operations that the whole rest of clox will rely on.
• This chapter implements just enough opcodes (constants, negation, add/subtract/multiply/divide) to run simple arithmetic expressions end to end, deliberately before any real compiler exists.
• Because there’s no compiler yet, this chapter’s test bytecode is written by hand directly in C, as a stand-in that gets replaced once chapter 17 builds a real compiler from Lox source to bytecode.

Memory Tip: Trace a small hand-written arithmetic bytecode sequence (like the bytecode for 1 + 2 * 3) against the value stack step by step, writing down the stack’s contents after each instruction — this is the fastest way to build real intuition for how a stack-based VM actually computes a result.

Common Mistake: Expecting this chapter to compile real Lox source code into bytecode — it deliberately does not; the bytecode run in this chapter is written by hand in C as a placeholder, and an actual compiler from Lox source to bytecode isn’t built until chapter 17.

Important Questions:

• Q1. What does it mean for clox’s virtual machine to be “stack-based,” and how does this affect how arithmetic instructions work? Being stack-based means the VM keeps a value stack for intermediate results, and instructions operate implicitly on whatever values are on top of that stack rather than referring to named registers or variables. An addition instruction, for example, pops the top two values off the stack, adds them, and pushes the result back on — so a whole expression like 1 + 2 * 3 compiles into a short sequence of push and arithmetic instructions that leave exactly the final result on the stack when they finish.
• Q2. What is the VM’s core execution loop, and what is it responsible for on each iteration? The core execution loop is the heart of the run() function: on each iteration, it reads the next byte from the current instruction pointer as an opcode, dispatches on that opcode (typically with a switch statement) to figure out which operation it represents, and then performs that operation — whether that’s pushing a constant, negating the top of the stack, or performing an arithmetic operation — before advancing to the next instruction and repeating.

Chapter 16: Scanning on Demand

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: rewriting the scanner in C, single-pass on-demand scanning

This chapter rewrites jlox’s Java scanner (from chapter 4) for clox, in C, with one key architectural difference: rather than scanning the entire source file into a list of tokens up front, clox’s scanner produces tokens one at a time, on demand, exactly when the compiler (built in the next chapter) asks for the next one. This on-demand design avoids allocating a large token array up front and fits naturally with the single-pass compiler clox is about to build, which compiles source directly to bytecode without ever materializing a full token list or AST.

Key Points:

• clox’s scanner is functionally very similar to jlox’s from chapter 4, recognizing the same tokens, but is reimplemented in C instead of Java.
• Rather than scanning the whole file into an array of tokens up front (as jlox did), clox’s scanner produces exactly one token per call, called on demand by the compiler as it needs each one.
• This on-demand design fits the single-pass compiler architecture that chapter 17 will build, where source is compiled straight to bytecode without ever building an intermediate token list or AST.
• The scanner tracks its position with raw pointers directly into the source string, rather than an index into an array, which is a common, efficient idiom in C string-processing code.
• Error tokens are produced as a distinct token type by the scanner itself, letting the compiler handle scan-time errors using the same error-reporting path it will use for parse-time errors.

Practice Tip: Compare this chapter’s scanToken() function side by side with jlox’s scanner from chapter 4 — recognizing exactly which parts stayed conceptually the same (the token types, maximal munch) versus which parts changed because of the on-demand, one-token-at-a-time design is the fastest way to absorb this chapter.

Common Mistake: Assuming clox’s scanner must be less capable than jlox’s because it doesn’t build a full token list — it recognizes exactly the same set of tokens; the only real difference is when each token gets produced (on demand vs. all up front), not what gets recognized.

Important Questions:

• Q1. How does clox’s on-demand scanning differ from jlox’s scanning approach in chapter 4, and why does clox use this approach? jlox’s scanner processed the entire source file in one pass up front, producing a complete list of tokens before parsing began. clox’s scanner instead produces exactly one token at a time, only when explicitly asked for it by the compiler, without ever materializing a full token array. clox uses this approach because chapter 17’s compiler is single-pass, compiling straight from source to bytecode without a full token list or AST as an intermediate step, so scanning on demand avoids unnecessary up-front allocation and fits that architecture directly.
• Q2. How does clox’s scanner track its position in the source, and why is this idiomatic for C? clox’s scanner keeps raw pointers directly into the original source string — one marking the start of the current lexeme and one marking the current scan position — rather than maintaining a separate numeric index into an array, as might be more natural in a higher-level language. This is idiomatic C because pointer arithmetic on a character buffer is a standard, efficient way to scan text in C, avoiding the overhead of index-based bounds checking on every character.

Chapter 17: Compiling Expressions

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: single-pass compilation to bytecode, Pratt parsing with a parse-rule table

This chapter builds clox’s real compiler, replacing chapter 15’s hand-written placeholder bytecode: a single-pass compiler that reads tokens from the on-demand scanner and emits bytecode directly, with no intermediate AST at all. To handle operator precedence without building a tree first, it introduces Pratt parsing formally, via a table of parsing functions and precedence levels for every token type — a more general and table-driven technique than the ad hoc recursive descent used for jlox’s expression parser in chapter 6, well suited to emitting bytecode directly as each expression is recognized.

Key Points:

• Unlike jlox’s two-stage parse-then-evaluate pipeline, clox’s compiler is single-pass: it parses and emits bytecode simultaneously, with no AST ever built as an intermediate structure.
• Pratt parsing (formally introduced here, though foreshadowed by jlox’s recursive descent parser in chapter 6) uses a table mapping each token type to a prefix-parsing function, an infix-parsing function, and a precedence level.
• Parsing an expression at a given precedence level means: parse a prefix expression, then repeatedly check if the next token is an infix operator with high enough precedence to continue consuming, calling that operator’s infix function if so.
• Because the compiler emits bytecode as it recognizes each piece of an expression, rather than after building a whole tree, its output naturally comes out already ordered for stack-based execution — operands before the operator that consumes them.
• The table-driven Pratt parsing approach makes it comparatively easy to add new operators later just by adding a new table entry, compared to jlox’s approach of writing a new parsing method for each precedence level.

Memory Tip: Keep the three-column parse-rule table (prefix function, infix function, precedence) open side by side with the parsePrecedence() function while reading — nearly everything this chapter does is best understood as: look up this token’s row, and do what the row says.

Common Mistake: Expecting clox’s compiler to build an AST the way jlox’s parser did — it deliberately does not; the whole point of this chapter’s single-pass, Pratt-parsing design is to go directly from tokens to bytecode without ever constructing a tree data structure in between.

Important Questions:

• Q1. What is Pratt parsing, and how does it let clox’s compiler handle operator precedence without building an AST first? Pratt parsing associates each token type with a prefix-parsing function, an (optional) infix-parsing function, and a numeric precedence level, all stored in a lookup table. Parsing at a given precedence level means calling the current token’s prefix function, then repeatedly checking whether the next token is an infix operator whose precedence is high enough to keep consuming, calling its infix function if so — this table-driven approach naturally handles precedence and, because each parsing function emits its own bytecode immediately, produces correct bytecode output with no separate tree-building step required.
• Q2. How is clox’s compiler fundamentally different in structure from jlox’s parser plus interpreter from Part II? jlox used a two-stage pipeline: a parser (chapter 6) built a complete AST, which a separate Interpreter (chapter 7) then walked to evaluate. clox’s compiler instead does both jobs at once, in a single pass: as it recognizes each piece of the expression grammar, it emits the corresponding bytecode immediately, with no AST data structure ever built or stored as an intermediate representation between parsing and execution.

Chapter 18: Types of Values

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: tagged unions for Lox values in C, the Value representation

Up to this point, clox’s Value type has only represented numbers. This chapter generalizes it into a proper tagged union — a C struct pairing a type tag (indicating whether a Value is a Boolean, number, or nil) with a union holding the actual underlying data — so clox’s stack and constant pool can hold any of Lox’s basic value types uniformly. It adds the corresponding opcodes for Boolean and nil literals, generalizes the arithmetic and comparison operators to correctly type-check their operands at run time, and adds native support for equality comparison across types.

Key Points:

• A Value in clox becomes a tagged union: a struct containing a ValueType tag (BOOL, NIL, or NUMBER) plus a C union holding the actual bits, since C has no built-in dynamically typed value representation.
• New opcodes (OP_TRUE, OP_FALSE, OP_NIL) let the compiler emit literal Boolean and nil values directly, without needing a constant-pool entry the way number literals do.
• Arithmetic and comparison operators are updated to check their operand types at run time and produce a proper Lox runtime error (rather than undefined C behavior) when given the wrong type, mirroring jlox’s runtime type checking from chapter 7.
• Equality comparison (==) is implemented to work correctly across Lox’s different value types, including correctly reporting values of different types as unequal.
• This tagged-union representation is a foundational data structure that every later clox chapter, including the object system built in chapter 19, builds directly on top of.

Practice Tip: Whenever a later chapter adds a new opcode that operates on a Value, check first whether it needs to call this chapter’s type-tag-checking macros (like IS_NUMBER or AS_NUMBER) — forgetting this check is the single most common category of bug introduced from this chapter onward.

Common Mistake: Assuming C’s own type system will catch a Lox-level type error (like adding a number to a Boolean) automatically — it will not; the whole point of this chapter’s tagged-union Value type is that clox itself must explicitly check the ValueType tag at run time before treating a Value’s underlying bits as a particular type.

Important Questions:

• Q1. Why does clox need a tagged union to represent Lox values, when jlox simply used Java’s own object types? Java already provides dynamically typed references and runtime type information built into the language, so jlox could just store a Lox value as a plain Java Object and use instanceof to check its type. C has no such built-in dynamic typing, so clox has to construct this capability itself: a tagged union pairs an explicit type tag with a C union holding the raw data, letting code check the tag before deciding how to interpret the underlying bits.
• Q2. How does this chapter extend runtime type checking (first introduced for jlox in chapter 7) to clox’s arithmetic and comparison operators? Each arithmetic and comparison operator’s bytecode handler in the VM’s execution loop now checks the ValueType tag of its operand(s) before performing the operation — for example, refusing to add two values unless both are tagged as numbers — and if the check fails, it reports a Lox runtime error and stops execution, exactly mirroring the runtime type checking jlox performed in its tree-walking Interpreter back in chapter 7.

Chapter 19: Strings

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: object representation, heap-allocated strings, string interning (introduced)

This chapter adds strings to clox, which requires a new kind of Value: heap-allocated objects, since strings (unlike numbers or Booleans) have variable size and need dynamic memory management. It introduces the Obj struct as a common header for all of Lox’s heap-allocated types, builds ObjString on top of it, links every allocated object into a linked list (laying the groundwork for garbage collection much later, in chapter 26), and implements string concatenation with +. It also introduces the concept of string interning, fully implemented in the next chapter’s hash table.

Key Points:

• clox introduces a new value type, OBJ, whose payload is a pointer to a heap-allocated Obj struct — the common header type for every kind of Lox object, starting with strings.
• ObjString extends the base Obj struct with the string’s length and character data, using a common C idiom for a form of manual, struct-based inheritance.
• Every object allocated by clox is linked into a global intrusive linked list at allocation time, which is not used yet but is essential groundwork for the mark-sweep garbage collector built in chapter 26.
• String concatenation via + is implemented by allocating a new heap string containing the combined characters, since Lox strings, once created, are treated as immutable.
• The chapter introduces the idea of string interning (ensuring equal strings share one allocation, so equality can be checked by pointer comparison) as motivation for the hash table built in the very next chapter.

Memory Tip: Notice that this chapter links every new object into a linked list purely for future use, with no payoff yet — recognizing this pattern (infrastructure built chapters ahead of when it’s actually used) is common throughout Part III and worth watching for.

Common Mistake: Assuming Lox strings are mutable in clox’s implementation — they are treated as immutable once created, exactly as in jlox, which is why concatenation must allocate an entirely new string rather than modifying an existing one in place.

Important Questions:

• Q1. Why does adding strings to clox require an entirely new kind of Value, unlike Booleans, numbers, and nil? Booleans, numbers, and nil are all fixed-size and can be stored directly inline inside the Value tagged union introduced in chapter 18. Strings, by contrast, have variable length and need their own dynamically allocated memory, so clox represents them as heap-allocated Obj structs, with the Value itself just holding a pointer to that heap allocation — a level of indirection numbers and Booleans don’t need.
• Q2. What is the purpose of linking every allocated object into a global linked list in this chapter, even though nothing uses that list yet? The linked list of all live objects is groundwork for the mark-sweep garbage collector built much later, in chapter 26 — when the collector eventually needs to sweep through every object clox has ever allocated to find and free the ones that are no longer reachable, this list is exactly what lets it do that. Building it now, alongside the first object type (strings), means every object type added in later chapters automatically participates in garbage collection without extra work.

Chapter 20: Hash Tables

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: building a hash table from scratch in C, open addressing, string interning

Because C provides no built-in hash table, this chapter builds one entirely from scratch for clox, using open addressing with linear probing and tombstone deletion to handle collisions and removals. This hash table becomes the mechanism for two important later features: interning every string clox creates (so identical strings share one allocation, and string equality can be checked with a single pointer comparison instead of comparing characters), and, in the next chapter, storing Lox’s global variables.

Key Points:

• clox implements its own open-addressing hash table with linear probing, since C’s standard library provides no general-purpose hash table type.
• Deleting an entry uses a tombstone marker rather than simply clearing the slot, since naively clearing a slot in an open-addressing table can break the probe sequence for other entries that hash to the same bucket.
• The table automatically grows (and rehashes all existing entries) once it crosses a load-factor threshold, keeping lookup performance from degrading as more entries are added.
• String interning is implemented using this hash table: whenever a new string is created, the table is checked first for an existing identical string, and if found, that same allocation is reused instead of creating a duplicate.
• Once interning guarantees that equal strings always share one allocation, string equality throughout clox can be checked with a single, fast pointer comparison rather than comparing characters one by one.

Practice Tip: Work through a small linear-probing insert-and-delete sequence by hand, including at least one tombstone case — understanding on paper why a deleted slot must be marked rather than cleared is the key insight that makes the rest of this chapter’s code make sense.

Common Mistake: Simply clearing a hash table slot to “empty” on deletion instead of marking it with a tombstone — in an open-addressing table, this can break the probe sequence for other entries that were placed further along the same collision chain, causing later lookups for those entries to incorrectly fail.

Important Questions:

• Q1. Why does a naive deletion (just clearing the slot) break an open-addressing hash table, and how does the tombstone technique fix this? In open addressing with linear probing, an entry that collides with an occupied slot is placed in the next available slot along a probe sequence; a lookup for that entry must keep probing past the original slot until it either finds the entry or hits a truly empty slot. If a deletion simply clears a slot to empty, it can incorrectly signal “nothing here, stop probing” partway through another entry’s probe sequence, causing that entry’s later lookups to fail even though it’s still in the table. Marking the deleted slot with a tombstone instead tells lookups “keep probing past here,” while still allowing that slot to be reused by future insertions.
• Q2. How does this chapter’s hash table enable string interning, and what performance benefit does interning provide? Whenever clox creates a new string, it first checks this hash table for an already-existing, identical string; if one is found, clox reuses that existing allocation instead of creating a duplicate, and only inserts a genuinely new entry when no match exists. Because this guarantees that every distinct string value in a running clox program has exactly one allocation, checking whether two strings are equal can be done with a single, fast pointer comparison, instead of comparing every character of both strings each time.

Chapter 21: Global Variables

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: implementing global variable declaration, access, and assignment in clox

This chapter adds global variables to clox, using the hash table built in the previous chapter to map each global variable’s name directly to its current value. It extends the compiler to recognize var declarations and variable-reference expressions at the top level, adds the corresponding opcodes for defining, reading, and assigning globals, and shows how storing globals by name in a hash table (rather than by fixed stack slot, as local variables will be in the next chapter) is a deliberately simple, if not maximally fast, design appropriate for clox’s first working variable system.

Key Points:

• Global variables are stored in a hash table (from chapter 20) mapping each variable’s interned name string directly to its current Value, making lookup, definition, and assignment all straightforward table operations.
• The compiler emits new opcodes — OP_DEFINE_GLOBAL, OP_GET_GLOBAL, and OP_SET_GLOBAL — each carrying a constant-pool index pointing at the variable’s name string.
• Storing globals by name in a hash table is explicitly noted as simple but not the fastest possible design; the next chapter’s local variables use a much faster, index-based scheme instead, since most variable accesses in real programs are to locals, not globals.
• Assigning to an undeclared global variable is treated as a runtime error, requiring the VM to check for the variable’s existence in the table before allowing the assignment to proceed.
• This chapter gives clox its first genuinely stateful programs — scripts that declare and update variables across multiple statements — something the purely expression-evaluating clox from earlier chapters could not do at all.

Memory Tip: Notice which design choice differs between this chapter’s globals (looked up by name, in a hash table) and the next chapter’s locals (looked up by fixed numeric stack slot) — this contrast is deliberate, and understanding why locals can be faster is exactly the point of chapter 22.

Common Mistake: Assuming clox’s global-variable design (hash table lookup by name) is how all Lox variables work — it’s specifically how globals work; the very next chapter replaces this approach for local variables with a much faster, index-based scheme, precisely because most variable accesses in real programs are to locals.

Important Questions:

• Q1. How are global variables stored and looked up in clox, and what data structure from the previous chapter makes this possible? Global variables are stored in the hash table built in chapter 20, which maps each variable’s interned name (a string) directly to its current Value. Declaring a global variable inserts an entry into this table; reading or assigning to one looks up or updates the entry by name, using the table’s existing insert and lookup operations with no new data structure required.
• Q2. Why does the book explicitly call out that hash-table-based global variable storage is not the fastest possible design? Looking up a variable by hashing its name string and probing a table, on every single access, is noticeably slower than simply reading a value out of a fixed array slot by numeric index. The book flags this because it’s a deliberate, temporary simplification: the very next chapter shows that local variables — which make up the overwhelming majority of variable accesses in typical programs — can instead be resolved to fixed stack slots at compile time, avoiding hash table lookups entirely and making them significantly faster than globals.

Chapter 22: Local Variables

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: stack-based local variable storage, compile-time resolution to stack slots

This chapter implements local variables in clox with a much faster design than globals: rather than looking them up by name at run time, the compiler tracks each local variable’s position directly on the VM’s value stack at compile time, so that reading or writing a local variable becomes, at run time, nothing more than reading or writing a specific numbered stack slot. It works through how the compiler manages nested scopes and variable shadowing purely as compile-time bookkeeping, with block scopes requiring no runtime environment objects at all, unlike jlox’s design in chapter 8.

Key Points:

• Local variables are resolved entirely at compile time: the compiler tracks, in an ordinary array, which stack slot each currently-in-scope local variable occupies.
• At run time, reading or writing a local variable compiles to a direct, indexed access into the VM’s value stack (OP_GET_LOCAL / OP_SET_LOCAL with a slot index), with no hash table lookup and no separate environment object at all.
• Entering a new block scope at compile time simply means remembering how many locals were declared before it started; exiting the block means popping the stack back down to that count and forgetting those local declarations.
• This design is a direct contrast with jlox’s Environment-chain approach from chapter 8 — where jlox allocated a real object per scope at run time, clox’s locals cost nothing at run time beyond ordinary stack slots.
• Variable shadowing (an inner-scope local variable reusing an outer scope’s name) is handled correctly because the compiler’s local-tracking array records each declaration’s specific scope depth, not just its name.

Practice Tip: Compare this chapter’s compile-time slot-tracking array directly against jlox’s runtime Environment chain from chapter 8 — both solve the exact same scoping problem, and seeing the same problem solved at two completely different points in the pipeline (compile time vs. run time) is the clearest way to appreciate clox’s core performance strategy.

Common Mistake: Expecting clox to allocate any kind of environment object for local variables at run time, the way jlox did — it deliberately does not; the whole performance gain of this chapter comes from resolving locals to plain stack slots entirely at compile time, leaving nothing but ordinary stack operations at run time.

Important Questions:

• Q1. How does clox’s compile-time approach to local variables differ from jlox’s runtime Environment-chain approach from chapter 8? jlox represented each scope with a real Environment object at run time, and looked up a local variable by walking outward through a chain of these environment objects. clox instead does all of this bookkeeping at compile time: the compiler tracks, in a simple array, exactly which stack slot each local variable occupies, and emits bytecode that reads or writes that specific slot number directly — so at run time, accessing a local variable is just an ordinary, fast, indexed stack access, with no environment object or chain-walking involved at all.
• Q2. How does clox handle entering and exiting a block scope, given that there’s no runtime environment object to create or discard? Entering a block scope at compile time just means the compiler records how many local variables were already declared before the block started. Exiting the block means the compiler emits pop instructions to remove exactly the locals that were declared inside it from the value stack, and then simply forgets those declarations from its own compile-time tracking array — there is no runtime environment object to allocate or discard at all, only ordinary stack pops.

Chapter 23: Jumping Back and Forth

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: implementing if, while, and for as bytecode jump instructions with backpatching

This chapter implements Lox’s control flow — if/else, while loops, and for loops — in clox using conditional and unconditional jump instructions that manipulate the VM’s instruction pointer directly, since bytecode has no inherent notion of nested blocks the way an AST does. Because the exact jump distance for a forward jump (like skipping over an else branch) isn’t known until the compiler has finished compiling everything in between, the chapter introduces backpatching: emitting a placeholder jump offset first, then going back and filling in the real offset once it’s known.

Key Points:

• Control flow in bytecode is implemented with jump instructions that directly modify the VM’s instruction pointer, either unconditionally or based on the truthiness of the value on top of the stack.
• Backpatching solves the problem of not knowing a forward jump’s exact target offset until after compiling the code that comes between the jump and its target: the compiler emits a placeholder offset, remembers its location, and patches in the real offset once it’s known.
• if/else compiles to a conditional jump (skipping the then-branch if the condition is false) followed by the then-branch code, an unconditional jump (skipping the else-branch), and then the else-branch code.
• while loops compile to a condition check, a conditional jump out of the loop, the loop body, and then an unconditional jump backward to re-check the condition — a backward jump, whose target offset is already known at the point it’s emitted, needing no backpatching.
• for loops, unlike in jlox’s desugaring approach in chapter 9, are compiled directly to their own combination of forward and backward jumps in clox, rather than being rewritten in terms of while loops before code generation.

Memory Tip: Keep clear which jumps need backpatching and which don’t: forward jumps (skip past code not yet compiled) need it, since their distance isn’t known yet, while backward jumps (loop back to already-compiled code) don’t, since that code’s position is already fixed and known.

Common Mistake: Assuming for loops in clox are desugared into while loops the same way jlox did back in chapter 9 — this chapter instead compiles for loops directly into their own bytecode jump pattern, without ever rewriting them in terms of a while loop first.

Important Questions:

• Q1. What is backpatching, and why does compiling an if statement’s jump instructions require it? Backpatching means emitting a jump instruction with a placeholder offset value first, recording the position of that placeholder, and then going back later to overwrite it with the real jump distance once that distance is known. Compiling an if statement needs this because the conditional jump that skips the then-branch has to know exactly how many bytes of then-branch bytecode to skip over — but the compiler doesn’t know that count until it has finished compiling the entire then-branch, which happens after the jump instruction itself has already been emitted.
• Q2. Why do backward jumps (used for loop conditions) not need backpatching, while forward jumps (used for skipping branches) do? A backward jump’s target — the point earlier in the bytecode where the loop condition check begins — has already been compiled and therefore has a known, fixed position by the time the backward jump instruction is emitted at the end of the loop body. A forward jump’s target, by contrast, is code that hasn’t been compiled yet at the point the jump instruction is emitted, so its exact distance can only be filled in after the fact, which is exactly what backpatching is for.

Chapter 24: Calls and Functions

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: implementing function calls in clox, call frames, the call stack

This chapter adds function declarations and calls to clox, the most substantial addition to the VM so far. It introduces CallFrame, a struct representing one active function call — its own instruction pointer, and its own window into the shared value stack for parameters and local variables — and reworks the VM’s core execution loop to operate relative to the current frame’s instruction pointer and stack window, so that calling and returning from a function is implemented as pushing and popping CallFrames rather than anything resembling jlox’s Java-exception-based return mechanism from chapter 10.

Key Points:

• A CallFrame represents one active function call: it stores its own return instruction pointer and a pointer marking where its portion of the shared value stack begins, so each call gets its own private “window” onto one shared stack.
• The VM maintains a call stack of CallFrames (a fixed-size array, since Lox doesn’t support truly unbounded recursion depth in clox), corresponding to the chain of currently active function calls.
• Calling a function pushes a new CallFrame, sets its stack window to start right after the function’s arguments (already on the stack), and redirects the VM’s fetch-decode-execute loop to read instructions from the callee’s bytecode instead.
• Returning from a function pops its CallFrame, discards its portion of the stack, and resumes execution using the calling frame’s saved instruction pointer — a much simpler, purely stack-based mechanism than jlox’s exception-based return from chapter 10.
• Native (built-in) functions, like clock() from chapter 10, are also reimplemented for clox, callable through the same call mechanism as user-defined Lox functions.

Practice Tip: Draw the shared value stack as one long strip, then mark off each active CallFrame’s window on it with brackets — seeing that every function call shares the same physical stack, just at a different offset, is the key mental model for understanding how clox handles calls without allocating anything on the heap for each call.

Common Mistake: Assuming each function call in clox gets its own separate stack, the way it conceptually might in some other systems — every CallFrame instead shares one single value stack, just starting at a different offset into it, which is exactly what makes clox’s function calls cheap compared to heap-allocating a fresh structure per call.

Important Questions:

• Q1. What is a CallFrame, and what two things does it need to track for each active function call? A CallFrame represents one currently active function call in clox. It tracks the function’s own return instruction pointer (so execution can resume in the right place in the calling code once the function returns) and a pointer marking where in the VM’s single, shared value stack this particular call’s parameters and local variables begin — giving each active call its own private “window” onto the one shared stack, without needing a separate stack allocation per call.
• Q2. How does returning from a function work in clox, and how does this compare to how jlox implemented return in chapter 10? In clox, returning from a function pops the current CallFrame off the VM’s call-frame stack, discards that frame’s portion of the shared value stack, and resumes execution using the calling frame’s saved instruction pointer — a purely mechanical stack operation. This is a much simpler mechanism than jlox’s approach in chapter 10, which relied on throwing and catching a special Java exception to unwind the tree-walking evaluation of nested statements back to the point of the function call.

Chapter 25: Closures

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: implementing closures in clox, upvalues, closing over stack variables

This chapter adds closures to clox — functions that capture variables from an enclosing function, exactly as jlox’s closures did in chapter 10, but now over locals that live on clox’s shared value stack, which get popped off and effectively disappear once the enclosing function returns. The solution is the upvalue: a small object that starts out pointing directly at a still-live stack slot, and then, when that stack slot is about to be popped (the local going out of scope), is “closed” by copying the value out of the stack and into the upvalue’s own storage — letting the closure keep referencing it safely afterward.

Key Points:

• An ObjClosure wraps a compiled function together with an array of upvalues, representing the specific set of outer-scope variables that particular closure has captured.
• An open upvalue points directly at a live slot on the VM’s value stack, so as long as the enclosing function is still running, reads and writes through the upvalue see the exact same value as the original local variable.
• When a local variable that has been captured by an upvalue is about to be popped off the stack (because its enclosing scope or function is ending), the VM “closes” the upvalue: it copies the value out of the stack slot into storage owned by the upvalue itself, and the upvalue is repointed to that copy.
• The VM keeps a sorted linked list of currently open upvalues so that multiple closures capturing the same local variable all share one single upvalue object, keeping their views of that variable correctly in sync.
• This upvalue mechanism is clox’s solution to the same fundamental problem jlox solved with its Environment-based closures in chapter 10, adapted to work correctly with clox’s much faster, stack-based local variable storage from chapter 22.

Memory Tip: Keep the open-vs-closed upvalue distinction front of mind: “open” means still pointing live into the stack (the enclosing function is still running), and “closed” means the value has been copied out because the stack slot it used to point to is about to be reused or discarded.

Common Mistake: Assuming a closure in clox could just keep a raw pointer into the value stack indefinitely — that pointer becomes invalid once the enclosing function returns and that stack region is reused, which is exactly the problem upvalues, and specifically the closing step, are designed to solve.

Important Questions:

• Q1. What problem do upvalues solve, and why is this problem specific to clox’s stack-based design rather than something jlox also had to solve the same way? clox stores local variables directly on a shared, reused value stack (chapter 22), so once the function that declared a local variable returns, that stack slot gets reused by later calls, which would corrupt any closure still trying to reference the original variable by its old stack position. jlox never had this problem because its Environment objects (chapter 10) were independently heap-allocated and simply stayed alive as long as any closure referenced them; clox needs upvalues specifically because it does not use per-scope heap allocation for locals, so it needs another mechanism to keep a captured variable alive and correct after its original stack slot is gone.
• Q2. What is the difference between an open upvalue and a closed upvalue? An open upvalue points directly at a live slot on the VM’s value stack, so it sees exactly the same value as the original local variable for as long as the enclosing function call is still active. A closed upvalue, by contrast, has had the value copied out of that stack slot into storage owned by the upvalue object itself, which happens right before the stack slot it used to point to would otherwise be popped or reused — letting the closure keep accessing a correct, stable copy of the value even after the original local variable’s stack frame is gone.

Chapter 26: Garbage Collection

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: mark-sweep garbage collection, tracing roots, GC-during-compilation edge cases

This chapter gives clox automatic memory management, since C provides none: a mark-sweep garbage collector that periodically traces every object reachable from the VM’s roots (the value stack, global variables, and open upvalues), marks each one as still in use, and then sweeps through the linked list of every allocated object (built all the way back in chapter 19) freeing anything left unmarked. The chapter pays particular attention to tricky edge cases where a collection could be triggered mid-compilation or mid-allocation, before an object is fully linked into a root-reachable structure, which would otherwise cause it to be incorrectly collected.

Key Points:

• Mark-sweep garbage collection has two phases: marking, which traces outward from a set of roots (the value stack, global variables, and open upvalues) to find every currently reachable object, and sweeping, which frees every allocated object that marking did not reach.
• Roots are the starting points for the mark phase — anything directly accessible without going through another object, including every value currently on the VM’s stack and every global variable.
• The linked list of all allocated objects, built starting in chapter 19 specifically for this purpose, is exactly what the sweep phase walks to find and free every unreached object.
• Certain objects (like class methods or closed-over upvalues) are only reachable indirectly, through another object, so marking must recursively trace through an object’s own references, not just check the roots directly.
• The chapter identifies and fixes specific timing bugs where a garbage collection triggered at exactly the wrong moment — such as mid-way through compiling, or right after allocating an object but before it’s stored anywhere reachable — could incorrectly free an object still in use, requiring careful placement of temporary “stack it immediately” safeguards.

Practice Tip: When reading the timing-bug fixes near the end of this chapter, ask for each one: “what object was reachable a moment ago but temporarily isn’t, from the collector’s point of view, right now?” — nearly every fix in this chapter is a variation on making sure a freshly allocated object is reachable from a root before anything else that could trigger a collection runs.

Common Mistake: Assuming a garbage collection can only happen at safe, predictable moments — the chapter’s whole final section is dedicated to showing that a collection can be triggered by any allocation, at unexpected points such as mid-compilation, which is exactly why several objects need explicit, temporary protection from being collected before they’re fully linked into a reachable structure.

Important Questions:

• Q1. What are the two phases of mark-sweep garbage collection, and what does each one do? The mark phase starts from the VM’s roots (everything on the value stack, all global variables, and all open upvalues) and recursively traces through every object reachable from them, marking each one found along the way as still in use. The sweep phase then walks the complete linked list of every object clox has ever allocated (built starting in chapter 19) and frees any object that the mark phase did not mark, since an unmarked object is, by definition, unreachable from any root and therefore safe to reclaim.
• Q2. Why does the timing of when a garbage collection can be triggered create tricky bugs, and what kind of situation does this chapter identify as especially risky? Because a collection can potentially be triggered by any memory allocation in clox, an object can be freshly allocated and then, before it’s actually stored anywhere the collector’s root-tracing would find it (such as being pushed onto the value stack or linked into another object), become the target of a collection triggered by a subsequent allocation — incorrectly freeing an object that’s still needed. This is especially risky during compilation, where intermediate objects (like string constants) can be created and briefly left unreachable from the VM’s usual roots before being placed into the chunk being compiled, requiring the chapter’s specific timing fixes.

Chapter 27: Classes and Instances

Difficulty: Intermediate · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: implementing classes and instances in clox, ObjClass, ObjInstance, property tables

This chapter brings object-oriented programming to clox, building ObjClass and ObjInstance as two new heap-allocated object types (extending the Obj system from chapter 19), each following the same pattern used for strings and functions. It adds the compiler support for class declarations and property get/set expressions, and implements each instance’s fields as its own hash table (reusing chapter 20’s hash table implementation directly), mirroring jlox’s LoxClass and LoxInstance design from chapter 12 but built from clox’s lower-level object and hash-table machinery.

Key Points:

• ObjClass and ObjInstance are two new object types, built on the same Obj header pattern established for strings (chapter 19) and functions (chapter 24), each participating in the same allocation-tracking and (eventually) garbage-collection systems automatically.
• Each ObjInstance stores its own fields directly in a hash table (reusing chapter 20’s hash table implementation), exactly mirroring how jlox stored instance fields in a map back in chapter 12.
• New opcodes (OP_GET_PROPERTY and OP_SET_PROPERTY) implement reading and writing instance fields by name, looking the name up as a key in the instance’s own field hash table.
• Classes are made callable, exactly as in jlox, so that calling a class value creates and returns a new ObjInstance — reusing the VM’s existing call-dispatch mechanism from chapter 24 rather than adding a separate instantiation code path.
• This chapter deliberately implements only fields, not yet methods — methods, and the more advanced bound-method optimization, are added in the next chapter.

Memory Tip: Compare this chapter’s ObjClass/ObjInstance design directly against jlox’s LoxClass/LoxInstance from chapter 12 — the conceptual design is almost identical; what’s different is only the lower-level machinery (Obj headers, an explicit hash table) that clox needs to build the same idea in C.

Common Mistake: Expecting method calls to work by the end of this chapter — this chapter deliberately implements only instance fields (get/set by name); actual method declarations and calls are added in the very next chapter, chapter 28.

Important Questions:

• Q1. How does clox represent an instance’s fields, and what earlier chapter’s data structure does this reuse? Each ObjInstance stores its own fields directly in a hash table, reusing the exact same open-addressing hash table implementation built in chapter 20 (originally for string interning and global variables). Reading a field (OP_GET_PROPERTY) or writing one (OP_SET_PROPERTY) is implemented as a lookup or insertion into that instance’s own table, keyed by the field’s (interned) name string.
• Q2. How does calling a class to create a new instance work in clox, and how does this compare to how jlox did it in chapter 12? Calling a class value goes through the same call-dispatch mechanism built in chapter 24 for ordinary function calls, with the VM recognizing that the callee is an ObjClass and, instead of running a function body, allocating and returning a new ObjInstance associated with that class. This closely mirrors jlox’s approach in chapter 12, where LoxClass implemented the same LoxCallable interface used by functions — in both interpreters, instantiating a class deliberately reuses the existing function-call machinery rather than introducing a separate mechanism.

Chapter 28: Methods and Initializers

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: implementing bound methods, method invocation optimization, init() as initializer

This chapter adds methods to clox’s classes, plus a specific performance optimization for the extremely common case of calling a method immediately (like instance.method()): rather than always creating an intermediate ObjBoundMethod object, the compiler emits a single combined OP_INVOKE instruction that looks up and calls a method in one step, falling back to the slower, general bound-method path only when a method is accessed without immediately being called. It also implements Lox’s init() method as a class’s designated initializer, automatically called on construction and always implicitly returning the instance itself.

Key Points:

• ObjBoundMethod represents a method that has been looked up on an instance but not yet called, pairing the method’s function with the instance it was bound to — the general-purpose mechanism, mirroring jlox’s this-binding-as-closure design from chapter 12.
• Because the common case is looking up a method and calling it immediately, the compiler recognizes this pattern and emits a single specialized OP_INVOKE instruction that performs the lookup and call together, skipping the overhead of allocating an intermediate ObjBoundMethod.
• The slower, general OP_GET_PROPERTY path is still used whenever a method is accessed without being immediately called (such as storing a reference to it in a variable), correctly falling back to producing a genuine ObjBoundMethod in that case.
• A class’s init() method, if defined, is automatically invoked whenever an instance of that class is created, implementing Lox’s constructor-initialization behavior.
• Calling return with no value inside init() (or reaching the end of init() without an explicit return) is specifically compiled to still return the instance itself, not nil, matching Lox’s rule that a constructor call always yields the new instance.

Practice Tip: Notice that OP_INVOKE is purely a performance optimization, not a new capability — everything it does could also be accomplished, just more slowly, by the existing OP_GET_PROPERTY followed by an ordinary call; recognizing optimizations like this as “the same behavior, done faster” is a useful lens for several of clox’s later chapters too.

Common Mistake: Forgetting that init() must always yield the instance itself, even when it contains an early, explicit, argument-less return — the chapter specifically compiles a bare return inside init() to still produce the instance, not nil, which requires special-casing in the compiler rather than falling out automatically from ordinary return handling.

Important Questions:

• Q1. What is the OP_INVOKE optimization, and what problem does it solve compared to always using ObjBoundMethod? Without this optimization, calling a method like instance.method() would always go through two separate steps: first looking up the method and allocating an ObjBoundMethod pairing it with the instance (OP_GET_PROPERTY), and then calling that bound method object. Since this immediate-lookup-then-call pattern is overwhelmingly the most common way methods are actually used, the compiler instead recognizes it and emits a single OP_INVOKE instruction that performs the lookup and the call together in one step, entirely avoiding the ObjBoundMethod allocation in the common case, while still falling back to the general two-step path when a method is accessed without being immediately called.
• Q2. How does clox ensure that calling a class’s init() method as a constructor always returns the newly created instance? The compiler specifically recognizes when it is compiling the body of a method named init(), and in that case, compiles a bare return statement (or the implicit return at the end of the method body) to load and return the instance itself (stored in local slot 0, the same slot this occupies for any method) rather than the usual nil — a targeted special case, since ordinarily a function or method with no explicit return value simply returns nil.

Chapter 29: Superclasses

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: implementing inheritance in clox, method table copying, compile-time super resolution

This final class-related chapter adds single inheritance to clox’s class system, matching jlox’s chapter 13 feature set but implemented very differently for speed: rather than walking a chain of superclasses at every method lookup, clox copies all of a superclass’s methods directly into the subclass’s own method table at class-declaration time, so a normal method lookup on any instance never needs to know or care whether that method was inherited. super calls are instead resolved specially, using a dedicated OP_GET_SUPER / OP_SUPER_INVOKE mechanism that explicitly bypasses the subclass’s own (possibly overriding) method table.

Key Points:

• When a subclass is declared, clox copies every entry from its superclass’s method table directly into its own method table, so that ordinary method lookup afterward requires no chain-walking at all — a direct, single-table lookup finds inherited methods exactly as if they’d been declared directly on the subclass.
• This copy-based design is a deliberate speed trade-off compared to jlox’s chapter 13 approach of walking up a live chain of superclass references on every lookup — clox instead pays a one-time cost at class-declaration time to make every later lookup fast.
• super expressions are resolved specially, since they must explicitly reach past the subclass’s own (possibly overriding) method to find the superclass’s original version — solved with a dedicated OP_GET_SUPER opcode that looks up the method starting specifically from the correct superclass.
• Just as OP_INVOKE optimized the common immediate-call case for ordinary methods in chapter 28, an analogous OP_SUPER_INVOKE opcode optimizes the common case of calling a super method immediately, avoiding an intermediate bound-method allocation.
• Because the compiler must know, at compile time, which superclass a given super expression refers to, the Resolver-like compile-time tracking introduced conceptually in jlox’s chapter 11 has a direct counterpart here in how clox’s compiler tracks the enclosing class hierarchy while compiling.

Memory Tip: Contrast this chapter’s copy-the-methods-once design directly against jlox’s walk-the-chain-every-time design from chapter 13 — both correctly implement the exact same inheritance semantics; the difference is entirely about where the cost is paid (once, at class declaration, versus repeatedly, on every lookup).

Common Mistake: Assuming clox looks up inherited methods by walking a live chain of superclass pointers, the way jlox did in chapter 13 — clox instead copies a superclass’s methods directly into each subclass’s own table once, at class-declaration time, specifically to avoid any chain-walking during ordinary method lookup afterward.

Important Questions:

• Q1. How does clox’s approach to inherited method lookup differ from jlox’s, and why does clox choose this different approach? jlox’s LoxClass (chapter 13) kept a live reference to its superclass and walked up that chain on every method lookup that wasn’t found directly on the instance’s own class. clox instead copies every method from a superclass’s table directly into the subclass’s own method table at the moment the subclass is declared, so an ordinary method lookup afterward is always a single, direct lookup in one table, with no chain to walk at all. clox makes this trade-off because chain-walking on every single method call would add repeated overhead, while copying the methods costs something only once, at class-declaration time, which happens far less often than method calls do.
• Q2. Why does resolving a super call require special handling (OP_GET_SUPER) rather than just using clox’s ordinary method lookup? Because clox copies a superclass’s methods into the subclass’s own table, an ordinary lookup by name on an instance would simply find whichever version of a method is currently in that table — which, if the subclass has overridden that method, would be the subclass’s own version, not the superclass’s original one that super is specifically meant to reach. OP_GET_SUPER instead performs a lookup that starts explicitly from a specific superclass (determined at compile time, since the compiler tracks the current class’s superclass while compiling), correctly bypassing any overriding version on the subclass itself.

Chapter 30: Optimization

Difficulty: Advanced · BSCS — Compilers / Programming Languages course, Part III (bytecode virtual machine, clox in C) · Key topics: profiling-driven optimization case studies, NaN boxing, faster hash table probing

The book’s final chapter steps back from adding new language features and instead works through concrete optimization case studies applied to the now-complete clox, demonstrating the profiling-first mindset that should guide real-world optimization work: measure before guessing what’s slow. It walks through NaN boxing (packing every Lox value, including numbers, Booleans, nil, and object pointers, into the bit pattern of a single 64-bit double, cutting Value’s memory footprint significantly) and a faster hash table probing strategy, framing both as examples of a general optimization process rather than as a checklist to apply blindly.

Key Points:

• The chapter’s central methodology point is to profile first and optimize based on real measurements, rather than guessing which parts of a program are slow — a general principle the specific optimizations in this chapter are meant to illustrate, not replace.
• NaN boxing is a technique for representing every kind of Lox Value — numbers, Booleans, nil, and object pointers — within the same 64 bits as a single double, by exploiting the large space of unused bit patterns within IEEE 754 NaN values, shrinking Value’s size considerably compared to the tagged-union design from chapter 18.
• A second optimization revisits the hash table’s probing strategy from chapter 20, showing how a small, targeted change to how collisions are resolved can measurably speed up the table without changing its overall open-addressing design.
• Both optimizations are presented together with real before-and-after benchmark results, modeling how to actually validate that a proposed optimization delivers a genuine, measurable improvement rather than just “seeming” faster.
• This chapter closes the book’s core narrative: with it, clox is a complete, reasonably fast bytecode virtual machine implementing the entire Lox language specified back in chapter 3, with two appendices (the Lox grammar and generated AST classes) as reference material after it.

Memory Tip: Treat this chapter’s two specific optimizations (NaN boxing, hash table probing) as worked examples of a process, not a checklist — the book’s own point is that profiling-driven measurement, not any specific trick, is the actual lesson meant to carry forward to other programs.

Common Mistake: Applying NaN boxing or similar low-level optimizations to a program without first profiling to confirm they address an actual measured bottleneck — this chapter explicitly frames profile-first measurement, not any particular trick, as the real, generalizable lesson to take away from it.

Important Questions:

• Q1. What is NaN boxing, and what problem does it solve compared to the tagged-union Value representation built in chapter 18? NaN boxing packs every kind of Lox value — numbers, Booleans, nil, and object pointers — into the same 64 bits as a single double-precision floating point number, by using specific, otherwise-unused bit patterns within the IEEE 754 standard’s space of NaN (“not a number”) values to encode non-number types. This solves a memory-footprint problem with chapter 18’s tagged-union design, whose separate type tag field makes every Value noticeably larger than a bare 64-bit double; NaN boxing fits everything into that same 64 bits, at the cost of significantly trickier, bit-manipulation-heavy code to pack and unpack values.
• Q2. What methodology does this chapter emphasize as more important than either specific optimization it demonstrates? The chapter repeatedly emphasizes profiling first: measuring where a program is actually spending its time before deciding what to optimize, and then validating any proposed change with real before-and-after benchmarks, rather than optimizing based on intuition about what “seems” slow. NaN boxing and the hash table probing improvement are presented as concrete illustrations of this process being applied to clox specifically, not as a general-purpose checklist meant to be applied to any program regardless of what its actual bottlenecks turn out to be.

Read Crafting Interpreters Online (Free)

This book is free from its official source — author Robert Nystrom publishes the complete text online for free, with every chapter fully readable, alongside the full source code for both interpreters built in the book. A paid print/ebook edition also exists, but the legitimate free way to read the complete book is the official web edition below.

How to Study This Book

This book should be read in order — Part II (jlox, Chapters 4–13) and Part III (clox, Chapters 14–30) both implement the exact same language, Lox, introduced in Chapter 3, so reading Part II first gives essential context for Part III’s much lower-level implementation of the same features.

Part I (Chapters 1–3) is short but essential — Chapter 3’s tour of the Lox language is the specification every later chapter, in both interpreters, implements piece by piece.

Within Part II, work through Chapters 4–13 in order and actually run the code — jlox is built incrementally, with each chapter’s interpreter a strict superset of the previous chapter’s, so skipping ahead makes later chapters hard to follow.

Part III (Chapters 14–30, clox) is significantly more demanding than Part II, since it’s written in C and covers low-level topics like manual memory management, a hash table built from scratch, and garbage collection — budget considerably more time per chapter here than in Part II.

The book’s own source code (linked from the official site) is worth keeping open alongside the text — both jlox and clox are complete, runnable projects, and running the actual code for a chapter is often clearer than reading the prose description alone.

Used In These Programs

This book is used as a Compilers, Programming Languages, or Language Implementation elective text in: BSCS and Programming coursework. Browse all Computer Science category books.

Who Should Read This

Crafting Interpreters is written for programmers who already have some programming experience and want a hands-on, project-based understanding of how programming languages are actually implemented — from scanning and parsing through evaluation, and down to a real bytecode virtual machine with manual memory management and garbage collection. It suits BSCS students taking a Compilers or Programming Languages elective, and is especially valuable for anyone who learns best by building two complete, working interpreters from scratch rather than only studying compiler theory.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS programs with a Compilers, Programming Languages, or Language Implementation elective course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, GIKI, LUMS, and other HEC-recognized institutions, and for self-learners who want a free, practical, project-based introduction to how interpreters and compilers are built.

FAQs

Related Books

• Structure and Interpretation of Computer Programs (SICP) – Abelson & Sussman (SICP’s metacircular evaluator chapter is a natural companion to this book’s own interpreter-building approach)
• Think Data Structures – Allen B. Downey (a complementary look at data structures and algorithms, useful background for clox’s hash table and garbage collector chapters)
• Introduction to Programming Using Java – David J. Eck (useful Java background for Part II’s jlox interpreter)

Crafting Interpreters is a free, hands-on guide to how programming languages actually work — taught by building two complete, working interpreters, jlox in Java and clox in C, for the same language, Lox, from scratch. Browse more Computer Science books for the rest of your semester.

Crafting Interpreters, by Robert Nystrom. Free to read online from its official, self-published source. Access for free at https://craftinginterpreters.com/contents.html