Section 2: The Reference Interpreter

At the end of Section 1 you had a calculator. At the end of this section you have a language: variables, scope, control flow, functions, recursion, and a golden test corpus that defines what every one of them means.

Then you stop, and you freeze it.

That is the unusual part of this section and the reason it exists as a separate one. The tree-walking interpreter you finish here is not a stepping stone to be discarded when the bytecode VM works — it is the semantic reference implementation, kept forever, and used in Lab 12 to prove the VM computes the same answers. Almost no teaching project does this. It is the single highest-leverage decision in the curriculum.

This section covers Milestones M3, M4, and M5.

What You Build

The Layer You Are Building

                 AST  (from §1)
                  │
                  ▼
   ┌────────────────────────────────────────────────────────────────┐
   │  INTERPRETER                                interp/            │
   │                                                                │
   │   eval_block ──▶ eval_stmt ──▶ eval_expr                       │
   │        │              │             │                          │
   │        │              │             └──▶ Value                 │
   │        │              │                                        │
   │        │              └──▶ control flow: how does `break`      │
   │        │                   get out of three nested blocks?     │
   │        │                                                       │
   │        └──▶ scope push/pop                                     │
   │                                                                │
   │   ┌──────────────────────────────────────────────────────┐     │
   │   │ ENVIRONMENT                             env.rs       │     │
   │   │   globals:  HashMap<String, Value>                   │     │
   │   │   scopes:   Vec<HashMap<String, Value>>   ← naive    │     │
   │   │                                              ON PURPOSE│    │
   │   └──────────────────────────────────────────────────────┘     │
   │                                                                │
   │   ┌──────────────────────────────────────────────────────┐     │
   │   │ CALL STACK                              mod.rs       │     │
   │   │   depth counter (the Rust stack is the call stack —  │     │
   │   │   which is exactly the problem the VM will fix)      │     │
   │   └──────────────────────────────────────────────────────┘     │
   └────────────────────────────────────────────────────────────────┘

Note: The environment is a Vec<HashMap<String, Value>> and it is wrong — a variable read costs a string hash and a walk up the scope chain. You will build it anyway, feel it, benchmark it in Lab 8, and then watch Section 3 replace it with an array index. Building the wrong thing deliberately, once, with a measurement, is how you earn the right to have an opinion about the right thing.

The Concepts, and Where Each Is Treated

The Labs

Deliverables

• local, assignment, blocks, and shadowing work; local x = x reads the outer x.
• if/elseif/else, while, numeric for, break, and return all work.
• Only nil and false are falsy; and/or short-circuit and return operands.
• A numeric for creates a fresh binding per iteration.
• Functions, recursion, and mutual recursion work.
• Runaway recursion returns ErrorKind::Limit with a traceback — it does not abort.
• tests/golden/ has 25+ programs, each with a .expected file.
• tests/harness.rs runs the corpus and is written so a second backend can be plugged in without touching the test cases.
• A benchmark records the tree walker's fib(25) time. This is the Section 3 baseline.
• docs/adr/ADR-003-keep-the-tree-walker.md written before any VM code exists.
• docs/learning/04-interpreter.md and 07-call-frames.md written.

Common Mistakes in This Section

How to Verify Success

# 1. Scope, shadowing, and the initializer rule.
ember run -e 'local x = 1; do local x = 2 end; return x'          # 1
ember run -e 'local x = 1; local x = x + 1; return x'             # 2

# 2. Truthiness and short-circuit, with NON-boolean operands.
ember run -e 'return nil or 5'                                    # 5
ember run -e 'return false and error_never_called'                # false
ember run -e 'return 0 and "zero is truthy"'                      # zero is truthy

# 3. Control flow.
ember run tests/golden/fizzbuzz.ember | head -20

# 4. Recursion, and the limit.
ember run -e 'local function f(n) if n<2 then return n end return f(n-1)+f(n-2) end return f(25)'
ember run -e 'local function f() return f() end return f()'
#   → error: stack overflow (call depth limit 200 exceeded), with a traceback.
#   → exit code 1. NOT a signal. Check with: echo $?

# 5. The corpus. Every program, every expected output.
cargo test --test golden

# 6. The baseline you will need in Section 3.
cargo bench --bench calls -- fib_25 | tee docs/learning/baseline-interp.txt

Every one of those must pass before you write a single opcode. Section 3 is a second implementation of a specification, and this is the specification.

Section Profile: What a Section 2 Graduate Can Do

• Implement lexical scope with shadowing, and explain why local x = x works.
• Explain why non-local control flow (break, return) cannot be a Rust break in a tree walker, and name three ways to implement it.
• Describe a calling convention: what a caller does, what a callee does, and who cleans up.
• Explain why a tree-walking interpreter's recursion limit is a safety property, and where the limit has to live.
• Argue for keeping a slow reference implementation, in writing, against the obvious objection.
• Build a test corpus that is backend-agnostic, and explain what "backend-agnostic" costs.

Next: Value Representation.