6.001/Recitation 21

Rob Speer

The metacircular evaluator

You know the idea by now: we want to implement Scheme in Scheme.

Terminology for my recitations: 0-Scheme is MIT Scheme or DrScheme. It has things like 0-procedures and 0-environments in it. We'll be writing an evaluator in it which runs 1-Scheme, which has 1-procedures and 1-environments.

What we will borrow from 0-Scheme:

• The lexical parser
• Numbers
• Strings
• The symbol table (but remember that a 0-symbol is a 1-variable)
• Pairs (we're sloppy!)

What we will not borrow:

• eval (duh)
• Environments
• Procedures
• Booleans
  • Why handle booleans differently than numbers or strings? Well, it doesn't take too much effort to define our own booleans, and Gerry and Hal wanted the illustrative example of having 0-booleans be different from 1-booleans.

So let's write this thing. Here's a start:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type -- EVAL" exp))))

Things we need to define now are:

Really easy things
  self-evaluating?
  variable?
  quoted?
  assignment?
  definition?
  if?
  lambda?
  begin?
  cond?
  application?

Harder things
  list-of-values
  eval-assignment
  eval-definition
  eval-if
  make-procedure
  eval-sequence
  cond->if      ; eh, this one is time-consuming, let's skip it
  apply

... plus some helper functions, presumably.

Finally, we need to make an initial environment.

If there's time

This evaluator is not very extendable. We should rewrite it as data-directed programming.

Side benefit: we can make define-macro work! Unhygenically.