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