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 Streams-a different way of structuring Slide 17.5.2 OR-have each object output a continuous stream of There is a very different way of thinking about such systems however. Rather than having structures that capture state explicitly, I could think about systems in which the state tennis ball being thrown against a set of walls, imagine tha of a information is only there in an implicit way. In my example while doing that action, I also include a set of cameras placed around the edges of the room. These cameras might record the movement of the ball, and thus can capture information about the state of the ball. In particular, imagine that this is happening in a continuous fashion That is. there is a constant stream of information being spewed out that represents the x and y position(for example)of the ball as it moves around the room Slide 17.5.3 Streams-a different way of structuring Under this view, my basic units now become the time series ofcomputation values of the different variables that represent my system. In the information ach object output a continuous stream of earlier version, my basic units were the objects themselves: the State of the simulation captured in the history(or stream)of values ball. the walls and the clock Now, I have changed my viewpoint. I have pulled out the state ables, and declared that my basic unit (or history)of values associated with each state variable. To capture the state of the system at any point, I simply take the values of all of those variables across the same point in time But my units that I want to focus on are the actual stream of values, the time history of values associated with each state
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.5.2 There is a very different way of thinking about such systems, however. Rather than having structures that capture state explicitly, I could think about systems in which the state information is only there in an implicit way. In my example of a tennis ball being thrown against a set of walls, imagine that while doing that action, I also include a set of cameras placed around the edges of the room. These cameras might record the movement of the ball, and thus can capture information about the state of the ball. In particular, imagine that this is happening in a continuous fashion. That is, there is a constant stream of information being spewed out that represents the x and y position (for example) of the ball as it moves around the room. Slide 17.5.3 Under this view, my basic units now become the time series of values of the different variables that represent my system. In the earlier version, my basic units were the objects themselves: the ball, the walls, and the clock. Now, I have changed my viewpoint. I have pulled out the state variables, and declared that my basic units are now the stream (or history) of values associated with each state variable. To capture the state of the system at any point, I simply take the values of all of those variables across the same point in time. But my units that I want to focus on are the actual stream of values, the time history of values associated with each state variable in my 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 © 2004 by Massachusetts Institute of Technology. Slide 17.5.7 So how could we use this idea in our context? We could create a new data abstraction, called a stream. Here is one version of this abstraction. It has a constructor, cons-stream and two selectors, stream-car and stream-cdr. You can see by their names, that we expect them to behave a lot like lists, with one exception. The exception is that we want the second part of the stream to be lazy, or better yet memoized and lazy. 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 to. Here we have represented this in a message passing system. We 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. Slide 17.5.8 A key change is that now I have a way of gluing together a sequence of values in which only the first value is explicitly evaluated when I do the construction of the data object. The second part of this structure is lazy: it is a promise to get the value when asked for, but I don't do the work of computing the value at construction time. Now, what does this do to our thinking about building sequences of values? Slide 17.5.9 A stream object thus looks a lot like a pair, except that the cdr part of the stream is lazy. It is not evaluated until some procedure actually needs its value, but once we have worked out its value, we keep track of it for later reference. Think about what happens now. For example, if I ask x to have the value of a cons-stream of 99 and (/ 1 0) what will happen?
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