Local Disk6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. All rights reserved6.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 © 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 © 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
View Full Document
Unlocking...