Question about SICP chpt 4.1 : How does (analyze expr) help speed up eval?

Question

I'm reading the following section of SICP

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1.7

According to the text, the following transformation of eval will improve offers a performance improvement, since an expression that gets evaluated many times will only be analyzed once?

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

Here is an analyze function given in the book:

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

I don't understand why the book says that analyze will only run once. Doesn't the the body of eval, which is ((analyze exp) env)) basically say that each time eval is called, analyze will be called with exp as its parameter? This would mean that analyze would be called every time eval is called.

What's wrong with my understanding? I would appreciate any feedback, thanks!

Answer 1

Indeed, every time you call eval with program code as a parameter, the syntactic evaluator will be invoked. However, when a function within that code calls another function within that code (or, in the simplest case, it calls itself by recursion), the inner apply will get the analyzed expression (which is in the end a lambda function) as an argument, rather than a blob of code which would need to be syntactically analyzed again in order to be executed.

Answer 2

Gintautas' answer is correct, but maybe an example is in order. Suppose you've developed a Scheme dialect that sports a loop construct

(do-n-times n expr)

with the obvious semantics. Now, when you call the naive eval to evaluate a loop that runs ten times

(eval '(do-n-times 10 (print 'hello)))

then it will analyze the loop body ten times. With the version of eval that separates analysis from evaluation, the loop body is analyzed once, then evaluated ten times.

The analysis phase returns a procedure, which may or not be fast in your Scheme interpreter. However, it could conceivably do all kinds of optimizations (dead code analysis, JIT compilation to machine code, etc.).

Answer 3

larsmans's answers is extremely good.

As a complementary answer, one can also view analyze(environ) as a curried form of eval(expr, environ) where the parameter expr has been passed in ahead of time. In SICP, you can read the example code like:

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

When you see a let (([var] [preprocessed stuff])), that is preprocessing being stored in a closure until it is needed later when environ is passed in.