6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 17.1 Slide 17.1.1 Normal Order(Lazy) Evaluation Over the past few lectures, we have been looking at evaluation especially how to implement eval and apply in a anguage such as Scheme, in order to define a language. What we have seen is that by creating, or specifying, eval and its associated procedures, we actually define the semantics of the nguage: what it means to determine an expressions value, or to associate meanings with expressions in the language We have also separated the semantics of eval and apply from the syntax of the language, meaning: how we choose to write an expression can be interfaced through a data abstraction 4 into the deduction of meaning associated with the expression In this lecture, we are going to look at variations on Scheme. We are going to explore the idea of how, by making changes, in many cases very small changes, to eval and apply, we can cause the language to behave in a very different fashion. We are going to look at how we gain some benefits(sometimes with a little cost) by making those changes, trading off design issues in the language for performance issues in actually using the language Normal Order(Lazy) Evaluation Slide 17.1.2 To set the stage for what we are about to do let's remind ourselves of what normal scheme does. remem ber that we said Scheme is an applicative order language. That means that wher valuate all arguments then apply operator evaluating a combination, we first evaluate all the arguments, reducing them to actual values, including the first argument, which in our syntax is the operator. We then apply that the values of all the other arguments Thus, we a ppy the operator( the procedure associated with that first argument) procedure to the values Slide 1.1.3 Normal Order(Lazy) Evaluation Now, while we have been accepting that as our method of Alternative models for computation operation in Scheme, in fact it is a design choice. This was a choice made by the creators of Scheme. There is at least one other way of designing the system, called normal order evaluate all arguments, then apply operator evaluation · Normal order In normal order evaluation, we do the following. When given a go ahead and apply operator with unevaluated argument compound expression, we apply the operator(the value of the evaluate a subexpression only when value is needed first subexpression) but to unevaluated argument (that is, primitive procedures ressions. Said another way, when given a compound expression, we can evaluate the first subexpression, but then can simply take the other pieces and substitute them into the
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 17.1 Slide 17.1.1 Over the past few lectures, we have been looking at evaluation, especially how to implement eval and apply in a language such as Scheme, in order to define a language. What we have seen is that by creating, or specifying, eval and its associated procedures, we actually define the semantics of the language: what it means to determine an expression's value, or to associate meanings with expressions in the language. We have also separated the semantics of eval and apply from the syntax of the language, meaning: how we choose to write an expression can be interfaced through a data abstraction into the deduction of meaning associated with the expression. In this lecture, we are going to look at variations on Scheme. We are going to explore the idea of how, by making changes, in many cases very small changes, to eval and apply, we can cause the language to behave in a very different fashion. We are going to look at how we gain some benefits (sometimes with a little cost) by making those changes, trading off design issues in the language for performance issues in actually using the language. Slide 17.1.2 To set the stage for what we are about to do, let's remind ourselves of what normal Scheme does. Remember that we said Scheme is an applicative order language. That means that when evaluating a combination, we first evaluate all the arguments, reducing them to actual values, including the first argument, which in our syntax is the operator. We then apply that operator (the procedure associated with that first argument) to the values of all the other arguments. Thus, we apply the procedure to the values. Slide 17.1.3 Now, while we have been accepting that as our method of operation in Scheme, in fact it is a design choice. This was a choice made by the creators of Scheme. There is at least one other way of designing the system, called normal order evaluation. In normal order evaluation, we do the following. When given a compound expression, we apply the operator (the value of the first subexpression) but to unevaluated argument subexpressions. Said another way, when given a compound expression, we can evaluate the first subexpression, but then can simply take the other pieces and substitute them into the
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology body of the procedure, and continue this process until we actually need the value of one of those subexpressions. In fact, we will evaluate a subexpression only when the value is needed in order to print something out, or because a primitive procedure is going to be applied to it. Thus, primitive procedures will be strict in requiring that their arguments are actual values Thus, normal order evaluation would have a very different substitution model than applicative order evaluation. In essence, we would take the subexpressions, substitute them into the body of the procedure, and keep doing that substitution until we have an expression that involves only primitive procedures and their application Our goal is to understand how that model leads to different evolution of the language, and how might we create ch a Applicative Order Example Slide 17.1. 4 o visualize the difference between these two kinds of 《Mm⊥te-1⊥ne"ins⊥ de foc”) evaluation, let's look at an example. Here is an example using applicative order(the normal kind of Scheme). We define foo (foo (begin (write-line eval arg") 222) to be a procedure as shown what happens if we call foo with the sequence of expressions shown as argument? In standard Scheme. the first thing we do is evaluate each of the (dfin·(f。ox ubexpressions. We get the value of foo, which is a procedure (srite-line "inside Eoo") object. We also evaluate the argument to foo at this stage f。。(beg1n( write-1ne"eva1arg")222)) Evaluating this begin statement leads to the following begin (write-lime eval axg") 222) behavior Applicative Order Example Slide 17.1.6 Evaluating the argument says we must evaluate this begin (write-line inside foo) expression, and therefore we evaluate the first subexpression, <foo (begin (write-line eval arg")222)) which writes out on the screen: eval arg
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. body of the procedure, and continue this process until we actually need the value of one of those subexpressions. In fact, we will evaluate a subexpression only when the value is needed in order to print something out, or because a primitive procedure is going to be applied to it. Thus, primitive procedures will be strict in requiring that their arguments are actual values. Thus, normal order evaluation would have a very different substitution model than applicative order evaluation. In essence, we would take the subexpressions, substitute them into the body of the procedure, and keep doing that substitution until we have an expression that involves only primitive procedures and their application. Our goal is to understand how that model leads to different evolution of the language, and how might we create such a language. Slide 17.1.4 To visualize the difference between these two kinds of evaluation, let's look at an example. Here is an example using applicative order (the normal kind of Scheme). We define foo to be a procedure as shown. What happens if we call foo with the sequence of expressions shown as argument? Slide 17.1.5 In standard Scheme, the first thing we do is evaluate each of the subexpressions. We get the value of foo, which is a procedure object. We also evaluate the argument to foo at this stage. Evaluating this begin statement leads to the following behavior. Slide 17.1.6 Evaluating the argument says we must evaluate this begin expression, and therefore we evaluate the first subexpression, which writes out on the screen: eval arg
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.1.7 We then evaluate the second subexpression in the begin Applicative Order Example expression. Since this is the last subexpression in this begin,I(detine(foo xy write-line inside too") that is the value returned as the value of the argument to foo +xx)) (foo (begin (write-line eval arg")222) : >(begin (writeline "eval arg)222) =>222 Applicative Order Example Slide 17.1.8 So now we apply the procedure named foo to that argument, (write-line inside foo") 222. By the substitution model, that reduces to evaluating the (foo (begin (write-line eval arg") 222)) begin statement shown on the side in blue. We could, of ( begin(wx⊥te-1ine“eva1arq")222 course. use the environment model here but the substitution =>begn(w⊥te-1ine"ins⊥defo。") model is sufficient for our purposes Slide 17.1.9 Applicative Order Example Of course, evaluating this begin expression's subexpressions I in order means we first write out: inside foo: then we te-line " inside foo"> evaluate the actual addition and return the value 444 ￡。。( begin( write-1ine"eva1ag")222)) (begin (write-line eval arg) 222) =>22 => begin《w⊥te-1ine" inside fo。") val arg 444 Applicative Order Example Slide 17.1.10 So lets summarize what we did. We first evaluated the ins⊥defo。" argument, then substituted that value into the body of the procedure. This lead to the observed behavior, as written out f。。( begin《 write-1ne"eva1arg”)222) that we evaluate the argument once, then proceeded inside the ->(begin (write-line Meval arg)222) procedure, then we returned the value. Keep that in mind as we te-1ne"ins⊥defo。") now go to the alternative model substituted value into the body of
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.1.7 We then evaluate the second subexpression in the begin expression. Since this is the last subexpression in this begin, that is the value returned as the value of the argument to foo. Slide 17.1.8 So now we apply the procedure named foo to that argument, 222. By the substitution model, that reduces to evaluating the begin statement shown on the side in blue. We could, of course, use the environment model here, but the substitution model is sufficient for our purposes. Slide 17.1.9 Of course, evaluating this begin expression's subexpressions in order means we first write out: inside foo; then we evaluate the actual addition, and return the value 444. Slide 17.1.10 So let's summarize what we did. We first evaluated the argument, then substituted that value into the body of the procedure. This lead to the observed behavior, as written out, that we evaluate the argument once, then proceeded inside the procedure, then we returned the value. Keep that in mind as we now go to the alternative model
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.1 Now. let's think about the alternative model. this is a normal N。 rmal Order Example rder model. in which we ng to first evaluate tl procedure subexpression to get the procedure, but then the write-line inside foo") arguments we are going to substitute into the body of that va1arg")222)) procedure, and keep unwinding the evaluations until we get down to things that either involve printing or application of primitive procedures. Same definition of foo, same call, but is there a different behavior? Normal order Example Slide 17.1.12 dene(f。x In this case, we get the value associated with foo, but we (write-line inside foo") substitute the entire argument into the body of foo without foo (begin (write-line eval arg") 222)) evaluation. This leads to the evaluation of the begin (begin (write-line" de too") (+(begin (w-1 " eval azg") 222) expression shown on the slide. Notice that no evaluation of the egin (w-l " eval arg") 222))) argument has taken place yet, just substitution of tree structure Thus, nothing has been printed out on the screen yet Slide 17. .13 Normal Order Example In this case, we evaluate the subexpressions to the top -level begin in order. Thus we first evaluate the line that says we te-line " inside foo"> re inside foo, which gets printed out as shown ￡。。( begin( write-1ine"eva1ag")222)) begin《w-1meva1axg Normal order Example Then, we turn to the next subexpression inside the top-level ins⊥defo。" begin. Here we evaluate the first subexpression of this (write-line combination, namely +. This has as a value a primitive procedure. So in this case, we need to actually evaluate the (begin (w-l eval arg)222)) argument expressions; there is no further substitution possible hus we evaluate the first of the two interior begin statements,which writes out eval arg; then gets the value of 222 and returns it to
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.1.11 Now, let's think about the alternative model. This is a normal order model, in which we are going to first evaluate the procedure subexpression to get the procedure, but then the arguments we are going to substitute into the body of that procedure, and keep unwinding the evaluations until we get down to things that either involve printing or application of primitive procedures. Same definition of foo, same call, but is there a different behavior? Slide 17.1.12 In this case, we get the value associated with foo, but we substitute the entire argument into the body of foo without evaluation. This leads to the evaluation of the begin expression shown on the slide. Notice that no evaluation of the argument has taken place yet, just substitution of tree structure. Thus, nothing has been printed out on the screen yet. Slide 17.1.13 In this case, we evaluate the subexpressions to the top-level begin in order. Thus we first evaluate the line that says we are inside foo, which gets printed out as shown. Slide 17.1.14 Then, we turn to the next subexpression inside the top-level begin. Here we evaluate the first subexpression of this combination, namely +. This has as a value a primitive procedure. So in this case, we need to actually evaluate the argument expressions; there is no further substitution possible. Thus we evaluate the first of the two interior begin statements, which writes out: eval arg; then gets the value of 222 and returns it to +
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.1.15 Then, do the same thing for the second interior begin N。 rmal Order Example expression, since is a primitive procedure and requires its write-line inside too") arguments be evaluated +xx)) (foo (begin (write-line eval arg")222) +(begin (w-l eval arg")222 egin (w-l eval arg") 222)) ev滴1画E Normal order Example Slide 17.1.16 dene(f。x hen actually apply the primitive procedure to the arguments, (write-line inside foo") and return the value foo (begin (write-line eval arg") 222)) a>(begin (writo-line de too") egin (w-l eval arg") ⊥ns⊥ de toc Slide 1.1.17 Normal Order Example So now we see there is a difference in behavior remember in the applicative order case, we noted that we first evaluated the te-line " inside foo"> argument(once)and then we went inside the procedure Here, it's as if we substituted the unevaluated arguments into f。。( begin( write-1ine"eva1arg")222)) the body of the procedure. Thus we first went inside the a> (begin (write-line "inside foo") procedure, then when required by a primitive procedure, we w-l eval arg") 22 evaluate the argument. And since it has been substituted twice into the body, we evaluate it twice body of the procedure Our goal then is to note that normal order has a different behavior: substitute until required to evaluate. Applicative was get value, then substitute. So why is this a useful change to make? And how do we change our evaluator to achieve normal der evolution 6.001 Notes: Section 17.2
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.1.15 Then, do the same thing for the second interior begin expression, since + is a primitive procedure and requires its arguments be evaluated. Slide 17.1.16 Then actually apply the primitive procedure to the arguments, and return the value. Slide 17.1.17 So now we see there is a difference in behavior. Remember in the applicative order case, we noted that we first evaluated the argument (once) and then we went inside the procedure. Here, it’s as if we substituted the unevaluated arguments into the body of the procedure. Thus we first went inside the procedure, then when required by a primitive procedure, we evaluate the argument. And since it has been substituted twice into the body, we evaluate it twice. Our goal then is to note that normal order has a different behavior: substitute until required to evaluate. Applicative was: get value, then substitute. So why is this a useful change to make? And how do we change our evaluator to achieve normal order evolution. 6.001 Notes: Section 17.2
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.2.1 Let's deal with the second issue first. What changes should we How can we implement lazy evaluation? make to eval and app ly in order to implement this new (define (l-apply procedure arguments env) i changed (cond ((primiti ve-procedure? procedure) idea of normal order evaluation(sometimes also called lazy pply-primitive-procedure evaluation). Note that it is called lazy evaluation because we (Iist-of-arg-values argunents env))) are only evaluating arguments when required, either because we ((compound-procedure? procedure) need to print them out or because we are down to primitive (procedure-body procedure procedures. So what changes are needed? 1t一E-de1ayd- arga ar e1器e《 error" Unknown proc" procedure))) How can we implement lazy evaluation? Slide 17.2.2 changed Let's start with the application of a compound procedure (cond ((primitive-procedure? procedure) something we have built with a lambda. We know we want to evaluate the body of that procedure in a new environment (list-of-arg-valuesargumentsenv))) ((compound-procedure? procedure) but what should the environment do? Extend- environment should take the set of parameters of the (extend-environrent (procedure ocedure) procedure, but glue together with them, not with the actual values, but with a set of delayed arguments. And what is a rocedure-environment procedure)))) (e1器e《eror" Unknown proc"pr delayed argument? Let's create a structure that let's us hold off on getting the actual value of an argument. That makes if you think of our example. When we want to apply a procedure we want to take the argument expressions and substitute them into the body without evaluation, but as unevaluated tree structure So our change in apply ing a compound procedure is to still evaluate the body of the procedure in a new environment, but rather than binding the procedure's parameters to their actual values, we will bind them to these pecial structures that keep track of the expression to be evaluated when required, plus we will have to keep track of the environment in which that evaluation should take place when required Slide 17.2.3 How can we im plement lazy evaluation? That last point is worth stressing, because it is a change. Prior (define (I-apply procedure arguments changed to this, apply didn t need to know about it's environment spply-prinitive-procedure We simply applied a procedure to a set of argument values Here, because we delay getting the argument values, we need to arguments env))) keep track of the information needed to actually compute the alues when needed. meaning the environment in which the expression should be evaluated Thus we need to pass the environment in as an argument to app l y so that we can pass procedure-env⊥ conment pr。ee (e1器e( error" Unknown proc"pro。 edure))) through to the construction of the delayed evaluation objects
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.2.1 Let's deal with the second issue first. What changes should we make to eval and apply in order to implement this new idea of normal order evaluation (sometimes also called lazy evaluation). Note that it is called lazy evaluation because we are only evaluating arguments when required, either because we need to print them out or because we are down to primitive procedures. So what changes are needed? Slide 17.2.2 Let's start with the application of a compound procedure, something we have built with a lambda. We know we want to evaluate the body of that procedure in a new environment, but what should the environment do? Extendenvironment should take the set of parameters of the procedure, but glue together with them, not with the actual values, but with a set of delayed arguments. And what is a delayed argument? Let’s create a structure that let's us hold off on getting the actual value of an argument. That makes sense if you think of our example. When we want to apply a procedure, we want to take the argument expressions and substitute them into the body without evaluation, but as unevaluated tree structure. So our change in applying a compound procedure is to still evaluate the body of the procedure in a new environment, but rather than binding the procedure's parameters to their actual values, we will bind them to these special structures that keep track of the expression to be evaluated when required, plus we will have to keep track of the environment in which that evaluation should take place, when required. Slide 17.2.3 That last point is worth stressing, because it is a change. Prior to this, apply didn't need to know about it's environment. We simply applied a procedure to a set of argument values. Here, because we delay getting the argument values, we need to keep track of the information needed to actually compute the values when needed, meaning the environment in which the expression should be evaluated. Thus we need to pass the environment in as an argument to apply so that we can pass it through to the construction of the delayed evaluation objects
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.2.4 How can we implement lazy evaluation? So with this change, compound procedure application will define (l-apply procedure arguments Env: changed correctly delay the evaluation of the arguments. We will cond ((primitive-procedure? procedur apply-primitive-procedure implement list-of-delayed-arguments shortly. Conceptually, we know that it should simply take a list ((conpound -procedure? procedure of expressions, and glue onto these expressions a marker that dentifies them as delayed Ultimately, however, we will red ce to a primit else (error Unknown proc procedure))) the arguments applying a primitive procedure, we need to ensure that the I arguments are reduced to actual values. This means we will force any delayed evaluation to now take place. Here again we will need to pass the environment into the procedure list-of-arg-values because we are going to have to walk our way down this list of expressions, asking each to be evaluated with respect to the environment Slide 17.2.5 How can we implement lazy evaluation? Notice that we have made only a small number of chang (define (I-apply proc app ly now takes an environment as an argument (primitive-procedure? procedure) (apply-prinitive-procedure application of a compound procedure constructs a set of delayed expressions; and application of a primitive procedure cedar constructs a set of actual values by evaluating any delayed argument. We have to implement the procedures to delay and (procedure-body procedure) force evaluation, but otherwise we have a very small set of anges (procedure-environment procedur e1器e《 error" Unknown proc"pr。 cedure)) Slide 17.2.6 Most of the work is in l-apply need to call it with What else do we have to change? Since we have changed actual value for the operato apply (which we here call l-apply for lazy apply),we need to change the use of that procedure in eval(which we fine (l-eval exp er here call I-eval). But in fact most of the work is now in l cond((≡。1f-va1 latina?exp)·xp) app ly. Here we call it with the actual value of the operator, ((app1⊥ea but just the expressions for the other arguments, plus the environment (e1器e《 errOr" Unknowm expression”exp)))) So our change to l-eval is very simple. When we get to an application, we pass the actual value of the operator(which ))to l-apply But notice that we just pass in the other expressions as tree structure, with no evaluation Notice that this is the only change to l-eval. All other expressions are still handled exactly as before Also notice that when app ly takes in these arguments, it may further pass the delayed arguments along unevaluated(if the application involves another compound expression ). Only when app l y reaches a primitive application will it force the arguments to be evaluated
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.2.4 So with this change, compound procedure application will correctly delay the evaluation of the arguments. We will implement list-of-delayed-arguments shortly. Conceptually, we know that it should simply take a list of expressions, and glue onto these expressions a marker that identifies them as delayed. Ultimately, however, we will reduce to a primitive application, and in that case, we want to do the actual work of evaluating the arguments. Thus, our other change will be to require when applying a primitive procedure, we need to ensure that the arguments are reduced to actual values. This means we will force any delayed evaluation to now take place. Here again we will need to pass the environment into the procedure list-of-arg-values because we are going to have to walk our way down this list of expressions, asking each to be evaluated with respect to the environment. Slide 17.2.5 Notice that we have made only a small number of changes: apply now takes an environment as an argument; application of a compound procedure constructs a set of delayed expressions; and application of a primitive procedure constructs a set of actual values by evaluating any delayed argument. We have to implement the procedures to delay and force evaluation, but otherwise we have a very small set of changes. Slide 17.2.6 What else do we have to change? Since we have changed apply (which we here call l-apply for lazy apply), we need to change the use of that procedure in eval (which we here call l-eval). But in fact most of the work is now in lapply. Here we call it with the actual value of the operator, but just the expressions for the other arguments, plus the environment. So our change to l-eval is very simple. When we get to an application, we pass the actual value of the operator (which means we need to be sure to do the evaluation) to l-apply. But notice that we just pass in the other expressions as tree structure, with no evaluation. Notice that this is the only change to l-eval. All other expressions are still handled exactly as before. Also notice that when apply takes in these arguments, it may further pass the delayed arguments along unevaluated (if the application involves another compound expression). Only when apply reaches a primitive application will it force the arguments to be evaluated
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.2.7 What else do we need? Notice that we have now made a Actual VS Delayed values distinction between getting the actual value of expressions, versus simply delaying the evaluation of an expression. We need values for operators, and for primitive applications only But this means we now have two different kinds of values the actual value of the expression, versus a promise to get the value when asked for it. We need to implement those two kinds of values which we do next Actual vs Delayed valt Slide 17.2.8 First, to get the actual value of an expression with respect to an (force-it (I-eval exp env))) environment, we would expect to see a use of l-evalWe can see that inside of this procedure. But notice that evaluating that expression might itself return a delayed object. If it is a nested combination of procedures, for instance, evaluating the first level may give us back something that is still a delayed promise to get a value. So we will add one more piece. We will add a procedure called force-it, which takes argument and ensures that it is fully evaluated and not delayed hus,actual-value of an expressions will evaluate any delayed expression, and ensure that the returned value is not delayed but fully evaluated Slide 17.2.9 Actual VS Delayed values As we saw we will use actual-value inside 1 eval to get the value of the procedure. We do that because force-it (l-eval exp env))) we need to know whether the procedure is primitive or compound, in order to keep unwrapping the substitution of Cons (actual-value (first-oporand o (1t-。f- arg-va1 st-operands exps unevaluated arguments into the bodies of procedures We also need to use actual-value when a primitive pplication requires an actual set of values. Thus, list-of- arg-values should take a set of expressions and an environment, and should recursively evaluate all of the expressions in that environment. Note how we just construct a list using recursive evaluation, but here using actual-value to ensure that evaluation of the expression completely unwinds any delayed objects
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.2.7 What else do we need? Notice that we have now made a distinction between getting the actual value of expressions, versus simply delaying the evaluation of an expression. We need values for operators, and for primitive applications only. But this means we now have two different kinds of values: the actual value of the expression, versus a promise to get the value when asked for it. We need to implement those two kinds of values, which we do next. Slide 17.2.8 First, to get the actual value of an expression with respect to an environment, we would expect to see a use of l-eval. We can see that inside of this procedure. But notice that evaluating that expression might itself return a delayed object. If it is a nested combination of procedures, for instance, evaluating the first level may give us back something that is still a delayed promise to get a value. So we will add one more piece. We will add a procedure called force-it, which takes an argument and ensures that it is fully evaluated, and not delayed. Thus, actual-value of an expressions will evaluate any delayed expression, and ensure that the returned value is not delayed, but fully evaluated. Slide 17.2.9 As we saw, we will use actual-value inside leval to get the value of the procedure. We do that because we need to know whether the procedure is primitive or compound, in order to keep unwrapping the substitution of unevaluated arguments into the bodies of procedures. We also need to use actual-value when a primitive application requires an actual set of values. Thus, list-ofarg-values should take a set of expressions and an environment, and should recursively evaluate all of the expressions in that environment. Note how we just construct a list using recursive evaluation, but here using actual-value to ensure that evaluation of the expression completely unwinds any delayed objects
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Actual VS Delayed values On the other hand, if we are applying a compound procedure to (force-it (l-eval exp env))) a set of arguments, we want to just take the argument expressions and substitute them directly into the body. But we define(1⊥gt。-Eq exps env) need to label them as something that is a delayed evaluation (1玉t。f-】 (rest-operands exp ist-of-delayed-args does exactly the opposite of list-of-arg-values It walks down the list of define expressions and glues a label onto each expression, creating a by) ends empe) promise for each expression to do the evaluation when required, where the promise consists of the tree structure of the I expression and the environment in which to ultimately do the evaluation, assembled together in some data structure Slide 17.2.ll alues Notice, these are the only changes we need to make to eval (define (actual-value exp env and apply to implement lazy evaluation, so let,'s recap what (force -it (l-eval exp env))) we have done. App ly of a primitive procedure gets the actual values of the arguments by forcing delayed expressions ( cons (actual-value (first-oporand xps) onv) 1⊥st-of App l y of a compound procedure delays the evaluation of all tine (list-or-del ayed -args expa env) other arguments. eval simply evaluates the first cons (delay-it (first-operand exps) env) subexpression of an application to get the procedure, but passes list-of-delayed-args (rest-operands exps) the rest of the arguments along as delayed, unevaluated objects These will get forced into evaluation when a primitive application takes places All that is left is to implement the data abstraction for delayed objects and the operation of forcing such objects Representing Thunks Slide 17.2.12 Abstractly-a thunk is a promise"to return a value wh For historical reasons, we call one of these delayed things, one later needed(forced") of these promises to do an evaluation, a thunk. abstractly, a thunk is simply a promise to return a value when it is needed, i.e. when it is forced. Thus, inside a thunk, we need to represent the actual expression as tree structure, the environment that will serve as the context for interpreting symbols within the expression, and a label identifying this thing as a thunk
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.2.10 On the other hand, if we are applying a compound procedure to a set of arguments, we want to just take the argument expressions and substitute them directly into the body. But we need to label them as something that is a delayed evaluation. List-of-delayed-args does exactly the opposite of list-of-arg-values. It walks down the list of expressions and glues a label onto each expression, creating a promise for each expression to do the evaluation when required, where the promise consists of the tree structure of the expression and the environment in which to ultimately do the evaluation, assembled together in some data structure. Slide 17.2.11 Notice, these are the only changes we need to make to eval and apply to implement lazy evaluation, so let's recap what we have done. Apply of a primitive procedure gets the actual values of the arguments by forcing delayed expressions. Apply of a compound procedure delays the evaluation of all other arguments. Eval simply evaluates the first subexpression of an application to get the procedure, but passes the rest of the arguments along as delayed, unevaluated objects. These will get forced into evaluation when a primitive application takes places. All that is left is to implement the data abstraction for delayed objects and the operation of forcing such objects. Slide 17.2.12 For historical reasons, we call one of these delayed things, one of these promises to do an evaluation, a thunk. Abstractly, a thunk is simply a promise to return a value when it is needed, i.e. when it is forced. Thus, inside a thunk, we need to represent the actual expression as tree structure, the environment that will serve as the context for interpreting symbols within the expression, and a label identifying this thing as a thunk
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.2.13 To actually implement this, we can just build this as a"tagged"Representing Thunks structure: a list with the label of a thunk, plus a pointer to the Abstractly-a thunk is a promise"to return a value when tree structure of the expression, plus a pointer to the later needed (forced environment Thunks-delay-it and force-it Slide 17.2.14 (define (delay-it exp env)(list thunk exp errv)) With that in mind, we can now implement this idea. Delay define (thunk? ob])(tagged-list? ob] *thunk)) just constructs this tagged list. Remember that since exp (define (thunk-ermv thunk) (cadd thunk) just passed in as list structure from the parser, it is just glued together into new list structure, without evaluation. As with any data abstraction, we have a predicate for identifying a thunk and selectors for getting out the parts of the thunk, the expression and the environment in which to evaluate the expressIon. Slide 17.2.15 Thunks-delay-it and force-it The corresponding piece is that when given a thunk, we can (define (delay-it exp env) (list force it to be evaluated. Here. we can be careful. We will first (thunk? ob])(tagged-list check to see if the object is a delayed thing. If it is not a thunk define (thunk-exp thunk) (cadr ti (define (thunk-errv thunk)(caddo thu then we know that this is already reduced to a value, and we simply pass it along. This is exactly why we put the label on the(d tane (trunk?t b3) object in the first place, allowing us to distinguish between tree (actual-val ue (thunk-exp obj) (thunk-ermv obj))) structure that is part of the data structure being manipulated and (el se ob]))) tree structure that represents something waiting to be evaluated On the other hand, if this is a thunk, then we extract the parts of the thunk(expression and environment), and then we do the actual evaluation by applying actual-value (which we know will force the evaluation of this expression ) Notice as a consequence that if ob] on first evaluation reduces to another delayed thing, actual-value will continue to force it, until a value is returned not a delayed
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.2.13 To actually implement this, we can just build this as a "tagged" structure: a list with the label of a thunk, plus a pointer to the tree structure of the expression, plus a pointer to the environment. Slide 17.2.14 With that in mind, we can now implement this idea. Delay just constructs this tagged list. Remember that since exp is just passed in as list structure from the parser, it is just glued together into new list structure, without evaluation. As with any data abstraction, we have a predicate for identifying a thunk, and selectors for getting out the parts of the thunk, the expression and the environment in which to evaluate the expression. Slide 17.2.15 The corresponding piece is that when given a thunk, we can force it to be evaluated. Here, we can be careful. We will first check to see if the object is a delayed thing. If it is not a thunk, then we know that this is already reduced to a value, and we simply pass it along. This is exactly why we put the label on the object in the first place, allowing us to distinguish between tree structure that is part of the data structure being manipulated and tree structure that represents something waiting to be evaluated. On the other hand, if this is a thunk, then we extract the parts of the thunk (expression and environment), and then we do the actual evaluation by applying actual-value (which we know will force the evaluation of this expression). Notice as a consequence that if obj on first evaluation reduces to another delayed thing, actual-value will continue to force it, until a value is returned not a delayed object
