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