forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-24.html
2654 lines (2106 loc) · 133 KB
/
book-Z-H-24.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
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http:https://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http:https://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta name="generator" content="HTML Tidy for Linux (vers 7 December 2008), see www.w3.org" />
<title>Structure and Interpretation of Computer Programs</title>
<link href="book-Z-C.css" title="default" rel="stylesheet" type="text/css" />
<meta name="robots" content="noindex,follow" />
</head>
<body>
<mbp:pagebreak />
<p><a name="%_sec_3.5"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.5">3.5 Streams</a></h2>
<p><a name="%_idx_3726"></a> We've gained a good understanding of
assignment as a tool in modeling, as well as an appreciation of
the complex problems that assignment raises. It is time to ask
whether we could have gone about things in a different way, so as
to avoid some of these problems. In this section, we explore an
alternative approach to modeling state, based on data structures
called <em>streams</em>. As we shall see, streams can mitigate
some of the complexity of modeling state.</p>
<p>Let's step back and review where this complexity comes from.
In an attempt to model real-world phenomena, we made some
apparently reasonable decisions: We modeled real-world objects
with local state by computational objects with local variables.
We identified time variation in the real world with time
variation in the computer. We implemented the time variation of
the states of the model objects in the computer with assignments
to the local variables of the model objects.</p>
<p>Is there another approach? Can we avoid identifying time in
the computer with time in the modeled world? Must we make the
model change with time in order to model phenomena in a changing
world? Think about the issue in terms of mathematical functions.
We can describe the time-varying behavior of a quantity
<em>x</em> as a function of time <em>x</em>(<em>t</em>). If we
concentrate on <em>x</em> instant by instant, we think of it as a
changing quantity. Yet if we concentrate on the entire time
history of values, we do not emphasize change -- the function
itself does not change.<a href="#footnote_Temp_442" name="call_footnote_Temp_442" id="call_footnote_Temp_442"><sup><small>52</small></sup></a></p>
<p>If time is measured in discrete steps, then we can model a
time function as a (possibly infinite) sequence. In this section,
we will see how to model change in terms of sequences that
represent the time histories of the systems being modeled. To
accomplish this, we introduce new data structures called
<em>streams</em>. From an abstract point of view, a stream is
simply a sequence. However, we will find that the straightforward
implementation of streams as lists (as in section <a href="book-Z-H-15.html#%_sec_2.2.1">2.2.1</a>) doesn't fully reveal
the power of stream processing. As an alternative, we introduce
the technique of <a name="%_idx_3730"></a><em>delayed
evaluation</em>, which enables us to represent very large (even
infinite) sequences as streams.</p>
<p>Stream processing lets us model systems that have state
without ever using assignment or mutable data. This has important
implications, both theoretical and practical, because we can
build models that avoid the drawbacks inherent in introducing
assignment. On the other hand, the stream framework raises
difficulties of its own, and the question of which modeling
technique leads to more modular and more easily maintained
systems remains open.</p>
<p><a name="%_sec_3.5.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.5.1">3.5.1 Streams Are
Delayed Lists</a></h3>
<p><a name="%_idx_3732"></a> As we saw in section <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>, sequences can serve as
standard interfaces for combining program modules. We formulated
powerful abstractions for manipulating sequences, such as
<tt>map</tt>, <tt>filter</tt>, and <tt>accumulate</tt>, that
capture a wide variety of operations in a manner that is both
succinct and elegant.</p>
<p>Unfortunately, if we represent sequences as lists, this
elegance is bought at the price of severe inefficiency with
respect to both the time and space required by our computations.
When we represent manipulations on sequences as transformations
of lists, our programs must construct and copy data structures
(which may be huge) at every step of a process.</p>
<p>To see why this is true, let us compare two programs for
computing the sum of all the prime numbers in an interval. The
first program is written in standard iterative style:<a href="#footnote_Temp_443" name="call_footnote_Temp_443" id="call_footnote_Temp_443"><sup><small>53</small></sup></a></p>
<p><tt><a name="%_idx_3734"></a>(define (sum-primes a b)<br />
(define (iter count accum)<br />
(cond ((> count b) accum)<br />
((prime? count) (iter (+ count 1) (+ count accum)))<br />
(else (iter (+ count 1) accum))))<br />
(iter a 0))<br /></tt></p>
<p>The second program performs the same computation using the
sequence operations of section <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>:</p>
<p><tt><a name="%_idx_3736"></a>(define (sum-primes a b)<br />
(accumulate +<br />
0<br />
(filter prime? (enumerate-interval a b))))<br />
</tt></p>
<p>In carrying out the computation, the first program needs to
store only the sum being accumulated. In contrast, the filter in
the second program cannot do any testing until
<tt>enumerate-interval</tt> has constructed a complete list of
the numbers in the interval. The filter generates another list,
which in turn is passed to <tt>accumulate</tt> before being
collapsed to form a sum. Such large intermediate storage is not
needed by the first program, which we can think of as enumerating
the interval incrementally, adding each prime to the sum as it is
generated.</p>
<p>The inefficiency in using lists becomes painfully apparent if
we use the sequence paradigm to compute the second prime in the
interval from 10,000 to 1,000,000 by evaluating the
expression</p>
<p><tt>(car (cdr (filter prime?<br />
(enumerate-interval 10000 1000000))))<br />
</tt></p>
<p>This expression does find the second prime, but the
computational overhead is outrageous. We construct a list of
almost a million integers, filter this list by testing each
element for primality, and then ignore almost all of the result.
In a more traditional programming style, we would interleave the
enumeration and the filtering, and stop when we reached the
second prime.</p>
<p>Streams are a clever idea that allows one to use sequence
manipulations without incurring the costs of manipulating
sequences as lists. With streams we can achieve the best of both
worlds: We can formulate programs elegantly as sequence
manipulations, while attaining the efficiency of incremental
computation. The basic idea is to arrange to construct a stream
only partially, and to pass the partial construction to the
program that consumes the stream. If the consumer attempts to
access a part of the stream that has not yet been constructed,
the stream will automatically construct just enough more of
itself to produce the required part, thus preserving the illusion
that the entire stream exists. In other words, although we will
write programs as if we were processing complete sequences, we
design our stream implementation to automatically and
transparently interleave the construction of the stream with its
use.</p>
<p>On the surface, streams are just lists with different names
for the procedures that manipulate them. There is a constructor,
<a name="%_idx_3738"></a><tt>cons-stream</tt>, and two selectors,
<a name="%_idx_3740"></a><tt>stream-car</tt> and <a name="%_idx_3742"></a><tt>stream-cdr</tt>, which satisfy the
constraints</p>
<div align="left"><img src="ch3-Z-G-34.gif" border="0" /></div>
<p>There is a distinguishable object, <a name="%_idx_3744"></a><a name="%_idx_3746"></a><a name="%_idx_3748"></a><tt>the-empty-stream</tt>, which cannot be the
result of any <tt>cons-stream</tt> operation, and which can be
identified with the predicate <a name="%_idx_3750"></a><tt>stream-null?</tt>.<a href="#footnote_Temp_444" name="call_footnote_Temp_444" id="call_footnote_Temp_444"><sup><small>54</small></sup></a> Thus we
can make and use streams, in just the same way as we can make and
use lists, to represent aggregate data arranged in a sequence. In
particular, we can build stream analogs of the list operations
from chapter 2, such as <tt>list-ref</tt>, <tt>map</tt>, and
<tt>for-each</tt>:<a href="#footnote_Temp_445" name="call_footnote_Temp_445" id="call_footnote_Temp_445"><sup><small>55</small></sup></a></p>
<p><tt><a name="%_idx_3758"></a>(define (stream-ref s n)<br />
(if (= n 0)<br />
(stream-car s)<br />
(stream-ref (stream-cdr s) (- n 1))))<br />
<a name="%_idx_3760"></a>(define (stream-map proc s)<br />
(if (stream-null? s)<br />
the-empty-stream<br />
(cons-stream (proc (stream-car s))<br />
(stream-map proc (stream-cdr s)))))<br />
<a name="%_idx_3762"></a>(define (stream-for-each proc s)<br />
(if (stream-null? s)<br />
'done<br />
(begin (proc (stream-car s))<br />
(stream-for-each proc (stream-cdr s)))))<br />
</tt></p>
<p><tt>Stream-for-each</tt> is useful for viewing streams:</p>
<p><tt><a name="%_idx_3764"></a>(define (display-stream s)<br />
(stream-for-each display-line s))<br />
<br />
<a name="%_idx_3766"></a>(define (display-line x)<br />
(newline)<br />
(display x))<br /></tt></p>
<p>To make the stream implementation automatically and
transparently interleave the construction of a stream with its
use, we will arrange for the <tt>cdr</tt> of a stream to be
evaluated when it is accessed by the <tt>stream-cdr</tt>
procedure rather than when the stream is constructed by
<tt>cons-stream</tt>. This implementation choice is reminiscent
of our discussion of rational numbers in section <a href="book-Z-H-14.html#%_sec_2.1.2">2.1.2</a>, where we saw that we
can choose to implement rational numbers so that the reduction of
numerator and denominator to lowest terms is performed either at
construction time or at selection time. The two rational-number
implementations produce the same data abstraction, but the choice
has an effect on efficiency. There is a similar relationship
between streams and ordinary lists. As a data abstraction,
streams are the same as lists. The difference is the time at
which the elements are evaluated. With ordinary lists, both the
<tt>car</tt> and the <tt>cdr</tt> are evaluated at construction
time. With streams, the <tt>cdr</tt> is evaluated at selection
time.</p>
<p><a name="%_idx_3768"></a><a name="%_idx_3770"></a>Our
implementation of streams will be based on a special form called
<tt>delay</tt>. Evaluating <tt>(delay <<em>exp</em>>)</tt>
does not evaluate the expression <<em>exp</em>>, but rather
returns a so-called <a name="%_idx_3772"></a><em>delayed
object</em>, which we can think of as a ``promise'' to evaluate
<<em>exp</em>> at some future time. As a companion to
<tt>delay</tt>, there is a procedure called <a name="%_idx_3774"></a><tt>force</tt> that takes a delayed object as
argument and performs the evaluation -- in effect, forcing the
<tt>delay</tt> to fulfill its promise. We will see below how
<tt>delay</tt> and <tt>force</tt> can be implemented, but first
let us use these to construct streams.</p>
<p><a name="%_idx_3776"></a><a name="%_idx_3778"></a><tt>Cons-stream</tt> is a special form defined
so that</p>
<p>
<tt>(cons-stream <<em>a</em>> <<em>b</em>>)<br />
</tt></p>
<p>is equivalent to</p>
<p>
<tt>(cons <<em>a</em>> (delay <<em>b</em>>))<br />
</tt></p>
<p>What this means is that we will construct streams using pairs.
However, rather than placing the value of the rest of the stream
into the <tt>cdr</tt> of the pair we will put there a promise to
compute the rest if it is ever requested. <tt>Stream-car</tt> and
<tt>stream-cdr</tt> can now be defined as procedures:</p>
<p><tt><a name="%_idx_3780"></a>(define (stream-car stream) (car stream))<br />
<br />
<a name="%_idx_3782"></a>(define (stream-cdr stream) (force (cdr stream)))<br />
</tt></p>
<p><tt>Stream-car</tt> selects the <tt>car</tt> of the pair;
<tt>stream-cdr</tt> selects the <tt>cdr</tt> of the pair and
evaluates the delayed expression found there to obtain the rest
of the stream.<a href="#footnote_Temp_446" name="call_footnote_Temp_446" id="call_footnote_Temp_446"><sup><small>56</small></sup></a>
<a name="%_sec_Temp_447"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_447">The stream
implementation in action</a></h4>
<p>To see how this implementation behaves, let us analyze the
``outrageous'' prime computation we saw above, reformulated in
terms of streams:</p>
<p><tt>(stream-car<br />
(stream-cdr<br />
(stream-filter prime?<br />
(stream-enumerate-interval 10000 1000000))))<br />
</tt></p>
<p>We will see that it does indeed work efficiently.</p>
<p>We begin by calling <tt>stream-enumerate-interval</tt> with
the arguments 10,000 and 1,000,000.
<tt>Stream-enumerate-interval</tt> is the stream analog of
<tt>enumerate-interval</tt> (section <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>):</p>
<p><tt><a name="%_idx_3788"></a>(define (stream-enumerate-interval low high)<br />
(if (> low high)<br />
the-empty-stream<br />
(cons-stream<br />
low<br />
(stream-enumerate-interval (+ low 1) high))))<br />
</tt></p>
<p>and thus the result returned by
<tt>stream-enumerate-interval</tt>, formed by the
<tt>cons-stream</tt>, is<a href="#footnote_Temp_448" name="call_footnote_Temp_448" id="call_footnote_Temp_448"><sup><small>57</small></sup></a></p>
<p><tt>(cons 10000<br />
(delay (stream-enumerate-interval 10001 1000000)))<br />
</tt></p>
<p>That is, <tt>stream-enumerate-interval</tt> returns a stream
represented as a pair whose <tt>car</tt> is 10,000 and whose
<tt>cdr</tt> is a promise to enumerate more of the interval if so
requested. This stream is now filtered for primes, using the
stream analog of the <tt>filter</tt> procedure
(section <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>):</p>
<p><tt><a name="%_idx_3790"></a>(define (stream-filter pred stream)<br />
(cond ((stream-null? stream) the-empty-stream)<br />
((pred (stream-car stream))<br />
(cons-stream (stream-car stream)<br />
(stream-filter pred<br />
(stream-cdr stream))))<br />
(else (stream-filter pred (stream-cdr stream)))))<br />
</tt></p>
<p><tt>Stream-filter</tt> tests the <tt>stream-car</tt> of the
stream (the <tt>car</tt> of the pair, which is 10,000). Since
this is not prime, <tt>stream-filter</tt> examines the
<tt>stream-cdr</tt> of its input stream. The call to
<tt>stream-cdr</tt> forces evaluation of the delayed
<tt>stream-enumerate-interval</tt>, which now returns</p>
<p><tt>(cons 10001<br />
(delay (stream-enumerate-interval 10002 1000000)))<br />
</tt></p>
<p><tt>Stream-filter</tt> now looks at the <tt>stream-car</tt> of
this stream, 10,001, sees that this is not prime either, forces
another <tt>stream-cdr</tt>, and so on, until
<tt>stream-enumerate-interval</tt> yields the prime 10,007,
whereupon <tt>stream-filter</tt>, according to its definition,
returns</p>
<p><tt>(cons-stream (stream-car stream)<br />
(stream-filter pred (stream-cdr stream)))<br />
</tt></p>
<p>which in this case is</p>
<p><tt>(cons 10007<br />
(delay<br />
(stream-filter<br />
prime?<br />
(cons 10008<br />
(delay<br />
(stream-enumerate-interval 10009<br />
1000000))))))<br />
</tt></p>
<p>This result is now passed to <tt>stream-cdr</tt> in our
original expression. This forces the delayed
<tt>stream-filter</tt>, which in turn keeps forcing the delayed
<tt>stream-enumerate-interval</tt> until it finds the next prime,
which is 10,009. Finally, the result passed to
<tt>stream-car</tt> in our original expression is</p>
<p><tt>(cons 10009<br />
(delay<br />
(stream-filter<br />
prime?<br />
(cons 10010<br />
(delay<br />
(stream-enumerate-interval 10011<br />
1000000))))))<br />
</tt></p>
<p><tt>Stream-car</tt> returns 10,009, and the computation is
complete. Only as many integers were tested for primality as were
necessary to find the second prime, and the interval was
enumerated only as far as was necessary to feed the prime
filter.</p>
<p>In general, we can think of delayed evaluation as <a name="%_idx_3792"></a>``demand-driven'' programming, whereby each
stage in the stream process is activated only enough to satisfy
the next stage. What we have done is to <a name="%_idx_3794"></a>decouple the actual order of events in the
computation from the apparent structure of our procedures. We
write procedures as if the streams existed ``all at once'' when,
in reality, the computation is performed incrementally, as in
traditional programming styles.</p>
<p><a name="%_sec_Temp_449"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_449">Implementing
<tt>delay</tt> and <tt>force</tt></a></h4>
<p><a name="%_idx_3796"></a>Although <tt>delay</tt> and
<tt>force</tt> may seem like mysterious operations, their
implementation is really quite straightforward. <tt>Delay</tt>
must package an expression so that it can be evaluated later on
demand, and we can accomplish this simply by treating the
expression as the body of a procedure. <tt>Delay</tt> can be a
special form such that</p>
<p><tt>(delay <<em>exp</em>>)<br /></tt></p>
<p>is syntactic sugar for</p>
<p><tt>(lambda () <<em>exp</em>>)<br /></tt></p>
<p><tt>Force</tt> simply calls the procedure (of no arguments)
produced by <tt>delay</tt>, so we can implement <tt>force</tt> as
a procedure:</p>
<p><tt><a name="%_idx_3798"></a>(define (force delayed-object)<br />
(delayed-object))<br /></tt></p>
<p><a name="%_idx_3800"></a><a name="%_idx_3802"></a>This
implementation suffices for <tt>delay</tt> and <tt>force</tt> to
work as advertised, but there is an important optimization that
we can include. In many applications, we end up forcing the same
delayed object many times. This can lead to serious inefficiency
in recursive programs involving streams. (See
exercise <a href="#%_thm_3.57">3.57</a>.) The solution is to
build delayed objects so that the first time they are forced,
they store the value that is computed. Subsequent forcings will
simply return the stored value without repeating the computation.
In other words, we implement <tt>delay</tt> as a special-purpose
memoized procedure similar to the one described in
exercise <a href="book-Z-H-22.html#%_thm_3.27">3.27</a>. One
way to accomplish this is to use the following procedure, which
takes as argument a procedure (of no arguments) and returns a
memoized version of the procedure. The first time the memoized
procedure is run, it saves the computed result. On subsequent
evaluations, it simply returns the result.</p>
<p><tt><a name="%_idx_3804"></a>(define (memo-proc proc)<br />
(let ((already-run? false) (result false))<br />
(lambda ()<br />
(if (not already-run?)<br />
(begin (set! result (proc))<br />
(set! already-run? true)<br />
result)<br />
result))))<br />
</tt></p>
<p><tt>Delay</tt> is then defined so that <tt>(delay
<<em>exp</em>>)</tt> is equivalent to</p>
<p>
<tt>(memo-proc (lambda () <<em>exp</em>>))<br />
</tt></p>
<p>and <tt>force</tt> is as defined previously.<a href="#footnote_Temp_450" name="call_footnote_Temp_450" id="call_footnote_Temp_450"><sup><small>58</small></sup></a></p>
<p><a name="%_thm_3.50"></a> <b>Exercise
3.50.</b> Complete the following definition, which
generalizes <tt>stream-map</tt> to allow procedures that take
multiple arguments, analogous to <tt>map</tt> in
section <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>,
footnote <a href="book-Z-H-15.html#footnote_Temp_166">12</a>.</p>
<p><tt><a name="%_idx_3824"></a>(define (stream-map proc . argstreams)<br />
(if (<<em>??</em>> (car argstreams))<br />
the-empty-stream<br />
(<<em>??</em>><br />
(apply proc (map <<em>??</em>> argstreams))<br />
(apply stream-map<br />
(cons proc (map <<em>??</em>> argstreams))))))<br />
</tt></p>
<p><a name="%_thm_3.51"></a> <b>Exercise
3.51.</b> <a name="%_idx_3826"></a>In order to take a
closer look at delayed evaluation, we will use the following
procedure, which simply returns its argument after printing
it:</p>
<p><tt>(define (show x)<br />
(display-line x)<br />
x)<br /></tt></p>
<p>What does the interpreter print in response to evaluating each
expression in the following sequence?<a href="#footnote_Temp_453" name="call_footnote_Temp_453" id="call_footnote_Temp_453"><sup><small>59</small></sup></a></p>
<p>
<tt>(define x (stream-map show (stream-enumerate-interval 0 10)))<br />
(stream-ref x 5)<br />
(stream-ref x 7)<br /></tt></p>
<p><a name="%_thm_3.52"></a> <b>Exercise
3.52.</b> <a name="%_idx_3830"></a>Consider the
sequence of expressions</p>
<p><tt>(define sum 0)<br />
(define (accum x)<br />
(set! sum (+ x sum))<br />
sum)<br />
(define seq (stream-map accum (stream-enumerate-interval 1 20)))<br />
(define y (stream-filter even? seq))<br />
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))<br />
seq))<br />
(stream-ref y 7)<br />
(display-stream z)<br /></tt></p>
<p>What is the value of <tt>sum</tt> after each of the above
expressions is evaluated? What is the printed response to
evaluating the <tt>stream-ref</tt> and <tt>display-stream</tt>
expressions? Would these responses differ if we had implemented
<tt>(delay <<em>exp</em>>)</tt> simply as <tt>(lambda
() <<em>exp</em>>)</tt> without using the optimization
provided by <tt>memo-proc</tt> ? Explain.</p>
<p><a name="%_sec_3.5.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.5.2">3.5.2 Infinite
Streams</a></h3>
<p><a name="%_idx_3832"></a> We have seen how to support the
illusion of manipulating streams as complete entities even
though, in actuality, we compute only as much of the stream as we
need to access. We can exploit this technique to represent
sequences efficiently as streams, even if the sequences are very
long. What is more striking, we can use streams to represent
sequences that are infinitely long. For instance, consider the
following definition of the stream of positive integers:</p>
<p><tt><a name="%_idx_3834"></a>(define (integers-starting-from n)<br />
(cons-stream n (integers-starting-from (+ n 1))))<br />
<br />
<a name="%_idx_3836"></a>(define integers (integers-starting-from 1))<br />
</tt></p>
<p>This makes sense because <tt>integers</tt> will be a pair
whose <tt>car</tt> is 1 and whose <tt>cdr</tt> is a promise to
produce the integers beginning with 2. This is an infinitely long
stream, but in any given time we can examine only a finite
portion of it. Thus, our programs will never know that the entire
infinite stream is not there.</p>
<p>Using <tt>integers</tt> we can define other infinite streams,
such as the stream of integers that are not divisible by 7:</p>
<p><tt><a name="%_idx_3838"></a>(define (divisible? x y) (= (remainder x y) 0))<br />
(define no-sevens<br />
(stream-filter (lambda (x) (not (divisible? x 7)))<br />
integers))<br />
</tt></p>
<p>Then we can find integers not divisible by 7 simply by
accessing elements of this stream:</p>
<p><tt>(stream-ref no-sevens 100)<br />
<i>117</i><br /></tt></p>
<p>In analogy with <tt>integers</tt>, we can define the infinite
stream of Fibonacci numbers:</p>
<p><tt>(define (fibgen a b)<br />
(cons-stream a (fibgen b (+ a b))))<br />
<a name="%_idx_3840"></a>(define fibs (fibgen 0 1))<br />
</tt></p>
<p><tt>Fibs</tt> is a pair whose <tt>car</tt> is 0 and whose
<tt>cdr</tt> is a promise to evaluate <tt>(fibgen 1 1)</tt>. When
we evaluate this delayed <tt>(fibgen 1 1)</tt>, it will produce a
pair whose <tt>car</tt> is 1 and whose <tt>cdr</tt> is a promise
to evaluate <tt>(fibgen 1 2)</tt>, and so on.</p>
<p><a name="%_idx_3842"></a>For a look at a more exciting
infinite stream, we can generalize the <tt>no-sevens</tt> example
to construct the infinite stream of prime numbers, using a method
known as the <a name="%_idx_3844"></a><em>sieve of
Eratosthenes</em>.<a href="#footnote_Temp_455" name="call_footnote_Temp_455" id="call_footnote_Temp_455"><sup><small>60</small></sup></a> We
start with the integers beginning with 2, which is the first
prime. To get the rest of the primes, we start by filtering the
multiples of 2 from the rest of the integers. This leaves a
stream beginning with 3, which is the next prime. Now we filter
the multiples of 3 from the rest of this stream. This leaves a
stream beginning with 5, which is the next prime, and so on. In
other words, we construct the primes by a sieving process,
described as follows: To sieve a stream <tt>S</tt>, form a stream
whose first element is the first element of <tt>S</tt> and the
rest of which is obtained by filtering all multiples of the first
element of <tt>S</tt> out of the rest of <tt>S</tt> and sieving
the result. This process is readily described in terms of stream
operations:</p>
<p><tt><a name="%_idx_3852"></a>(define (sieve stream)<br />
(cons-stream<br />
(stream-car stream)<br />
(sieve (stream-filter<br />
(lambda (x)<br />
(not (divisible? x (stream-car stream))))<br />
(stream-cdr stream)))))<br />
<br />
<a name="%_idx_3854"></a>(define primes (sieve (integers-starting-from 2)))<br />
</tt></p>
<p>Now to find a particular prime we need only ask for it:</p>
<p><tt>(stream-ref primes 50)<br />
<i>233</i><br /></tt></p>
<p>It is interesting to contemplate the signal-processing system
set up by <tt>sieve</tt>, shown in the <a name="%_idx_3856"></a>``Henderson diagram'' in figure <a href="#%_fig_3.31">3.31</a>.<a href="#footnote_Temp_456" name="call_footnote_Temp_456" id="call_footnote_Temp_456"><sup><small>61</small></sup></a> The
input stream feeds into an ``un<tt>cons</tt>er'' that separates
the first element of the stream from the rest of the stream. The
first element is used to construct a divisibility filter, through
which the rest is passed, and the output of the filter is fed to
another sieve box. Then the original first element is
<tt>cons</tt>ed onto the output of the internal sieve to form the
output stream. Thus, not only is the stream infinite, but the
signal processor is also infinite, because the sieve contains a
sieve within it.</p>
<p><a name="%_fig_3.31"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.31:</b> The prime sieve viewed as a
signal-processing system.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-35.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_sec_Temp_457"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_457">Defining
streams implicitly</a></h4>
<p><a name="%_idx_3860"></a> The <tt>integers</tt> and
<tt>fibs</tt> streams above were defined by specifying
``generating'' procedures that explicitly compute the stream
elements one by one. An alternative way to specify streams is to
take advantage of delayed evaluation to define streams
implicitly. For example, the following expression defines the
stream <tt>ones</tt> to be an infinite stream of ones:</p>
<p><tt><a name="%_idx_3862"></a>(define ones (cons-stream 1 ones))<br />
</tt></p>
<p>This works much like the definition of a recursive procedure:
<tt>ones</tt> is a pair whose <tt>car</tt> is 1 and whose
<tt>cdr</tt> is a promise to evaluate <tt>ones</tt>. Evaluating
the <tt>cdr</tt> gives us again a 1 and a promise to evaluate
<tt>ones</tt>, and so on.</p>
<p>We can do more interesting things by manipulating streams with
operations such as <tt>add-streams</tt>, which produces the
elementwise sum of two given streams:<a href="#footnote_Temp_458" name="call_footnote_Temp_458" id="call_footnote_Temp_458"><sup><small>62</small></sup></a></p>
<p><tt><a name="%_idx_3864"></a>(define (add-streams s1 s2)<br />
(stream-map + s1 s2))<br /></tt></p>
<p>Now we can define the integers as follows:</p>
<p><tt><a name="%_idx_3866"></a>(define integers (cons-stream 1 (add-streams ones integers)))<br />
</tt></p>
<p>This defines <tt>integers</tt> to be a stream whose first
element is 1 and the rest of which is the sum of <tt>ones</tt>
and <tt>integers</tt>. Thus, the second element of
<tt>integers</tt> is 1 plus the first element of
<tt>integers</tt>, or 2; the third element of <tt>integers</tt>
is 1 plus the second element of <tt>integers</tt>, or 3; and so
on. This definition works because, at any point, enough of the
<tt>integers</tt> stream has been generated so that we can feed
it back into the definition to produce the next integer.</p>
<p>We can define the Fibonacci numbers in the same style:</p>
<p><tt><a name="%_idx_3868"></a>(define fibs<br />
(cons-stream 0<br />
(cons-stream 1<br />
(add-streams (stream-cdr fibs)<br />
fibs))))<br />
</tt></p>
<p>This definition says that <tt>fibs</tt> is a stream beginning
with 0 and 1, such that the rest of the stream can be generated
by adding <tt>fibs</tt> to itself shifted by one place:</p>
<table border="0">
<tr>
<td valign="top"></td>
<td valign="top"></td>
<td valign="top">1</td>
<td valign="top">1</td>
<td valign="top">2</td>
<td valign="top">3</td>
<td valign="top">5</td>
<td valign="top">8</td>
<td valign="top">13</td>
<td valign="top">21</td>
<td valign="top"><tt>...</tt> = <tt>(stream-cdr
fibs)</tt></td>
</tr>
<tr>
<td valign="top"></td>
<td valign="top"></td>
<td valign="top">0</td>
<td valign="top">1</td>
<td valign="top">1</td>
<td valign="top">2</td>
<td valign="top">3</td>
<td valign="top">5</td>
<td valign="top">8</td>
<td valign="top">13</td>
<td valign="top"><tt>...</tt> = <tt>fibs</tt></td>
</tr>
<tr>
<td valign="top">0</td>
<td valign="top">1</td>
<td valign="top">1</td>
<td valign="top">2</td>
<td valign="top">3</td>
<td valign="top">5</td>
<td valign="top">8</td>
<td valign="top">13</td>
<td valign="top">21</td>
<td valign="top">34</td>
<td valign="top"><tt>...</tt> = <tt>fibs</tt></td>
</tr>
<tr>
<td valign="top"></td>
</tr>
</table>
<p><tt>Scale-stream</tt> is another useful procedure in
formulating such stream definitions. This multiplies each item in
a stream by a given constant:</p>
<p><tt><a name="%_idx_3870"></a>(define (scale-stream stream factor)<br />
(stream-map (lambda (x) (* x factor)) stream))<br />
</tt></p>
<p>For example,</p>
<p>
<tt>(define double (cons-stream 1 (scale-stream double 2)))<br />
</tt></p>
<p>produces the stream of powers of 2: 1, 2, 4, 8, 16, 32,
<tt>...</tt>.</p>
<p>An alternate definition of the stream of primes can be given
by starting with the integers and filtering them by testing for
primality. We will need the first prime, 2, to get started:</p>
<p><tt><a name="%_idx_3872"></a>(define primes<br />
(cons-stream<br />
2<br />
(stream-filter prime? (integers-starting-from 3))))<br />
</tt></p>
<p>This definition is not so straightforward as it appears,
because we will test whether a number <em>n</em> is prime by
checking whether <em>n</em> is divisible by a prime (not by just
any integer) less than or equal to <img src="book-Z-G-D-13.gif" border="0" /><em>n</em>:</p>
<p><tt><a name="%_idx_3874"></a>(define (prime? n)<br />
(define (iter ps)<br />
(cond ((> (square (stream-car ps)) n) true)<br />
((divisible? n (stream-car ps)) false)<br />
(else (iter (stream-cdr ps)))))<br />
(iter primes))<br /></tt></p>
<p>This is a recursive definition, since <tt>primes</tt> is
defined in terms of the <tt>prime?</tt> predicate, which itself
uses the <tt>primes</tt> stream. The reason this procedure works
is that, at any point, enough of the <tt>primes</tt> stream has
been generated to test the primality of the numbers we need to
check next. That is, for every <em>n</em> we test for primality,
either <em>n</em> is not prime (in which case there is a prime
already generated that divides it) or <em>n</em> is prime (in
which case there is a prime already generated -- i.e., a prime
less than <em>n</em> -- that is greater than <img src="book-Z-G-D-13.gif" border="0" /><em>n</em>).<a href="#footnote_Temp_459" name="call_footnote_Temp_459" id="call_footnote_Temp_459"><sup><small>63</small></sup></a></p>
<p><a name="%_thm_3.53"></a> <b>Exercise
3.53.</b> Without running the program, describe the
elements of the stream defined by</p>
<p>
<tt>(define s (cons-stream 1 (add-streams s s)))<br />
</tt></p>
<p><a name="%_thm_3.54"></a> <b>Exercise
3.54.</b> Define a procedure <a name="%_idx_3886"></a><a name="%_idx_3888"></a><a name="%_idx_3890"></a><tt>mul-streams</tt>, analogous to
<tt>add-streams</tt>, that produces the elementwise product of
its two input streams. Use this together with the stream of
<tt>integers</tt> to complete the following definition of the
stream whose <em>n</em>th element (counting from 0) is <em>n</em>
+ 1 factorial:</p>
<p>
<tt>(define factorials (cons-stream 1 (mul-streams <<em>??</em>> <<em>??</em>>)))<br />
</tt></p>
<p><a name="%_thm_3.55"></a> <b>Exercise
3.55.</b> Define a procedure <a name="%_idx_3892"></a><tt>partial-sums</tt> that takes as argument a
stream <em>S</em> and returns the stream whose elements are
<em>S</em><sub>0</sub>, <em>S</em><sub>0</sub> +
<em>S</em><sub>1</sub>, <em>S</em><sub>0</sub> +
<em>S</em><sub>1</sub> + <em>S</em><sub>2</sub>, <tt>...</tt>.
For example, <tt>(partial-sums integers)</tt> should be the
stream 1, 3, 6, 10, 15, <tt>...</tt>.</p>
<p><a name="%_thm_3.56"></a> <b>Exercise 3.56.</b> A
famous problem, first raised by <a name="%_idx_3894"></a>R.
Hamming, is to enumerate, in ascending order with no repetitions,
all positive integers with no prime factors other than 2, 3, or
5. One obvious way to do this is to simply test each integer in
turn to see whether it has any factors other than 2, 3, and 5.
But this is very inefficient, since, as the integers get larger,
fewer and fewer of them fit the requirement. As an alternative,
let us call the required stream of numbers <tt>S</tt> and notice
the following facts about it.</p>
<ul>
<li><tt>S</tt> begins with 1.</li>
<li>The elements of <tt>(scale-stream S 2)</tt> are also
elements of <tt>S</tt>.</li>
<li>The same is true for <tt>(scale-stream S 3)</tt> and
<tt>(scale-stream 5 S)</tt>.</li>
<li>These are all the elements of <tt>S</tt>.</li>
</ul>
<p><a name="%_idx_3896"></a>Now all we have to do is combine
elements from these sources. For this we define a procedure
<tt>merge</tt> that combines two ordered streams into one ordered
result stream, eliminating repetitions:</p>
<p><tt><a name="%_idx_3898"></a>(define (merge s1 s2)<br />
(cond ((stream-null? s1) s2)<br />
((stream-null? s2) s1)<br />
(else<br />
(let ((s1car (stream-car s1))<br />
(s2car (stream-car s2)))<br />
(cond ((< s1car s2car)<br />
(cons-stream s1car (merge (stream-cdr s1) s2)))<br />
((> s1car s2car)<br />
(cons-stream s2car (merge s1 (stream-cdr s2))))<br />
(else<br />
(cons-stream s1car<br />
(merge (stream-cdr s1)<br />
(stream-cdr s2)))))))))<br />
</tt></p>
<p>Then the required stream may be constructed with
<tt>merge</tt>, as follows:</p>
<p>
<tt>(define S (cons-stream 1 (merge <<em>??</em>> <<em>??</em>>)))<br />
</tt></p>
<p>Fill in the missing expressions in the places marked
<<em>??</em>> above.</p>
<p><a name="%_thm_3.57"></a> <b>Exercise
3.57.</b> <a name="%_idx_3900"></a>How many additions
are performed when we compute the <em>n</em>th Fibonacci number
using the definition of <tt>fibs</tt> based on the
<tt>add-streams</tt> procedure? Show that the number of additions
would be exponentially greater if we had implemented <tt>(delay
<<em>exp</em>>)</tt> simply as <tt>(lambda ()
<<em>exp</em>>)</tt>, without using the optimization
provided by the <tt>memo-proc</tt> procedure described in
section <a href="#%_sec_3.5.1">3.5.1</a>.<a href="#footnote_Temp_465" name="call_footnote_Temp_465" id="call_footnote_Temp_465"><sup><small>64</small></sup></a></p>
<p><a name="%_thm_3.58"></a> <b>Exercise
3.58.</b> Give an interpretation of the stream
computed by the following procedure:</p>
<p><tt>(define (expand num den radix)<br />
(cons-stream<br />
(quotient (* num radix) den)<br />
(expand (remainder (* num radix) den) den radix)))<br />
</tt></p>
<p><a name="%_idx_3906"></a><a name="%_idx_3908"></a>(<tt>Quotient</tt> is a primitive that returns
the integer quotient of two integers.) What are the successive
elements produced by <tt>(expand 1 7 10)</tt> ? What is produced
by <tt>(expand 3 8 10)</tt> ?</p>
<p><a name="%_thm_3.59"></a> <b>Exercise
3.59.</b> <a name="%_idx_3910"></a><a name="%_idx_3912"></a>In section <a href="book-Z-H-18.html#%_sec_2.5.3">2.5.3</a> we saw how to implement
a polynomial arithmetic system representing polynomials as lists
of terms. In a similar way, we can work with <em>power
series</em>, such as</p>
<p><a name="%_idx_3914"></a></p>
<div align="left"><img src="ch3-Z-G-36.gif" border="0" /></div>
<p><a name="%_idx_3916"></a></p>
<div align="left"><img src="ch3-Z-G-37.gif" border="0" /></div>
<p><a name="%_idx_3918"></a></p>
<div align="left"><img src="ch3-Z-G-38.gif" border="0" /></div>
<p>represented as infinite streams. We will represent the series
<em>a</em><sub>0</sub> + <em>a</em><sub>1</sub> <em>x</em> +
<em>a</em><sub>2</sub> <em>x</em><sup>2</sup> +
<em>a</em><sub>3</sub> <em>x</em><sup>3</sup> +
<tt>···</tt> as the stream whose elements