forked from ldct/isicp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
3-5-streams.html
1830 lines (1436 loc) · 97.1 KB
/
3-5-streams.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 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> Streams </h2>
<p> 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 <tt>streams</tt> . As we shall see, streams can mitigate some of the complexity of modeling state.
<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> 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 x as a function of time x(t). If we concentrate on x 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.@footnote{Physicists sometimes adopt this view by introducing the ``world lines'' of particles as a device for reasoning about motion. We've also already mentioned (section 2-2-3) that this is the natural way to think about signal-processing systems. We will explore applications of streams to signal processing in section 3-5-3.}
<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 <tt>streams</tt> . 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 2-2-1) doesn't fully reveal the power of stream processing. As an alternative, we introduce the technique of <tt>delayed evaluation</tt> , which enables us to represent very large (even infinite) sequences as streams.
<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.
<h3> Streams Are Delayed Lists </h3>
<p> As we saw in section 2-2-3, 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> 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> 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:@footnote{Assume that we have a predicate <tt>prime?</tt> (e.g., as in section 1-2-6) that tests for primality.}
<div id="">
(define (sum-primes a b)
(define (iter count accum)
(cond ((> count b) accum)
((prime? count) (iter (+ count 1) (+ count accum)))
(else (iter (+ count 1) accum))))
(iter a 0))
</div>
<script>
prompt();
</script>
<p> The second program performs the same computation using the sequence operations of section 2-2-3:
<div id="">
(define (sum-primes a b)
(accumulate +
0
(filter prime? (enumerate-interval a b))))
</div>
<script>
prompt();
</script>
<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> 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
<div id="">
(car (cdr (filter prime?
(enumerate-interval 10000 1000000))))
</div>
<script>
prompt();
</script>
<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> 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> On the surface, streams are just lists with different names for the procedures that manipulate them. There is a constructor, <tt>cons-stream</tt>, and two selectors, <tt>stream-car</tt> and <tt>stream-cdr</tt>, which satisfy the constraints
<pre>
(stream-car (cons-stream x y)) = x
(stream-cdr (cons-stream x y)) = y
</pre>
<p> There is a distinguishable object, <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 <tt>stream-null?</tt>.@footnote{In the @acronym{MIT} implementation, <tt>the-empty-stream</tt> is the same as the empty list <tt>'()</tt>, and <tt>stream-null?</tt> is the same as <tt>null?</tt>.} 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>:@footnote{This should bother you. The fact that we are defining such similar procedures for streams and lists indicates that we are missing some underlying abstraction. Unfortunately, in order to exploit this abstraction, we will need to exert finer control over the process of evaluation than we can at present. We will discuss this point further at the end of section 3-5-4. In section 4-2, we'll develop a framework that unifies lists and streams.}
<div id="">
(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
(define (stream-map proc s)
(if (stream-null? s)
the-empty-stream
(cons-stream (proc (stream-car s))
(stream-map proc (stream-cdr s)))))
(define (stream-for-each proc s)
(if (stream-null? s)
'done
(begin (proc (stream-car s))
(stream-for-each proc (stream-cdr s)))))
</div>
<script>
prompt();
</script>
<tt>Stream-for-each</tt> is useful for viewing streams:
<div id="">
(define (display-stream s)
(stream-for-each display-line s))
(define (display-line x)
(newline)
(display x))
</div>
<script>
prompt();
</script>
<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 2-1-2, 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> Our implementation of streams will be based on a special form called <tt>delay</tt>. Evaluating <tt>(delay <exp</tt>>) does not evaluate the expression <exp>, but rather returns a so-called <tt>delayed object</tt> , which we can think of as a ``promise'' to evaluate <exp> at some future time. As a companion to <tt>delay</tt>, there is a procedure called <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.
<tt>Cons-stream</tt> is a special form defined so that
<div id="">
(cons-stream <a> <b>)
</div>
<script>
prompt();
</script>
is equivalent to
<div id="">
(cons <a> (delay <b>))
</div>
<script>
prompt();
</script>
<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:
<div id="">
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
</div>
<script>
prompt();
</script>
<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.@footnote{Although <tt>stream-car</tt> and <tt>stream-cdr</tt> can be defined as procedures, <tt>cons-stream</tt> must be a special form. If <tt>cons-stream</tt> were a procedure, then, according to our model of evaluation, evaluating <tt>(cons-stream <a</tt>> <@var{b>)} would automatically cause <b> to be evaluated, which is precisely what we do not want to happen. For the same reason, <tt>delay</tt> must be a special form, though <tt>force</tt> can be an ordinary procedure.}
<h4> The stream implementation in action </h4>
<p> To see how this implementation behaves, let us analyze the ``outrageous'' prime computation we saw above, reformulated in terms of streams:
<div id="">
(stream-car
(stream-cdr
(stream-filter prime?
(stream-enumerate-interval 10000 1000000))))
</div>
<script>
prompt();
</script>
<p> We will see that it does indeed work efficiently.
<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 2-2-3):
<div id="">
(define (stream-enumerate-interval low high)
(if (> low high)
the-empty-stream
(cons-stream
low
(stream-enumerate-interval (+ low 1) high))))
</div>
<script>
prompt();
</script>
<p> and thus the result returned by <tt>stream-enumerate-interval</tt>, formed by the <tt>cons-stream</tt>, is@footnote{The numbers shown here do not really appear in the delayed expression. What actually appears is the original expression, in an environment in which the variables are bound to the appropriate numbers. For example, <tt>(+ low 1)</tt> with <tt>low</tt> bound to 10,000 actually appears where <tt>10001</tt> is shown.}
<div id="">
(cons 10000
(delay (stream-enumerate-interval 10001 1000000)))
</div>
<script>
prompt();
</script>
<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 2-2-3):
<div id="">
(define (stream-filter pred stream)
(cond ((stream-null? stream) the-empty-stream)
((pred (stream-car stream))
(cons-stream (stream-car stream)
(stream-filter pred
(stream-cdr stream))))
(else (stream-filter pred (stream-cdr stream)))))
</div>
<script>
prompt();
</script>
<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
<div id="">
(cons 10001
(delay (stream-enumerate-interval 10002 1000000)))
</div>
<script>
prompt();
</script>
<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
<div id="">
(cons-stream (stream-car stream)
(stream-filter pred (stream-cdr stream)))
</div>
<script>
prompt();
</script>
which in this case is
<div id="">
(cons 10007
(delay
(stream-filter
prime?
(cons 10008
(delay
(stream-enumerate-interval 10009
1000000))))))
</div>
<script>
prompt();
</script>
<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
<div id="">
(cons 10009
(delay
(stream-filter
prime?
(cons 10010
(delay
(stream-enumerate-interval 10011
1000000))))))
</div>
<script>
prompt();
</script>
<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> In general, we can think of delayed evaluation as ``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 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.
<h4> Implementing <tt>delay</tt> and <tt>force</tt> </h4>
<p> 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
<div id="">
(delay <exp>)
</div>
<script>
prompt();
</script>
<p> is syntactic sugar for
<div id="">
(lambda () <exp>)
</div>
<script>
prompt();
</script>
<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:
<div id="">
(define (force delayed-object)
(delayed-object))
</div>
<script>
prompt();
</script>
<p> 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 3-57.) 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 3-27. 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.
<div id="">
(define (memo-proc proc)
(let ((already-run? false) (result false))
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? true)
result)
result))))
</div>
<script>
prompt();
</script>
<p> <tt>Delay</tt> is then defined so that <tt>(delay <exp</tt>>) is equivalent to
<div id="">
(memo-proc (lambda () <exp>))
</div>
<script>
prompt();
</script>
<p> and <tt>force</tt> is as defined previously.@footnote{There are many possible implementations of streams other than the one described in this section. Delayed evaluation, which is the key to making streams practical, was inherent in Algol 60's <tt>call-by-name</tt> parameter-passing method. The use of this mechanism to implement streams was first described by Landin (1965). Delayed evaluation for streams was introduced into Lisp by Friedman and Wise (1976). In their implementation, <tt>cons</tt> always delays evaluating its arguments, so that lists automatically behave as streams. The memoizing optimization is also known as <tt>call-by-need</tt> . The Algol community would refer to our original delayed objects as <tt>call-by-name thunks</tt> and to the optimized versions as <tt>call-by-need thunks</tt> .}
<div class="exercise">
<p> <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 2-2-3, footnote Footnote 12.
<div id="">
(define (stream-map proc . argstreams)
(if (<??> (car argstreams))
the-empty-stream
(<??>
(apply proc (map <??> argstreams))
(apply stream-map
(cons proc (map <??> argstreams))))))
</div>
<script>
prompt();
</script>
</div>
<div class="exercise">
<p> <b>Exercise 3.51:</b> In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it:
<div id="">
(define (show x)
(display-line x)
x)
</div>
<script>
prompt();
</script>
<p> What does the interpreter print in response to evaluating each expression in the following sequence?@footnote{Exercises such as Exercise 3-51 and Exercise 3-52 are valuable for testing our understanding of how <tt>delay</tt> works. On the other hand, intermixing delayed evaluation with printing---and, even worse, with assignment---is extremely confusing, and instructors of courses on computer languages have traditionally tormented their students with examination questions such as the ones in this section. Needless to say, writing programs that depend on such subtleties is odious programming style. Part of the power of stream processing is that it lets us ignore the order in which events actually happen in our programs. Unfortunately, this is precisely what we cannot afford to do in the presence of assignment, which forces us to be concerned with time and change.}
<div id="">
(define x (stream-map show (stream-enumerate-interval 0 10)))
(stream-ref x 5)
(stream-ref x 7)
</div>
<script>
prompt();
</script>
</div>
<div class="exercise">
<b>Exercise 3.52:</b> Consider the sequence of
expressions
<div id="">
(define sum 0)
(define (accum x)
(set! sum (+ x sum))
sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(define y (stream-filter even? seq))
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
seq))
(stream-ref y 7)
(display-stream z)
</div>
<script>
prompt();
</script>
<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 <exp</tt>>) simply as <tt>(lambda () <exp</tt>>) without using the optimization provided by <tt>memo-proc</tt>? Explain
</div>
<h3> Infinite Streams </h3>
<p> 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:
<div id="">
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))
</div>
<script>
prompt();
</script>
<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> Using <tt>integers</tt> we can define other infinite streams, such as the stream of integers that are not divisible by 7:
<div id="">
(define (divisible? x y) (= (remainder x y) 0))
(define no-sevens
(stream-filter (lambda (x) (not (divisible? x 7)))
integers))
</div>
<script>
prompt();
</script>
<p> Then we can find integers not divisible by 7 simply by accessing elements of this stream:
<div id="">
(stream-ref no-sevens 100)
117
</div>
<script>
prompt();
</script>
<p> In analogy with <tt>integers</tt>, we can define the infinite stream of Fibonacci numbers:
<div id="">
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))
</div>
<script>
prompt();
</script>
<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> 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 <tt>sieve of Eratosthenes</tt> .@footnote{Eratosthenes, a third-century @acronym{B.C.} Alexandrian Greek philosopher, is famous for giving the first accurate estimate of the circumference of the Earth, which he computed by observing shadows cast at noon on the day of the summer solstice. Eratosthenes's sieve method, although ancient, has formed the basis for special-purpose hardware ``sieves''that, until recently, were the most powerful tools in existence for locating large primes. Since the 70s, however, these methods have been superseded by outgrowths of the probabilistic techniques discussed in section 1-2-6.} 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:
<div id="">
(define (sieve stream)
(cons-stream
(stream-car stream)
(sieve (stream-filter
(lambda (x)
(not (divisible? x (stream-car stream))))
(stream-cdr stream)))))
(define primes (sieve (integers-starting-from 2)))
</div>
<script>
prompt();
</script>
<p> Now to find a particular prime we need only ask for it:
<div id="">
(stream-ref primes 50)
233
</div>
<script>
prompt();
</script>
<p> It is interesting to contemplate the signal-processing system set up by <tt>sieve</tt>, shown in the ``Henderson diagram'' in Figure 3-31.@footnote{We have named these figures after Peter Henderson, who was the first person to show us diagrams of this sort as a way of thinking about stream processing. Each solid line represents a stream of values being transmitted. The dashed line from the <tt>car</tt> to the <tt>cons</tt> and the <tt>filter</tt> indicates that this is a single value rather than a stream.} 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.
<div class="exercise">
<b>Figure 3.31:</b> The prime sieve viewed as a
signal-processing system.
<pre>
+---------------------------------------------------------------+
| sieve |
| |
| __/| |\__ |
| __/car|........................................| \__ |
| _/ | : | \_ |
----><_ | V | cons _>---->
| \__ | +------------+ +------------+ | __/ |
| \cdr|--->| filter: | | sieve |--->| __/ |
| \| | |--->| | |/ |
| | not | | | |
| | divisible? | | | |
| +------------+ +------------+ |
+---------------------------------------------------------------+
</pre>
</div>
<h4> Defining streams implicitly </h4>
<p> 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:
<div id="">
(define ones (cons-stream 1 ones))
</div>
<script>
prompt();
</script>
<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> 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:@footnote{This uses the generalized version of <tt>stream-map</tt> from Exercise 3-50.}
<div id="">
(define (add-streams s1 s2)
(stream-map + s1 s2))
</div>
<script>
prompt();
</script>
<p> Now we can define the integers as follows:
<div id="">
(define integers (cons-stream 1 (add-streams ones integers)))
</div>
<script>
prompt();
</script>
<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> We can define the Fibonacci numbers in the same style:
<div id="">
(define fibs
(cons-stream 0
(cons-stream 1
(add-streams (stream-cdr fibs)
fibs))))
</div>
<script>
prompt();
</script>
<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:
<pre>
1 1 2 3 5 8 13 21 ... = <tt>(stream-cdr fibs)</tt>
0 1 1 2 3 5 8 13 ... = <tt>fibs</tt>
0 1 1 2 3 5 8 13 21 34 ... = <tt>fibs</tt>
</pre>
<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:
<div id="">
(define (scale-stream stream factor)
(stream-map (lambda (x) (* x factor)) stream))
</div>
<script>
prompt();
</script>
For example,
<div id="">
(define double (cons-stream 1 (scale-stream double 2)))
</div>
<script>
prompt();
</script>
<p> produces the stream of powers of 2: 1, 2, 4, 8, 16, 32, ....
<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:
<div id="">
(define primes
(cons-stream
2
(stream-filter prime? (integers-starting-from 3))))
</div>
<script>
prompt();
</script>
<p> This definition is not so straightforward as it appears, because we will test whether a number n is prime by checking whether n is divisible by a prime (not by just any integer) less than or equal to <em>[sqrt]</em>(n):
<div id="">
(define (prime? n)
(define (iter ps)
(cond ((> (square (stream-car ps)) n) true)
((divisible? n (stream-car ps)) false)
(else (iter (stream-cdr ps)))))
(iter primes))
</div>
<script>
prompt();
</script>
<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 n we test for primality, either n is not prime (in which case there is a prime already generated that divides it) or n is prime (in which case there is a prime already generated---i.e., a prime less than n---that is greater than <em>[sqrt]</em>(n)).@footnote{This last point is very subtle and relies on the fact that p_(n+1) <= p_n^2. (Here, p_k denotes the kth prime.) Estimates such as these are very difficult to establish. The ancient proof by Euclid that there are an infinite number of primes shows that p_(n+1)<= p_1 p_2...p_n + 1, and no substantially better result was proved until 1851, when the Russian mathematician P. L. Chebyshev established that p_(n+1)<= 2p_n for all n. This result, originally conjectured in 1845, is known as <tt>Bertrand's hypothesis</tt> . A proof can be found in section 22.3 of Hardy and Wright 1960.}
<div class="exercise">
<b>Exercise 3.53:</b> Without running the program, describe the elements of the stream defined by
<div id="">
(define s (cons-stream 1 (add-streams s s)))
</div>
<script>
prompt();
</script>
</div>
<div class="exercise">
<b>Exercise 3.54:</b> Define a procedure <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 nth element (counting from 0) is n + 1 factorial:
<div id="">
(define factorials (cons-stream 1 (mul-streams <??> <??>)))
</div>
<script>
prompt();
</script>
</div>
<div class="exercise">
<b>Exercise 3.55:</b> Define a procedure <tt>partial-sums</tt> that takes as argument a stream S and returns the stream whose elements are S_0, S_0 + S_1, S_0 + S_1 + S_2, .... For example, <tt>(partial-sums integers)</tt> should be the stream 1, 3, 6, 10, 15, ....
</div>
<div class="exercise">
<b>Exercise 3.56:</b> A famous problem, first raised by 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.
<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>
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:
<div id="">
(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< s1car s2car)
(cons-stream s1car (merge (stream-cdr s1) s2)))
((> s1car s2car)
(cons-stream s2car (merge s1 (stream-cdr s2))))
(else
(cons-stream s1car
(merge (stream-cdr s1)
(stream-cdr s2)))))))))
</div>
<script>
prompt();
</script>
Then the required stream may be constructed with <tt>merge</tt>, as follows:
<div id="">
(define S (cons-stream 1 (merge <??> <??>)))
</div>
<script>
prompt();
</script>
Fill in the missing expressions in the places marked <??> above.
</div>
<div class="exercise">
<b>Exercise 3.57:</b> How many additions are performed when we compute the nth 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 <exp</tt>>) simply as <tt>(lambda () <exp</tt>>), without using the optimization provided by the <tt>memo-proc</tt> procedure described in section 3-5-1.@footnote{This exercise shows how call-by-need is closely related to ordinary memoization as described in Exercise 3-27. In that exercise, we used assignment to explicitly construct a local table. Our call-by-need stream optimization effectively constructs such a table automatically, storing values in the previously forced parts of the stream.}
</div>
<div class="exercise">
<b>Exercise 3.58:</b> Give an interpretation of the stream computed by the following procedure:
<div id="">
(define (expand num den radix)
(cons-stream
(quotient (* num radix) den)
(expand (remainder (* num radix) den) den radix)))
</div>
<script>
prompt();
</script>
(<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>?
</div>
<div class="exercise">
<b>Exercise 3.59:</b> In section 2-5-3 we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with <tt>power series</tt> , such as
<pre>
x^2 x^3 x^4
e^x = 1 + x + ----- + ----- + --------- + ...
2 3 * 2 4 * 3 * 2
x^2 x^4
cos x = 1 - ----- + --------- - ...
2 4 * 3 * 2
x^3 x^5
sin x = x - ----- + ------------- - ...
3 * 2 5 * 4 * 3 * 2
</pre>
represented as infinite streams. We will represent the series a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ... as the stream whose elements are the coefficients a_0, a_1, a_2, a_3, ....
<ul>
@item
The integral of the series a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ... is the series
<pre>
1 1 1
c + a_0 x + --- x_1 r^2 + --- a_2 r^3 + --- a_3 r^4 + ...
2 3 4
</pre>
where c is any constant. Define a procedure <tt>integrate-series</tt> that takes as input a stream a_0, a_1, a_2, ... representing a power series and returns the stream a_0, (1/2)a_1, (1/3)a_2, ... of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use <tt>integrate-series</tt>, we will <tt>cons</tt> on the appropriate constant.)
@item
The function x |-> e^x is its own derivative. This implies that e^x and the integral of e^x are the same series, except for the constant term, which is e^0 = 1. Accordingly, we can generate the series for e^x as
<div id="">
(define exp-series
(cons-stream 1 (integrate-series exp-series)))
</div>
<script>
prompt();
</script>
Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:
<div id="">
(define cosine-series
(cons-stream 1 <??>))
(define sine-series
(cons-stream 0 <??>))
</div>
<script>
prompt();
</script>
</ul>
</div>
<div class="exercise">
<b>Exercise 3.60:</b> With power series represented as streams of coefficients as in Exercise 3-59, adding series is implemented by <tt>add-streams</tt>. Complete the definition of the following procedure for multiplying series:
<div id="">
(define (mul-series s1 s2)
(cons-stream <??> (add-streams <??> <??>)))
</div>
<script>
prompt();
</script>
You can test your procedure by verifying that sin^2 x + cos^2 x = 1, using the series from Exercise 3-59.
</div>
<div class="exercise">
<b>Exercise 3.61:</b> Let S be a power series (Exercise 3-59) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that S * X = 1. Write S = 1 + S_R where S_R is the part of S after the constant term. Then we can solve for X as follows:
<pre>
S * X = 1
(1 + S_R) * X = 1
X + S_R * X = 1
X = 1 - S_R * X
</pre>
In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of S_R times X. Use this idea to write a procedure <tt>invert-unit-series</tt> that computes 1/S for a power series S with constant term 1. You will need to use <tt>mul-series</tt> from Exercise 3-60.
</div>
<div class="exercise">
<b>Exercise 3.62:</b> Use the results of Exercise 3-60 and Exercise 3-61 to define a procedure <tt>div-series</tt> that divides two power series. <tt>Div-series</tt> should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then <tt>div-series</tt> should signal an error.) Show how to use <tt>div-series</tt> together with the result of Exercise 3-59 to generate the power series for tangent.
</div>
<h3> Exploiting the Stream Paradigm </h3>
Streams with delayed evaluation can be a powerful modeling tool, providing many of the benefits of local state and assignment. Moreover, they avoid some of the theoretical tangles that accompany the introduction of assignment into a programming language.
The stream approach can be illuminating because it allows us to build systems with different module boundaries than systems organized around assignment to state variables. For example, we can think of an entire time series (or signal) as a focus of interest, rather than the values of the state variables at individual moments. This makes it convenient to combine and compare components of state from different moments.
<h4> Formulating iterations as stream processes </h4>
In section 1-2-1, we introduced iterative processes, which proceed by updating state variables. We know now that we can represent state as a ``timeless'' stream of values rather than as a set of variables to be updated. Let's adopt this perspective in revisiting the square-root procedure from section 1-1-7. Recall that the idea is to generate a sequence of better and better guesses for the square root of x by applying over and over again the procedure that improves guesses:
<div id="">
(define (sqrt-improve guess x)
(average guess (/ x guess)))
</div>
<script>
prompt();
</script>
In our original <tt>sqrt</tt> procedure, we made these guesses be the successive values of a state variable. Instead we can generate the infinite stream of guesses, starting with an initial guess of 1:@footnote{We can't use <tt>let</tt> to bind the local variable <tt>guesses</tt>, because the value of <tt>guesses</tt> depends on <tt>guesses</tt> itself. Exercise 3-63 addresses why we want a local variable here.}
<div id="">
(define (sqrt-stream x)
(define guesses
(cons-stream 1.0
(stream-map (lambda (guess)
(sqrt-improve guess x))
guesses)))
guesses)
(display-stream (sqrt-stream 2))
1.
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
...
</div>
<script>
prompt();
</script>
We can generate more and more terms of the stream to get better and better guesses. If we like, we can write a procedure that keeps generating terms until the answer is good enough. (See Exercise 3-64.)
Another iteration that we can treat in the same way is to generate an approximation to [pi], based upon the alternating series that we saw in section 1-3-1:
<pre>
[pi] 1 1 1
---- = 1 - --- + --- - --- + ...
4 3 5 7
</pre>
We first generate the stream of summands of the series (the reciprocals of the odd integers, with alternating signs). Then we take the stream of sums of more and more terms (using the <tt>partial-sums</tt> procedure of Exercise 3-55) and scale the result by 4:
<div id="">
(define (pi-summands n)
(cons-stream (/ 1.0 n)
(stream-map - (pi-summands (+ n 2)))))
(define pi-stream
(scale-stream (partial-sums (pi-summands 1)) 4))
(display-stream pi-stream)
4.
2.666666666666667
3.466666666666667
2.8952380952380956
3.3396825396825403
2.9760461760461765
3.2837384837384844
3.017071817071818
...
</div>
<script>
prompt();
</script>
This gives us a stream of better and better approximations to [pi], although the approximations converge rather slowly. Eight terms of the sequence bound the value of [pi] between 3.284 and 3.017.
So far, our use of the stream of states approach is not much different from updating state variables. But streams give us an opportunity to do some interesting tricks. For example, we can transform a stream with a <tt>sequence accelerator</tt> that converts a sequence of approximations to a new sequence that converges to the same value as the original, only faster.
One such accelerator, due to the eighteenth-century Swiss mathematician Leonhard Euler, works well with sequences that are partial sums of alternating series (series of terms with alternating signs). In Euler's technique, if S_n is the nth term of the original sum sequence, then the accelerated sequence has terms
<pre>
(S_(n+1) - S_n)^2
S_(n+1) - ------------------------
S_(n-1) - 2S_n + S_(n+1)
</pre>
Thus, if the original sequence is represented as a stream of values, the transformed sequence is given by
<div id="">
(define (euler-transform s)
(let ((s0 (stream-ref s 0)) ; S_(n-1)
(s1 (stream-ref s 1)) ; S_n
(s2 (stream-ref s 2))) ; S_(n+1)
(cons-stream (- s2 (/ (square (- s2 s1))
(+ s0 (* -2 s1) s2)))
(euler-transform (stream-cdr s)))))
</div>
<script>