Schemelike Metacircular Eval

Create a mental model of interpretation levels:

• Level 0: The host language (e.g., Python running interp.py)
• Level 1: The first interpreter (eval.scm running in Python)
• Level 2: The metacircular layer (eval.scm interpreting eval.scm)

Core Implementation Strategy

Environment Management

Implement environment operations with clear semantics:

;; Environment structure: list of frames, each frame is list of (name . value) pairs
(define (make-env) '(()))

(define (extend-env params args env)
  ;; Create new frame with parameter bindings, prepend to env
  (cons (make-frame params args) env))

(define (lookup var env)
  ;; Search frames from innermost to outermost
  ...)

(define (env-define! var val env)
  ;; Add binding to current (first) frame
  ...)

Critical: Test environment operations in isolation before using them in the evaluator. Create unit tests for:

• Empty environment lookup (should error)
• Single binding lookup
• Shadowed variable lookup
• Definition in nested environments

Closure Representation

Closures must capture their defining environment:

(define (make-closure params body env)
  (list 'closure params body env))

(define (closure? obj)
  (and (pair? obj) (eq? (car obj) 'closure)))

(define (closure-params c) (cadr c))
(define (closure-body c) (caddr c))
(define (closure-env c) (cadddr c))

Key insight for metacircular interpretation: At level 2, closures are data structures that the level-1 interpreter must correctly recognize and apply. Ensure predicates like closure? work on data that has passed through multiple interpretation layers.

The Eval-Apply Loop

(define (eval exp env)
  (cond
    ((self-evaluating? exp) exp)
    ((variable? exp) (lookup exp env))
    ((quoted? exp) (cadr exp))
    ((definition? exp) (eval-definition exp env))
    ((if? exp) (eval-if exp env))
    ((lambda? exp) (make-closure (lambda-params exp) (lambda-body exp) env))
    ((let? exp) (eval-let exp env))
    ((begin? exp) (eval-sequence (begin-actions exp) env))
    ((application? exp) (apply-proc (eval (car exp) env)
                                     (eval-args (cdr exp) env)
                                     env))
    (else (error "Unknown expression type"))))

(define (apply-proc proc args env)
  (cond
    ((primitive? proc) (apply-primitive proc args))
    ((closure? proc)
     (eval-sequence (closure-body proc)
                    (extend-env (closure-params proc)
                                args
                                (closure-env proc))))
    (else (error "Unknown procedure type"))))

Handling let Expressions

Two approaches:

Direct implementation:

(define (eval-let exp env)
  (let ((vars (let-vars exp))
        (vals (map (lambda (e) (eval e env)) (let-vals exp)))
        (body (let-body exp)))
    (eval-sequence body (extend-env vars vals env))))

Transform to lambda (fallback approach):

(define (let->lambda exp)
  (cons (list 'lambda (let-vars exp) (let-body exp))
        (let-vals exp)))

Note: Transforming let to lambda can be a workaround but may mask underlying issues. Prefer direct implementation and investigate if problems persist.

Debugging Multi-Level Interpretation

Systematic Bisection Approach

When something works at level 1 but fails at level 2:

1. Identify the failing component - Is it environment lookup, closure application, or expression evaluation?

2. Create minimal reproduction - Write the smallest program that demonstrates the failure:

   ;; Test at level 1
   (eval '(let ((x 1)) x) (make-env))
   
   ;; Test at level 2 - have eval.scm interpret a simple let
   

3. Add debug output - Insert print statements at key points:

   • Before/after environment extension
   • When creating closures
   • When applying procedures
   • When looking up variables

4. Compare execution traces - Run the same expression at level 1 and level 2, comparing the debug output to find where behavior diverges.

Common Multi-Level Issues

Predicate confusion: At level 2, pair? on the host might return #t for a closure structure, but the interpreted pair? might behave differently if closures are represented as lists.

Environment corruption: When environments pass through multiple interpretation layers, ensure the structure is preserved. A common bug is the environment becoming "flattened" or losing nested structure.

Primitive vs. closure distinction: Ensure primitive? and closure? predicates are mutually exclusive and correctly identify procedures at all interpretation levels.

Testing Strategy

Unit Test Core Abstractions First

Before testing full programs, verify:

;; Test environment operations
(define test-env (make-env))
(env-define! 'x 1 test-env)
(assert (= (lookup 'x test-env) 1))

;; Test shadowing
(define nested-env (extend-env '(x) '(2) test-env))
(assert (= (lookup 'x nested-env) 2))

;; Test closure creation and access
(define test-closure (make-closure '(a) '((+ a 1)) test-env))
(assert (closure? test-closure))
(assert (equal? (closure-params test-closure) '(a)))

Progressive Complexity

1. Self-evaluating expressions: Numbers, strings, booleans
2. Variable lookup: Simple bindings
3. Conditionals: if expressions
4. Lambda and application: Basic function calls
5. Let expressions: Local bindings
6. Closures: Functions that capture environment
7. Metacircular test: eval.scm interpreting simple expressions
8. Full metacircular: eval.scm interpreting itself

Test File Organization

Create separate test files for different concerns:

• test-env.scm - Environment operations
• test-closure.scm - Closure creation and application
• test-eval-basic.scm - Basic evaluation
• test-metacircular.scm - Self-interpretation

Common Pitfalls

Shell Command Issues

When running tests via shell commands:

• echo -e behavior varies between shells; prefer printf for consistent escape handling
• Always verify test output format before debugging code issues

Premature Workarounds

Avoid these until root cause is understood:

• Renaming primitives to avoid "collisions"
• Transforming constructs (let to lambda) without understanding why direct implementation fails
• Adding special cases for specific test files

Incomplete Understanding of Levels

Before implementing fixes, clearly answer:

• At which level does evaluation happen for each sub-expression?
• Which environment is used at each point?
• How are closures represented when they cross interpretation boundaries?

Over-reliance on Debug Mode

When using debug/trace output:

• Analyze the output systematically rather than skimming
• Look for patterns in where success and failure diverge
• Create hypotheses and test them explicitly

Verification Checklist

Before considering the implementation complete:

• All self-evaluating expressions work at levels 1 and 2
• Variable lookup works with shadowing at all levels
• Lambda creates closures that capture correct environment
• Closure application extends the closure's environment, not the call site's
• Let expressions work for nested lets at all levels
• Recursive functions work (requires proper environment setup)
• The evaluator can evaluate itself running simple programs
• The evaluator can evaluate itself running programs with closures