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