The Metacircular Evaluator

Our evaluator for Lisp will be implemented as a Lisp program. It may seem circular to think about evaluating Lisp programs using an evaluator that is itself implemented in Lisp. However, evaluation is a process, so it is appropriate to describe the evaluation process using Lisp, which, after all, is our tool for describing processes.3 An evaluator that is written in the same language that it evaluates is said to be metacircular . The metacircular evaluator is essentially a Scheme formulation of the environment model of evaluation described in section 3.2. Recall that the model has two basic parts:

• To evaluate a combination (a compound expression other than a special form), evaluate the subexpressions and then apply the value of the operator subexpression to the values of the operand subexpressions.

• To apply a compound procedure to a set of arguments, evaluate the body of the procedure in a new environment. To construct this environment, extend the environment part of the procedure object by a frame in which the formal parameters of the procedure are bound to the arguments to which the procedure is applied.

These two rules describe the essence of the evaluation process, a basic cycle in which expressions to be evaluated in environments are reduced to procedures to be applied to arguments, which in turn are reduced to new expressions to be evaluated in new environments, and so on, until we get down to symbols, whose values are looked up in the environment, and to primitive procedures, which are applied directly (see Figure 4-1).4 This evaluation cycle will be embodied by the interplay between the two critical procedures in the evaluator, eval and apply, which are described in section 4.1.1 (see Figure 4-1).

The implementation of the evaluator will depend upon procedures that define the syntax of the expressions to be evaluated. We will use data abstraction to make the evaluator independent of the representation of the language. For example, rather than committing to a choice that an assignment is to be represented by a list beginning with the symbol set! we use an abstract predicate assignment? to test for an assignment, and we use abstract selectors assignment-variable and assignment-value to access the parts of an assignment. Implementation of expressions will be described in detail in section 4.1.2. There are also operations, described in section 4.1.3, that specify the representation of procedures and environments. For example, make-procedure constructs compound procedures, lookup-variable-value accesses the values of variables, and apply-primitive-procedure applies a primitive procedure to a given list of arguments.

4.1.1 The Core of the Evaluator

Figure 4.1: The eval-apply cycle exposes the essence of a computer language.

The evaluation process can be described as the interplay between two procedures: eval and apply.

Eval

Eval takes as arguments an expression and an environment. It classifies the expression and directs its evaluation. Eval is structured as a case analysis of the syntactic type of the expression to be evaluated. In order to keep the procedure general, we express the determination of the type of an expression abstractly, making no commitment to any particular representation for the various types of expressions. Each type of expression has a predicate that tests for it and an abstract means for selecting its parts. This abstract syntax makes it easy to see how we can change the syntax of the language by using the same evaluator, but with a different collection of syntax procedures.

Primitive expressions

• For self-evaluating expressions, such as numbers, eval returns the expression itself.

• Eval must look up variables in the environment to find their values.

Special forms

• For quoted expressions, eval returns the expression that was quoted.
• An assignment to (or a definition of) a variable must recursively call eval to compute the new value to be associated with the variable. The environment must be modified to change (or create) the binding of the variable.

• An if expression requires special processing of its parts, so as to evaluate the consequent if the predicate is true, and otherwise to evaluate the alternative.

• A lambda expression must be transformed into an applicable procedure by packaging together the parameters and body specified by the lambda expression with the environment of the evaluation.

• A begin expression requires evaluating its sequence of expressions in the order in which they appear.

• A case analysis (cond) is transformed into a nest of if expressions and then evaluated.

Combinations

• For a procedure application, eval must recursively evaluate the operator part and the operands of the combination. The resulting procedure and arguments are passed to apply, which handles the actual procedure application.

Here is the definition of eval:

For clarity, eval has been implemented as a case analysis using cond. The disadvantage of this is that our procedure handles only a few distinguishable types of expressions, and no new ones can be defined without editing the definition of eval. In most Lisp implementations, dispatching on the type of an expression is done in a data-directed style. This allows a user to add new types of expressions that eval can distinguish, without modifying the definition of eval itself. (See Exercise 4-3.)

Apply

