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 simulation6.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