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:

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

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

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

Add debug output - Insert print statements at key points:
- Before/after environment extension
- When creating closures
- When applying procedures
- When looking up variables
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

Self-evaluating expressions: Numbers, strings, booleans
Variable lookup: Simple bindings
Conditionals: if expressions
Lambda and application: Basic function calls
Let expressions: Local bindings
Closures: Functions that capture environment
Metacircular test: eval.scm interpreting simple expressions
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

schemelike-metacircular-eval