forked from ldct/isicp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
4-2-lazy.html
679 lines (525 loc) · 32.4 KB
/
4-2-lazy.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
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<meta charset="UTF-8">
<link rel="stylesheet" type="text/css" href="web-worker-interpreter/deps/codemirror/lib/codemirror.css" />
<link rel="stylesheet" type="text/css" href="css/isicp.css" />
<link rel="stylesheet" type="text/css" href="css/footnotes.css" />
<link rel="stylesheet" type="text/css" href="css/theme.css" />
<script src="js/helper.js"></script>
<script src="js/jquery.min.js"></script>
<script src="web-worker-interpreter/deps/codemirror/lib/codemirror.js"></script>
<script src="web-worker-interpreter/deps/codemirror/mode/scheme/scheme.js"></script>
<script src="web-worker-interpreter/coding.js"> </script>
<script>
set_interpreter_path("web-worker-interpreter/");
set_language("scheme");
</script>
<script src="js/footnotes.js"></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$']]}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<title> iSICP 2.4 - Multiple Representations for Abstract Data </title>
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-36868476-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
</head>
<body>
<div id="sidebox">
<div class="tab"></div>
<div class="content">
<p>
<a href="index.html" class="navlink"> <img src='images/home.svg' width=32 height=32> </a>
<span id="toc-link" class="navlink"> <img src='images/list.svg' width=32 height=32> </span>
<span id="currently-editing-link" class="navlink"> <img src='images/file-edit.svg' width=32 height=32> </span>
<script src="http://cdn.jotfor.ms/static/feedback2.js?3.2.310" type="text/javascript">
new JotformFeedback({
formId:'40222623177447',
base:'http://jotform.me/',
windowTitle:'Notify Me',
background:'#FFA500',
fontColor:'#FFFFFF',
type:false,
height:500,
width:700
});
</script>
<a class="lightbox-40222623177447" style="cursor:pointer;color:blue;text-decoration:underline;"><img src='images/envelope.svg' width=32 height=32></a>
<p>
<div id="currently-editing"> </div>
<script>
function hideAll() {
$("#currently-editing").hide();
$("#toc").hide();
}
$("#currently-editing-link").click(function() {
hideAll();
$("#currently-editing").show();
});
$("#toc-link").click(function() {
hideAll();
$("#toc").show();
});
</script>
<div id="toc"> </div>
<p style='font-size:12px'> (Click on the left edge of this green box to hide it!)
<script>
hideAll();
$("#toc").show();
</script>
</div>
</div>
<script>
$('#sidebox .tab').toggle(function(){
$('#sidebox').animate({'right':'0%'});
}, function(){
$('#sidebox').animate({'right':'-30%'});
});
$(document).ready(createTOC);
</script>
<div id="main">
<h2> Variations on a Scheme – Lazy Evaluation </h2>
<p> 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@footnote{Snarf: ``To grab, especially a large document or 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.)} 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.
@menu
* 4-2-1:: Normal Order and Applicative Order
* 4-2-2:: An Interpreter with Lazy Evaluation
* 4-2-3:: Streams as Lazy Lists
@end menu
<h3> Normal Order and Applicative Order </h3>
<p> In section 1-1, where we began our discussion of models of evaluation, we noted that Scheme is an <tt>applicative-order</tt> language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, <tt>normal-order</tt> 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 <tt>lazy evaluation</tt> .@footnote{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.} Consider the procedure
<div id="">
(define (try a b)
(if (= a 0) 1 b))
</div>
<script>
prompt();
</script>
<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>
<div id="">
(define (unless condition usual-value exceptional-value)
(if condition exceptional-value usual-value))
</div>
<script>
prompt();
</script>
<p> that can be used in expressions such as
<div id="">
(unless (= b 0)
(/ a b)
(begin (display "exception: returning 0")
0))
</div>
<script>
prompt();
</script>
<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 1-6). 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 <tt>non-strict</tt> in that argument. If the argument is evaluated before the body of the procedure is entered we say that the procedure is <tt>strict</tt> in that argument.@footnote{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 Hassle has certain strict primitives. Other procedures take their arguments by lazy evaluation.''} 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.
<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 4-2-3 to implement the streams of Chapter 3 as lists formed of non-strict <tt>cons</tt> pairs.
<div class="exercise">
<p> <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
<div id="">
(define (factorial n)
(unless (= n 1)
(* n (factorial (- n 1)))
1))
</div>
<script>
prompt();
</script>
<p> What happens if we attempt to evaluate <tt>(factorial 5)</tt>? Will our definitions work in a normal-order language?
</div>
<div class="exercise">
<p> <b>Exercise 4.26:</b> 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.
</div>
<h3> An Interpreter with Lazy Evaluation </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 4-1-1 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 <tt>thunks</tt> .@footnote{The word <tt>thunk</tt> was invented by an informal 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).} 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> The process of evaluating the expression in a thunk is called <tt>forcing</tt> .@footnote{This is analogous to the use of <tt>force</tt> 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.} 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 <tt>memoize</tt> 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.@footnote{Lazy evaluation combined with memoization is sometimes referred to as <tt>call-by-need</tt>
<p> argument passing, in contrast to <tt>call-by-name</tt> argument passing. (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 4-31). As you might expect from Chapter 3, these choices raise issues that become both subtle and confusing in the presence of assignments. (See Exercise 4-27 and Exercise 4-29.) An excellent article by Clinger (1982) attempts to clarify the multiple dimensions of confusion that arise here.}
<h4> Modifying the evaluator </h4>
<p> The main difference between the lazy evaluator and the one in section 4-1 is in the handling of procedure applications in <tt>eval</tt> and <tt>apply</tt>.
<p> The <tt>application?</tt> clause of <tt>eval</tt> becomes
<div id="">
((application? exp)
(apply (actual-value (operator exp) env)
(operands exp)
env))
</div>
<script>
prompt();
</script>
<p> This is almost the same as the <tt>application?</tt> clause of <tt>eval</tt> in section 4-1-1. 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
<div id="">
(define (actual-value exp env)
(force-it (eval exp env)))
</div>
<script>
prompt();
</script>
<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 4-1-1. 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.
<div id="">
(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))))
</div>
<script>
prompt();
</script>
<p> The procedures that process the arguments are just like <tt>list-of-values</tt> from section 4-1-1, 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>:
<div id="">
(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))))
</div>
<script>
prompt();
</script>
<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:
<div id="">
(define (eval-if exp env)
(if (true? (actual-value (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))
</div>
<script>
prompt();
</script>
<p> Finally, we must change the <tt>driver-loop</tt> procedure (section 4-1-4) 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:
<div id="">
(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))
</div>
<script>
prompt();
</script>
<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 4-2-1 indicates that the interpreter is performing lazy evaluation:
<div id="">
(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
</div>
<script>
prompt();
</script>
<h4> Representing thunks </h4>
<p> 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:
<div id="">
(define (force-it obj)
(if (thunk? obj)
(actual-value (thunk-exp obj) (thunk-env obj))
obj))
</div>
<script>
prompt();
</script>
<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:
<div id="">
(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))
</div>
<script>
prompt();
</script>
<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.@footnote{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 <tt>garbage-collected</tt> and its space recycled, as we will discuss in section 5-3.
<p> Similarly, we could have allowed unneeded environments in the memoized delayed objects of section 3-5-1 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.}
<div id="">
(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 <tt>exp</tt> with its value
(set-cdr! (cdr obj) '()) ; forget unneeded <tt>env</tt>
result))
((evaluated-thunk? obj)
(thunk-value obj))
(else obj)))
</div>
<script>
prompt();
</script>
<p> Notice that the same <tt>delay-it</tt> procedure works both with and without memoization.
<div class="exercise">
<b>Exercise 4.27:</b> Suppose we type in the following
definitions to the lazy evaluator:
<div id="">
(define count 0)
(define (id x)
(set! count (+ count 1))
x)
</div>
<script>
prompt();
</script>
<p> Give the missing values in the following sequence of interactions, and explain your answers.@footnote{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.}
<div id="">
(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>
</div>
<script>
prompt();
</script>
</div>
<div class="exercise">
<p> <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> <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 4-27 and <tt>count</tt> starts at 0:
<div id="">
(define (square x)
(* x x))
;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
<response>
;;; L-Eval input:
count
;;; L-Eval value:
<response>
</div>
<script>
prompt();
</script>
<p> Give the responses both when the evaluator memoizes and when it does not.
</div>
<div class="exercise">
<p> <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 4-1-1 to use <tt>actual-value</tt> rather than <tt>eval</tt>:
<div id="">
(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))))
</div>
<script>
prompt();
</script>
<ul>
@item
Ben Bitdiddle thinks Cy is wrong. He shows Cy the <tt>for-each</tt> procedure
described in Exercise 2-23, which gives an important example of a
sequence with side effects:
<div id="">
(define (for-each proc items)
(if (null? items)
'done
(begin (proc (car items))
(for-each proc (cdr items)))))
</div>
<script>
prompt();
</script>
He claims that the evaluator in the text (with the original
<tt>eval-sequence</tt>) handles this correctly:
<div id="">
;;; L-Eval input:
(for-each (lambda (x) (newline) (display x))
(list 57 321 88))
57
321
88
;;; L-Eval value:
done
</div>
<script>
prompt();
</script>
Explain why Ben is right about the behavior of <tt>for-each</tt>.
@item
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:
<div id="">
(define (p1 x)
(set! x (cons x '(2)))
x)
(define (p2 x)
(define (p e)
e
x)
(p (set! x (cons x '(2)))))
</div>
<script>
prompt();
</script>
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>?
@item
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.
@item
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?
</ul>
</div>
<div class="exercise">
<p> <b>Exercise 4.31:</b> 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 <tt>upward-compatible extension</tt> , 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
<div id="">
(define (f a (b lazy) c (d lazy-memo))
...)
</div>
<script>
prompt();
</script>
<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.
</div>
<h3> Streams as Lazy Lists </h3>
<p> In section 3-5-1, 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.@footnote{This is precisely the issue with the <tt>unless</tt> procedure, as in Exercise 4-26.} 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 2-1-3) that there is no fundamental need to implement <tt>cons</tt> as a primitive at all. Instead, we can represent pairs as procedures:@footnote{This is the procedural representation described in Exercise 2-4. 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 Exercise 4-33 and Exercise 4-34.)}
<div id="">
(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)))
</div>
<script>
prompt();
</script>
<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:
<div id="">
(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
</div>
<script>
prompt();
</script>
<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.@footnote{This permits us to create delayed versions of more general kinds of list structures, not just sequences. Hughes 1990 discusses some applications of ``lazy trees.''} 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 3-5-4, where we found that formulating stream models of systems with loops may require us to sprinkle our programs with 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 3-5-4:
<div id="">
(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
</div>
<script>
prompt();
</script>
<div class="exercise">
<p> <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?
</div>
<div class="exercise">
<p> <b>Exercise 4.33:</b> Ben Bitdiddle tests the lazy list implementation given above by evaluating the expression
<div id="">
(car '(a b c))
</div>
<script>
prompt();
</script>
<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.
</div>
<div class="exercise">
<p> <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.
</div>
<br>
<br>
<hr>
<div id="footnotes">
<h3 id='Notes'> Notes </h3>
</div>
<hr>
<p> <a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/deed.en_US" target="_blank"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-sa/3.0/88x31.png" /></a><br /> Based on Structure and Interpretation of Computer Programs, a work at <a xmlns:dct="http://purl.org/dc/terms/" href="http://mitpress.mit.edu/sicp/" rel="dct:source" target="_blank">http://mitpress.mit.edu/sicp/</a>.
</div>
<a href="https://github.com/zodiac/isicp" target="_blank"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_green_007200.png" alt="Fork me on GitHub"></a>
</body>
</html>