Guide for implementing metacircular evaluators—interpreters that can interpret themselves. This skill should be used when building self-interpreting Scheme-like evaluators, debugging multi-level interpretation issues, or implementing language features like environments, closures, and special forms. Focuses on incremental development, continuous metacircular testing, and systematic debugging of nested interpretation failures.
This skill provides systematic guidance for implementing metacircular evaluators—interpreters written in the language they interpret. The critical challenge is not just building a working interpreter, but building one that can interpret itself (the metacircular property).
A metacircular evaluator must pass this test:
# Level 1: Direct interpretation
echo 'test-program.scm' | interpreter eval.scm
# Level 2: Self-interpretation (MUST produce same output)
echo -e 'eval.scm\ntest-program.scm' | interpreter eval.scm
Test the metacircular property continuously throughout development, not just at the end. Every feature must work at both levels before adding the next.
Wrong approach: Implement all features, then test metacircular property.
Correct approach: For each feature:
Start with the smallest possible evaluator that can interpret itself:
Required features for bootstrap:
Test program for bootstrap verification:
;; bootstrap-test.scm
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
(display (fact 5))
(newline)
Run at both levels. If level 2 fails, stop and debug before adding features.
After the core works metacircularly, add features one at a time:
For each addition, create a minimal test and verify at both levels.
Use a structure that can be manipulated consistently at all interpretation levels:
;; Environment as list of frames
;; Frame = (vars . vals) where vars and vals are parallel lists
;; env = (frame1 frame2 ... global-frame)
(define (extend-env vars vals base-env)
(cons (cons vars vals) base-env))
(define (lookup var env)
(if (null? env)
(error "Undefined variable:" var)
(lookup-in-frame var (car env)
(lambda () (lookup var (cdr env))))))
After any environment operation, verify:
(vars . vals) not ((vars vals))Bug: Dotted pairs vs. proper lists
;; Wrong: creates single frame, not extendable
(cons vars vals) ; If vars=(x y), vals=(1 2), result is ((x y) . (1 2))
;; Verify structure manually before proceeding
Bug: Environment extension corrupts at level 2
At level 2, environments are interpreted data structures. The same extend-env code manipulates different representations at different levels. Test environment operations in isolation at level 2:
;; test-env-level2.scm
(define env (extend-env '(x) '(42) '()))
(display (lookup 'x env))
(newline)
Direct let implementation is error-prone for metacircular evaluation. Transform instead:
;; Transform: (let ((x 1) (y 2)) body...)
;; Into: ((lambda (x y) body...) 1 2)
Verification steps:
(let ((x 1)) x) should behave exactly like ((lambda (x) x) 1)Lambda must capture the environment at definition time, not evaluation time:
(define (make-procedure params body env)
(list 'procedure params body env)) ; env captured here
Test closure capture:
(define (make-adder n)
(lambda (x) (+ x n))) ; n must be captured
((make-adder 5) 3) ; Must return 8
This is the most common and difficult debugging scenario.
Step 1: Isolate the failing feature
If (let ((x 5)) (display x)) fails at level 2:
((lambda (x) x) 5) at level 2(define x 5) x at level 2(display 42) at level 2Find the smallest failing case.
Step 2: Trace data structure transformations
At level 2, data structures are themselves interpreted. Manually trace:
Expression: ((lambda (x) x) 42)
Level 1:
- Create closure: (procedure (x) ((x)) env1)
- Extend env: env2 = (((x) . (42)) . env1)
- Lookup x: 42
Level 2:
- Outer eval creates inner closure as data structure
- Inner closure's environment is also a data structure
- Verify: Can lookup still traverse this nested representation?
Step 3: Check representation invariants
Create diagnostic programs:
;; test-structure.scm
(define env (extend-env '(x) '(42) '()))
(display (car env)) ; Frame
(display (car (car env))) ; Variables list
(display (cdr (car env))) ; Values list
Run at level 1 and level 2. Compare outputs.
Pattern: Lambda body not evaluated at level 2
Symptom: ((lambda (x) (display x)) 42) prints nothing at level 2.
Likely cause: Environment extension creates malformed structure at level 2, causing body evaluation to fail silently.
Debug: Test ((lambda (x) x) 42) first (simpler body).
Pattern: Infinite recursion with primitive names
Symptom: Recursion error mentioning primitives like 'not', 'null?', 'eq?'.
Likely cause: Host-level operations in evaluator code conflicting with interpreted primitives.
Solution: Use explicit comparisons in evaluator code:
;; Instead of: (not (null? x))
;; Use: (if (null? x) #f #t)
;; Or: (eq? x #f)
Pattern: EOF/input confusion
Symptom: Read returns wrong values or EOF too early at level 2.
Likely cause: Input stream consumed at wrong level.
Debug: Use printf not echo -e (behavior varies by shell):
# Reliable input formatting
printf 'eval.scm\ntest.scm\ninput-line\n' | interpreter eval.scm
Before considering the evaluator complete:
Core features at level 1:
Metacircular property (level 2):
42 evaluates to 42(+ 1 2) evaluates to 3((lambda (x) x) 42) evaluates to 42((lambda (x) (+ x 1)) 5) evaluates to 6(define x 5) x evaluates to 5Full self-interpretation:
eval.scm can interpret eval.scm interpreting test programseval.scm → eval.scm → test.scm) worksEvery untested feature may introduce bugs that cascade. Test at both levels after each feature.
When level 2 fails, systematically:
Don't randomly modify code hoping it works.
(eq? 'x 'x) may behave differently when symbols are interpreted data at level 2. Test primitive operations on interpreted data structures explicitly.
The initial evaluator should be as small as possible while still being self-interpreting. Add complexity only after the core works metacircularly.
When eval.scm interprets itself: