6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.5.31 Having the ability to create these infinite data structures, suchFinding all the primes as the infinite stream of ones, or the infinite stream of integers, let's us change our way of conceptualizing processes. I particular, remember the sieve that we saw many lectures ago nx13141171920 ZX2223z4E26272829 The Sieve of Erastosthenes said that to find all the primes, start 3132333333738 with the integers beginning at 2, and do the following process 15253豇5675859〖g Take the next integer and include it as a prime. Then remove 61〖234且5虽67689胚 from the remaining set all integers that are divisible by this 71x73I4R677X8790 R828384B868X88890 number. This creates a new set of integers. Now take the next one, include it as a prime, remove any elements in the rest of the sequence th nat are divisible by this element, and continue 4 Remember that when we did this using lists we had to create a list of integers from 1 to some point, and then execute this process to get the first prime plus generate a new list of all the remaining elements not divisible by 2, and so on. At each step, we had to generate a big list of values, only to throw much of it away. With streams, we can rethink this process Remember our sieve? Slide 17.5.32 The idea of infinite data structures let's me create a sieve that is define (sieve str) in fact much cleaner than the list version! as we said. in the list version, I would have to generate the entire list of integers, then lambda (x) filter that to generate another huge list, and so on l trota - dr stb) 2 x (atream-oar tm)) On the other hand, with infinite data structures,I can generate the elements of the lists only as needed. Notice how I can do de1n●px1m· (sieve (stream-cdr ints))) this. I can create a sieve that says: given an input stream ( sieve(filter ints 2)) generate an output stream the first element of which will be the first element of the input stream. The rest of the stream will be a promise: a promise to take the rest of the input stream, filter it to remove anything divisible by the first element of the input stream, and then taking the sieve of that! That is nice, because that sieve will then, when asked to be evaluated, will generate the first element of that filtered stream, plus a promise to sieve again. This means that I will only pull out those elements from this sieve that I need, on demand I can conceptualize the computation as if the entire sequence of elements is available, but only do the computation incrementally as needed Thus, I can define the primes as shown, and this structure will, when asked, compute as many primes as you request Slide 17.5.33 Remember our sieve? Notice, by the way, that this sieve definition does not include a base casel! There is not test for the end of the input stream. But dcone- teca that is okay, because the input streams are infinite and we don't (strear-car str) have to worry about reaching the end. The computation will (lambda (x) simply keep generating more and more promises to get future (stream-odr stx)))) elements as needed. Thus there is no base case, just the def⊥nepx⊥m些s construction of the stream, element by element s⊥eve( stream-cdr⊥nts))6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.5.31 Having the ability to create these infinite data structures, such as the infinite stream of ones, or the infinite stream of integers, let's us change our way of conceptualizing processes. In particular, remember the sieve that we saw many lectures ago. The Sieve of Erastosthenes said that to find all the primes, start with the integers beginning at 2, and do the following process. Take the next integer and include it as a prime. Then remove from the remaining set all integers that are divisible by this number. This creates a new set of integers. Now take the next one, include it as a prime, remove any elements in the rest of the sequence that are divisible by this element, and continue. Remember that when we did this using lists, we had to create a list of integers from 1 to some point, and then execute this process to get the first prime, plus generate a new list of all the remaining elements not divisible by 2, and so on. At each step, we had to generate a big list of values, only to throw much of it away. With streams, we can rethink this process. Slide 17.5.32 The idea of infinite data structures let's me create a sieve that is in fact much cleaner than the list version! As we said, in the list version, I would have to generate the entire list of integers, then filter that to generate another huge list, and so on. On the other hand, with infinite data structures, I can generate the elements of the lists only as needed. Notice how I can do this. I can create a sieve that says: given an input stream, generate an output stream the first element of which will be the first element of the input stream. The rest of the stream will be a promise: a promise to take the rest of the input stream, filter it to remove anything divisible by the first element of the input stream, and then taking the sieve of that! That is nice, because that sieve will then, when asked to be evaluated, will generate the first element of that filtered stream, plus a promise to sieve again. This means that I will only pull out those elements from this sieve that I need, on demand. I can conceptualize the computation as if the entire sequence of elements is available, but only do the computation incrementally as needed. Thus, I can define the primes as shown, and this structure will, when asked, compute as many primes as you request. Slide 17.5.33 Notice, by the way, that this sieve definition does not include a base case! There is not test for the end of the input stream. But that is okay, because the input streams are infinite and we don't have to worry about reaching the end. The computation will simply keep generating more and more promises to get future elements as needed. Thus there is no base case, just the construction of the stream, element by element