Metacircular Evaluator

Abelson & Sussman · 1996 · SICP §4.1

A Scheme interpreter written in Scheme. eval dispatches on expression type, apply dispatches on procedure type. The mutual recursion between eval and apply is the whole story.

The core of the evaluator — eval

eval takes an expression and an environment. It classifies the expression — self-evaluating? variable? special form? application? — and dispatches accordingly. For applications, it evaluates the operator and operands, then calls apply.

Scheme

; A tiny eval — dispatches on expression type.
; We represent expressions as tagged lists.

(define (my-eval exp env)
  (cond ((number? exp) exp)                     ; self-evaluating
        ((symbol? exp) (lookup exp env))         ; variable
        ((eq? (car exp) 'quote) (cadr exp))      ; quoted
        ((eq? (car exp) 'if)                     ; conditional
         (if (my-eval (cadr exp) env)
             (my-eval (caddr exp) env)
             (my-eval (cadddr exp) env)))
        (else                                    ; application
         (my-apply (my-eval (car exp) env)
                   (map (lambda (e) (my-eval e env))
                        (cdr exp))))))

; Stub helpers for demonstration
(define (lookup var env)
  (cond ((null? env) (error "Unbound variable" var))
        ((eq? var (caar env)) (cdar env))
        (else (lookup var (cdr env)))))

(define (my-apply proc args)
  (cond ((procedure? proc) (apply proc args))
        (else (error "Not a procedure" proc))))

; Test: evaluate arithmetic in a tiny environment
(define env (list (cons '+ +) (cons '* *) (cons 'x 10)))
(display (my-eval '(+ x 5) env))
(newline)
; => 15

(display (my-eval '(* x x) env))
(newline)
; => 100

(display (my-eval '(if #t 42 99) env))
; => 42

; A tiny eval — dispatches on expression type.
; We represent expressions as tagged lists.

(define (my-eval exp env)
  (cond ((number? exp) exp)                     ; self-evaluating
        ((symbol? exp) (lookup exp env))         ; variable
        ((eq? (car exp) 'quote) (cadr exp))      ; quoted
        ((eq? (car exp) 'if)                     ; conditional
         (if (my-eval (cadr exp) env)
             (my-eval (caddr exp) env)
             (my-eval (cadddr exp) env)))
        (else                                    ; application
         (my-apply (my-eval (car exp) env)
                   (map (lambda (e) (my-eval e env))
                        (cdr exp))))))

; Stub helpers for demonstration
(define (lookup var env)
  (cond ((null? env) (error "Unbound variable" var))
        ((eq? var (caar env)) (cdar env))
        (else (lookup var (cdr env)))))

(define (my-apply proc args)
  (cond ((procedure? proc) (apply proc args))
        (else (error "Not a procedure" proc))))

; Test: evaluate arithmetic in a tiny environment
(define env (list (cons '+ +) (cons '* *) (cons 'x 10)))
(display (my-eval '(+ x 5) env))
(newline)
; => 15

(display (my-eval '(* x x) env))
(newline)
; => 100

(display (my-eval '(if #t 42 99) env))
; => 42

The core of the evaluator — apply

apply takes a procedure and a list of arguments. For primitive procedures, it calls the underlying implementation. For compound procedures, it extends the environment with bindings for the formal parameters and evaluates the body.

Scheme

; apply: dispatch on procedure type.
; Compound procedures carry their own environment.

(define (make-procedure params body env)
  (list 'compound params body env))

(define (compound? proc) (and (pair? proc) (eq? (car proc) 'compound)))
(define (proc-params proc) (cadr proc))
(define (proc-body proc) (caddr proc))
(define (proc-env proc) (cadddr proc))

(define (extend-env params args env)
  (if (null? params) env
      (cons (cons (car params) (car args))
            (extend-env (cdr params) (cdr args) env))))

(define (my-apply2 proc args)
  (cond ((procedure? proc) (apply proc args))  ; primitive
        ((compound? proc)                        ; compound
         (eval-body (proc-body proc)
                    (extend-env (proc-params proc)
                                args
                                (proc-env proc))))
        (else (error "Unknown procedure type"))))

(define (eval-body body env)
  ; simplified: body is a single expression
  (my-eval2 body env))

; Reuse eval with our new apply
(define (my-eval2 exp env)
  (cond ((number? exp) exp)
        ((symbol? exp) (lookup exp env))
        ((eq? (car exp) 'lambda)
         (make-procedure (cadr exp) (caddr exp) env))
        (else
         (my-apply2 (my-eval2 (car exp) env)
                    (map (lambda (e) (my-eval2 e env))
                         (cdr exp))))))

; Test: define and call a lambda
(define base-env (list (cons '+ +) (cons '* *)))
(define square-expr '((lambda (x) (* x x)) 7))
(display (my-eval2 square-expr base-env))
; => 49

; apply: dispatch on procedure type.
; Compound procedures carry their own environment.

(define (make-procedure params body env)
  (list 'compound params body env))

(define (compound? proc) (and (pair? proc) (eq? (car proc) 'compound)))
(define (proc-params proc) (cadr proc))
(define (proc-body proc) (caddr proc))
(define (proc-env proc) (cadddr proc))

(define (extend-env params args env)
  (if (null? params) env
      (cons (cons (car params) (car args))
            (extend-env (cdr params) (cdr args) env))))

(define (my-apply2 proc args)
  (cond ((procedure? proc) (apply proc args))  ; primitive
        ((compound? proc)                        ; compound
         (eval-body (proc-body proc)
                    (extend-env (proc-params proc)
                                args
                                (proc-env proc))))
        (else (error "Unknown procedure type"))))

(define (eval-body body env)
  ; simplified: body is a single expression
  (my-eval2 body env))

; Reuse eval with our new apply
(define (my-eval2 exp env)
  (cond ((number? exp) exp)
        ((symbol? exp) (lookup exp env))
        ((eq? (car exp) 'lambda)
         (make-procedure (cadr exp) (caddr exp) env))
        (else
         (my-apply2 (my-eval2 (car exp) env)
                    (map (lambda (e) (my-eval2 e env))
                         (cdr exp))))))

; Test: define and call a lambda
(define base-env (list (cons '+ +) (cons '* *)))
(define square-expr '((lambda (x) (* x x)) 7))
(display (my-eval2 square-expr base-env))
; => 49

Python

# apply in Python — compound procedures carry their env.
import operator

class Procedure:
    def __init__(self, params, body, env):
        self.params = params
        self.body = body
        self.env = env

def my_apply(proc, args):
    if callable(proc):                        # primitive
        return proc(*args)
    if isinstance(proc, Procedure):           # compound
        new_env = dict(list(proc.env.items()) + list(zip(proc.params, args)))
        return my_eval(proc.body, new_env)
    raise TypeError(f"Not a procedure: {proc}")

def my_eval(exp, env):
    if isinstance(exp, (int, float)):
        return exp
    if isinstance(exp, str):
        return env[exp]
    if exp[0] == 'lambda':
        _, params, body = exp
        return Procedure(params, body, env)
    proc = my_eval(exp[0], env)
    args = [my_eval(a, env) for a in exp[1:]]
    return my_apply(proc, args)

base_env = {'+': operator.add, '*': operator.mul}
# ((lambda (x) (* x x)) 7)
print(my_eval([['lambda', ['x'], ['*', 'x', 'x']], 7], base_env))
# => 49

# apply in Python — compound procedures carry their env.
import operator

class Procedure:
    def __init__(self, params, body, env):
        self.params = params
        self.body = body
        self.env = env

def my_apply(proc, args):
    if callable(proc):                        # primitive
        return proc(*args)
    if isinstance(proc, Procedure):           # compound
        new_env = dict(list(proc.env.items()) + list(zip(proc.params, args)))
        return my_eval(proc.body, new_env)
    raise TypeError(f"Not a procedure: {proc}")

def my_eval(exp, env):
    if isinstance(exp, (int, float)):
        return exp
    if isinstance(exp, str):
        return env[exp]
    if exp[0] == 'lambda':
        _, params, body = exp
        return Procedure(params, body, env)
    proc = my_eval(exp[0], env)
    args = [my_eval(a, env) for a in exp[1:]]
    return my_apply(proc, args)

base_env = {'+': operator.add, '*': operator.mul}
# ((lambda (x) (* x x)) 7)
print(my_eval([['lambda', ['x'], ['*', 'x', 'x']], 7], base_env))
# => 49

Representing expressions

The evaluator classifies expressions with simple predicates: self-evaluating?, variable?, quoted?, assignment?, definition?, if?, lambda?, begin?, and application?. Each predicate checks the tag (first element) of the expression list. This is data-directed programming applied to syntax.

Scheme

; Expression classification predicates.
; The evaluator pattern-matches on these.

(define (self-evaluating? exp)
  (or (number? exp) (string? exp) (boolean? exp)))

(define (variable? exp) (symbol? exp))

(define (tagged-list? exp tag)
  (and (pair? exp) (eq? (car exp) tag)))

(define (quoted? exp)    (tagged-list? exp 'quote))
(define (assignment? exp)(tagged-list? exp 'set!))
(define (definition? exp)(tagged-list? exp 'define))
(define (if? exp)        (tagged-list? exp 'if))
(define (lambda? exp)    (tagged-list? exp 'lambda))
(define (begin? exp)     (tagged-list? exp 'begin))

; Test each classifier
(display "42 self-eval? ")  (display (self-evaluating? 42))  (newline)
(display "x variable?   ")  (display (variable? 'x))         (newline)
(display "'foo quoted?  ")  (display (quoted? '(quote foo)))  (newline)
(display "if? on (if ..) ") (display (if? '(if #t 1 2)))     (newline)
(display "lambda?       ")  (display (lambda? '(lambda (x) x)))

Evaluator data structures — environments

An environment is a chain of frames. Each frame is a table of bindings (name → value). Variable lookup walks the chain from innermost to outermost. define adds to the first frame; set! mutates the first frame where the variable is found.

Scheme

; Environments as lists of frames.
; Each frame is an alist (association list).

(define (make-frame vars vals)
  (map cons vars vals))

(define (extend-environment vars vals base-env)
  (cons (make-frame vars vals) base-env))

(define (lookup-variable-value var env)
  (define (scan frame)
    (cond ((null? frame) #f)
          ((eq? var (caar frame)) (cdar frame))
          (else (scan (cdr frame)))))
  (if (null? env)
      (error "Unbound variable" var)
      (let ((result (scan (car env))))
        (if result result
            (lookup-variable-value var (cdr env))))))

; Build an environment: global -> local
(define global (extend-environment '(x y) '(1 2) '()))
(define local  (extend-environment '(x z) '(10 30) global))

; x is shadowed in local
(display "x in local: ")  (display (lookup-variable-value 'x local))  (newline)
; => 10
(display "y in local: ")  (display (lookup-variable-value 'y local))  (newline)
; => 2  (found in enclosing frame)
(display "z in local: ")  (display (lookup-variable-value 'z local))
; => 30

; Environments as lists of frames.
; Each frame is an alist (association list).

(define (make-frame vars vals)
  (map cons vars vals))

(define (extend-environment vars vals base-env)
  (cons (make-frame vars vals) base-env))

(define (lookup-variable-value var env)
  (define (scan frame)
    (cond ((null? frame) #f)
          ((eq? var (caar frame)) (cdar frame))
          (else (scan (cdr frame)))))
  (if (null? env)
      (error "Unbound variable" var)
      (let ((result (scan (car env))))
        (if result result
            (lookup-variable-value var (cdr env))))))

; Build an environment: global -> local
(define global (extend-environment '(x y) '(1 2) '()))
(define local  (extend-environment '(x z) '(10 30) global))

; x is shadowed in local
(display "x in local: ")  (display (lookup-variable-value 'x local))  (newline)
; => 10
(display "y in local: ")  (display (lookup-variable-value 'y local))  (newline)
; => 2  (found in enclosing frame)
(display "z in local: ")  (display (lookup-variable-value 'z local))
; => 30

Running the evaluator

The driver loop reads an expression, evaluates it, and prints the result. This is the read-eval-print loop (REPL). The metacircular evaluator is a REPL implemented in the language it evaluates — Scheme interpreting Scheme.

Scheme

; A complete tiny evaluator, end to end.
; Supports: numbers, variables, if, lambda, application.

(define (tiny-eval exp env)
  (cond ((number? exp) exp)
        ((boolean? exp) exp)
        ((symbol? exp) (cdr (assoc exp env)))
        ((eq? (car exp) 'if)
         (if (tiny-eval (cadr exp) env)
             (tiny-eval (caddr exp) env)
             (tiny-eval (cadddr exp) env)))
        ((eq? (car exp) 'lambda)
         (list 'closure (cadr exp) (caddr exp) env))
        (else  ; application
         (let ((proc (tiny-eval (car exp) env))
               (args (map (lambda (a) (tiny-eval a env)) (cdr exp))))
           (if (procedure? proc)
               (apply proc args)
               ; compound: extend env with param bindings
               (tiny-eval (caddr proc)
                          (append (map cons (cadr proc) args)
                                  (cadddr proc))))))))

(define env (list (cons '+ +) (cons '- -) (cons '* *)
                  (cons '< <) (cons '= =)))

; factorial via the metacircular evaluator!
(define fact-prog
  '((lambda (f n) (f f n))
    (lambda (self n)
      (if (< n 2) 1
          (* n (self self (- n 1)))))
    10))

(display "10! = ")
(display (tiny-eval fact-prog env))
; => 3628800

; A complete tiny evaluator, end to end.
; Supports: numbers, variables, if, lambda, application.

(define (tiny-eval exp env)
  (cond ((number? exp) exp)
        ((boolean? exp) exp)
        ((symbol? exp) (cdr (assoc exp env)))
        ((eq? (car exp) 'if)
         (if (tiny-eval (cadr exp) env)
             (tiny-eval (caddr exp) env)
             (tiny-eval (cadddr exp) env)))
        ((eq? (car exp) 'lambda)
         (list 'closure (cadr exp) (caddr exp) env))
        (else  ; application
         (let ((proc (tiny-eval (car exp) env))
               (args (map (lambda (a) (tiny-eval a env)) (cdr exp))))
           (if (procedure? proc)
               (apply proc args)
               ; compound: extend env with param bindings
               (tiny-eval (caddr proc)
                          (append (map cons (cadr proc) args)
                                  (cadddr proc))))))))

(define env (list (cons '+ +) (cons '- -) (cons '* *)
                  (cons '< <) (cons '= =)))

; factorial via the metacircular evaluator!
(define fact-prog
  '((lambda (f n) (f f n))
    (lambda (self n)
      (if (< n 2) 1
          (* n (self self (- n 1)))))
    10))

(display "10! = ")
(display (tiny-eval fact-prog env))
; => 3628800

Python

# Complete tiny evaluator in Python
import operator

def tiny_eval(exp, env):
    if isinstance(exp, (int, float, bool)):
        return exp
    if isinstance(exp, str):
        return env[exp]
    if exp[0] == 'if':
        _, test, yes, no = exp
        return tiny_eval(yes, env) if tiny_eval(test, env) else tiny_eval(no, env)
    if exp[0] == 'lambda':
        _, params, body = exp
        return ('closure', params, body, env)
    # application
    proc = tiny_eval(exp[0], env)
    args = [tiny_eval(a, env) for a in exp[1:]]
    if callable(proc):
        return proc(*args)
    # compound procedure
    _, params, body, closure_env = proc
    new_env = dict(list(closure_env.items()) + list(zip(params, args)))
    return tiny_eval(body, new_env)

env = {'+': operator.add, '-': operator.sub,
       '*': operator.mul, '<': operator.lt, '=': operator.eq}

# factorial: ((lambda (f n) (f f n)) (lambda (self n) ...) 10)
fact_prog = [['lambda', ['f', 'n'], ['f', 'f', 'n']],
             ['lambda', ['self', 'n'],
              ['if', ['<', 'n', 2], 1,
               ['*', 'n', ['self', 'self', ['-', 'n', 1]]]]],
             10]

print(f"10! = {tiny_eval(fact_prog, env)}")  # 3628800

# Complete tiny evaluator in Python
import operator

def tiny_eval(exp, env):
    if isinstance(exp, (int, float, bool)):
        return exp
    if isinstance(exp, str):
        return env[exp]
    if exp[0] == 'if':
        _, test, yes, no = exp
        return tiny_eval(yes, env) if tiny_eval(test, env) else tiny_eval(no, env)
    if exp[0] == 'lambda':
        _, params, body = exp
        return ('closure', params, body, env)
    # application
    proc = tiny_eval(exp[0], env)
    args = [tiny_eval(a, env) for a in exp[1:]]
    if callable(proc):
        return proc(*args)
    # compound procedure
    _, params, body, closure_env = proc
    new_env = dict(list(closure_env.items()) + list(zip(params, args)))
    return tiny_eval(body, new_env)

env = {'+': operator.add, '-': operator.sub,
       '*': operator.mul, '<': operator.lt, '=': operator.eq}

# factorial: ((lambda (f n) (f f n)) (lambda (self n) ...) 10)
fact_prog = [['lambda', ['f', 'n'], ['f', 'f', 'n']],
             ['lambda', ['self', 'n'],
              ['if', ['<', 'n', 2], 1,
               ['*', 'n', ['self', 'self', ['-', 'n', 1]]]]],
             10]

print(f"10! = {tiny_eval(fact_prog, env)}")  # 3628800

Notation reference

Scheme	Python	Meaning
(eval exp env)	eval(exp, env)	Evaluate expression in environment
(apply proc args)	proc(*args)	Apply procedure to arguments
(tagged-list? e 'if)	e[0] == 'if'	Check expression type by tag
(extend-environment ...)	dict(env, **new)	Create new frame over base env
(define (f x) body)	def f(x): body	Syntactic sugar for lambda + define

Neighbors

Translation notes

The metacircular evaluator uses Scheme to interpret Scheme, so the host language and the interpreted language share the same syntax. In Python, we represent Scheme expressions as nested lists. This survives the translation: eval classifies expressions, apply classifies procedures, and they call each other. The only structural difference is that Python's compound procedures use dictionaries for environments while Scheme uses association lists.

Ready for the real thing? Read SICP §4.1.

← Streams by june.kim Lazy Evaluation · 15 of 22 →