6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 12.1 Slide 12.1.1 In the last lecture, we introduced mutation as a component of 6001s|cP our data structures We saw for example that set was a Environment mode way of changing the value associated with a variable in our system, and we saw that set-car! and set-cdr! were ways of changing the values of parts of list structure Now, several important things happened when we introduced mutation. First we introduced the notion of time and context into our interpretation Scheme. The order in which things were evaluated now mattered in terms of changes in returned values As a consequence, secondly we shifted from a functional 60015e programming perspective to a more state-based programming perspective, a point to which we will return. Third, we unfortunately introduced the opportunity for bugs and errors in our system, since shared objects allow the mutation of one to affect the value of the other, another point to which we will return. And finally, fourth, we broke the substitution model This last point needs to be addressed, and indeed in addressing it, we will also address many of these other points In this lecture, then, we are going to replace the substitution model with a stronger model, that incorporates the substitution model as a piece of it, but also accounts for state time, context and mutation Slide 12.1.2 6001s|cP To stress this idea that the substitution model no longer holds. Environment model consider the following example. Why does this code behave in Can you figure out why this code works? his manner? (lambda (n) We can see that make-counter is a higher-order (lambda ( (set! n ( n 1) procedure, that is, it returns a procedure as its value. Suppose (define ca (make-counter 0)) we use it to create a counter called ca. now if we all this procedure(or evaluate its application) several times, we see that and cb are independent t is behavior is to count starting at 1, increasing the returned (define cb (make-counter o value by one each time. Thus the standard substitution model 6 001 SICP (or functional programming model) no longer holds, because the same expression is being evaluated each time, but a different value results, depending on when we evaluate the expression If we create a second counter, cb, we end up with different structures. as shown in the last two examples, these two counters are independent, with ch now counting from 1, but ca continuing to count from its place. Thus, even though these objects were created by evaluating the same expression, they do not share any common state So, our substitution model is broken, caused by the introduction of mutation. We thus need a better model that would explain how this code behaves
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 12.1 Slide 12.1.1 In the last lecture, we introduced mutation as a component of our data structures. We saw, for example, that set! was a way of changing the value associated with a variable in our system, and we saw that set-car! and set-cdr! were ways of changing the values of parts of list structure. Now, several important things happened when we introduced mutation. First, we introduced the notion of time and context into our interpretation Scheme. The order in which things were evaluated now mattered in terms of changes in returned values. As a consequence, secondly we shifted from a functional programming perspective to a more state-based programming perspective, a point to which we will return. Third, we unfortunately introduced the opportunity for bugs and errors in our system, since shared objects allow the mutation of one to affect the value of the other, another point to which we will return. And finally, fourth, we broke the substitution model. This last point needs to be addressed, and indeed in addressing it, we will also address many of these other points. In this lecture, then, we are going to replace the substitution model with a stronger model, that incorporates the substitution model as a piece of it, but also accounts for state, time, context and mutation. Slide 12.1.2 To stress this idea that the substitution model no longer holds, consider the following example. Why does this code behave in this manner? We can see that make-counter is a higher-order procedure, that is, it returns a procedure as its value. Suppose we use it to create a counter, called ca. Now if we all this procedure (or evaluate its application) several times, we see that is behavior is to count starting at 1, increasing the returned value by one each time. Thus the standard substitution model (or functional programming model) no longer holds, because the same expression is being evaluated each time, but a different value results, depending on when we evaluate the expression. If we create a second counter, cb, we end up with different structures. As shown in the last two examples, these two counters are independent, with cb now counting from 1, but ca continuing to count from its place. Thus, even though these objects were created by evaluating the same expression, they do not share any common state. So, our substitution model is broken, caused by the introduction of mutation. We thus need a better model that would explain how this code behaves
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.1.3 To do this, we are going to introduce a better model of What the EM is: evaluation known as the environment model. This model will explain things covered by the substitution model, as well as new effects such as mutation. And it is going to lead us towards much better understanding of the evaluation process 6001S What the EM is: Slide 12. 1. 4 A precise, completely mechanical description of: So what is the environment model? For now think of it as a of a var very precise, very mechanical description of a set of rules for hanging the value of determining the values associated with expressions in Scheme lambda-rule creating a procedure Thus, similar to what we saw several lectures ago, we will have applying a procedure rules for dealing for getting the value of a variable, a rule for creating a value of a variable. and a rule for changing the value of a variable. We ll also have a rule for creating procedures, and a rule for applying procedures 6001 SICP Slide 12. 1.5 What the EM is. So our goal will first be to determine the specific rules for the environment model for these kinds of expressions. Once we name-rule looking up the value of a variable have set out those details, we will be able to explain the define-rule new evolution of the evaluation of arbitrarily complex expressions, changing the value of a variable such as the example we just saw. More importantly, by using the model to analyze code, we arn how to associa particular coding choices with their effects of the evaluation .Enables analyzing arbitrary scheme code process. This will allow us to reverse the process. By deciding the behavior we want in our evaluation process, we will be able to work backwards to determine the code components needed to 1 001 SICP achieve that behavior
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.1.3 To do this, we are going to introduce a better model of evaluation, known as the environment model. This model will explain things covered by the substitution model, as well as new effects such as mutation. And it is going to lead us towards a much better understanding of the evaluation process. Slide 12.1.4 So what is the environment model? For now, think of it as a very precise, very mechanical description of a set of rules for determining the values associated with expressions in Scheme. Thus, similar to what we saw several lectures ago, we will have rules for dealing for getting the value of a variable, a rule for creating a value of a variable, and a rule for changing the value of a variable. We'll also have a rule for creating procedures, and a rule for applying procedures. Slide 12.1.5 So our goal will first be to determine the specific rules for the environment model for these kinds of expressions. Once we have set out those details, we will be able to explain the evolution of the evaluation of arbitrarily complex expressions, such as the example we just saw. More importantly, by using the model to analyze code, we will learn how to associate particular coding choices with their effects of the evaluation process. This will allow us to reverse the process. By deciding the behavior we want in our evaluation process, we will be able to work backwards to determine the code components needed to achieve that behavior
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.1.6 What the EM is: There are two main reasons for doing this. The first is simply to A precise, completely mechanical des understand the effect of our design choices in creating name-rule looking up the of ava procedures, for example how mutation will affect behavior setl-rule changing the value of a variable Ultimately, however, we are going to see that this environment ting a procedure lying a procedure model serves as a blueprint for building an actual interpreter for Scheme, that is, the actual mechanism for evaluating Scheme .Enables analyzing arbitrary scheme code expressions inside a machine As a consequence, for now we will use abstract representations for now draw EM stat oxes and pointers for our environment model, but we will eventually see how this later on: implement wit leads to a very mechanical method that can be implemented to I actually build a Scheme system Slide 12.1.7 A shift in v As we build up the pieces of our environment model, a key As we introduce the environment model, we are going to hing to keep in mind is that we are about to shift our viewpoint hift our viewpoint on computation on what constitutes the basic units of computation Variable. Until we introduced mutation, we could think of a variable as OLD-name for value NEW- place into which one can store things just being a name for a value. That was exactly how it behaved in the functional viewpoint of computation. Now we are going OLD-functional description to change that viewpoint. We are going to think of a variable as, ErpreEw-object with inherited context a place into which one can store things, a name for a cubicle Now only have meaning with respect to an emvironment into which things can be placed The second change we are going to make deals with 600SC procedures. Up until now, we could really think of a procedure as a functional description of some computation We stressed this idea that evaluating the same expression gave rise to the same value, it behaved as a mapping from input values to output values, like any ordinary function would. Now, we are going to change that viewpoint. We will instead think of a procedure as an object, with an inherited context. That context tells us how to interpret symbols in that computation, which will change our overall view of computation And finally, we are going to change the way we think about expressions. We now will say that an expression only has meaning with respect to a structure called an environment, something that we are about to define. This means that an expression now inherits its value, by inheriting information about what was occurring when they were created So we ask that you keep these ideas in mind as we build our new model of computation. Variables are now places into which one can store things, procedures are now objects with an inherited context, and expressions have meaning only with respect to an environment
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.1.6 There are two main reasons for doing this. The first is simply to understand the effect of our design choices in creating procedures, for example how mutation will affect behavior. Ultimately, however, we are going to see that this environment model serves as a blueprint for building an actual interpreter for Scheme, that is, the actual mechanism for evaluating Scheme expressions inside a machine. As a consequence, for now we will use abstract representations for our environment model, but we will eventually see how this leads to a very mechanical method that can be implemented to actually build a Scheme system. Slide 12.1.7 As we build up the pieces of our environment model, a key thing to keep in mind is that we are about to shift our viewpoint on what constitutes the basic units of computation. Until we introduced mutation, we could think of a variable as just being a name for a value. That was exactly how it behaved, in the functional viewpoint of computation. Now we are going to change that viewpoint. We are going to think of a variable as a place into which one can store things, a name for a cubicle into which things can be placed. The second change we are going to make deals with procedures. Up until now, we could really think of a procedure as a functional description of some computation. We stressed this idea that evaluating the same expression gave rise to the same value, it behaved as a mapping from input values to output values, like any ordinary function would. Now, we are going to change that viewpoint. We will instead think of a procedure as an object, with an inherited context. That context tells us how to interpret symbols in that computation, which will change our overall view of computation. And finally, we are going to change the way we think about expressions. We now will say that an expression only has meaning with respect to a structure called an environment, something that we are about to define. This means that an expression now inherits its value, by inheriting information about what was occurring when they were created. So we ask that you keep these ideas in mind as we build our new model of computation. Variables are now places into which one can store things, procedures are now objects with an inherited context, and expressions have meaning only with respect to an environment
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.1. 8 Frame: a table of bindings Now we can start building our environment model. first of all Binding: a pairing of a name and a value if variables should now be thought of as places, we need a way of organizing them. So the first piece of an environment is something we call a frame. This just consists of a table of gs binding refers to a pairing of a name and a slot nto which a value can be stored which will be associated with that name Slide 12.1.9 Frame: a table of bindings In terms of an abstract schematic for keeping track of things,. Binding: a pairing of a name and a value here is a table of bindings table a. which we also refer to as frame has two bindings in it it has a binding for the variable and a binding for the variable y Frame: a table of bin Slide 2.1.10 ng: a pairing of a name and a value And in particular, we say that x is bound to the value 15 Example: x is bound to 15 in frame A within Frame A, and y is bound to the value of the list(1 y is bound to(1 2)in frame A 2)within Frame A the value of the variable x in frame a is 15 Notice that the expression x has a value 15 associated with it in this frame, as determine by looking up the binding of x within this table. Shortly we will talk about how we actually establish bindings in this frames, but for now we have the first piece of our environment model. A frame is a table of bindings, and a binding is a pairing of a name and a value Slide 12.1.11 Environment: a sequence of frames An environment consists of a sequence of frames, for reasons that we will see shortly M w: HICp
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.1.8 Now we can start building our environment model. First of all, if variables should now be thought of as places, we need a way of organizing them. So the first piece of an environment is something we call a frame. This just consists of a table of bindings, and a binding refers to a pairing of a name and a slot into which a value can be stored, which will be associated with that name. Slide 12.1.9 In terms of an abstract schematic for keeping track of things, here is a table of bindings. Table A, which we also refer to as a frame, has two bindings in it: it has a binding for the variable x, and a binding for the variable y. Slide 12.1.10 And in particular, we say that x is bound to the value 15 within Frame A, and y is bound to the value of the list (1 2) within Frame A. Notice that the expression x has a value 15 associated with it in this frame, as determine by looking up the binding of x within this table. Shortly we will talk about how we actually establish bindings in this frames, but for now we have the first piece of our environment model. A frame is a table of bindings, and a binding is a pairing of a name and a value. Slide 12.1.11 An environment consists of a sequence of frames, for reasons that we will see shortly
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.1.12 Environment: a sequence of frames So here is our frame from before. with the bindings we had °B Slide 12.1.13 Environment: a sequence of frames and here is a second frame, with its own set of bindings. An Environment E1 consists of frames a and B environment is a nested sequence of frames, so environment El consists in this case of frame a followed by frame B z:10 Environment: a sequence of frames Slide 12.1.14 Environment E1 consists of frames a and B A second environment, E2, might just consist of Frame B, So Environment E2 consists of frame B only note that a frame can be shared by more than one environment A frame may be shared by multiple environments and we will see shortly why that is a powerful tool Slide 12.1.15 Environment: a sequence of frames The connection between frames is important, and is called an onsists of frames a and B enclosing environment pointer. So for example, El starts with Environment E2 consists of frame B only Frame A, and inherits Frame B as its enclosing environment, A frame may be shared by multiple environments which in fact is similar to E2 We will see shortly why all these pieces put together help us understanding exactly how z:10 evaluation is going to proceed So far, we have just been talking about details: we have frames environment pointer which are tables of bindings, we have connections between frames, and we have environments as sequences of frames With all of these pieces in mind, we can now start relating them to the actual evaluation of expressions
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.1.12 So here is our frame from before, with the bindings we had... Slide 12.1.13 ... and here is a second frame, with its own set of bindings. An environment is a nested sequence of frames, so environment E1 consists in this case of Frame A followed by Frame B. Slide 12.1.14 A second environment, E2, might just consist of Frame B, so note that a frame can be shared by more than one environment, and we will see shortly why that is a powerful tool. Slide 12.1.15 The connection between frames is important, and is called an enclosing environment pointer. So for example, E1 starts with Frame A, and inherits Frame B as its enclosing environment, which in fact is similar to E2. We will see shortly why all these pieces put together help us understanding exactly how evaluation is going to proceed. So far, we have just been talking about details: we have frames, which are tables of bindings, we have connections between frames, and we have environments as sequences of frames. With all of these pieces in mind, we can now start relating them to the actual evaluation of expressions
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Evaluation in the environment model Slide 12.1.16 Now we are ready to see how to connect environments to All evaluation occurs in an environment evaluation. First, as we have already suggested, all evaluation is The current environment changes when the going to take place with respect to some environment. The environment will provide the context for how to interpret symbols and names. Notice that this won't al ways be the same environment, and a key issue is that whenever we apply a procedure, we will create a new environment, which captures he context for interpreting the variables of that procedure 6 001 SICP Slide 12.1.17 Evaluation in the environment model We have said that all evaluation of expressions is going to take place with respect to an environment. And we have also seen All evaluation occurs in an environment that environments can inherit other environments as part of the interpreter applies a procedure chaining process. Nonetheless, this means that eventually we have to terminate that chaining of environments, and to do that The top environment is called the global environment(GE) we have a special environment, called the global environment Only the gE has no enclosing environment It has no enclosing environment and is the only such environment with that property. This is the environment in which we will normally evaluate expressions, as it is our starting point. It is also going to hold the bindings for our basic| 4 6001S expressions in our language Evaluation in the environment model Slide l2.1.18 So we are ready to start putting together rules for evaluating All evaluation occurs in an environment The current environment changes when the expressions with respect to an environment. Before we do, lets terpreter applies a procedure remind you that our central rule for evaluation deal with combinations, and in this new model things are nearly the same top environment is called the global environment(GE) as they were in the substitution model ly the GE has no enclosing environment As before, we will evaluate the subexpressions in any order To evaluate a combinatio Evaluate the subexpressions in the current environment now with respect to the current environment. Then we will ply the value of the first to the values of the rest apply the value of the first subexpression to the values of the others. We will see shortly how to do that in a very mechanis 6 001 SICP I way. With all of this in place, lets start actually building tfo stic environment model 6.001 Notes: Section 12.2
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.1.16 Now we are ready to see how to connect environments to evaluation. First, as we have already suggested, all evaluation is going to take place with respect to some environment. The environment will provide the context for how to interpret symbols and names. Notice that this won't always be the same environment, and a key issue is that whenever we apply a procedure, we will create a new environment, which captures the context for interpreting the variables of that procedure. Slide 12.1.17 We have said that all evaluation of expressions is going to take place with respect to an environment. And we have also seen that environments can inherit other environments as part of the chaining process. Nonetheless, this means that eventually we have to terminate that chaining of environments, and to do that we have a special environment, called the global environment. It has no enclosing environment and is the only such environment with that property. This is the environment in which we will normally evaluate expressions, as it is our starting point. It is also going to hold the bindings for our basic expressions in our language. Slide 12.1.18 So we are ready to start putting together rules for evaluating expressions with respect to an environment. Before we do, lets remind you that our central rule for evaluation deal with combinations, and in this new model things are nearly the same as they were in the substitution model. As before, we will evaluate the subexpressions in any order, now with respect to the current environment. Then we will apply the value of the first subexpression to the values of the others. We will see shortly how to do that in a very mechanistic way. With all of this in place, lets start actually building the environment model. 6.001 Notes: Section 12.2
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.2.1 Okay, we are ready to start looking at our rules for evaluation inName-rule our new model, especially to how environments are created and manipulated as part of the evaluation process The simplest possible expressions are just numbers. These are self-evaluating which means that their value is just their value independent of the environment The first interesting rule comes with names. We have a way of dealing with evaluation of names, our simplest kind of primitive, and that rule should tell us how to get the value ated with a variabl 6001Sc Slide 12.2.2 A name X evaluated in environment E gi\ The rule is straightforward, but quite mechanistic. A name X the value of x in the first frame of e whe is bound evaluated in an environment e gives back the value of X in the first frame of e in which there is a binding for X. Remember, an environment is a sequence of frames, so we will start in the first frame of the lent, looking for a binding of that name. We will continue up the chain of frames until we find the first such binding, in which case we return the value associated with that binding Slide 12.2.3 Name-rule So here are our example environments from before. We will A name X evaluated in environment E gives call the top level environment, the global environment, or our the value of x in the first frame of e where x is bound stopgap environment Environment El has its own frame, and inherits as its enclosing environment, the global environment z:10 Slide 12. 2.4 A name x evaluated in environment E gives We can now talk about the value of a variable with respect to the value of x in the first frame of e where x is bound an environment; in fact we should always talk about the value I o=> 10 2In=>10 *Ie=> 15 of any expression with respect to some environment. For example, we can ask for the value of the variable z with respect to the global environment. Notice the notation we use for this namely the expression, then a i to indicate the evaluation with respect to some environment, then a subscript to denote the actual environment. Note that normally we will evaluate expressions with respect to the global environment, since that is where we interact with the Scheme system. If I type in a the expression to the Scheme interpreter, I am interacting with
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.2.1 Okay, we are ready to start looking at our rules for evaluation in our new model, especially to how environments are created and manipulated as part of the evaluation process. The simplest possible expressions are just numbers. These are self-evaluating which means that their value is just their value, independent of the environment. The first interesting rule comes with names. We have a way of dealing with evaluation of names, our simplest kind of primitive, and that rule should tell us how to get the value associated with a variable. Slide 12.2.2 The rule is straightforward, but quite mechanistic. A name X evaluated in an environment E gives back the value of X in the first frame of E in which there is a binding for X. Remember, an environment is a sequence of frames, so we will start in the first frame of the environment, looking for a binding of that name. We will continue up the chain of frames until we find the first such binding, in which case we return the value associated with that binding. Slide 12.2.3 So here are our example environments from before. We will call the top level environment, the global environment, or our stopgap environment. Environment E1 has its own frame, and inherits as its enclosing environment, the global environment. Slide 12.2.4 We can now talk about the value of a variable with respect to an environment; in fact we should always talk about the value of any expression with respect to some environment. For example, we can ask for the value of the variable z with respect to the global environment. Notice the notation we use for this, namely the expression, then a | to indicate the evaluation with respect to some environment, then a subscript to denote the actual environment. Note that normally we will evaluate expressions with respect to the global environment, since that is where we interact with the Scheme system. If I type in an expression to the Scheme interpreter, I am interacting with the
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology global environment. Our rule can now be used. The value of variable z with respect to the global environment is clearly 10, as that is the pairing associated with it. If I ask for the value of z with respect to the environment el, I start in frame a Since there is no binding for z in that frame, I move up the enclosing environment pointer to the next frame, in this case, the global environment, and look for the binding of z there. Since there is one, i return the value 10 Finally, if I ask for the value of x with respect to El, it points to the first frame A, and I look there for a binding Since there is one. I return that value. 15 Slide 12.2.5 Name-rule On the other hand, if I ask for the value of x with respect to the in environment E gives global environment, I first look in Frame B for a binding. This the value of x in the first frame of E where Xis bound returns the value 3 the value associated with x in that frame z|=>10xlx=>15 In E1, the binding of x in frame A shadows the binding of x in B In this case. x has a different value in different environments In one, its value is 15, in another it is 3 We say that the it hides it so that if we start in Frame A, we only see the binding/&x OF 15 binding of x in Frame A shadows the binding of x in Frame B Ⅴ isible there ·□ Thus. we see how the name rule tells us the mechanism by which we look up the value associated with a variable in some environment Slide 12.2.6 Given that we have a rule for looking up values associated with creates or replaces a binding in the first frame of E variables, what about a rule for creating bindings for variables? That, we know, is a define expression, and we have a rule for dealing with such expressions. a define special form when evaluated in an environment E, creates or replaces a binding for that variable in the first frame of E, and it always does this in the first frame ofe 6 01 SIP Slide 12.2.7 Here is our environment structure from before. Let's look at a define special form evaluated in environment E what defines do when they are evaluated with respect to creates or replaces a binding in the first frame of E this structure ·口A
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. global environment. Our rule can now be used. The value of variable z with respect to the global environment is clearly 10, as that is the pairing associated with it. If I ask for the value of z with respect to the environment E1, I start in frame A. Since there is no binding for z in that frame, I move up the enclosing environment pointer to the next frame, in this case, the global environment, and look for the binding of z there. Since there is one, I return the value 10. Finally, if I ask for the value of x with respect to E1, it points to the first frame A, and I look there for a binding. Since there is one, I return that value, 15. Slide 12.2.5 On the other hand, if I ask for the value of x with respect to the global environment, I first look in Frame B for a binding. This returns the value 3, the value associated with x in that frame. In this case, x has a different value in different environments. In one, its value is 15, in another it is 3. We say that the binding of x in Frame A shadows the binding of x in Frame B, it hides it so that if we start in Frame A, we only see the binding visible there. Thus, we see how the name rule tells us the mechanism by which we look up the value associated with a variable in some environment. Slide 12.2.6 Given that we have a rule for looking up values associated with variables, what about a rule for creating bindings for variables? That, we know, is a define expression, and we have a rule for dealing with such expressions. A define special form, when evaluated in an environment E, creates or replaces a binding for that variable in the first frame of E, and it always does this in the first frame of E. Slide 12.2.7 Here is our environment structure from before. Let's look at what defines do when they are evaluated with respect to this structure
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.2.8 Define-rule First, suppose we evaluate (define z 20)in the global environment. As I said earlier, this might be an (define z 20)I c expression that you typed into the computer, and we want to see ⊙ z:10 what happens x:3 Slide 12.2.9 Note what the rule says: create a binding or replace a binding A define special form evaluated in environment E for the variable. in this case z. in the first frame of the creates or replaces a binding in the first frame of E environment, in this case, the global environment. So that old (define z 20)I c binding for z as 10 gets replaced by a new binding of z to 20 Define-rule Slide 12.2.10 A define special form evaluated in environment E On the other hand, suppose we evaluate (define creates or replaces a binding in the first frame of E 25)with respect to El. What happens in this case? (define z 20)I sx (define 2 25)IEl z:20 Slide 12.2.11 Define-rule Remember our rule: create or replace a binding for the variable in the first frame of the environment. So in this case we do this A define special form evaluated in environment E es or replaces a binding in the first frame of E frame A. the first frame of environment el. Since there is define z 20)I gr (define z 25)IEl current binding for z in this frame. we create a new one. and ; we have now set up a shadowing of z. The z bound to 25 in z:20 Frame a will shadow the binding of z to 20 in Frame B, similar to what we saw in the previous slide
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.2.8 First, suppose we evaluate (define z 20) in the global environment. As I said earlier, this might be an expression that you typed into the computer, and we want to see what happens. Slide 12.2.9 Note what the rule says: create a binding or replace a binding for the variable, in this case z, in the first frame of the environment, in this case, the global environment. So that old binding for z as 10 gets replaced by a new binding of z to 20. Slide 12.2.10 On the other hand, suppose we evaluate (define z 25) with respect to E1. What happens in this case? Slide 12.2.11 Remember our rule: create or replace a binding for the variable in the first frame of the environment. So in this case, we do this in frame A, the first frame of environment E1. Since there is no current binding for z in this frame, we create a new one, and we have now set up a shadowing of z. The z bound to 25 in Frame A will shadow the binding of z to 20 in Frame B, similar to what we saw in the previous slide
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 12.2.12 Set Thus, we have a rule for looking up the binding of a variable, the binding of x in the first frame o ironment E changes and a rule for creating a binding of a variable. We should also A setl of variable x evaluated in X is bound have a rule for mutation of the binding of a variable This is our set! rule. The rule says: mutating a variable x with respect to an environment e changes the binding for x in the first ame of E for which such a binding exists. Note carefully how this differs from define Slide 12.2.13 Setk-rule Here is our environment structure from before. Let's look at A set! of variable X evaluated in environment E changes what happens we evaluate set! expressions with respect to the binding of x in the first frame of E where X is bound this environment structure Slide 12.2.14 A setI of variable X evaluated in environment E changes Let's evaluate(set! z 20) with respect to the global he binding of x in the first frame of E where x is bound (set! z 20)I gr Slide 12.2.15 Setd-rule The rule says: find the first binding for z in that environment Sinc re using the global environment, we look there first the binding of x in the first frame of E where X is bound and fortunately there is a binding for z in that environment. So set! z 20)I we change it. In place of the binding for z we substitute the walue 20, causing a mutation. If we look back at the v ye same slide, we can see that in this case the effect is exactly as a define. So why do we have two different forms?
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 12.2.12 Thus, we have a rule for looking up the binding of a variable, and a rule for creating a binding of a variable. We should also have a rule for mutation of the binding of a variable. This is our set! rule. The rule says: mutating a variable x with respect to an environment E changes the binding for x in the first frame of E for which such a binding exists. Note carefully how this differs from define. Slide 12.2.13 Here is our environment structure from before. Let's look at what happens we evaluate set! expressions with respect to this environment structure. Slide 12.2.14 Let's evaluate (set! z 20) with respect to the global environment. Slide 12.2.15 The rule says: find the first binding for z in that environment. Since we are using the global environment, we look there first, and fortunately there is a binding for z in that environment. So we change it. In place of the binding for z we substitute the value 20, causing a mutation. If we look back at the previous slide, we can see that in this case the effect is exactly the same as a define. So why do we have two different forms?