The Metacircular Evaluator

A metacircular evaluator is a Lisp interpreter written in Lisp. SICP chapter 4 builds one. The heart is the mutual recursion of eval (evaluate an expression in an environment) and apply (apply a procedure to arguments).

Variations to explore (SICP 4.2–4.4): a lazy evaluator (normal-order evaluation), the amb evaluator (nondeterministic search), and a logic-programming evaluator (query language).

;; A compact evaluator for a Scheme subset (environments as lists of alists)
(define (m-eval exp env)
  (cond ((or (number? exp) (string? exp) (boolean? exp)) exp)
        ((symbol? exp) (lookup exp env))
        ((pair? exp)
         (case (car exp)
           ((quote) (cadr exp))
           ((if) (if (m-eval (cadr exp) env)
                     (m-eval (caddr exp) env)
                     (m-eval (cadddr exp) env)))
           ((lambda) (list 'closure (cadr exp) (cddr exp) env))
           ((define) (define-var! (cadr exp) (m-eval (caddr exp) env) env) 'ok)
           ((begin) (eval-sequence (cdr exp) env))
           (else (m-apply (m-eval (car exp) env)
                          (map (lambda (e) (m-eval e env)) (cdr exp))))))
        (else (error "Unknown expression" exp))))

(define (m-apply proc args)
  (cond ((procedure? proc) (apply proc args))                      ; primitive
        ((and (pair? proc) (eq? (car proc) 'closure))
         (let ((params (cadr proc)) (body (caddr proc)) (env (cadddr proc)))
           (eval-sequence body (extend-env params args env))))
        (else (error "Not a procedure" proc))))

(define (eval-sequence exps env)
  (if (null? (cdr exps))

…