6.001 Structure and Interpretation of Computer Programs. Copyright C 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 12.3 12.3.1 luse this is the central part of the environment model, let's look in very painful detail at an example of an evaluation. In (square 4)I g particular, let's look at the evaluation of (square 4)with x;10 respect to the global environment. Here is the structure we start with. Assume that x has already been bound to the value 4 by some define expression in the environment, and that we ameters have created the definition of square as we just saw, it is body (* xx) pointing to the indicated procedure object Now we want to see is how the rules for the environment model tell us how to get the value associated with squaring 4 in 6001 SICP this environment
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 12.3 Slide 12.3.1 Because this is the central part of the environment model, let's look in very painful detail at an example of an evaluation. In particular, let's look at the evaluation of (square 4) with respect to the global environment. Here is the structure we start with. Assume that x has already been bound to the value 4 by some define expression in the environment, and that we have created the definition of square as we just saw, it is pointing to the indicated procedure object. Now, we want to see is how the rules for the environment model tell us how to get the value associated with squaring 4 in this environment
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3.2 (square 4)I This is a compound expression, so first we have to get the values of the subexpressions with respect to the same environment. 4 is easy to evaluate, it's just 4. We also need to get the value of s quare with respect to the global environment square G Slide 12.3.3 and that just comes from applying the name rule We look (square 4)I gE up the binding for square in this environment, and it simply points to that double bubble as shown. square I GE==># [pro (square 4)I gE Slide 12.3. 4 Aha! We are applying a procedure, one of those double m一- bubbles, to a set of arguments, so our four-step rule now comes into play. Step one: create a new frame, lets call it A ” square >#[pr。c] 4 Slide 12.3.5 (square 4)I gg Step two: convert that frame into an environment, by having its enclosing environment pointer point to the same environment as the environment pointer of the procedure object square 600Sc
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.2 This is a compound expression, so first we have to get the values of the subexpressions with respect to the same environment. 4 is easy to evaluate, it's just 4. We also need to get the value of square with respect to the global environment. Slide 12.3.3 ... and that just comes from applying the name rule. We look up the binding for square in this environment, and it simply points to that double bubble as shown. Slide 12.3.4 Aha! We are applying a procedure, one of those double bubbles, to a set of arguments, so our four-step rule now comes into play. Step one: create a new frame, lets call it A. Slide 12.3.5 Step two: convert that frame into an environment, by having its enclosing environment pointer point to the same environment as the environment pointer of the procedure object
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3.6 (square 4)I In fact, we can create a nice notation to keep track of this. I can link these two pointers together, to indicate that the enclosing environment of frame A comes from the application of the indicated procedure object square >#lproc] Slide 12.3.7 Step three: take the formal parameters of the procedure object (square 4)I gE eing applied, in this case X, and bind them within that new frame to the corresponding procedure argument values, in this case 4 boy:(kxx)④ square I GE==># [pro (square 4)I gE Slide 123.8 Now, with respect to that new environment, El, evaluate the m一一 body of the procedure being applied. So notice, evaluating (square 4) with respect to one environment, has reduced to evaluating a simpler expression, ( xx), with espect to a new environment - square >#[ ( 2 *)el Slide 12.3.9 (square 4)I Now the same rules apply as before. This is a compound expression, so we need to get the values of the subexpressions ith respect to El. We start by getting the value of x with square respect to el square I ge==># [proc] 46053
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.6 In fact, we can create a nice notation to keep track of this. I can link these two pointers together, to indicate that the enclosing environment of Frame A comes from the application of the indicated procedure object. Slide 12.3.7 Step three: take the formal parameters of the procedure object being applied, in this case x, and bind them within that new frame to the corresponding procedure argument values, in this case 4. Slide 12.3.8 Now, with respect to that new environment, E1, evaluate the body of the procedure being applied. So notice, evaluating (square 4) with respect to one environment, has reduced to evaluating a simpler expression, (* x x), with respect to a new environment. Slide 12.3.9 Now the same rules apply as before. This is a compound expression, so we need to get the values of the subexpressions with respect to E1. We start by getting the value of * with respect to E1
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3.10 (square 4)I Well. certainly doesn, t have a binding in the first frame of El. That frame came from the application of the procedure *: # prim object, and only formal parameters of the procedure are bound there. So our rule says to go up the enclosing environment pointer to the global environment and look for a binding in that environment We didn,'t tell you this, but in fact the global environment square >#lproc] creates a bindings for all the built-in procedures. Thus, is bound to the primitive multiplication procedure in that environment. Thus, our name rule looks up the value associated J with * and returns a pointer to this primitive procedure Slide 12.3.11 (square 4)I So in this case we do get a value associated with x *: #[prim] square: parameters: x square I GE==># [proc] (square 4)I gE Slide 12.3.12 Remember where we were. We were getting the values of the Ge=quare: N subexpressions of(* xx)with respect to El. We have the * #I prim] value of the first subexpression, so what about the value ofx with respect to El? This is just the name rule, so starting in El look for a binding of this variable. Of course, we find such a body (*x) binding in the first frame of el, so we get back the value square I GE ==># [proc] associated with x in that frame *n -> #[prim x
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.10 Well ... * certainly doesn't have a binding in the first frame of E1. That frame came from the application of the procedure object, and only formal parameters of the procedure are bound there. So our rule says to go up the enclosing environment pointer to the global environment and look for a binding in that environment. We didn't tell you this, but in fact the global environment creates a bindings for all the built-in procedures. Thus, * is bound to the primitive multiplication procedure in that environment. Thus, our name rule looks up the value associated with * and returns a pointer to this primitive procedure. Slide 12.3.11 So in this case we do get a value associated with *. Slide 12.3.12 Remember where we were. We were getting the values of the subexpressions of (* x x) with respect to E1. We have the value of the first subexpression, so what about the value of x with respect to E1? This is just the name rule, so starting in E1, look for a binding of this variable. Of course, we find such a binding in the first frame of E1, so we get back the value associated with x in that frame
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3.13 In particular, we get back the value 4. Not the value 10 to (square 4)I gE which x is bound in the global environment! Remember we start in the first frame of El looking for a binding for this * #[prim] square variable. Since there is such a binding. it shadows the other binding in the global environment body (*x x:4 ( 3 *)E1 lg=>4 (square 4)I gE Slide 12.3.14 s pre We get the value of th x;10 econd x in the same way. Thus we are left with the application *: #[prim] a primitive procedure to numbers. This just returns t the value 16, which is the value of the last expression in the body of the procedure being applied. Thus, this is the value returned for the x:4 entire expression square I GE ==>#[proc] Although this was a long example, step back to notice how the >16 mechanistic rules of the environment model simply tell us how |1=>#[prim] lg=>4 to trace the evaluation of an expression with respect to an I environment, reducing it to simpler expressions Slide 12.3.15 Example: inc-square Now, let's be slightly more daring! Having seen the application of a simple procedure like square, let,'s look at something GE-anc-square that involves a little more work. In particular, let,'s assume that we have defined square and inc-square, as shown in this environment structure P: 2 b: (* I x) b:(+1《 square y)) (define square (lambda (x)(*x x)))I (define ing-square (lambda (y)(+ 1 (square y)))I Example contd: (inc-square 4)I ge Slide 12.3.16 So lets evaluate (inc-square 4) with respect to the inc-square global environment, and here is the environment structure corresponding to that environment
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.13 In particular, we get back the value 4. Not the value 10 to which x is bound in the global environment! Remember we start in the first frame of E1 looking for a binding for this variable. Since there is such a binding, it shadows the other binding in the global environment. Slide 12.3.14 And now we complete this process. We get the value of the second x in the same way. Thus we are left with the application of a primitive procedure to numbers. This just returns the value 16, which is the value of the last expression in the body of the procedure being applied. Thus, this is the value returned for the entire expression. Although this was a long example, step back to notice how the mechanistic rules of the environment model simply tell us how to trace the evaluation of an expression with respect to an environment, reducing it to simpler expressions. Slide 12.3.15 Now, let's be slightly more daring! Having seen the application of a simple procedure like square, let's look at something that involves a little more work. In particular, let's assume that we have defined square and inc-square, as shown in this environment structure. Slide 12.3.16 So lets evaluate (inc-square 4) with respect to the global environment, and here is the environment structure corresponding to that environment
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3.17 name rule, is just the double bubble pointed to by that variableo mple cont d: (inc-square 4)I Ge As in the previous case, this is a compound expression need to first evaluate the subexpressions with respect to same environment. The value of inc-square, by tnc-square b:*xx)B:+1 (square y)) Example contd: (inc-square 4)I gE Slide 12.3.18 And as we saw before, our four-step rule kicks in. Step one: csquare: create a fram P: Y b:(*xx)b:(+1 inc-square I Er=>#Icompound-proe..I 6001 SIC specified by the procedure that is being appll vironment g/Example cont d: (ing-square 4)I Slide 12.3.19 Step two: turn it into an environment, by having the encloser environment pointer of the frame point to the env 1 inc-squareg Example contd: (inc-square 4)I gE Slide 12.3.20 and that we know is specified by the second part of the double bubble of the procedure being used (square y)) ind-square I cr >#Icompound-proc ..I
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.17 As in the previous case, this is a compound expression, so we need to first evaluate the subexpressions with respect to the same environment. The value of inc-square, by the name rule, is just the double bubble pointed to by that variable. Slide 12.3.18 And as we saw before, our four-step rule kicks in. Step one: create a frame. Slide 12.3.19 Step two: turn it into an environment, by having the enclosing environment pointer of the frame point to the environment specified by the procedure that is being applied... Slide 12.3.20 ... and that we know is specified by the second part of the double bubble of the procedure being used
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3.21 Step three: take the formal parameter of this procedure and Example cont'd: (inc-square 4)I create a binding for it in the new frame to the value of the argument passed in tnc-square (square y)) Example contd: (inc-square 4)I gE Slide 12.3. 22 Step four: take the body of that procedure object and evaluate csquare: it with respect to this new environment, that is, ( 1 (square y)) with respect to E1 P: Y b:(*xx)b:(+1 (square y)) inc-square I Er=>#Icompound-proe..I ( 1 (square y))Ie 6001 SIC Slide 12.3.23 Again. notice how we have reduced the evaluation of one Example cont'd: (inc-square 4)I gE compound expression with respect to one environment to the Ge-ine-gquare evaluation of a simpler compound expression with respect to another environment As before, to evaluate this compound expression, we first need a the values of the subexpressions. The value of with respect top: chain from El to the global environment to get the primitive ?t b:(*xx b:(+1 El is determined by the name rule, chasing up the environmen (square y)) ine-square I G #[compound-pro ddition operation. The value of l is just a self-evaluation rule ( 1(square y))El 排【prim Example contd: (inc-square 4)I gE Slide 12.3.24 So all we have left to do is get the value of (square y) with respect to E1. This is again a compound expression,being evaluated with respect to this new environment b: (* xx) ind-square I cr >#Icompound-proc ..I quare y))I +|=>#[pxim El
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.21 Step three: take the formal parameter of this procedure and create a binding for it in the new frame, to the value of the argument passed in. Slide 12.3.22 Step four: take the body of that procedure object and evaluate it with respect to this new environment, that is, (+ 1 (square y)) with respect to E1. Slide 12.3.23 Again, notice how we have reduced the evaluation of one compound expression with respect to one environment to the evaluation of a simpler compound expression with respect to another environment. As before, to evaluate this compound expression, we first need the values of the subexpressions. The value of + with respect to E1 is determined by the name rule, chasing up the environment chain from E1 to the global environment to get the primitive addition operation. The value of 1 is just a self-evaluation rule. Slide 12.3.24 So all we have left to do is get the value of (square y) with respect to E1. This is again a compound expression, being evaluated with respect to this new environment
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3. 25 To complete this evaluation, we need to get the value of Example contd: (square y)Ie (square y) with respect to El, and here is a clean tnc-square version of the environment structure developed so far (square y)) 0:31 EXample cont'd: (square y)E Slide 12.3. 26 Well, let's do it in steps. We first get the values of each of the csquare: subexpressions, now with respect to El. First, what is the value of s quare with respect to El? This is a little different than last time. We start in El. Since there is no binding for square there, we go up the environment chain to the global P: Y b:(*xx}b:(+1 environment, where we find the binding, and thus return (square y)) 6001 9ICP Slide 12.3.27 Example contd: (square y)Ie the appropriate procedure 1 (square y)) square n => #[compoundI Example contd: (square y)Ig Slide 12.3. 28 The second subexpression is y and we need its value with respect to El (square y)) square n=> #[compound] yE 1001 iCP
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.25 To complete this evaluation, we need to get the value of (square y) with respect to E1, and here is a clean version of the environment structure developed so far. Slide 12.3.26 Well, let's do it in steps. We first get the values of each of the subexpressions, now with respect to E1. First, what is the value of square with respect to E1? This is a little different than last time. We start in E1. Since there is no binding for square there, we go up the environment chain to the global environment, where we find the binding, and thus return ... Slide 12.3.27 ... the appropriate procedure. Slide 12.3.28 The second subexpression is y and we need its value with respect to E1
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3.29 and our name rule says to simply look it up with respect to Example contd:(square y)I this environment chain starting in el. This. of course. returns the value 4 tnc-square (square y)) Y K== 6001C EXample cont'd: (square y)E Slide 12.3.30 So we are set for our big rule again. We have the application of inc-square a procedure, one of those double bubbles, to a set of value Step one says: drop a frame P: Y +1 6001 9ICP Slide 12.3.31 Example contd: (square y)Ie Extend that frame into an environment by having its enclosing environment pointer match that specified by the procedure object 1 (square y)) square nI => #[compound] y KI == 4 Example contd: (square y)Ig Slide 123.32 which says we want this one. Notice an interesting point here. This new environment E2 is scoped by the global environment, not by El. You might have thought this should be el because that was where we were doing the evaluation but remember that rule says the enclosing environment is specified by the procedure being applied, not by the frame in b: (* xx) which we are doing the evaluation (square y)) square In=>#[compound] yIn==>4 1001 iCP
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.29 ... and our name rule says to simply look it up with respect to this environment chain starting in E1. This, of course, returns the value 4. Slide 12.3.30 So we are set for our big rule again. We have the application of a procedure, one of those double bubbles, to a set of values. Step one says: drop a frame. Slide 12.3.31 Extend that frame into an environment by having its enclosing environment pointer match that specified by the procedure object... Slide 12.3.32 ... which says we want this one. Notice an interesting point here. This new environment E2 is scoped by the global environment, not by E1. You might have thought this should be E1, because that was where we were doing the evaluation, but remember that rule says the enclosing environment is specified by the procedure being applied, not by the frame in which we are doing the evaluation
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.3.33 Step three: create a binding, that is, take the formal parameter Example contd:(square y)I of the procedure, x, and bind it in that frame to the value tnc-square passed in, 4 (square y)) square e=> #[compound] y n==>4 0:31 EXample cont'd: (square y)E Slide 12.3.34 And step four: with respect to that new environment, evaluate squasquare: the body of this procedure, (* xx). So we have reduced this evaluation to multiplying x by itself within environment E2 x:4 P: Y b:(*xx)b:(+1 6001 sCP Slide 12.3.35 Example contd: (square y)Ie So now we are almost done. The values of each of these subexpression with respect to E2 are obtained by applying the Ge-ine-ggu name rule, starting in the first frame of E2. We then apply the primitive multiplication procedure to the value of 4 and 4 1 square nI => #[compound] y KI == 4 |n2==>#【prim]6m=>4 Example contd: (square y)Ig Slide 12.3.36 That of course just returns 16 (square y)) square n1 =>#[compound] yg==> 4 I E2 == #[prim 4
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.3.33 Step three: create a binding, that is, take the formal parameter of the procedure, x, and bind it in that frame to the value passed in, 4. Slide 12.3.34 And step four: with respect to that new environment, evaluate the body of this procedure, (* x x). So we have reduced this evaluation to multiplying x by itself within environment E2. Slide 12.3.35 So now we are almost done. The values of each of these subexpression with respect to E2 are obtained by applying the name rule, starting in the first frame of E2. We then apply the primitive multiplication procedure to the value of 4 and 4. Slide 12.3.36 That of course just returns 16