Difference between Metacircular Evaluator and the Analyzing (Metacircular) Evaluator

Question

In section 4.1 of the Structure and Interpretation of Computer Programs there are two evaluators introduced, being the metacircular evaluator and the analysing metacircular evaluator.

The full metacircular evaluator can be found here: https://mitpress.mit.edu/sicp/code/ch4.scm

And the full metacircular evaluator with analysis can be found here: https://mitpress.mit.edu/sicp/code/ch4-analyzingmceval.scm

Now, the difference between the two is that the analysing evaluator eval has analysis methods for analysing the expression.

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

(define (analyze exp)
  (cond ((self-evaluating? exp) 
         (analyze-self-evaluating exp))
        ((quoted? exp) (analyze-quoted exp))
        (...)

Where the analysis procedure does for example this:

(define (analyze-self-evaluating exp)
  (lambda (env) exp))

or this:

(define (analyze-quoted exp)
  (let ((qval (text-of-quotation exp)))
    (lambda (env) qval)))

Whereas the metacircular evaluator eval does this:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
  (...)

(define (text-of-quotation exp) (cadr exp))

What I expected the analysing evaluator to do is caching previously analyzed results somewhere in the environment, but I do not see this. I don't see what the analysing evaluator exactly does.

So, what does the analyzing evaluator exactly do and why does it speed up the evaluator by a fair bit?

Renzo Renzo · Accepted Answer · 2016-01-28T18:23:30

If you look with attention to the analyze-something functions, you will see that each of them (a part analyze-self-evaluating and analyze-variables), performs some operation, and then returns a lambda. For instance:

(define (analyze-if exp)
  (let ((pproc (analyze (if-predicate exp)))
        (cproc (analyze (if-consequent exp)))
        (aproc (analyze (if-alternative exp))))
    (lambda (env)
      (if (true? (pproc env))
          (cproc env)
          (aproc env)))))

while in the other interpreter, we have:

(define (eval-if exp env)
  (if (true? (eval (if-predicate exp) env))
      (eval (if-consequent exp) env)
      (eval (if-alternative exp) env)))

What is happening here? In the second case, every time the same expression is evaluated (for instance because we are executing the body of a recursive function a lot of times), the eval-something version is called on the expression, and everything is evaluated again, including the things that the analyzing-something counterpart executes before returning the function!

In the first case, instead, the first part of the analysing function is executed only once, and what is get executed many times is the procedure returned by it.

This should be clear if you consider in particular the definition case. Compare the two functions:

(define (analyze-definition exp)
  (let ((var (definition-variable exp))
        (vproc (analyze (definition-value exp))))
    (lambda (env)
      (define-variable! var (vproc env) env)
      'ok)))

and

(define (eval-definition exp env)
  (define-variable! (definition-variable exp)
                    (eval (definition-value exp) env)
                    env)
  'ok)

In the second one, the function evaluates the form (definition-value exp) every time it is called inside eval:

...
((definition? exp) (eval-definition exp env))
...

In the first case, instead, you can see that there is a call to (analyze (definition-value exp)) in the let part of the function, then its result is stored into the var, so that it will not be evaluated any more.

Difference between Metacircular Evaluator and the Analyzing (Metacircular) Evaluator

1 Answers