Schemelike Metacircular Eval

Schemelike Metacircular Eval

Overview

This skill provides guidance for building metacircular evaluators—interpreters written in the same language they interpret, capable of interpreting themselves. These tasks require careful handling of evaluation levels, environment structures, and the distinction between host-level and interpreted-level data.

Initial Exploration Phase

Before writing any code:

1. Examine the host interpreter implementation - Read the existing interpreter (e.g., interp.py) to understand what primitives are provided, how values are represented, and what the evaluation model looks like.

2. Study the test files - Understand what constructs need to be supported by examining test cases. Identify which tests involve single-level vs. multi-level interpretation.

3. Establish reliable test execution - Verify the testing mechanism works correctly before deep debugging. Shell command quirks (like echo -e vs printf behavior) can cause false positives in debugging.

4. 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