Structure and Interpretation of Computer Programs (77 page)

One easy way to package an expression with an environment is to make a
list containing the expression and the environment.
Thus, we create a thunk as follows:

(define (delay-it exp env)
  (list 'thunk exp env))
(define (thunk? obj)
  (tagged-list? obj 'thunk))
(define (thunk-exp thunk) (cadr thunk))
(define (thunk-env thunk) (caddr thunk))

Actually, what we want for our interpreter is not quite this, but
rather thunks that have been memoized.
When a thunk is forced, we will turn it into an evaluated thunk
by replacing the stored expression with its value and
changing the
thunk
tag so that it can be recognized as
already evaluated.
³⁷

(define (evaluated-thunk? obj)
  (tagged-list? obj 'evaluated-thunk))
(define (thunk-value evaluated-thunk) (cadr evaluated-thunk))
(define (force-it obj)
  (cond ((thunk? obj)
         (let ((result (actual-value
                        (thunk-exp obj)
                        (thunk-env obj))))
           (set-car! obj 'evaluated-thunk)
           (set-car! (cdr obj) result)  
; replace 
exp
 with its value
           (set-cdr! (cdr obj) '())     
; forget unneeded 
env
           result))
        ((evaluated-thunk? obj)
         (thunk-value obj))
        (else obj)))

Notice that the same
delay-it
procedure works both with and
without memoization.

Exercise 4.27.
  Suppose we type in the following definitions to the lazy evaluator:

(define count 0)
(define (id x)
  (set! count (+ count 1))
  x)

Give the missing values in the following sequence of
interactions, and explain your answers.
³⁸

(define w (id (id 10)))
;;; L-Eval input:
count
;;; L-Eval value:
<
response
>
;;; L-Eval input:
w
;;; L-Eval value:
<
response
>
;;; L-Eval input:
count
;;; L-Eval value:
<
response
>

Exercise 4.28.
  
Eval
uses
actual-value
rather than
eval
to evaluate the operator before passing it to
apply
,
in order to force the value of the operator.
Give an example that demonstrates the need for this forcing.

Exercise 4.29.
  Exhibit a program that you would expect to run much more slowly
without memoization than with memoization. Also, consider the
following interaction, where the
id
procedure is defined as in
exercise 
4.27
and
count
starts at 0:

(define (square x)
  (* x x))
;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
<
response
>
;;; L-Eval input:
count
;;; L-Eval value:
<
response
>

Give the responses both when the evaluator memoizes and when it does not.

Exercise 4.30.
  Cy D. Fect, a reformed C programmer, is worried that some side effects
may never take place, because the lazy evaluator doesn't force the
expressions in a sequence.
Since the value of an expression in a sequence other than the last one
is not used (the expression is there only for its effect, such as
assigning to a variable or printing), there can be no subsequent use
of this value (e.g., as an argument to a primitive procedure) that
will cause it to be forced. Cy thus thinks that when evaluating
sequences, we must force all expressions in the sequence except the
final one. He proposes to modify
eval-sequence
from
section 
4.1.1
to use
actual-value
rather
than
eval
:

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

a. Ben Bitdiddle thinks Cy is wrong.
He shows Cy the
for-each
procedure described in
exercise 
2.23
, which gives an important example of
a sequence with side effects:

(define (for-each proc items)
  (if (null? items)
      'done
      (begin (proc (car items))
             (for-each proc (cdr items)))))

He claims that the evaluator in the text (with the original
eval-sequence
) handles this correctly:

;;; L-Eval input:
(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
57
321
88
;;; L-Eval value:
done

Explain why Ben is right about the behavior of
for-each
.

b. Cy agrees that Ben is right about the
for-each
example,
but says that that's not the kind of program he was thinking about
when he proposed his change to
eval-sequence
.
He defines the following two procedures in the lazy evaluator:

(define (p1 x)
  (set! x (cons x '(2)))
  x)
(define (p2 x)
  (define (p e)
    e
    x)
  (p (set! x (cons x '(2)))))

What are the values of
(p1 1)
and
(p2 1)
with the
original
eval-sequence
?
What would the values be with Cy's proposed change to
eval-sequence
?

c. Cy also points out that changing
eval-sequence
as he proposes
does not affect the behavior of the example in part a.
Explain why this is true.

d. How do you think sequences ought to be treated in the lazy evaluator?
Do you like Cy's approach, the approach in the text, or some other approach?

Exercise 4.31.
  
The approach taken in this section is somewhat unpleasant, because it
makes an incompatible change to Scheme. It might be nicer to
implement lazy evaluation as an
upward-compatible extension
,
that is, so that ordinary Scheme programs will work as before. We can
do this by extending the syntax of procedure declarations to let the user
control whether or not arguments are to be delayed. While we're at
it, we may as well also give the user the choice between delaying with
and without memoization. For example, the definition

(define (f a (b lazy) c (d lazy-memo))
  
...
)

would define
f
to be a procedure of four arguments, where the
first and third arguments are evaluated when the procedure is called,
the second argument is delayed, and the fourth argument is both
delayed and memoized. Thus, ordinary procedure definitions will
produce the same behavior as ordinary Scheme, while adding the
lazy-memo
declaration to each parameter of every compound procedure
will produce the behavior of the lazy evaluator defined in this
section. Design and implement the changes required to produce such an
extension to Scheme. You will have to implement new syntax procedures
to handle the new syntax for
define
. You must also arrange for
eval
or
apply
to determine when arguments are to be delayed, and to
force or delay arguments accordingly, and you must arrange for forcing
to memoize or not, as appropriate.

In section 
3.5.1
, we showed how to implement streams
as delayed lists. We introduced special forms
delay
and
cons-stream
, which allowed us to construct a “promise” to compute
the
cdr
of a stream, without actually fulfilling that promise
until later. We could use this general technique of introducing
special forms whenever we need more control over the evaluation process,
but this is awkward. For one thing, a special form is not a
first-class object like a procedure, so we cannot use it together with
higher-order procedures.
³⁹
Additionally,
we were forced to create streams as a new kind of data object
similar but not identical to lists, and this required us to
reimplement many ordinary list operations (
map
,
append
, and
so on) for use with streams.

With lazy evaluation, streams and lists can be identical, so there is
no need for special forms or for separate list and stream operations.
All we need to do is to arrange matters so that
cons
is
non-strict. One way to accomplish this is to extend the lazy
evaluator to allow for non-strict primitives, and to implement
cons
as one of these. An easier way is to recall
(section 
2.1.3
) that there is no fundamental need to
implement
cons
as a primitive at all. Instead, we can represent
pairs as procedures:
⁴⁰

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))

In terms of these basic operations, the standard definitions of the
list operations will work with infinite lists (streams) as well as
finite ones, and the stream operations can be implemented as list operations.
Here are some examples:

(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))
(define (map proc items)
  (if (null? items)
      '()
      (cons (proc (car items))
            (map proc (cdr items)))))
(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))
(define (add-lists list1 list2)
  (cond ((null? list1) list2)
        ((null? list2) list1)
        (else (cons (+ (car list1) (car list2))
                    (add-lists (cdr list1) (cdr list2))))))
(define ones (cons 1 ones))
(define integers (cons 1 (add-lists ones integers)))
;;; L-Eval input:
(list-ref integers 17)
;;; L-Eval value:
18

Note that these lazy lists are even lazier than the streams of
chapter 3: The
car
of the list, as well as the
cdr
, is
delayed.
⁴¹
In fact, even accessing the
car
or
cdr
of a lazy
pair need not force the value of a list element. The value will be
forced only when it is really needed – e.g., for use as the
argument of a primitive, or to be printed as an answer.

Lazy pairs also help with the problem that arose with streams in
section 
3.5.4
, where we found that
formulating stream models of systems with loops may require us to
sprinkle our programs with
explicit
delay
operations, beyond the
ones supplied by
cons-stream
. With lazy evaluation, all
arguments to procedures are delayed uniformly. For instance, we can
implement procedures to integrate lists and solve differential
equations as we originally intended in
section 
3.5.4
:

(define (integral integrand initial-value dt)
  (define int
    (cons initial-value
          (add-lists (scale-list integrand dt)
                    int)))
  int)
(define (solve f y0 dt)
  (define y (integral dy y0 dt))
  (define dy (map f y))
  y)
;;; L-Eval input:
(list-ref (solve (lambda (x) x) 1 0.001) 1000)
;;; L-Eval value:
2.716924

Exercise 4.32.
  Give some examples that illustrate the difference between the streams
of chapter 3 and the “lazier” lazy lists described in this section.
How can you take advantage of this extra laziness?

Exercise 4.33.
  Ben Bitdiddle tests the lazy list implementation given above by
evaluating the expression

(car '(a b c))

To his surprise, this produces an error. After some thought, he
realizes that the “lists” obtained by reading in quoted expressions
are different from the lists manipulated by the new definitions of
cons
,
car
, and
cdr
. Modify the evaluator's
treatment of quoted expressions so that quoted lists typed at the
driver loop will produce true lazy lists.

Exercise 4.34.
  Modify the driver loop for the evaluator so that lazy pairs and lists
will print in some reasonable way. (What are you going to do about
infinite lists?) You may also need to modify the representation of
lazy pairs so that the evaluator can identify them in order
to print them.