-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbook-Z-H-27.html
748 lines (657 loc) · 40.8 KB
/
book-Z-H-27.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4n,
(c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>
<p><div class=navigation>[Go to <a href="book.html">first</a>,
<a href="book-Z-H-26.html">previous</a>,
<a href="book-Z-H-28.html">next</a> page; <a href="book-Z-H-4.html#%_toc_start">contents</a>; <a href="book-Z-H-38.html#%_index_start">index</a>]</div><p>
<a name="%_sec_4.2"></a>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_4.2">4.2 Variations on a Scheme -- Lazy Evaluation</a></h2><p>
<a name="%_idx_4666"></a><a name="%_idx_4668"></a>
<a name="%_idx_4670"></a><a name="%_idx_4672"></a>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<a name="call_footnote_Temp_484" href="#footnote_Temp_484"><sup><small>31</small></sup></a> 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.<p>
<a name="%_sec_4.2.1"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.1">4.2.1 Normal Order and Applicative Order</a></h3><p>
<p>
<a name="%_idx_4680"></a><a name="%_idx_4682"></a>In section <a href="book-Z-H-10.html#%_sec_1.1">1.1</a>, where we began our discussion
of models of evaluation, we noted that Scheme is an <em>applicative-order</em> language, namely, that all the arguments to Scheme
procedures are evaluated when the procedure is applied. In
contrast, <em>normal-order</em> 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 <a name="%_idx_4684"></a><em>lazy evaluation</em>.<a name="call_footnote_Temp_485" href="#footnote_Temp_485"><sup><small>32</small></sup></a>
Consider the procedure<p>
<p><tt>(define (try a b)<br>
(if (= a 0) 1 b))<br>
</tt><p>
Evaluating <tt>(try 0 (/ 1 0))</tt> generates an error in Scheme. With
lazy evaluation, there would be no error. Evaluating the expression
would return 1, because the argument <tt>(/ 1 0)</tt> would
never be evaluated.<p>
An example that exploits lazy evaluation is the
definition of a procedure <tt>unless</tt><p>
<p><tt>(define (unless condition usual-value exceptional-value)<br>
(if condition exceptional-value usual-value))<br>
</tt><p>
that can be used in expressions such as<p>
<p><tt>(unless (= b 0)<br>
(/ a b)<br>
(begin (display "exception: returning 0")<br>
0))<br>
</tt><p>
This won't work in an applicative-order language because both the
usual value and the exceptional value will be evaluated before
<tt>unless</tt> is called (compare exercise <a href="book-Z-H-10.html#%_thm_1.6">1.6</a>). An
advantage of lazy evaluation is that some procedures, such as <tt>unless</tt>, can do useful computation even if evaluation of some of their
arguments would produce errors or would not terminate.<p>
If the body of a procedure is entered before an argument has been
evaluated we say that the procedure is <a name="%_idx_4686"></a><em>non-strict</em> in that
argument. If the argument is evaluated before the body of the
procedure is entered we say that the procedure is <a name="%_idx_4688"></a><em>strict</em> in that
argument.<a name="call_footnote_Temp_486" href="#footnote_Temp_486"><sup><small>33</small></sup></a>
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 <a href="#%_thm_4.31">4.31</a>) that give programmers
detailed control over the strictness of the procedures they define.<p>
A striking example of a procedure that can usefully be made non-strict
is <tt>cons</tt> (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 <a href="#%_sec_4.2.3">4.2.3</a> to implement the
streams of chapter 3 as lists formed of non-strict <tt>cons</tt>
pairs.<p>
<p><a name="%_thm_4.25"></a>
<b>Exercise 4.25.</b> Suppose that (in ordinary applicative-order Scheme) we define <tt>unless</tt>
as shown above and then define <tt>factorial</tt> in terms of <tt>unless</tt> as<p>
<p><tt>(define (factorial n)<br>
(unless (= n 1)<br>
(* n (factorial (- n 1)))<br>
1))<br>
</tt><p>
What happens if we attempt to evaluate <tt>(factorial 5)</tt>? Will our
definitions work in a normal-order language?
<p><p>
<p><a name="%_thm_4.26"></a>
<b>Exercise 4.26.</b> <a name="%_idx_4692"></a><a name="%_idx_4694"></a>Ben Bitdiddle and Alyssa P. Hacker disagree over the importance of
lazy evaluation for implementing things such as <tt>unless</tt>. Ben
points out that it's possible to implement <tt>unless</tt> in applicative
order as a special form.
Alyssa counters that, if one did that, <tt>unless</tt> 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 <tt>unless</tt> as a derived expression
(like <tt>cond</tt> or <tt>let</tt>),
and give an example of a situation where it might be useful to have
<tt>unless</tt> available as a procedure, rather than as a special form.
<p><p>
<a name="%_sec_4.2.2"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.2">4.2.2 An Interpreter with Lazy Evaluation</a></h3><p>
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 <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> so that the language it interprets behaves
this way. Almost all the required changes center around procedure
application.<p>
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 <a name="%_idx_4696"></a><em>thunk</em>s.<a name="call_footnote_Temp_489" href="#footnote_Temp_489"><sup><small>34</small></sup></a>
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.<p>
<a name="%_idx_4704"></a><a name="%_idx_4706"></a>The process of evaluating the expression in a thunk is called <em>forcing</em>.<a name="call_footnote_Temp_490" href="#footnote_Temp_490"><sup><small>35</small></sup></a>
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 <a name="%_idx_4710"></a><em>memoize</em> thunks, as we did with delayed objects in
section <a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a>. 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.<a name="call_footnote_Temp_491" href="#footnote_Temp_491"><sup><small>36</small></sup></a><p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Modifying the evaluator</a></h4><p>
The main difference between the lazy evaluator and the one in
section <a href="book-Z-H-26.html#%_sec_4.1">4.1</a> is in the handling of procedure
applications in <tt>eval</tt> and <tt>apply</tt>.<p>
<a name="%_idx_4720"></a>The <tt>application?</tt> clause of <tt>eval</tt> becomes<p>
<p><tt>((application? exp)<br>
(apply (actual-value (operator exp) env)<br>
(operands exp)<br>
env))<br>
</tt><p>
This is almost the same as the <tt>application?</tt> clause of <tt>eval</tt>
in section <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>. For lazy evaluation, however,
we call <tt>apply</tt> 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 <tt>apply</tt> needs the actual procedure to be applied
in order to dispatch on its type (primitive versus compound) and apply it.<p>
Whenever we need the actual value of an expression, we use
<p><tt><a name="%_idx_4722"></a>(define (actual-value exp env)<br>
(force-it (eval exp env)))<br>
</tt><p>
instead of just <tt>eval</tt>, so that if the expression's value
is a thunk, it will be forced.<p>
Our new version of <tt>apply</tt> is also almost the same as the
version in section <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>. The difference is
that <tt>eval</tt> 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.<p>
<p><tt><a name="%_idx_4724"></a>(define (apply procedure arguments env)<br>
(cond ((primitive-procedure? procedure)<br>
(apply-primitive-procedure<br>
procedure<br>
(list-of-arg-values arguments env))) <em>; changed</em><br>
((compound-procedure? procedure)<br>
(eval-sequence<br>
(procedure-body procedure)<br>
(extend-environment<br>
(procedure-parameters procedure)<br>
(list-of-delayed-args arguments env) <em>; changed</em><br>
(procedure-environment procedure))))<br>
(else<br>
(error<br>
"Unknown procedure type -- APPLY" procedure))))<br>
</tt><p>
The procedures that process the arguments are just like <tt>list-of-values</tt> from section <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>, except that
<tt>list-of-delayed-args</tt> delays the arguments instead of evaluating
them, and <tt>list-of-arg-values</tt> uses <tt>actual-value</tt> instead
of <tt>eval</tt>:<p>
<p><tt><a name="%_idx_4726"></a>(define (list-of-arg-values exps env)<br>
(if (no-operands? exps)<br>
'()<br>
(cons (actual-value (first-operand exps) env)<br>
(list-of-arg-values (rest-operands exps)<br>
env))))<br>
<br>
<a name="%_idx_4728"></a>(define (list-of-delayed-args exps env)<br>
(if (no-operands? exps)<br>
'()<br>
(cons (delay-it (first-operand exps) env)<br>
(list-of-delayed-args (rest-operands exps)<br>
env))))<br>
</tt><p><p>
The other place we must change the evaluator is in the handling of
<tt>if</tt>, where we must use <tt>actual-value</tt> instead
of <tt>eval</tt> to get the value of the predicate expression
before testing whether it is true or false:<p>
<p><tt><a name="%_idx_4730"></a>(define (eval-if exp env)<br>
(if (true? (actual-value (if-predicate exp) env))<br>
(eval (if-consequent exp) env)<br>
(eval (if-alternative exp) env)))<br>
</tt><p><p>
<a name="%_idx_4732"></a>Finally, we must change the <tt>driver-loop</tt>
procedure (section <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>) to use <tt>actual-value</tt> instead
of <tt>eval</tt>, 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:<p>
<p><tt><a name="%_idx_4734"></a>(define input-prompt ";;; L-Eval input:")<br>
(define output-prompt ";;; L-Eval value:")<br>
<br>
<a name="%_idx_4736"></a>(define (driver-loop)<br>
(prompt-for-input input-prompt)<br>
(let ((input (read)))<br>
(let ((output<br>
(actual-value input the-global-environment)))<br>
(announce-output output-prompt)<br>
(user-print output)))<br>
(driver-loop))<br>
</tt><p><p>
With these changes made, we can start the evaluator and test it. The
successful evaluation of the <tt>try</tt> expression discussed in
section <a href="#%_sec_4.2.1">4.2.1</a> indicates that the interpreter is
performing lazy evaluation:<p>
<p><tt>(define the-global-environment (setup-environment))<br>
<br>
(driver-loop)<br>
<br>
<i>;;; L-Eval input:</i><br>
(define (try a b)<br>
(if (= a 0) 1 b))<br>
<i>;;; L-Eval value:</i><br>
<i>ok</i><br>
<br>
<i>;;; L-Eval input:</i><br>
(try 0 (/ 1 0))<br>
<i>;;; L-Eval value:</i><br>
<i>1</i><br>
</tt><p><p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Representing thunks</a></h4><p>
<a name="%_idx_4738"></a>
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 <tt>actual-value</tt> rather than <tt>eval</tt> 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:<p>
<p><tt><a name="%_idx_4740"></a>(define (force-it obj)<br>
(if (thunk? obj)<br>
(actual-value (thunk-exp obj) (thunk-env obj))<br>
obj))<br>
</tt><p><p>
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:<p>
<p><tt><a name="%_idx_4742"></a>(define (delay-it exp env)<br>
(list 'thunk exp env))<br>
<br>
(define (thunk? obj)<br>
(tagged-list? obj 'thunk))<br>
<br>
(define (thunk-exp thunk) (cadr thunk))<br>
<br>
(define (thunk-env thunk) (caddr thunk))<br>
</tt><p><p>
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 <tt>thunk</tt> tag so that it can be recognized as
already evaluated.<a name="call_footnote_Temp_492" href="#footnote_Temp_492"><sup><small>37</small></sup></a><p>
<p><tt>(define (evaluated-thunk? obj)<br>
(tagged-list? obj 'evaluated-thunk))<br>
<br>
(define (thunk-value evaluated-thunk) (cadr evaluated-thunk))<br>
<br>
<a name="%_idx_4748"></a>(define (force-it obj)<br>
(cond ((thunk? obj)<br>
(let ((result (actual-value<br>
(thunk-exp obj)<br>
(thunk-env obj))))<br>
(set-car! obj 'evaluated-thunk)<br>
(set-car! (cdr obj) result) <em>; replace <tt>exp</tt> with its value</em><br>
(set-cdr! (cdr obj) '()) <em>; forget unneeded <tt>env</tt></em><br>
result))<br>
((evaluated-thunk? obj)<br>
(thunk-value obj))<br>
(else obj)))<br>
</tt><p>
Notice that the same <tt>delay-it</tt> procedure works both with and
without memoization.<p>
<p><a name="%_thm_4.27"></a>
<b>Exercise 4.27.</b> Suppose we type in the following definitions to the lazy evaluator:
<p><tt>(define count 0)<br>
<br>
(define (id x)<br>
(set! count (+ count 1))<br>
x)<br>
</tt><p>
Give the missing values in the following sequence of
interactions, and explain your answers.<a name="call_footnote_Temp_494" href="#footnote_Temp_494"><sup><small>38</small></sup></a>
<p><tt>(define w (id (id 10)))<br>
<br>
<i>;;; L-Eval input:</i><br>
count<br>
<i>;;; L-Eval value:</i><br>
<<em>response</em>><br>
<br>
<i>;;; L-Eval input:</i><br>
w<br>
<i>;;; L-Eval value:</i><br>
<<em>response</em>><br>
<br>
<i>;;; L-Eval input:</i><br>
count<br>
<i>;;; L-Eval value:</i><br>
<<em>response</em>><br>
</tt><p>
<p><p>
<p><a name="%_thm_4.28"></a>
<b>Exercise 4.28.</b> <tt>Eval</tt> uses <tt>actual-value</tt> rather than <tt>eval</tt>
to evaluate the operator before passing it to <tt>apply</tt>,
in order to force the value of the operator.
Give an example that demonstrates the need for this forcing.
<p><p>
<p><a name="%_thm_4.29"></a>
<b>Exercise 4.29.</b> Exhibit a program that you would expect to run much more slowly
without memoization than with memoization. Also, consider the
following interaction, where the <tt>id</tt> procedure is defined as in
exercise <a href="#%_thm_4.27">4.27</a> and <tt>count</tt> starts at 0:
<p><tt>(define (square x)<br>
(* x x))<br>
<br>
<i>;;; L-Eval input:</i><br>
(square (id 10))<br>
<i>;;; L-Eval value:</i><br>
<<em>response</em>><br>
<br>
<i>;;; L-Eval input:</i><br>
count<br>
<i>;;; L-Eval value:</i><br>
<<em>response</em>><br>
</tt><p>
Give the responses both when the evaluator memoizes and when it does not.
<p><p>
<p><a name="%_thm_4.30"></a>
<b>Exercise 4.30.</b> 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 <tt>eval-sequence</tt> from
section <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> to use <tt>actual-value</tt> rather
than <tt>eval</tt>:<p>
<p><tt>(define (eval-sequence exps env)<br>
(cond ((last-exp? exps) (eval (first-exp exps) env))<br>
(else (actual-value (first-exp exps) env)<br>
(eval-sequence (rest-exps exps) env))))<br>
</tt><p><p>
<p><p>a. Ben Bitdiddle thinks Cy is wrong.
He shows Cy the <tt>for-each</tt> procedure described in
exercise <a href="book-Z-H-15.html#%_thm_2.23">2.23</a>, which gives an important example of
a sequence with side effects:<p>
<p><tt><a name="%_idx_4750"></a>(define (for-each proc items)<br>
(if (null? items)<br>
'done<br>
(begin (proc (car items))<br>
(for-each proc (cdr items)))))<br>
</tt><p>
He claims that the evaluator in the text (with the original <tt>eval-sequence</tt>) handles this correctly:<p>
<p><tt><i>;;; L-Eval input:</i><br>
(for-each (lambda (x) (newline) (display x))<br>
(list 57 321 88))<br>
<i>57</i><br>
<i>321</i><br>
<i>88</i><br>
<i>;;; L-Eval value:</i><br>
<i>done</i><br>
</tt><p>
Explain why Ben is right about the behavior of <tt>for-each</tt>.<p>
<p><p>b. Cy agrees that Ben is right about the <tt>for-each</tt> example,
but says that that's not the kind of program he was thinking about
when he proposed his change to <tt>eval-sequence</tt>.
He defines the following two procedures in the lazy evaluator:<p>
<p><tt>(define (p1 x)<br>
(set! x (cons x '(2)))<br>
x)<br>
<br>
(define (p2 x)<br>
(define (p e)<br>
e<br>
x)<br>
(p (set! x (cons x '(2)))))<br>
</tt><p>
What are the values of <tt>(p1 1)</tt> and <tt>(p2 1)</tt> with the
original <tt>eval-sequence</tt>?
What would the values be with Cy's proposed change to <tt>eval-sequence</tt>?<p>
<p><p>c. Cy also points out that changing <tt>eval-sequence</tt> as he proposes
does not affect the behavior of the example in part a.
Explain why this is true.<p>
<p><p>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?
<p><p>
<p><a name="%_thm_4.31"></a>
<b>Exercise 4.31.</b> <a name="%_idx_4752"></a>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 <em>upward-compatible extension</em>,
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
<p><tt>(define (f a (b lazy) c (d lazy-memo))<br>
<tt>...</tt>)<br>
</tt><p>
would define <tt>f</tt> 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 <tt>lazy-memo</tt> 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 <tt>define</tt>. You must also arrange for
<tt>eval</tt> or <tt>apply</tt> 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.
<p><p>
<a name="%_sec_4.2.3"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.3">4.2.3 Streams as Lazy Lists</a></h3><p>
<a name="%_idx_4754"></a><a name="%_idx_4756"></a><a name="%_idx_4758"></a><a name="%_idx_4760"></a><a name="%_idx_4762"></a>
<a name="%_idx_4764"></a><a name="%_idx_4766"></a><a name="%_idx_4768"></a><a name="%_idx_4770"></a>In section <a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a>, we showed how to implement streams
as delayed lists. We introduced special forms <tt>delay</tt> and <tt>cons-stream</tt>, which allowed us to construct a ``promise'' to compute
the <tt>cdr</tt> 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.<a name="call_footnote_Temp_499" href="#footnote_Temp_499"><sup><small>39</small></sup></a> 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 (<tt>map</tt>, <tt>append</tt>, and
so on) for use with streams.<p>
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 <tt>cons</tt> is
non-strict. One way to accomplish this is to extend the lazy
evaluator to allow for non-strict primitives, and to implement <tt>cons</tt> as one of these. An easier way is to recall
(section <a href="book-Z-H-14.html#%_sec_2.1.3">2.1.3</a>) that there is no fundamental need to
implement <tt>cons</tt> as a primitive at all. Instead, we can represent
<a name="%_idx_4772"></a>pairs as procedures:<a name="call_footnote_Temp_500" href="#footnote_Temp_500"><sup><small>40</small></sup></a><p>
<p><tt><a name="%_idx_4774"></a>(define (cons x y)<br>
(lambda (m) (m x y)))<br>
<br>
<a name="%_idx_4776"></a>(define (car z)<br>
(z (lambda (p q) p)))<br>
<br>
<a name="%_idx_4778"></a>(define (cdr z)<br>
(z (lambda (p q) q)))<br>
</tt><p><p>
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:<p>
<p><tt><a name="%_idx_4780"></a>(define (list-ref items n)<br>
(if (= n 0)<br>
(car items)<br>
(list-ref (cdr items) (- n 1))))<br>
<br>
<a name="%_idx_4782"></a>(define (map proc items)<br>
(if (null? items)<br>
'()<br>
(cons (proc (car items))<br>
(map proc (cdr items)))))<br>
<br>
<a name="%_idx_4784"></a>(define (scale-list items factor)<br>
(map (lambda (x) (* x factor))<br>
items))<br>
<br>
<a name="%_idx_4786"></a>(define (add-lists list1 list2)<br>
(cond ((null? list1) list2)<br>
((null? list2) list1)<br>
(else (cons (+ (car list1) (car list2))<br>
(add-lists (cdr list1) (cdr list2))))))<br>
<br>
<a name="%_idx_4788"></a>(define ones (cons 1 ones))<br>
<br>
<a name="%_idx_4790"></a>(define integers (cons 1 (add-lists ones integers)))<br>
<br>
<i>;;; L-Eval input:</i><br>
(list-ref integers 17)<br>
<i>;;; L-Eval value:</i><br>
<i>18</i><br>
</tt><p><p>
Note that these lazy lists are even lazier than the streams of
chapter 3: The <tt>car</tt> of the list, as well as the <tt>cdr</tt>, is
delayed.<a name="call_footnote_Temp_501" href="#footnote_Temp_501"><sup><small>41</small></sup></a>
In fact, even accessing the <tt>car</tt> or <tt>cdr</tt> 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.<p>
Lazy pairs also help with the problem that arose with streams in
section <a href="book-Z-H-24.html#%_sec_3.5.4">3.5.4</a>, where we found that
formulating stream models of systems with loops may require us to
sprinkle our programs with <a name="%_idx_4798"></a><a name="%_idx_4800"></a>explicit <tt>delay</tt> operations, beyond the
ones supplied by <tt>cons-stream</tt>. 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 <a href="book-Z-H-24.html#%_sec_3.5.4">3.5.4</a>:<p>
<p><tt><a name="%_idx_4802"></a>(define (integral integrand initial-value dt)<br>
(define int<br>
(cons initial-value<br>
(add-lists (scale-list integrand dt)<br>
int)))<br>
int)<br>
<br>
<a name="%_idx_4804"></a>(define (solve f y0 dt)<br>
(define y (integral dy y0 dt))<br>
(define dy (map f y))<br>
y)<br>
<br>
<i>;;; L-Eval input:</i><br>
(list-ref (solve (lambda (x) x) 1 0.001) 1000)<br>
<i>;;; L-Eval value:</i><br>
<i>2.716924</i></tt><p><p>
<p><a name="%_thm_4.32"></a>
<b>Exercise 4.32.</b> 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?
<p><p>
<p><a name="%_thm_4.33"></a>
<b>Exercise 4.33.</b> Ben Bitdiddle tests the lazy list implementation given above by
evaluating the expression
<p><tt>(car '(a b c))<br>
</tt><p>
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
<tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt>. Modify the evaluator's
treatment of quoted expressions so that quoted lists typed at the
driver loop will produce true lazy lists.
<p><p>
<p><a name="%_thm_4.34"></a>
<b>Exercise 4.34.</b> 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.
<p><p>
<p><div class=smallprint><hr></div><p>
<div class=footnote><p><a name="footnote_Temp_484" href="#call_footnote_Temp_484"><sup><small>31</small></sup></a> Snarf: ``To grab, especially a large document or
<a name="%_idx_4674"></a><a name="%_idx_4676"></a><a name="%_idx_4678"></a>file for the purpose of using it either with or without the owner's
permission.'' Snarf down: ``To snarf, sometimes with the connotation
of absorbing, processing, or understanding.'' (These definitions were
snarfed from Steele et al. 1983. See also Raymond 1993.)
<p><a name="footnote_Temp_485" href="#call_footnote_Temp_485"><sup><small>32</small></sup></a> The difference between the ``lazy'' terminology and
the ``normal-order'' terminology is somewhat fuzzy. Generally, ``lazy''
refers to the mechanisms of particular evaluators, while ``normal-order''
refers to the semantics of languages, independent of any particular
evaluation strategy. But this is not a hard-and-fast distinction, and
the two terminologies are often used interchangeably.
<p><a name="footnote_Temp_486" href="#call_footnote_Temp_486"><sup><small>33</small></sup></a> The ``strict'' versus ``non-strict'' terminology means essentially the
same thing as ``applicative-order'' versus ``normal-order,'' except that
it refers to individual procedures and arguments rather than to the
language as a whole. At a conference on programming languages you
might hear someone say, ``The normal-order language <a name="%_idx_4690"></a>Hassle has certain
strict primitives. Other procedures take their arguments by lazy
evaluation.''
<p><a name="footnote_Temp_489" href="#call_footnote_Temp_489"><sup><small>34</small></sup></a> The word <em>thunk</em> was invented by an informal
<a name="%_idx_4698"></a><a name="%_idx_4700"></a><a name="%_idx_4702"></a>working group that was discussing the implementation of call-by-name
in Algol 60. They observed that most of the analysis of (``thinking
about'') the expression could be done at compile time; thus, at run
time, the expression would already have been ``thunk'' about (Ingerman
et al. 1960).
<p><a name="footnote_Temp_490" href="#call_footnote_Temp_490"><sup><small>35</small></sup></a> This is analogous to the use of <tt>force</tt>
<a name="%_idx_4708"></a>on the delayed objects that were introduced in chapter 3 to represent
streams. The critical difference between what we are
doing here and what we did in chapter 3 is that we are building
delaying and forcing into the evaluator, and thus making this uniform
and automatic throughout the language.
<p><a name="footnote_Temp_491" href="#call_footnote_Temp_491"><sup><small>36</small></sup></a> Lazy evaluation combined with memoization is sometimes
<a name="%_idx_4712"></a>referred to as <em>call-by-need</em> argument passing, in contrast to
<em>call-by-name</em> argument passing. <a name="%_idx_4714"></a><a name="%_idx_4716"></a>(Call-by-name, introduced in
Algol 60, is similar to non-memoized lazy evaluation.)
As language designers, we can build our evaluator to memoize,
not to memoize, or leave this an option for programmers
(exercise <a href="#%_thm_4.31">4.31</a>). As you might expect
from chapter 3, these choices raise issues that become both subtle and
confusing in the presence of assignments. (See
exercises <a href="#%_thm_4.27">4.27</a> and <a href="#%_thm_4.29">4.29</a>.)
<a name="%_idx_4718"></a>An excellent article by Clinger (1982) attempts to clarify the
multiple dimensions of confusion that arise here.
<p><a name="footnote_Temp_492" href="#call_footnote_Temp_492"><sup><small>37</small></sup></a> Notice that we also erase the <tt>env</tt> from the thunk once the
expression's value has been computed. This makes no difference in the
values returned by the interpreter. It does help save space,
however, because removing the reference from the thunk to the <tt>env</tt>
once it is no longer needed allows this structure to be
<a name="%_idx_4744"></a><a name="%_idx_4746"></a><em>garbage-collected</em> and its
space recycled, as we will discuss in section <a href="book-Z-H-33.html#%_sec_5.3">5.3</a>.<p>
Similarly, we could have allowed unneeded environments in the memoized
delayed objects of section <a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a> to be garbage-collected,
by having <tt>memo-proc</tt> do something like <tt>(set! proc '())</tt>
to discard the procedure <tt>proc</tt> (which includes the environment
in which the <tt>delay</tt> was evaluated) after storing its value.
<p><a name="footnote_Temp_494" href="#call_footnote_Temp_494"><sup><small>38</small></sup></a> This exercise
demonstrates that the interaction between lazy evaluation and side
effects can be very confusing. This is just what you might expect
from the discussion in chapter 3.
<p><a name="footnote_Temp_499" href="#call_footnote_Temp_499"><sup><small>39</small></sup></a> This is precisely the issue with the <tt>unless</tt> procedure,
as in exercise <a href="#%_thm_4.26">4.26</a>.
<p><a name="footnote_Temp_500" href="#call_footnote_Temp_500"><sup><small>40</small></sup></a> This is the procedural representation described in
exercise <a href="book-Z-H-14.html#%_thm_2.4">2.4</a>. Essentially any procedural representation
(e.g., a message-passing implementation) would do as well. Notice
that we can install these definitions in the lazy evaluator simply by
typing them at the driver loop. If we had originally included <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt> as primitives in the global
environment, they will be redefined. (Also see
exercises <a href="#%_thm_4.33">4.33</a> and <a href="#%_thm_4.34">4.34</a>.)
<p><a name="footnote_Temp_501" href="#call_footnote_Temp_501"><sup><small>41</small></sup></a> This permits us to create delayed versions of more general kinds of
<a name="%_idx_4792"></a>list structures, not just sequences. Hughes 1990 discusses some
<a name="%_idx_4794"></a><a name="%_idx_4796"></a>applications of ``lazy trees.''
</div>
<p><div class=navigation>[Go to <a href="book.html">first</a>,
<a href="book-Z-H-26.html">previous</a>,
<a href="book-Z-H-28.html">next</a> page; <a href="book-Z-H-4.html#%_toc_start">contents</a>; <a href="book-Z-H-38.html#%_index_start">index</a>]</div><p>
</body>
</html>