Separating Syntactic Analysis from Execution

The evaluator implemented above is simple, but it is very
inefficient, because the syntactic analysis of expressions is interleaved
with their execution. Thus if a program is executed many times, its
syntax is analyzed many times. Consider, for example, evaluating `
(factorial 4)` using the following definition of `factorial`:

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

Each time `factorial` is called, the evaluator must determine that
the body is an `if` expression and extract the predicate.
Only then can it evaluate the
predicate and dispatch on its value. Each time it evaluates the
expression `(* (factorial (- n 1)) n)`,
or the subexpressions `(factorial (- n 1))` and `(- n 1)`,
the evaluator must perform
the case analysis in `eval` to determine that the expression is an
application, and must extract its operator and operands. This
analysis is expensive. Performing it repeatedly is wasteful.

We can transform the evaluator to be significantly more efficient by
arranging things so that syntactic analysis is performed only
once.^{} We split `eval`, which takes an
expression and an environment, into two parts. The procedure `
analyze` takes only the expression. It performs the syntactic
analysis and returns a new procedure, the
*execution procedure*, that
encapsulates the work to be done in executing the analyzed
expression. The execution procedure takes an environment as its
argument and completes the evaluation. This saves work because `
analyze` will be called only once on an expression, while the
execution procedure may be called many times.

With the separation into analysis and execution, `eval` now becomes

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

The result of calling `analyze` is the execution procedure to
be applied to the environment. The `analyze` procedure is
the same case analysis as performed by the original `eval` of
section , except that the procedures to
which we dispatch perform only analysis, not full evaluation:

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

Here is the simplest syntactic analysis procedure, which handles self-evaluating expressions. It returns an execution procedure that ignores its environment argument and just returns the expression:

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

For a quoted expression, we can gain a little efficiency by extracting the text of the quotation only once, in the analysis phase, rather than in the execution phase.

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

Looking up a variable value must still be done in the execution phase,
since this depends upon knowing the environment.^{}

(define (analyze-variable exp) (lambda (env) (lookup-variable-value exp env)))

`Analyze-assignment` also must defer actually setting the variable
until the execution, when the environment has been supplied. However,
the fact that the `assignment-value` expression can be
analyzed (recursively) during analysis is a major gain in efficiency,
because the `assignment-value` expression will now be analyzed
only once. The same holds true for definitions.

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

For `if` expressions, we extract and analyze the predicate,
consequent, and alternative at analysis time.

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

Analyzing a `lambda` expression also achieves a major
gain in efficiency: We analyze the `lambda` body only once, even though
procedures resulting from evaluation of the `lambda`
may be applied many times.

(define (analyze-lambda exp) (let ((vars (lambda-parameters exp)) (bproc (analyze-sequence (lambda-body exp)))) (lambda (env) (make-procedure vars bproc env))))

Analysis of a sequence of expressions (as in a `begin` or the body
of a `lambda` expression) is more involved.
^{}
Each expression
in the sequence is analyzed, yielding an execution
procedure. These execution procedures are combined to produce an
execution
procedure that takes an environment as argument and sequentially calls
each individual execution procedure with the environment as argument.

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

To analyze an application, we analyze the operator and operands and
construct an execution procedure that
calls the operator execution procedure (to obtain the
actual procedure to be applied) and the operand execution
procedures (to obtain the actual arguments). We then pass these to `
execute-application`, which is the analog of `apply` in
section .
`Execute-application` differs from `
apply` in that the procedure body for a compound procedure has already
been analyzed, so there is no need to do further analysis. Instead,
we just call the execution procedure for the body on the extended
environment.

(define (analyze-application exp) (let ((fproc (analyze (operator exp))) (aprocs (map analyze (operands exp)))) (lambda (env) (execute-application (fproc env) (map (lambda (aproc) (aproc env)) aprocs)))))(define (execute-application proc args) (cond ((primitive-procedure? proc) (apply-primitive-procedure proc args)) ((compound-procedure? proc) ((procedure-body proc) (extend-environment (procedure-parameters proc) args (procedure-environment proc)))) (else (error "Unknown procedure type - EXECUTE-APPLICATION" proc))))

Our new evaluator uses the same data structures, syntax procedures, and run-time support procedures as in sections , , and .

**Exercise.**
Extend the evaluator in this section to support the special form `let`.
(See exercise .)

**Exercise.**
Alyssa P. Hacker doesn't understand why `analyze-sequence` needs to be
so complicated. All the other analysis procedures
are straightforward transformations of the corresponding evaluation
procedures (or `eval` clauses) in section .
She expected `analyze-sequence` to look like this:

(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))))Eva Lu Ator explains to Alyssa that the version in the text does more of the work of evaluating a sequence at analysis time. Alyssa's sequence-execution procedure, rather than having the calls to the individual execution procedures built in, loops through the procedures in order to call them: In effect, although the individual expressions in the sequence have been analyzed, the sequence itself has not been.

Compare the two versions of `analyze-sequence`. For example,
consider the common case (typical of procedure bodies) where the
sequence has just one expression. What work will the execution
procedure produced by Alyssa's program do? What about the execution
procedure produced by the program in the text above? How do the two
versions compare for a sequence with two expressions?

**Exercise.**
Design and carry out some experiments to
compare the speed of the original metacircular evaluator
with the version in this section. Use your results to estimate the fraction
of time that is spent in analysis versus execution for various
procedures.