Apply takes two arguments, a procedure and a list of arguments to which the procedure should be applied. Apply classifies procedures into two kinds: It calls apply-primitive-procedure to apply primitives; it applies compound procedures by sequentially evaluating the expressions that make up the body of the procedure. The environment for the evaluation of the body of a compound procedure is constructed by extending the base environment carried by the procedure to include a frame that binds the parameters of the procedure to the arguments to which the procedure is to be applied. Here is the definition of apply:

Procedure arguments

When eval processes a procedure application, it uses list-of-values to produce the list of arguments to which the procedure is to be applied. List-of-values takes as an argument the operands of the combination. It evaluates each operand and returns a list of the corresponding values:5

Conditionals

Eval-if evaluates the predicate part of an if expression in the given environment. If the result is true, eval-if evaluates the consequent, otherwise it evaluates the alternative:

The use of true? in eval-if highlights the issue of the connection between an implemented language and an implementation language. The if-predicate is evaluated in the language being implemented and thus yields a value in that language. The interpreter predicate true? translates that value into a value that can be tested by the if in the implementation language: The metacircular representation of truth might not be the same as that of the underlying Scheme.6

Sequences

Eval-sequence is used by apply to evaluate the sequence of expressions in a procedure body and by eval to evaluate the sequence of expressions in a begin expression. It takes as arguments a sequence of expressions and an environment, and evaluates the expressions in the order in which they occur. The value returned is the value of the final expression.

Assignments and definitions

The following procedure handles assignments to variables. It calls eval to find the value to be assigned and transmits the variable and the resulting value to set-variable-value! to be installed in the designated environment.

Definitions of variables are handled in a similar manner.7

We have chosen here to return the symbol ok as the value of an assignment or a definition.8

4.1.2 Representing Expressions

The evaluator is reminiscent of the symbolic differentiation program discussed in section 2.3.2. Both programs operate on symbolic expressions. Inboth programs, the result of operating on a compound expression is determinedby operating recursively on the pieces of the expression and combining theresults in a way that depends on the type of the expression. In both programswe used data abstraction to decouple the general rules of operation from thedetails of how expressions are represented. In the differentiation programthis meant that the same differentiation procedure could deal with algebraicexpressions in prefix form, in infix form, or in some other form. For theevaluator, this means that the syntax of the language being evaluated isdetermined solely by the procedures that classify and extract pieces of expressions.

Here is the specification of the syntax of our language:

• The only self-evaluating items are numbers and strings:

  (define (self-evaluating? exp) (cond ((number? exp) true) ((string? exp) true) (else false)))

• Variables are represented by symbols:

  (define (variable? exp) (symbol? exp))

