《Structure and Interpretation of Computer Programs》lecture 21 webhan

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