《Structure and Interpretation of Computer Programs》lecture 21 webha2.pdf_大学文库

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 17.5 Slide 17.5.1 Streams-a different way of structuring Now, let's look at one example in which changing the computation evaluation model allows us to explore a very different kind of computational problem. Our goal is to show how a smal have a very different way of thinking about programs anet us change in the evaluator, basically our lazy evaluator, can let us Imagine that I want to simulate the motion of an object in a complex environment. A simple case might be a tennis ball that I throw against a set of walls. i would like to simulate how the ve】 ori ty elastici ball would bounce against those obstacles and where it might end up In our earlier approach, we might have chosen to model this using an object oriented system, which seems like a natural vay of breaking this problem up into pieces. Under that view, we would have a different object to represent each different structure in our simulation world. For example, we might have an object that represented the ball, with some internal state that captured the properties of the ball. Similarly each wall would be an object, perhaps witI fferent characteristics representing how objects bounce off them. And we might have a clock to synchronize interactions between the objects, leading to an object centered system very similar to what we saw in earlier lectures. In this way, each synchronization step would cause the objects to update their state, including detecting when, for example, two objects have collided so that the physics captured in each object would then govern changes in the state of the objects The thing to notice is that while this is a natural way of breaking up the system into units, the state of the simulation is basically captured in an instantaneous way. At any instant, we can determine the state of the overall stem by the values of the state variables of each object. But we don,'t have a lot of information about how the ystem has been evolving Said a different way, by breaking up this system into units of this form, we are naturally focusing on the discrete objects within the system, not on the behavior of the system

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 17.5 Slide 17.5.1 Now, let's look at one example in which changing the evaluation model allows us to explore a very different kind of computational problem. Our goal is to show how a small change in the evaluator, basically our lazy evaluator, can let us have a very different way of thinking about programs and programming. Imagine that I want to simulate the motion of an object in a complex environment. A simple case might be a tennis ball that I throw against a set of walls. I would like to simulate how the ball would bounce against those obstacles and where it might end up. In our earlier approach, we might have chosen to model this using an object oriented system, which seems like a natural way of breaking this problem up into pieces. Under that view, we would have a different object to represent each different structure in our simulation world. For example, we might have an object that represented the ball, with some internal state that captured the properties of the ball. Similarly each wall would be an object, perhaps with different characteristics representing how objects bounce off them. And we might have a clock to synchronize interactions between the objects, leading to an object centered system very similar to what we saw in earlier lectures. In this way, each synchronization step would cause the objects to update their state, including detecting when, for example, two objects have collided so that the physics captured in each object would then govern changes in the state of the objects. The thing to notice is that while this is a natural way of breaking up the system into units, the state of the simulation is basically captured in an instantaneous way. At any instant, we can determine the state of the overall system by the values of the state variables of each object. But we don't have a lot of information about how the system has been evolving. Said a different way, by breaking up this system into units of this form, we are naturally focusing on the discrete objects within the system, not on the behavior of the system

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.5. 4 Streams-a different way of structuring a key question, then, is how can I efficiently capture this kind OR- have each object output a continuous stream of of information? An obvious approach would be to just represent State of the simulation captured in the history(or the history of values as a list. We could just glue new values of stream)of values each variable onto the front of a list representing each such variable. While that is an appropriate way of conceptualizing the idea of capturing histories of values, we will see that when we move to complex systems, this becomes difficult to do in an efficient way. We would like to capture these histories with a minimum of computational effort, and for that we are going to return to the ideas we saw in the last lecture Slide 17.5.5 Remember our Lazy Language? Now we just saw how to convert our standard, or applicative Normal( Lazy) Order Evaluation order, evaluator, into a normal order, or lazy, evaluator. I want ahead and apply operator with unevaluated to take that idea, and use it to change the way we think about evaluate a subexpression only when value is needed programming, by showing how changing our viewpoint on evaluation coupled with this idea of capturing objects by their by primitive procedure( that is, primitive procedures are"strict in their arguments streams of values, gives us a very different way of Memoization- keep track of value after expression is pre grammi The key ideas we are going to use are the notion of deferring ach: give programmer control evaluation of subexpressions until only when needed; and the idea of avoiding re-evaluation of the same subexpression, by memoizing it Variable Declarations: lazy and 1azy-memo Slide 17.5.6 Handle lazy and lazy-memo extensions in an upward- So we saw an evaluator in which the programmer could declare, when building a procedure, how to treat the different (lambda (a (b lazy)c(d lazy-memo)).. parameters. In this little example, a and C are normal variables, meaning that the expressions associated with them procedure application will be fully evaluated before we apply the procedure. Variable "b"'s az, i gets (reevaluated each ime its value is b we treat as lazy, meaning that we do not evaluate the associated expression at application but ather wait until the any other time it is neede lue is returned again value is actually required within the body of the procedure (e.g when a primitive procedure is applied to this expression). In I this case, however, once the value associated with the expression has been used in that primitive application, it is discarded. Thus if the same expression is used somewhere else in the body, we will redo the work to compute it when it's value is needed. Variable d is also to be treated as lazy but in this case, once we have obtained the actual value for the variable, we keep it around, and just use that value if any other part of the procedure body uses the

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.5.4 A key question, then, is how can I efficiently capture this kind of information? An obvious approach would be to just represent the history of values as a list. We could just glue new values of each variable onto the front of a list representing each such variable. While that is an appropriate way of conceptualizing the idea of capturing histories of values, we will see that when we move to complex systems, this becomes difficult to do in an efficient way. We would like to capture these histories with a minimum of computational effort, and for that we are going to return to the ideas we saw in the last lecture. Slide 17.5.5 Now we just saw how to convert our standard, or applicative order, evaluator, into a normal order, or lazy, evaluator. I want to take that idea, and use it to change the way we think about programming, by showing how changing our viewpoint on evaluation coupled with this idea of capturing objects by their streams of values, gives us a very different way of programming. The key ideas we are going to use are the notion of deferring evaluation of subexpressions until only when needed; and the idea of avoiding re-evaluation of the same subexpression, by memoizing it. Slide 17.5.6 So we saw an evaluator in which the programmer could declare, when building a procedure, how to treat the different parameters. In this little example, a and c are normal variables, meaning that the expressions associated with them will be fully evaluated before we apply the procedure. Variable b we treat as lazy, meaning that we do not evaluate the associated expression at application but ather wait until the value is actually required within the body of the procedure (e.g. when a primitive procedure is applied to this expression). In this case, however, once the value associated with the expression has been used in that primitive application, it is discarded. Thus if the same expression is used somewhere else in the body, we will redo the work to compute it when it's value is needed. Variable d is also to be treated as lazy, but in this case, once we have obtained the actual value for the variable, we keep it around, and just use that value if any other part of the procedure body uses the same expression

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.5.7 So how could we use this idea in our context? We could create How do we use this new lazy evaluation? a new data abstraction, called a stream. Here is one version of Our users could implement a stream abstraction this abstraction It has a constructor. cons-stream and 1 ambda《n8q) two selectors. stream-car and stream -cdr. You (cond ((oq? msg ' strean-car) x) (q?m细g'吨tm-cdx)望) can see by their names, that we expect them to behave a lot like unknown stream nss 892))) ists, with one exception. The exception is that we want the can-car s)(s 'stream-o second part of the stream to be lazy, or better yet memoized and oR eam-cdr g)(8’ strean= Here we have represented this in a message passing system, we( oscam iue rte an u anr) azy. This means that when I make a stream, I want to defer getting the value of the second part of the stream until I am actually required tream-odr cdr) could also have done this using cons directly, although we have to be careful about ensuring that cons does not force the evaluation of the cdr part of the pairing until asked to by some other primitive operation How do we use this new lazy evaluation? Slide 17.5.8 Our users could implement a stream abstraction a key change is that now I have a way of gluing together a (define (cons-strean x(y lazy-memo sequence of values in which only the first value is explicitly eond《《eq? evaluated when i do the construction of the data object the rerror "unknown tran mg"meg) )))second part of this structure is lazy: it is a promise to get the (strean-car s) value when asked for, but I don 't do the work of computing the stream-ear)) (stream-edr stream-cdr)) value at construction time dene(cong-t工eanx(y1azy-抛emo) low, what does this do to our thinking about building sequences of values? (define stream-car car) leine stream-cdr cdr) Slide 17.5.9 Stream object A stream object thus looks a lot like a pair, except that the A pair-like object, except the cdr part is lazy cdr part of the stream is lazy. It is not evaluated until some (not evaluated until needed) procedure actually needs its value, but once we have worked cons-sfream out its value, we keep track of it for later reference. Think about stream-cdr what happens now. For example, if I ask x to have the value of va| ue thunk-mem。 a cons-stream of 99 and(/1 0)what will 4

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.5.10 Stream object If I did this just using a normal cons, I would get an error, (not evaluated until because cons would evaluate each of its arguments before constructing the pair, causing the division by zero to take place stream-cdr In the case of cons-stream, we get a different behavio stream-car Cons-stream will create an object with the value of the thunk-nemo first argument as the first piece(99), but the second part is x (cons-stream 99 (/1 0))) simply stored as a promise to compute a value when needed -car x)=>99 and these two things are glued together. As a consequence, x is (stream-cdr error -divide by zero safely defined, and I get the first part of the stream without problem. It is only when I try to access the second part, using stream-cdr, that the evaluation of the deferred promise will take place, and I will see the error due to division by zero Thus, we see there is a difference between a stream object as a pair and a standard pair, in that the second part of a tream object is not evaluated until required We are now going to build on that idea to see how we can create very different data structures and very different ways of thinking about computation Slide 17.5.1l his may seem like a very straightforward change What I have Decoupling computation from description in essence done is say: here is an alternative way of gluing to Can separate order of events in computer from apparent things together into pairs, specifically gluing together the value of the first thing with a promise to get the value of the second thing. It doesn 't sound like a lot, but in fact it has a fundamental impact on how I can think about computation In particular, I can now decouple the computation of values from the description of those values, or said another way, I can separate the order of events that occur inside of the computer from the apparent order of events as captured in the procedure description. Let's look at an example Decoupling computation from description Slide 17.5.12 Can separate order of events in computer from appare Suppose I want to find the value of the 100th prime. Here is the standard way of doing that, using lists Enumerate filter (lambda (x) (prine? x)) nterval could generate a list of all the integers between (enunerate-interval 1 100000000)) I and 100,000,000. I could then filter that list, using a predicate that checks for primes( the details of the predicate are not important here). Given that new list of primes, I could then walk down the list to get the 100th element Notice what has happened here. I first had to generate a list sa integers I will have to check before I find my answer. Thus/ 100,000,000 elements long, because I am not certain how man have done a lot of computation and i have chewed up a lot of memory creating a huge data structure. Filter then runs down that list and generates a new list, not quite large list and involving a lot of inally list-ref just walks down this new list, finds the 100th element, keeps it, and throws everything else away! Using standard methods, I have to do all of the computation to get the value of an argument, before I can move on to the next stage of the computation. Thus, I have to generate an entire data structure before I can move on to

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.5.10 If I did this just using a normal cons, I would get an error, because cons would evaluate each of its arguments before constructing the pair, causing the division by zero to take place. In the case of cons-stream, we get a different behavior. Cons-stream will create an object with the value of the first argument as the first piece (99), but the second part is simply stored as a promise to compute a value when needed, and these two things are glued together. As a consequence, x is safely defined, and I get the first part of the stream without problem. It is only when I try to access the second part, using stream-cdr, that the evaluation of the deferred promise will take place, and I will see the error due to division by zero. Thus, we see there is a difference between a stream object as a pair and a standard pair, in that the second part of a stream object is not evaluated until required. We are now going to build on that idea to see how we can create very different data structures and very different ways of thinking about computation. Slide 17.5.11 This may seem like a very straightforward change. What I have in essence done is say: here is an alternative way of gluing to things together into pairs, specifically gluing together the value of the first thing with a promise to get the value of the second thing. It doesn't sound like a lot, but in fact it has a fundamental impact on how I can think about computation. In particular, I can now decouple the computation of values from the description of those values, or said another way, I can separate the order of events that occur inside of the computer from the apparent order of events as captured in the procedure description. Let's look at an example. Slide 17.5.12 Suppose I want to find the value of the 100th prime. Here is the standard way of doing that, using lists. Enumerateinterval could generate a list of all the integers between 1 and 100,000,000. I could then filter that list, using a predicate that checks for primes (the details of the predicate are not important here). Given that new list of primes, I could then walk down the list to get the 100th element. Notice what has happened here. I first had to generate a list 100,000,000 elements long, because I am not certain how many integers I will have to check before I find my answer. Thus I have done a lot of computation and I have chewed up a lot of memory creating a huge data structure. Filter then runs down that list and generates a new list, not quite as long as the original, but still a very large list, and involving a lot of computation. Finally, list-ref just walks down this new list, finds the 100th element, keeps it, and throws everything else away! Using standard methods, I have to do all of the computation to get the value of an argument, before I can move on to the next stage of the computation. Thus, I have to generate an entire data structure before I can move on to

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology computations involving that data structure, even though much of the data structure may be irrelevant to my computation In this example that computation is wasted Slide 17.5.13 Decoupling computation from description Suppose instead we change viewpoint. Rather than creating an Can separate order of events in computer from apparent 4 entire list of integers before starting to look for primes, let's order of events in procedure description create a structure with the first integer that i need, and a filter (lambda (x) (prine? x) promise to generate the rest of the integers when necessary nunerate-interval 1 100000000)) Rather than creating enumerate-interval as a very (define (strean-fnterval a b) ong list, I can use streams. Because of the lazy nature of (it ( a b) streams, when I evaluate (stream-interval a the-enpty-strean (eons-t工eama( stream-⊥ nerve1a1)b)》 b) i will get a data structure with the value of a as the first (stream-ref piece, and a promise to generate the rest of the interval from stream-⊥ter( L abda《x)(pxne?x)) (stream-interval 1 100000000)) a 1) to b, when required 100 I can easily create a stream-filter that behaves like a filter on lists, but uses the constructor and selectors for streams instead of for pairs With that, notice what happens Here, when I evaluate the last expression, stream-interval will generate a structure with the value 1 and a promise to generate the interval from 2 to 100,000,000. That can immediately be passed to stream-filter which will check to see if the first element is prime. Since it is not in this case, we will throw that value away, and ask for the next element in the stream. Remember that stream-filter will just walk down the stream the same way filter walked down a list. This will cause the computation to go back to stream -interval and ask it to generate the rest of its stream, the deferred second part. This will in turn ask cons -stream to generate the value 2 and another promise to generate the rest of the stream from here As a consequence these two procedures will work in synchrony stream -interval generating the next element in the stream, then passing that value plus a promise to stream -filter which will keep checking the value, and asking stream-interval for the next element until it finds one it likes. Thus, we will only generate as many elements in the stream as we need until stream -re f is able to extract the 100th prime Decoupling computation from description Slide 17.5.14 Can separate order of events in computer from apparent Note what this allows us to do. We can now think about the 4 processing as if the entire set of values was available. We are (filter (lambda (x) (prine? x) thinking about how to deal with streams as if the entire (enunerate-intexval 1 100000000)) sequence of values were there. But in fact, when we go to the computation, the laziness allows us to separate the order of 口> events insides of the computer from the apparent order of Its in the de Thus we get th (eons-t工eama( stream- nerva1什+a1)b)))) efficiency of only computing what we need, while allowing us to think about things as if the entire sequence of valt available. To go back to our motivating e build 100 simulations in which we think about having the entire sequence of position values as if they were available, but we don't have to do all the computation needed to generate them in order to run the simulation

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. computations involving that data structure, even though much of the data structure may be irrelevant to my computation. In this example, that computation is wasted. Slide 17.5.13 Suppose instead we change viewpoint. Rather than creating an entire list of integers before starting to look for primes, let's create a structure with the first integer that I need, and a promise to generate the rest of the integers when necessary. Rather than creating enumerate-interval as a very long list, I can use streams. Because of the lazy nature of streams, when I evaluate (stream-interval a b) I will get a data structure with the value of a as the first piece, and a promise to generate the rest of the interval from (+ a 1) to b, when required. I can easily create a stream-filter that behaves like a filter on lists, but uses the constructor and selectors for streams instead of for pairs. With that, notice what happens. Here, when I evaluate the last expression, stream-interval will generate a structure with the value 1 and a promise to generate the interval from 2 to 100,000,000. That can immediately be passed to stream-filter which will check to see if the first element is prime. Since it is not in this case, we will throw that value away, and ask for the next element in the stream. Remember that stream-filter will just walk down the stream the same way filter walked down a list. This will cause the computation to go back to stream-interval and ask it to generate the rest of its stream, the deferred second part. This will in turn ask cons-stream to generate the value 2 and another promise to generate the rest of the stream from here. As a consequence, these two procedures will work in synchrony: stream-interval generating the next element in the stream, then passing that value plus a promise to stream-filter which will keep checking the value, and asking stream-interval for the next element until it finds one it likes. Thus, we will only generate as many elements in the stream as we need until stream-ref is able to extract the 100th prime. Slide 17.5.14 Note what this allows us to do. We can now think about the processing as if the entire set of values was available. We are thinking about how to deal with streams as if the entire sequence of values were there. But in fact, when we go to the computation, the laziness allows us to separate the order of events insides of the computer from the apparent order of events in the description of the process. Thus we get the efficiency of only computing what we need, while allowing us to think about things as if the entire sequence of values was available. To go back to our motivating example, we can build simulations in which we think about having the entire sequence of position values as if they were available, but we don't have to do all the computation needed to generate them in order to run the simulation

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.5.15 To see how lazy evaluation gives us this behavior, let's look in a Some details on stream procedures little more detail at this method. here is a standard stream define (stream-filter pred str) procedure, which looks exactly like our filter procedure (if (pred (stream-car str) (cons-stream (stream-car str for lists, the only difference is that we use stream abstractions (stream-filter pred in place of pair abstractions. But how does the lazy evaluation (stream-cdr str))) buried inside of cons-stream allow this procedure that (stream-filter pred streamed str)))) looks just like a normal list procedure to have this different behavior, decoupling the order of evaluation within the machine from the apparent order described by the procedure? Some details on stream procedures Slide 17.5.16 eam-fil (define (stream-filter pred str) deed, a standard question might be "Why (if (pred (strea r str) end up generating all of the elements of the at once?" cQn七工专西叫( tream-car七 The answer is here. When we apply this procedure to a stream, stream-filter pred (stream-cdr str)) it will recursively test each element in the stream, until it finds ( stream-filter pred one that satisfies the predicate. At that stage, note what streamed str)))) happens. We generate a stream with that element as the first element, and with a lazy(or delayed) promise to filter the rest of the stream when needed. Thus, we generate the first element of the new stream, and a lazy promise, not the entire stream Slide 17.5.17 ling order of evaluatie Let's check it out on our simple example. Suppose we filter the (atrean-filter prine> (atria 1 stream of integers from 1 to 100,000,000, using the predicate prime?. Let's follow this computation, noting how lazy evaluation controls the order of evaluation of the parts of the data structure coupling order of evaluation Slide 17.5.18 an-filter prime? (str-in 1 100000000)) Since stream-filter is just a standard procedure, we nents. Prime? will simply point to some procedure. (Stream-interval 1 100000000) needs to be evaluated, but we know that stream-interval is defined in terms of cons stream. So this returns one of these stream objects, which has the value of the first element, 1, already available, but simply has a promise(shown within that squiggly line )to get ne value of the next arg t. which is the stream interval from 2 to 100,000,000. At this stage, all that has been explicitly

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.5.15 To see how lazy evaluation gives us this behavior, let's look in a little more detail at this method. Here is a standard stream procedure, which looks exactly like our filter procedure for lists, the only difference is that we use stream abstractions in place of pair abstractions. But how does the lazy evaluation buried inside of cons-stream allow this procedure that looks just like a normal list procedure to have this different behavior, decoupling the order of evaluation within the machine from the apparent order described by the procedure? Slide 17.5.16 Indeed, a standard question might be "Why doesn't stream-filter end up generating all of the elements of the stream at once?" The answer is here. When we apply this procedure to a stream, it will recursively test each element in the stream, until it finds one that satisfies the predicate. At that stage, note what happens. We generate a stream with that element as the first element, and with a lazy (or delayed) promise to filter the rest of the stream when needed. Thus, we generate the first element of the new stream, and a lazy promise, not the entire stream. Slide 17.5.17 Let's check it out on our simple example. Suppose we filter the stream of integers from 1 to 100,000,000, using the predicate prime?. Let's follow this computation, noting how lazy evaluation controls the order of evaluation of the parts of the data structure. Slide 17.5.18 Since stream-filter is just a standard procedure, we need to get the values of its arguments. Prime? will simply point to some procedure. (Stream-interval 1 100000000) needs to be evaluated, but we know that stream-interval is defined in terms of consstream. So this returns one of these stream objects, which has the value of the first element, 1, already available, but simply has a promise (shown within that squiggly line) to get the value of the next argument, which is the stream interval from 2 to 100,000,000. At this stage, all that has been explicitly

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology computed is the first value. Everything else is just sitting around as a promise to do some work later Slide 17.5. 19 Having evaluated the two arguments to stream-filter/Decoupling order of evaluation (strearfilter prine (str-in 1 100000000)1 we can now apply that procedure, i.e. evaluate its body. What does that do? It applies the predicate(the first argument )to the first value of the stream(the second argument ). Since in this case I is not prime, stream-filter will return the prime value of the second clause of its if expression. This is a recursive call to stream-filter with the same predicate but now with the stream-cdr of the second argument. This means we should now force that promis etting stream -interval from 2 to 100,000,000 Decoupling order of evaluation Slide 17.5.20 (streanfilter prine, (str-in 1 1000000001) Here is where a potential confusion can arise. It might seem like evaluating the stream-cdr of this stream should cause all the remaining elements of the stream, everything from 2 to 100.000.000. to be evaluated But remember that 工 airfilter prime stream-interval says to do a cons-stream of the first argument onto a promise to get the rest of the value tream-filter prime So in fact it returns another stream object, with the next element in the sequence and another promise to generate the remaining elements. That is what will be supplied to stream- filter Slide 17.5.2 Decoupling order of evaluation So now stream-filter can evaluate its body testing ith its predicate to see if the first element of this stream is a prime. It is, so it returns a cons-stream of the first element of the input stream, which is a 2, and a promise, and here the promise is to do a stream-filter on the remaining things And notice what this stream-filter Iwtream-filter prim is It is a promise to filter using prime on the stream- cdr of the object we started with Thus we now have two delayed promises. We have a promise to do the filter, and inside of it is a promise to generate the rest of the initial stream. Thus we can see that we will only pull out values from the stream as we need them. If we ask for the next element in this stream, we would then force the evaluation of the stream-filter expression which would force the evaluation of the stream -interval expression By hiding the lazy evaluation within the constructor, then building our procedures on top of that abstraction, we can easily enable the separation of the actual order of computation from the apparent order of computation

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. computed is the first value. Everything else is just sitting around as a promise to do some work later. Slide 17.5.19 Having evaluated the two arguments to stream-filter we can now apply that procedure, i.e. evaluate its body. What does that do? It applies the predicate (the first argument) to the first value of the stream (the second argument). Since in this case 1 is not prime, stream-filter will return the value of the second clause of its if expression. This is a recursive call to stream-filter with the same predicate but now with the stream-cdr of the second argument. This means we should now force that promise, getting stream-interval from 2 to 100,000,000. Slide 17.5.20 Here is where a potential confusion can arise. It might seem like evaluating the stream-cdr of this stream should cause all the remaining elements of the stream, everything from 2 to 100,000,000, to be evaluated. But remember that stream-interval says to do a cons-stream of the first argument onto a promise to get the rest of the values. So in fact it returns another stream object, with the next element in the sequence and another promise to generate the remaining elements. That is what will be supplied to streamfilter. Slide 17.5.21 So now stream-filter can evaluate its body, testing with its predicate to see if the first element of this stream is a prime. It is, so it returns a cons-stream of the first element of the input stream, which is a 2, and a promise, and here the promise is to do a stream-filter on the remaining things. And notice what this stream-filter is. It is a promise to filter using prime? on the streamcdr of the object we started with. Thus we now have two delayed promises. We have a promise to do the filter, and inside of it is a promise to generate the rest of the initial stream. Thus we can see that we will only pull out values from the stream as we need them. If we ask for the next element in this stream, we would then force the evaluation of the stream-filter expression, which would force the evaluation of the stream-interval expression. By hiding the lazy evaluation within the constructor, then building our procedures on top of that abstraction, we can easily enable the separation of the actual order of computation from the apparent order of computation

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.5.25 and infinite stream of 1s No matter how many times i ask Result: Infinite Data Structures for the next element of this sequence, I will al ways get a 1 Thus I have a structure that I can conceptualize as representing (streamer (streamer ones))=> 1 an infinite set of things. whenever i ask for some element in this sequence, it will always provide it to me, for any such The nfinite stream of 1sl element ones;111111 Result: Infinite Data Structures Slide 17.5.26 he comparison to Some very interesting behavi his may still seem odd, so let's think ( define oneg(on-t工e品n1oneg)) the standard evaluation model. Let's se that i tried to do stream-car (stream-cdr ones))=>1 ons in place of cons-stream In this cas The nfinite stream of 1'sl I get an error, because cons will evaluate both its arguments ones:111111 before constructing the data structure. Clearly I do not yet have a value for ones, so I can't glue it together with 1. with the lazy evaluation buried inside of streams, I can hold off on getting the value of this variable until I have completed the structure which means the name ones will be bound to something when I go to get its value. Thus lazy evaluation provides the means necessary to enable creation of infinite data structures Slide 17.5.27 Finite list procs turn into infinite stream procs So what does this buy us? Well, this way of thinking about infinite data structures let,'s us think about creating procedures Icon that operate as if the entire data structure were available to us Thus procedures that typically apply to lists can be turned into ar 82) procedures that handle infinite streams. Here is a procedure that (strean-cdr s2)))))) adds together two streams, using the stream data abstraction detine ints eons- stream1(add-st工ea丑 s ones intg》) This should take two infinite streams as input and create an output stream in which the first element is computed by adding together the first elements of the input streams, and is glued onto a promise to add the remaining streams together when demanded Using this idea we can create an infinite data structure of all the integers. We simply cons-stream the first integer, which is 1, onto a promise to add together the stream of ones and the stream of integers Let' s check this out since it seems a bit odd

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.5.25 ... and infinite stream of 1's. No matter how many times I ask for the next element of this sequence, I will always get a 1. Thus I have a structure that I can conceptualize as representing an infinite set of things. Whenever I ask for some element in this sequence, it will always provide it to me, for any such element. Slide 17.5.26 This may still seem odd, so let's think about the comparison to the standard evaluation model. Let's suppose that I tried to do this using cons in place of cons-stream. In this case, I get an error, because cons will evaluate both its arguments before constructing the data structure. Clearly I do not yet have a value for ones, so I can't glue it together with 1. With the lazy evaluation buried inside of streams, I can hold off on getting the value of this variable until I have completed the structure, which means the name ones will be bound to something when I go to get its value. Thus lazy evaluation provides the means necessary to enable creation of infinite data structures. Slide 17.5.27 So what does this buy us? Well, this way of thinking about infinite data structures let's us think about creating procedures that operate as if the entire data structure were available to us. Thus procedures that typically apply to lists can be turned into procedures that handle infinite streams. Here is a procedure that adds together two streams, using the stream data abstraction. This should take two infinite streams as input and create an output stream in which the first element is computed by adding together the first elements of the input streams, and is glued onto a promise to add the remaining streams together when demanded. Using this idea we can create an infinite data structure of all the integers. We simply cons-stream the first integer, which is 1, onto a promise to add together the stream of ones and the stream of integers. Let's check this out, since it seems a bit odd