• Quotations have the form (quote <text-of-quotation>):9

  (define (quoted? exp) (tagged-list? exp 'quote)) (define (text-of-quotation exp) (cadr exp))

  Quoted? is defined in terms of the procedure tagged-list?, which identifies lists beginning with a designated symbol:

  (define (tagged-list? exp tag) (if (pair? exp) (eq? (car exp) tag) false))

• Assignments have the form (set! ⟨var⟩ ⟨value⟩):

  (define (assignment? exp) (tagged-list? exp 'set!)) (define (assignment-variable exp) (cadr exp)) (define (assignment-value exp) (caddr exp))

• Definitions have the form

  (define ⟨var⟩ ⟨value⟩)

  or the form

  (define (⟨var⟩ ⟨parameter_1⟩ ... ⟨parameter_n⟩) ⟨body⟩)

  The latter form (standard procedure definition) is syntactic sugar for

  (define ⟨var⟩ (lambda (⟨parameter_1⟩ ... ⟨parameter_n⟩) ⟨body⟩))

  The corresponding syntax procedures are the following:

  (define (definition? exp) (tagged-list? exp 'define)) (define (definition-variable exp) (if (symbol? (cadr exp)) (cadr exp) (caadr exp))) (define (definition-value exp) (if (symbol? (cadr exp)) (caddr exp) (make-lambda (cdadr exp) ; formal parameters (cddr exp)))) ; body

• Lambda expressions are lists that begin with the symbol lambda:

  (define (lambda? exp) (tagged-list? exp 'lambda)) (define (lambda-parameters exp) (cadr exp)) (define (lambda-body exp) (cddr exp))

  We also provide a constructor for lambda expressions, which is used by definition-value, above:

  (define (make-lambda parameters body) (cons 'lambda (cons parameters body)))

• Conditionals begin with if and have a predicate, a consequent, and an (optional) alternative. If the expression has no alternative part, we provide false as the alternative.10

  (define (if? exp) (tagged-list? exp 'if)) (define (if-predicate exp) (cadr exp)) (define (if-consequent exp) (caddr exp)) (define (if-alternative exp) (if (not (null? (cdddr exp))) (cadddr exp) 'false))

  We also provide a constructor for if expressions, to be used by cond->if to transform cond expressions into if expressions:

  (define (make-if predicate consequent alternative) (list 'if predicate consequent alternative))

• Begin packages a sequence of expressions into a single expression. We include syntax operations on begin expressions to extract the actual sequence from the begin expression, as well as selectors that return the first expression and the rest of the expressions in the sequence.11

  (define (begin? exp) (tagged-list? exp 'begin)) (define (begin-actions exp) (cdr exp)) (define (last-exp? seq) (null? (cdr seq))) (define (first-exp seq) (car seq)) (define (rest-exps seq) (cdr seq))

  We also include a constructor sequence->exp (for use by cond->if) that transforms a sequence into a single expression, using begin if necessary:

  (define (sequence->exp seq) (cond ((null? seq) seq) ((last-exp? seq) (first-exp seq)) (else (make-begin seq)))) (define (make-begin seq) (cons 'begin seq))

• A procedure application is any compound expression that is not one of the above expression types. The car of the expression is the operator, and the cdr is the list of operands:

  (define (application? exp) (pair? exp)) (define (operator exp) (car exp)) (define (operands exp) (cdr exp)) (define (no-operands? ops) (null? ops)) (define (first-operand ops) (car ops)) (define (rest-operands ops) (cdr ops))

Derived expressions

Some special forms in our language can be defined in terms of expressions involving other special forms, rather than being implemented directly. One example is cond, which can be implemented as a nest of if expressions. For example, we can reduce the problem of evaluating the expression

to the problem of evaluating the following expression involving if and begin expressions:

Implementing the evaluation of cond in this way simplifies the evaluator because it reduces the number of special forms for which the evaluation process must be explicitly specified.

We include syntax procedures that extract the parts of a cond expression, and a procedure cond->if that transforms cond expressions into if expressions. A case analysis begins with cond and has a list of predicate-action clauses. A clause is an else clause if its predicate is the symbol else.12

Expressions (such as cond) that we choose to implement as syntactic transformations are called derived expressions. Let expressions are also derived expressions (see Exercise 4-6).4

4.1.3 Evaluator Data Structures

In addition to defining the external syntax of expressions, the evaluator implementation must also define the data structures that the evaluator manipulates internally, as part of the execution of a program, such as the representation of procedures and environments and the representation of true and false.

Testing of predicates

For conditionals, we accept anything to be true that is not the explicit false object.

Representing procedures

To handle primitives, we assume that we have available the following procedures:

• (apply-primitive-procedure proc args) applies the given primitive procedure to the argument values in the list <args> and returns the result of the application.
• (primitive-procedure? proc) tests whether <proc> is a primitive procedure.

These mechanisms for handling primitives are further described in section 4-1-4.

Compound procedures are constructed from parameters, procedure bodies, and environments using the constructor make-procedure:

Operations on Environments

The evaluator needs operations for manipulating environments. As explained in section 3.2, an environment is a sequence of frames, where each frame is a table of bindings that associate variables with their corresponding values. We use the following operations for manipulating environments:

• (lookup-variable-value var env) returns the value that is bound to the symbol <var> in the environment <env>, or signals an error if the variable is unbound.
• (extend-environment variables values base-env)

  returns a new environment, consisting of a new frame in which the symbols in the list <variables> are bound to the corresponding elements in the list <values>, where the enclosing environment is the environment <base-env>.

• (define-variable! var value env) adds to the first frame in the environment <env> a new binding that associates the variable <var> with the value <value>.
• (set-variable-value! var value env) changes the binding of the variable <var> in the environment <env> so that the variable is now bound to the value <value>, or signals an error if the variable is unbound.

To implement these operations we represent an environment as a list of frames. The enclosing environment of an environment is the cdr of the list. The empty environment is simply the empty list.

Each frame of an environment is represented as a pair of lists: a list of the variables bound in that frame and a list of the associated values.14

To extend an environment by a new frame that associates variables with values, we make a frame consisting of the list of variables and the list of values, and we adjoin this to the environment. We signal an error if the number of variables does not match the number of values.

To look up a variable in an environment, we scan the list of variables in the first frame. If we find the desired variable, we return the corresponding element in the list of values. If we do not find the variable in the current frame, we search the enclosing environment, and so on. If we reach the empty environment, we signal an ``unbound variable'' error.

To set a variable to a new value in a specified environment, we scan for the variable, just as in lookup-variable-value, and change the corresponding value when we find it.

To define a variable, we search the first frame for a binding for the variable, and change the binding if it exists (just as in set-variable-value!). If no such binding exists, we adjoin one to the first frame.

The method described here is only one of many plausible ways to represent environments. Since we used data abstraction to isolate the rest of the evaluator from the detailed choice of representation, we could change the environment representation if we wanted to. (See Exercise 4-11.) In a production-quality Lisp system, the speed of the evaluator's environment operations---especially that of variable lookup---has a major impact on the performance of the system. The representation described here, although conceptually simple, is not efficient and would not ordinarily be used in a production system.15

4.1.4 Running the Evaluator as a Program

Given the evaluator, we have in our hands a description (expressed in Lisp) of the process by which Lisp expressions are evaluated. One advantage of expressing the evaluator as a program is that we can run the program. This gives us, running within Lisp, a working model of how Lisp itself evaluates expressions. This can serve as a framework for experimenting with evaluation rules, as we shall do later in this chapter.

Our evaluator program reduces expressions ultimately to the application of primitive procedures. Therefore, all that we need to run the evaluator is to create a mechanism that calls on the underlying Lisp system to model the application of primitive procedures.

There must be a binding for each primitive procedure name, so that when eval evaluates the operator of an application of a primitive, it will find an object to pass to apply. We thus set up a global environment that associates unique objects with the names of the primitive procedures that can appear in the expressions we will be evaluating. The global environment also includes bindings for the symbols true and false, so that they can be used as variables in expressions to be evaluated.

It does not matter how we represent the primitive procedure objects, so long as apply can identify and apply them by using the procedures primitive-procedure? and apply-primitive-procedure. We have chosen to represent a primitive procedure as a list beginning with the symbol primitive and containing a procedure in the underlying Lisp that implements that primitive.

Setup-environment will get the primitive names and implementation procedures from a list:16

To apply a primitive procedure, we simply apply the implementation procedure to the arguments, using the underlying Lisp system:17

For convenience in running the metacircular evaluator, we provide a driver loop that models the read-eval-print loop of the underlying Lisp system. It prints a prompt , reads an input expression, evaluates this expression in the global environment, and prints the result. We precede each printed result by an output prompt so as to distinguish the value of the expression from other output that may be printed.18

We use a special printing procedure, user-print, to avoid printing the environment part of a compound procedure, which may be a very long list (or may even contain cycles).

Now all we need to do to run the evaluator is to initialize the global environment and start the driver loop. Here is a sample interaction:

4.1.5 Data as Programs

In thinking about a Lisp program that evaluates Lisp expressions, an analogy might be helpful. One operational view of the meaning of a program is that a program is a description of an abstract (perhaps infinitely large) machine. For example, consider the familiar program to compute factorials:

We may regard this program as the description of a machine containing parts that decrement, multiply, and test for equality, together with a two-position switch and another factorial machine. (The factorial machine is infinite because it contains another factorial machine within it.) Figure 4-2 is a flow diagram for the factorial machine, showing how the parts are wired together.

    +-----------------------------------+
    | factorial                   |1    |
    |              |1             V     |
    |              |           +-----+  |
    |              V           | #   |  |
    |           +-----+        |     |  |
6 --------*-----|  =  |------->|   #-+-----> 720
    |     |     +-----+        |  /  |  |
    |     |                    | #   |  |
    |     |                    +-----+  |
    |     |                       ^     |
    |     |                       |     |
    |     |                    +--+--+  |
    |     *------------------->|  *  |  |
    |     |                    +-----+  |
    |     V                       ^     |
    |  +-----+    +-----------+   |     |
    |  |  -  +--->| factorial +---+     |
    |  +-----+    +-----------+         |
    |     ^                             |
    |     |1                            |
    +-----------------------------------+

In a similar way, we can regard the evaluator as a very special machine that takes as input a description of a machine. Given this input, the evaluator configures itself to emulate the machine described. For example, if we feed our evaluator the definition of factorial, as shown in Figure 4-3, the evaluator will be able to compute factorials.

From this perspective, our evaluator is seen to be a universal machine . It mimics other machines when these are described as Lisp programs.@footnote{The fact that the machines are described in Lisp is inessential. If we give our evaluator a Lisp program that behaves as an evaluator for some other language, say C, the Lisp evaluator will emulate the C evaluator, which in turn can emulate any machine described as a C program. Similarly, writing a Lisp evaluator in C produces a C program that can execute any Lisp program. The deep idea here is that any evaluator can emulate any other. Thus, the notion of ``what can in principle be computed'' (ignoring practicalities of time and memory required) is independent of the language or the computer, and instead reflects an underlying notion of computability . This was first demonstrated in a clear way by Alan M. Turing (1912-1954), whose 1936 paper laid the foundations for theoretical computer science. In the paper, Turing presented a simple computational model---now known as a Turing machine ---and argued that any ``effective process'' can be formulated as a program for such a machine. (This argument is known as the Church-Turing thesis .) Turing then implemented a universal machine, i.e., a Turing machine that behaves as an evaluator for Turing-machine programs. He used this framework to demonstrate that there are well-posed problems that cannot be computed by Turing machines (see Exercise 4-15), and so by implication cannot be formulated as ``effective processes.'' Turing went on to make fundamental contributions to practical computer science as well. For example, he invented the idea of structuring programs using general-purpose subroutines. See Hodges 1983 for a biography of Turing.} This is striking. Try to imagine an analogous evaluator for electrical circuits. This would be a circuit that takes as input a signal encoding the plans for some other circuit, such as a filter. Given this input, the circuit evaluator would then behave like a filter with the same description. Such a universal electrical circuit is almost unimaginably complex. It is remarkable that the program evaluator is a rather simple program.@footnote{Some people find it counterintuitive that an evaluator, which is implemented by a relatively simple procedure, can emulate programs that are more complex than the evaluator itself. The existence of a universal evaluator machine is a deep and wonderful property of computation. Recursion theory , a branch of mathematical logic, is concerned with logical limits of computation. Douglas Hofstadter's beautiful book @cite{G@"odel, Escher, Bach} (1979) explores some of these ideas.} Another striking aspect of the evaluator is that it acts as a bridge between the data objects that are manipulated by our programming language and the programming language itself. Imagine that the evaluator program (implemented in Lisp) is running, and that a user is typing expressions to the evaluator and observing the results. From the perspective of the user, an input expression such as (* x x) is an expression in the programming language, which the evaluator should execute. From the perspective of the evaluator, however, the expression is simply a list (in this case, a list of three symbols: *, x, and x) that is to be manipulated according to a well-defined set of rules. That the user's programs are the evaluator's data need not be a source of confusion. In fact, it is sometimes convenient to ignore this distinction, and to give the user the ability to explicitly evaluate a data object as a Lisp expression, by making eval available for use in programs. Many Lisp dialects provide a primitive eval procedure that takes as arguments an expression and an environment and evaluates the expression relative to the environment.@footnote{Warning: This eval primitive is not identical to the eval procedure we implemented in section 4.1.1, because it uses actual Scheme environments rather than the sample environment structures we built in section 4.1.3. These actual environments cannot be manipulated by the user as ordinary lists; they must be accessed via eval or other special operations. Similarly, the apply primitive we saw earlier is not identical to the metacircular apply, because it uses actual Scheme procedures rather than the procedure objects we constructed in sections 4-1-3 and 4-1-4.} Thus,

will both return 25.@footnote{The @acronym{MIT} implementation of Scheme includes eval, as well as a symbol user-initial-environment that is bound to the initial environment in which the user's input expressions are evaluated.}

4.1.6 Internal Definitions

Our environment model of evaluation and our metacircular evaluator execute definitions in sequence, extending the environment frame one definition at a time. This is particularly convenient for interactive program development, in which the programmer needs to freely mix the application of procedures with the definition of new procedures. However, if we think carefully about the internal definitions used to implement block structure (introduced in section 1-1-8), we will find that name-by-name extension of the environment may not be the best way to define local variables. Consider a procedure with internal definitions, such as

Our intention here is that the name odd? in the body of the procedure even? should refer to the procedure odd? that is defined after even?. The scope of the name odd? is the entire body of f, not just the portion of the body of f starting at the point where the define for odd? occurs. Indeed, when we consider that odd? is itself defined in terms of even?---so that even? and odd? are mutually recursive procedures---we see that the only satisfactory interpretation of the two defines is to regard them as if the names even? and odd? were being added to the environment simultaneously. More generally, in block structure, the scope of a local name is the entire procedure body in which the define is evaluated. As it happens, our interpreter will evaluate calls to f correctly, but for an ``accidental'' reason: Since the definitions of the internal procedures come first, no calls to these procedures will be evaluated until all of them have been defined. Hence, odd? will have been defined by the time even? is executed. In fact, our sequential evaluation mechanism will give the same result as a mechanism that directly implements simultaneous definition for any procedure in which the internal definitions come first in a body and evaluation of the value expressions for the defined variables doesn't actually use any of the defined variables. (For an example of a procedure that doesn't obey these restrictions, so that sequential definition isn't equivalent to simultaneous definition, see Exercise 4-19.)@footnote{Wanting programs to not depend on this evaluation mechanism is the reason for the ``management is not responsible'' remark in Footnote 28 of Chapter 1. By insisting that internal definitions come first and do not use each other while the definitions are being evaluated, the @acronym{IEEE} standard for Scheme leaves implementors some choice in the mechanism used to evaluate these definitions. The choice of one evaluation rule rather than another here may seem like a small issue, affecting only the interpretation of ``badly formed'' programs. However, we will see in section 5.5.6 that moving to a model of simultaneous scoping for internal definitions avoids some nasty difficulties that would otherwise arise in implementing a compiler.} There is, however, a simple way to treat definitions so that internally defined names have truly simultaneous scope---just create all local variables that will be in the current environment before evaluating any of the value expressions. One way to do this is by a syntax transformation on lambda expressions. Before evaluating the body of a lambda expression, we ``scan out'' and eliminate all the internal definitions in the body. The internally defined variables will be created with a let and then set to their values by assignment. For example, the procedure

4.1.7 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:

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.@footnote{This technique is an integral part of the compilation process, which we shall discuss in Chapter 5. Jonathan Rees wrote a Scheme interpreter like this in about 1982 for the T project (Rees and Adams 1982). Marc Feeley (1986) (see also Feeley and Lapalme 1987) independently invented this technique in his master's thesis.} 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

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 4.1.1, except that the procedures to which we dispatch perform only analysis, not full evaluation:

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:

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.

Looking up a variable value must still be done in the execution phase, since this depends upon knowing the environment.@footnote{There is, however, an important part of the variable search that can be done as part of the syntactic analysis. As we will show in section 5.5.6, one can determine the position in the environment structure where the value of the variable will be found, thus obviating the need to scan the environment for the entry that matches the variable.}

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.

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

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.

Analysis of a sequence of expressions (as in a begin or the body of a lambda expression) is more involved.@footnote{See Exercise 4-23 for some insight into the processing of sequences.} 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.

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 4-1-1. 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.

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

Interactive SICP is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
Based on a work at https://mitpress.mit.edu/sicp/.