Structure and Interpretation of Computer Programs (76 page)

Now that we have an evaluator expressed as a Lisp program, we can
experiment with alternative choices in language design simply by
modifying the evaluator. Indeed, new languages are often invented by
first writing an evaluator that embeds the new language within an
existing high-level language. For example, if we wish to discuss some
aspect of a proposed modification to Lisp with another member of the
Lisp community, we can supply an evaluator that embodies
the change. The recipient can then experiment with the new
evaluator and send back comments as further modifications. Not only
does the high-level implementation base make it easier to test and
debug the evaluator; in addition, the embedding enables the designer
to snarf
³¹
features
from the underlying language, just as our embedded Lisp evaluator
uses primitives and control structure from the underlying Lisp. Only
later (if ever) need the designer go to the trouble of building a
complete implementation in a low-level language or in hardware. In
this section and the next we explore some variations on Scheme that
provide significant additional expressive power.

In section 
1.1
, where we began our discussion
of models of evaluation, we noted that Scheme is an
applicative-order
language, namely, that all the arguments to Scheme
procedures are evaluated when the procedure is applied. In
contrast,
normal-order
languages delay evaluation of procedure arguments
until the actual argument values are needed.
Delaying evaluation of procedure arguments until the
last possible moment (e.g., until they are required by a primitive
operation) is called
lazy evaluation
.
³²
Consider the procedure

(define (try a b)
  (if (= a 0) 1 b))

Evaluating
(try 0 (/ 1 0))
generates an error in Scheme. With
lazy evaluation, there would be no error. Evaluating the expression
would return 1, because the argument
(/ 1 0)
would
never be evaluated.

An example that exploits lazy evaluation is the
definition of a procedure
unless

(define (unless condition usual-value exceptional-value)
  (if condition exceptional-value usual-value))

that can be used in expressions such as

(unless (= b 0)
        (/ a b)
        (begin (display "exception: returning 0")
               0))

This won't work in an applicative-order language because both the
usual value and the exceptional value will be evaluated before
unless
is called (compare exercise 
1.6
). An
advantage of lazy evaluation is that some procedures, such as
unless
, can do useful computation even if evaluation of some of their
arguments would produce errors or would not terminate.

If the body of a procedure is entered before an argument has been
evaluated we say that the procedure is
non-strict
in that
argument. If the argument is evaluated before the body of the
procedure is entered we say that the procedure is
strict
in that
argument.
³³
In a purely applicative-order language, all procedures are strict in
each argument. In a purely normal-order language, all compound
procedures are non-strict in each argument, and primitive procedures may be
either strict or non-strict. There are also languages (see
exercise 
4.31
) that give programmers
detailed control over the strictness of the procedures they define.

A striking example of a procedure that can usefully be made non-strict
is
cons
(or, in general, almost any constructor for data
structures). One can do useful computation, combining elements to
form data structures and operating on the resulting data structures,
even if the values of the elements are not known. It makes perfect
sense, for instance, to compute the length of a list without knowing
the values of the individual elements in the list. We will exploit
this idea in section 
4.2.3
to implement the
streams of chapter 3 as lists formed of non-strict
cons
pairs.

Exercise 4.25.
  Suppose that (in ordinary applicative-order Scheme) we define
unless
as shown above and then define
factorial
in terms of
unless
as

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

What happens if we attempt to evaluate
(factorial 5)
? Will our
definitions work in a normal-order language?

Exercise 4.26.
  
Ben Bitdiddle and Alyssa P. Hacker disagree over the importance of
lazy evaluation for implementing things such as
unless
. Ben
points out that it's possible to implement
unless
in applicative
order as a special form.
Alyssa counters that, if one did that,
unless
would be merely
syntax, not a procedure that could be used in conjunction with
higher-order procedures. Fill in the details on both sides of the
argument. Show how to implement
unless
as a derived expression
(like
cond
or
let
),
and give an example of a situation where it might be useful to have
unless
available as a procedure, rather than as a special form.

In this section we will implement a normal-order language that is
the same as Scheme except that compound procedures are non-strict
in each argument. Primitive procedures will still be strict.
It is not difficult to modify the evaluator of
section 
4.1.1
so that the language it interprets behaves
this way. Almost all the required changes center around procedure
application.

