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 © 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 © 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 © 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 © 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 © 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 © 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
View Full Document
Unlocking...