6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.2.16 Thunks-delay-it and force-it So there are the changes. Very simple changes to our evaluator delay-it exp env) (,thunk exp em)) have allowed us to build something that does lazy evaluation thunk? obj)(tagged-list thunk) define (thunk-exp cadr th We made a small change to apply, we made a small change (define (thunk-emv thunk)(cadd thunk )) to eval, we introduced one new kind of thing, a delayed (define (force-it obj) eond(( thunk?。b) object or thunk, but thats it. Thus we have a dramatic change in (actual-val behavior based on a small change in the evaluator 6.001 Notes: Section 17.3 Slide 17.3.1 Memo-izing evaluation So what have we accomplished to this point? We have converted our standard evaluator, our applicative order evaluator. into a normal order evaluator. and to do that we had to make only a small number of changes in the evaluator itself. However, we did need to introduce a couple of new things. The primary one was this idea of a delayed object the idea of taking an expression, plus the environment in which it is to be evaluated, and sticking them together into a promise, a thunk, that says: " I am not going to evaluate myself now, but when you ask me for my value, I will give it to you. We use that to delay evaluation of any of the arguments to procedure applications, until we get down to things that need to be printed or to applications of primitive procedures evaluation Slide 17.3.2 In lazy evaluation, if se an argument, have te One consequence of using these delayed objects as part of our reevaluate each time lazy evaluation is that we end up doing, at least at present, some In normal evaluation, argument is evaluated once, and just extra work. If you go back to our earlier example, when we Can we keep track of values once we've obtained the compared normal order and applicative order using the foo and avoid cost of reevaluation? procedure, you will see that in lazy evaluation, if we used the same argument multiple places inside a procedure body we had to re-evaluate it each time. If this is an expensive computation we could be wasting a lot of effort On the other hand, in applicative order evaluation, we evaluated he argument once, and then simply used it, or referenced it as part of the environment, inside the body of the procedure. So we trade this off? Is there some way of keeping track of values once we have forced a delayed object, in order avoid the cost of re-evaluation?6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.2.16 So there are the changes. Very simple changes to our evaluator have allowed us to build something that does lazy evaluation. We made a small change to apply, we made a small change to eval, we introduced one new kind of thing, a delayed object or thunk, but that's it. Thus we have a dramatic change in behavior based on a small change in the evaluator. 6.001 Notes: Section 17.3 Slide 17.3.1 So what have we accomplished to this point? We have converted our standard evaluator, our applicative order evaluator, into a normal order evaluator. And to do that we had to make only a small number of changes in the evaluator itself. However, we did need to introduce a couple of new things. The primary one was this idea of a delayed object: the idea of taking an expression, plus the environment in which it is to be evaluated, and sticking them together into a promise, a thunk, that says: "I am not going to evaluate myself now, but when you ask me for my value, I will give it to you". We use that to delay evaluation of any of the arguments to procedure applications, until we get down to things that need to be printed or to applications of primitive procedures. Slide 17.3.2 One consequence of using these delayed objects as part of our lazy evaluation is that we end up doing, at least at present, some extra work. If you go back to our earlier example, when we compared normal order and applicative order using the foo procedure, you will see that in lazy evaluation, if we used the same argument multiple places inside a procedure body, we had to re-evaluate it each time. If this is an expensive computation, we could be wasting a lot of effort. On the other hand, in applicative order evaluation, we evaluated the argument once, and then simply used it, or referenced it as part of the environment, inside the body of the procedure. So can we trade this off? Is there some way of keeping track of values once we have forced a delayed object, in order to avoid the cost of re-evaluation?