Skip to main content

Interpreter Construction Clinic

Build a small tree-walking Lisp interpreter from scratch, then extend it. The base target is the 30-50 line skeleton in Concept 11. The clinic adds test cases, extensions, a staged variant, and a debugging protocol you can apply to any interpreter you encounter later.

Retrieval Prompts​

  1. What are the two mutually-recursive procedures at the heart of any Scheme-like evaluator?
  2. What single field in your procedure representation enforces lexical scope?
  3. Why must if be handled before argument evaluation?
  4. What is the difference between the interpreter and the parser?

Base Task -- 30-50 line evaluator​

Implement the Python or Scheme evaluator described in Concept 11. At minimum, support:

  • atoms: numbers, symbols
  • special forms: quote, if, define, set!, lambda, begin
  • procedure application
  • primitives: +, -, *, /, =, <, >, car, cdr, cons, null?, list, print

Include a tokenizer + parser that accepts these token types: (, ), numbers, symbols.

Acceptance Tests (all must pass)​

Test 1 -- Arithmetic and conditionals​

(+ 1 (* 2 3))                          ; 7
(if (< 3 5) 'yes 'no)                 ; 'yes

Test 2 -- Recursion​

(define fact (lambda (n)
  (if (= n 0) 1 (* n (fact (- n 1))))))
(fact 6)                               ; 720

Test 3 -- Higher-order​

(define compose (lambda (f g) (lambda (x) (f (g x)))))
((compose car cdr) (list 1 2 3))       ; 2

Test 4 -- Closures (lexical scope)​

(define make-adder (lambda (n) (lambda (x) (+ x n))))
(define add5 (make-adder 5))
(define add7 (make-adder 7))
(+ (add5 10) (add7 10))                 ; 32

Test 5 -- Mutable counter​

(define make-counter
  (lambda () (define n 0) (lambda () (set! n (+ n 1)) n)))
(define c (make-counter))
(c) (c) (c)                            ; 3

Test 6 -- Dynamic scope negative test​

The following should not print 99 with a lexical evaluator; it should print 5. If you print 99, you have a dynamic-scope bug.

(define x 5)
(define f (lambda () x))
(define g (lambda (x) (f)))
(g 99)                                 ; expected: 5

Extension 1 -- let, and, or, cond​

Add these as either special forms or macros:

  • (let ((x v1) (y v2)) body) -- desugars to ((lambda (x y) body) v1 v2)
  • (cond (p1 e1) (p2 e2) ... (else e)) -- nested if
  • (and a b) -- short-circuit
  • (or a b) -- short-circuit

Test each with a small example.

Extension 2 -- Error handling​

Replace crashes with informative errors for:

  • unbound variable lookup
  • wrong number of arguments to a lambda
  • calling a non-procedure
  • unknown special form

A good error includes the expression being evaluated.

Extension 3 -- Stage: separate analysis from execution​

Port Concept 12's idea: turn the evaluator into a two-phase system.

  • analyze(exp) -> λenv. result
  • Top-level: run(prog) = (analyze(prog))(env)

Benchmark (fact 10) in a tight 100 000-iteration loop. Report the speedup.

Extension 4 -- Tail-call safety​

Without this, deep recursion blows Python's stack. Add a trampoline: have eval_ return either a value or a TailCall(proc, args, env) object. Wrap the top-level in a while loop that re-enters.

Test: (define (loop n) (if (= n 0) 'done (loop (- n 1)))) (loop 100000) should return 'done.

Debugging Protocol​

When a test fails, apply this checklist before reading your code:

  1. Is the parser producing the shape you think? Print the AST.
  2. Are you dispatching on the right special form? Add a print at the top of eval_.
  3. Does your lambda capture the right environment? Add a print when a procedure is applied, listing its captured env's keys.
  4. Are you evaluating if branches before the test? (Common bug if you treat if as an application.)
  5. Are your primitive bindings in the base env or nested too deep?

Each of these maps to an almost-certain real bug you will hit at least once.

Evidence Check​

This clinic is complete only if:

  • All six acceptance tests pass on the base evaluator.
  • At least two extensions (1-4) are implemented.
  • The staged variant runs and you have numbers for its speedup.
  • A log file exists with at least three real bugs you hit and how you diagnosed them.
  • You can explain, pointing at a specific line, where lexical scope is enforced.