Structure and Interpretation of Computer Programs (71 page)

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

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.

• For self-evaluating expressions, such as numbers,
  eval
  returns
  the expression itself.
  
• Eval
  must look up variables in the environment to find their values.
  

• 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.
  

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

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

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

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

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

(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values (rest-operands exps) env))))

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:

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

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.
⁶

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.

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

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.

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

Definitions of variables are handled in a similar
manner.
⁷

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

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

Exercise 4.1.
  
Notice that we cannot tell whether the metacircular evaluator
evaluates operands from left to right or from right to left. Its evaluation
order is inherited from the underlying Lisp:
If the arguments to
cons
in
list-of-values
are evaluated from left to right, then
list-of-values
will
evaluate operands from left to right; and
if the arguments to
cons
are evaluated from right to left, then
list-of-values
will
evaluate operands from right to left.

Write a version of
list-of-values
that evaluates operands
from left to right regardless of the order of evaluation in the underlying
Lisp. Also write a version of
list-of-values
that evaluates operands
from right to left.

The evaluator is reminiscent of the symbolic differentiation program
discussed in section 
2.3.2
. Both
programs operate on symbolic expressions. In both programs, the
result of operating on a compound expression is determined by
operating recursively on the pieces of the expression and combining
the results in a way that depends on the type of the expression. In
both programs we used
data abstraction to decouple the general rules
of operation from the details of how expressions are represented. In
the differentiation program this meant that the same differentiation
procedure could deal with algebraic expressions in prefix form, in
infix form, or in some other form. For the evaluator, this means that
the syntax of the language being evaluated is determined 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
>)
:
⁹

(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
₁
>
...
<
parameter
_n
>)
  <
body
>)

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

(define <
var
>
  (lambda (<
parameter
₁
>
...
<
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.
¹⁰

(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.
¹¹