6.001/Recitation 22

Rob Speer

More meta-circular evaluation

Here's our eval and apply again, this time with more abstraction:

(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))))

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))

• What changes do we need to make to make this evaluator use dynamic scope instead of lexical?
• Let's replace eval with something data-directed, and then make it possible to add macros.

Static analysis

We want to do as much work as possible before we run the program. By just scanning over the code, we know everything but the environment it's running in. So give it everything but the environment, and fill the environment in later.

The new eval:

(define (eval exp env)
  ((analyze exp) env))

Well, that was trivial and uninformative. The magic is now done by analyze:

(define (analyze exp)
  (cond ((self-evaluating? exp) 
         (analyze-self-evaluating exp))
        ((quoted? exp) (analyze-quoted exp))
        ((variable? exp) (analyze-variable exp))
        ((assignment? exp) (analyze-assignment exp))
        ((definition? exp) (analyze-definition exp))
        ((if? exp) (analyze-if exp))
        ((lambda? exp) (analyze-lambda exp))
        ((begin? exp) (analyze-sequence (begin-actions exp)))
        ((cond? exp) (analyze (cond->if exp)))
        ((application? exp) (analyze-application exp))
        (else
         (error "Unknown expression type -- ANALYZE" exp))))

So we need to implement these parts of analyze.

• analyze-self-evaluating is stupidly easy.
• analyze-quoted is easy too.
• analyze-variable at least needs to make use of the environement.
• Let's skip analyze-assignment.
• analyze-definition can do almost all of what it needs to do.
• analyze-if needs to store a fair amount of state.
• analyze-lambda is where we'll gain a lot of efficiency. Why?
• analyze-sequence is unexpectedly hard to do, so we'll skip it.
• analyze-application is where all the work of apply needs to be done. What do we do once everything's analyzed?

The eval/apply loop is gone. What took its place? What makes recursion work now?

We can work out what happens on this example:

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

analyze-sequence

Here's Hal and Gerry's code for analyze-sequence:

(define (analyze-sequence exps)
  (define (sequentially proc1 proc2)
    (lambda (env) (proc1 env) (proc2 env)))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc (car rest-procs))
              (cdr rest-procs))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence -- ANALYZE"))
    (loop (car procs) (cdr procs))))

You may have thought it would be simpler, like the following procedure. What's wrong with it?

(define (analyze-sequence exps)
  (define (execute-sequence procs env)
    (cond ((null? (cdr procs)) ((car procs) env))
          (else ((car procs) env)
                (execute-sequence (cdr procs) env))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence -- ANALYZE"))
    (lambda (env) (execute-sequence procs env))))