The basic idea is that, when applying a procedure, the interpreter
must determine which arguments are to be
evaluated and which are to be
delayed. The delayed arguments are not
evaluated; instead, they are transformed into objects called
thunk
s.
³⁴
The thunk must contain the information required to produce the value
of the argument when it is needed, as if it had been evaluated at
the time of the application. Thus, the thunk must contain the
argument expression and the environment in
which the procedure application is being evaluated.

The process of evaluating the expression in a thunk is called
forcing
.
³⁵
In general, a thunk will be forced only when its value is needed:
when it is passed to a primitive procedure that
will use the value of the thunk; when it is the
value of a predicate of a conditional; and when it
is the value of an operator that is about to be applied as a procedure.
One design choice we have available is whether or not to
memoize
thunks, as we did with delayed objects in
section 
3.5.1
. With memoization, the first time a
thunk is forced, it stores the value that is computed. Subsequent
forcings simply return the stored value without repeating the
computation. We'll make our interpreter memoize, because this is
more efficient for many applications. There are tricky
considerations here, however.
³⁶

The main difference between the lazy evaluator and the one in
section 
4.1
is in the handling of procedure
applications in
eval
and
apply
.

The
application?
clause of
eval
becomes

((application? exp)
 (apply (actual-value (operator exp) env)
        (operands exp)
        env))

This is almost the same as the
application?
clause of
eval
in section 
4.1.1
. For lazy evaluation, however,
we call
apply
with the operand expressions, rather than the
arguments produced by evaluating them. Since we will need the environment to
construct thunks if the arguments are to be delayed, we must pass this as well.
We still evaluate the
operator, because
apply
needs the actual procedure to be applied
in order to dispatch on its type (primitive versus compound) and apply it.

Whenever we need the actual value of an expression, we use

(define (actual-value exp env)
  (force-it (eval exp env)))

instead of just
eval
, so that if the expression's value
is a thunk, it will be forced.

Our new version of
apply
is also almost the same as the
version in section 
4.1.1
. The difference is
that
eval
has passed in unevaluated operand expressions:
For primitive procedures (which are strict), we evaluate all the
arguments before applying the primitive;
for compound procedures (which are non-strict) we delay all the
arguments before applying the procedure.

(define (apply procedure arguments env)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure
          procedure
          (list-of-arg-values arguments env)))  
; changed
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (extend-environment
           (procedure-parameters procedure)
           (list-of-delayed-args arguments env) 
; changed
           (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))

The procedures that process the arguments are just like
list-of-values
from section 
4.1.1
, except that
list-of-delayed-args
delays the arguments instead of evaluating
them, and
list-of-arg-values
uses
actual-value
instead
of
eval
:

(define (list-of-arg-values exps env)
  (if (no-operands? exps)
      '()
      (cons (actual-value (first-operand exps) env)
            (list-of-arg-values (rest-operands exps)
                                env))))
(define (list-of-delayed-args exps env)
  (if (no-operands? exps)
      '()
      (cons (delay-it (first-operand exps) env)
            (list-of-delayed-args (rest-operands exps)
                                  env))))

The other place we must change the evaluator is in the handling of
if
, where we must use
actual-value
instead
of
eval
to get the value of the predicate expression
before testing whether it is true or false:

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

Finally, we must change the
driver-loop
procedure (section 
4.1.4
) to use
actual-value
instead
of
eval
, so that if a delayed value
is propagated back to the read-eval-print loop, it will be forced
before being printed. We also change the prompts to indicate that
this is the lazy evaluator:

(define input-prompt ";;; L-Eval input:")
(define output-prompt ";;; L-Eval value:")
(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output
           (actual-value input the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))

With these changes made, we can start the evaluator and test it. The
successful evaluation of the
try
expression discussed in
section 
4.2.1
indicates that the interpreter is
performing lazy evaluation:

(define the-global-environment (setup-environment))
(driver-loop)
;;; L-Eval input:
(define (try a b)
  (if (= a 0) 1 b))
;;; L-Eval value:
ok
;;; L-Eval input:
(try 0 (/ 1 0))
;;; L-Eval value:
1

Our evaluator must arrange to create thunks when procedures are
applied to arguments and to force these thunks later. A thunk must
package an expression together with the environment, so that the
argument can be produced later.
To force the thunk, we simply extract the expression and environment
from the thunk and evaluate the expression in the environment.
We use
actual-value
rather than
eval
so that in case the
value of the expression is itself a thunk, we will force that, and so
on, until we reach something that is not a thunk:

(define (force-it obj)
  (if (thunk? obj)
      (actual-value (thunk-exp obj) (thunk-env obj))
      obj))