《Structure and Interpretation of Computer Programs》lecture 16 webhan

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 13.1 Slide 13.1.1 The role of abstractions In this lecture, we are going to look at a very different style of creating large systems, a style called object oriented programming. This style focuses on breaking systems up in a different manner than those we have seen before To set the stage for this, we are first going to return to the notion of abstractions, and use that idea to see how we can capture objects with some internal state that reflects the status of those objects. We are going to be led from there to a style of programming called message-passing in which we treat systems as if they consist of large collections of objects that 60015e communicate with one another to cause computation to take The role of abstractions Slide 13.1.2 Let's start by going back and thinking about the tools we have Data abstraction developed for thinking about computation. Two of the key tools we have developed dealt with abstractions We have seen procedural abstractions here the idea is to capture a common pattern of processing into a procedure, then isolate the details of the computation from the use of the computation, by simply naming the procedure and using that name with appropriate conditions on the procedure's input. We saw that this style of approach is particularly useful when dealing with problems that are easily addressed in a functional programming approach, that is, where we can treat the dures as generalized mathematical function that their output for a given input will be the same whenever we evaluate it We have also seen data abstractions. Here the idea is to modularize our system by creating data structures that capture key parts of the information we need to handle. The goal is to hide the details of the representation and storage of the data behind standard interfaces, primarily our constructors and selectors. This means the user can then manipulate data objects without having to worry about details of how they are maintained As you might expect, often the data abstractions and the procedural abstractions work hand-in-hand, with the procedures used to manipulate the data using the data abstraction interfaces, and with the structure of the procedures tending to mirror the actual structure of the data

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 13.1 Slide 13.1.1 In this lecture, we are going to look at a very different style of creating large systems, a style called object oriented programming. This style focuses on breaking systems up in a different manner than those we have seen before. To set the stage for this, we are first going to return to the notion of abstractions, and use that idea to see how we can capture objects with some internal state that reflects the status of those objects. We are going to be led from there to a style of programming called message-passing in which we treat systems as if they consist of large collections of objects that communicate with one another to cause computation to take place. Slide 13.1.2 Let's start by going back and thinking about the tools we have developed for thinking about computation. Two of the key tools we have developed dealt with abstractions. We have seen procedural abstractions. Here the idea is to capture a common pattern of processing into a procedure, then isolate the details of the computation from the use of the computation, by simply naming the procedure and using that name with appropriate conditions on the procedure's input. We saw that this style of approach is particularly useful when dealing with problems that are easily addressed in a functional programming approach, that is, where we can treat the procedures as generalized mathematical functions, meaning that their output for a given input will be the same whenever we evaluate it. We have also seen data abstractions. Here the idea is to modularize our system by creating data structures that capture key parts of the information we need to handle. The goal is to hide the details of the representation and storage of the data behind standard interfaces, primarily our constructors and selectors. This means the user can then manipulate data objects without having to worry about details of how they are maintained. As you might expect, often the data abstractions and the procedural abstractions work hand-in-hand, with the procedures used to manipulate the data using the data abstraction interfaces, and with the structure of the procedures tending to mirror the actual structure of the data

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 13.1.3 The goal in each case is actually the same: we want to hide The role of abstractions details of the abstraction so that we can treat complex things as if they are primitive units. In the case of procedural abstractions, we want to hide the details of the computation, Goal: treat complex things as primitives, and hide details and treat the procedure as a primitive computational unit. In the case of data abstractions we want to hide the details of how components are glued together, and treat each unit as an abstract collection of parts 6001 sICP The role of abstractions Slide 13.1. 4 Procedural abstractions Given that we want to use abstractions as a tool in controlling Data abstractions complexity in large systems, there are several questions that come up when thinking about how to use abstractions. The first Goal: treat complex things as primitives, and hide details is: what is the best way to break a new problem area up into a set of modules? Both data modules and procedure modules? As ve have already seen in earlier lectures, some problems break Questions: How easy is it to em into abstraction modules? up in multiple ways, and breaking them up in different ways makes some processes easier and others harder so a ke Adding new question is: How do I use the idea of abstraction to break Adding new 601 SICP systems into modules and what s the best way to do this? The second question deals with how easy it is to extend the system. If I want to add new data types to my system, is that easy? If I want to add new methods to my system, new ways of manipulating data types, is that easy? We have seen several examples of this already, we are now going to return to these questions in order to lead to a very different way of breaking systems up into convenient sized chunks Slide 13. 1.5 Let's start by going back to data objects and data abstractions One view of Data Here is the traditional way of looking at data, at least as we Some complex structure constructed from cons cells have done thi Explicit tags to ke of data types Implement a data abstraction as set of procedures that operate on First, we build some complex data structure out of primitives the data for example, cons cells or pairs. Second, we use tags to identify the type of structure being represented This tells us how to interpret the different slots in the list structure. For example, is the car of the list structure the name of a person or his batting average or his GPA? Then, the data abstraction is actually built by creating a set of 4 procedures that operate on the data. These are procedures that take in instances of the data, use selectors to get out the pieces, do some manipulation to create new pieces, and then use the constructor to re-glue the abstraction back together. This led to the concept of data-directed ogramming, which we saw earlier. We use the tag to determine the right set of procedures to apply. and this allows the user to program in a generic fashion. They can focus on what they want to do, but have the code direct the data to the right place for the actual work

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 13.1.3 The goal in each case is actually the same: we want to hide details of the abstraction so that we can treat complex things as if they are primitive units. In the case of procedural abstractions, we want to hide the details of the computation, and treat the procedure as a primitive computational unit. In the case of data abstractions, we want to hide the details of how components are glued together, and treat each unit as an abstract collection of parts. Slide 13.1.4 Given that we want to use abstractions as a tool in controlling complexity in large systems, there are several questions that come up when thinking about how to use abstractions. The first is: what is the best way to break a new problem area up into a set of modules? Both data modules and procedure modules? As we have already seen in earlier lectures, some problems break up in multiple ways, and breaking them up in different ways makes some processes easier and others harder. So a key question is: How do I use the idea of abstraction to break systems into modules and what’s the best way to do this? The second question deals with how easy it is to extend the system. If I want to add new data types to my system, is that easy? If I want to add new methods to my system, new ways of manipulating data types, is that easy? We have seen several examples of this already, we are now going to return to these questions in order to lead to a very different way of breaking systems up into convenient sized chunks. Slide 13.1.5 Let's start by going back to data objects and data abstractions. Here is the traditional way of looking at data, at least as we have done things so far. First, we build some complex data structure out of primitives, for example, cons cells or pairs. Second, we use tags to identify the type of structure being represented. This tells us how to interpret the different slots in the list structure. For example, is the car of the list structure the name of a person or his batting average or his GPA? Then, the data abstraction is actually built by creating a set of procedures that operate on the data. These are procedures that take in instances of the data, use selectors to get out the pieces, do some manipulation to create new pieces, and then use the constructor to re-glue the abstraction back together. This led to the concept of data-directed programming, which we saw earlier. We use the tag to determine the right set of procedures to apply. And this allows the user to program in a generic fashion. They can focus on what they want to do, but have the code direct the data to the right place for the actual work

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 13.1.6 One view of Data Here is a simple example to illustrate this point. Suppose I have a set of different geometric objects, things like numbers, lines Some complex structure constructed from cons cells shapes, and I want to write a procedure, or an operation, that Explicit tags to keep track of data types mplement a data abstraction as set of procedures that will scale each of those objects by some amount. Then a perate on the data generic operation, under the data-directed approach would look Generic"operations by looking at types like this procedure shown here. Given an object and my desired scale factor, I use the type of the object to dispatch: if it is a cond ((number? x)(* x factor)) number, I just multiply; if it is a line, I ship it to the procedure that will scale a line and so on (else (error unknown type)))) The point of this example is that I think about things in terms of 6 001 SICP I the kinds of objects I have and procedures for manipulating each distinct object type. I use the tag or the type of the object to tell me which procedure to send the object to Slide 13.17 Dispatch on Type So now let's go back to our questions. How easy is it to extend such a system, a system where we are breaking things up into Adding new data types Must change every generic operation tagged data, and using data directed programming? First, if we add a new data type to our system, what do we have to do? Adding new methods Just create generic operations Well we can see from our example that we will have to all the procedures like scale, to add a new clause to each cond dispatching on that new type of object. As a consequence, if there are many such procedures, we have a lot of changes to nake, both a great deal of code to write, and more importantly aking sure that we change all the relevant procedures If we add a new operation or method what do we need to do? This is easier, as we just need to develop a subprocedure for each type of object to which the method will apply Thus in this style of programming, adding a new data type is painful, while adding a new method is reasonable. As when the changes are mostly new methods or operations, or when the different kinds of data structures in the or a consequence, this approach to modularizing systems works best when there are only a few data abstractions system are mostly independent of one another. In those cases, this style of approach works well. But not everything fits these cases What should we do in those cases? Slide 13.1.8 Adding new data types So let's step back from this organization for a second. One way Must change every generic operation to think about structuring a large system is to realize that we are Must keep names distinct Adding new methods likely to have a large number of different data objects( Just create generic operations stances of data abstractions ) and a large number of operations we want to perform on those objects. Conceptually ata type 1 Data type 2 Data type 3 Data tyt this means we have a big table, where we can use a different operation 1 Some proc Some proc some proc Some proc row for each operation we want to perform, and a different peration 2 Some proe Some proc Some proc Some proc column for each kind of data abstraction we have. Then at each peration a some proc some proc some proc some proc element in this table, we can conceptualize having a specific Operation 4 Some proc Some proe Some proc Some proe procedure, intended to perform the particular operation(e.g scaling )on the particular kind of data object(e. g. a number)

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 13.1.6 Here is a simple example to illustrate this point. Suppose I have a set of different geometric objects, things like numbers, lines, shapes, and I want to write a procedure, or an operation, that will scale each of those objects by some amount. Then a generic operation, under the data-directed approach would look like this procedure shown here. Given an object and my desired scale factor, I use the type of the object to dispatch: if it is a number, I just multiply; if it is a line, I ship it to the procedure that will scale a line, and so on. The point of this example is that I think about things in terms of the kinds of objects I have and procedures for manipulating each distinct object type. I use the tag or the type of the object to tell me which procedure to send the object to. Slide 13.1.7 So now let's go back to our questions. How easy is it to extend such a system, a system where we are breaking things up into tagged data, and using data directed programming? First, if we add a new data type to our system, what do we have to do? Well we can see from our example that we will have to all the procedures like scale, to add a new clause to each cond, dispatching on that new type of object. As a consequence, if there are many such procedures, we have a lot of changes to make, both a great deal of code to write, and more importantly making sure that we change all the relevant procedures. If we add a new operation or method, what do we need to do? This is easier, as we just need to develop a subprocedure for each type of object to which the method will apply. Thus in this style of programming, adding a new data type is painful, while adding a new method is reasonable. As a consequence, this approach to modularizing systems works best when there are only a few data abstractions or when the changes are mostly new methods or operations, or when the different kinds of data structures in the system are mostly independent of one another. In those cases, this style of approach works well. But not everything fits these cases. What should we do in those cases? Slide 13.1.8 So let's step back from this organization for a second. One way to think about structuring a large system is to realize that we are likely to have a large number of different data objects (or instances of data abstractions), and a large number of operations we want to perform on those objects. Conceptually, this means we have a big table, where we can use a different row for each operation we want to perform, and a different column for each kind of data abstraction we have. Then at each element in this table, we can conceptualize having a specific procedure, intended to perform the particular operation (e.g. scaling) on the particular kind of data object (e.g. a number)

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 13.1.9 One way of actually building such a system is to focus on the Dispatch on Type rows of the table, that is the operations. Indeed, our use of tagged data was based around this viewpoint, in which we Must change every generic operation Must keep names distinct created generic operations that handle the same operation for Adding new methods different data objects, and used the tag on the data object to Just create generic operations dispatch to the appropriate version of the procedure to handle that kind of data Data type 1 Data type 2 Data type 3 Data type 4 oc Some pro Some Operation 4 Some proc Some Some proc Some proc Dispatch on type Slide 13.1.10 Adding new data types But given this table, there is an alternative possible Must change every generic operation organization, which is around the columns of the table. This Must keep names distinct would focus on creating a generic data object that would know Adding new methods Just create generic operations how to handle different operations on that kind of data structure Data ty ata type 3Data type 4 proc Some proc me proc Some pr operation 4 Some proc ome proc/ Some proc Some pro Slide 13.1.1 Let's step back and rethink data. This sounds like an odd thing An Alternative View of Data Procedures with state to do but let's think about data in a very different way. Rather than thinking of data abstractions as some slots into which we A procedure has can put things, let's instead consider data to be a procedure with parameters and body as specified by n expression environment (which can hold name-value bindings some internal state This sounds strange! But, what is a procedure? It really has two parts: it has a set of parameters and a body which define the pattern of computation to perform as a function of the objects d in and as we saw in the environment model it has an associated environment which can hold name-value bindings, 4 60015e that is, pall of names and values

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 13.1.9 One way of actually building such a system is to focus on the rows of the table, that is the operations. Indeed, our use of tagged data was based around this viewpoint, in which we created generic operations that handle the same operation for different data objects, and used the tag on the data object to dispatch to the appropriate version of the procedure to handle that kind of data. Slide 13.1.10 But given this table, there is an alternative possible organization, which is around the columns of the table. This would focus on creating a generic data object that would know how to handle different operations on that kind of data structure. Slide 13.1.11 Let's step back and rethink data. This sounds like an odd thing to do but let's think about data in a very different way. Rather than thinking of data abstractions as some slots into which we can put things, let's instead consider data to be a procedure with some internal state. This sounds strange! But, what is a procedure? It really has two parts: it has a set of parameters and a body which define the pattern of computation to perform as a function of the objects passed in; and as we saw in the environment model, it has an associated environment which can hold name-value bindings, that is, pairings of names and values

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 13.1.12 An Alternative view of data: So what, you say! Well, we can use this idea to captu Procedures with State information about a data structure. In particular, we can use a procedure to represent data objects with state. What would that A procedure has parameters and body as specified by a expression mean? It would say that we could use the local environment of environment (which can hold name-value bindings the procedure plus its parameters to hold the values of the late(and hide) data, and datum, and we could create local procedures within the data procedure to manipulate these values, to change the state of the Need access to that environment ructor, accessors, mutators, predicates This means that the only access to the values of the data object ion: changes in the private state of the will be through the procedure representing the data. This would 6 001 SICP I nicely encapsulate the data structure inside this procedure This probably still sounds odd so let's look at a specific 6.001 Notes: Section 13.2 Slide 13.2.1 Example: Pair as a Procedure with State To illustrate this idea of using a procedure to represent a data structure,an object with state, let's look at the following, rather(define (cons x y) dd, example Here is a very different way of implementing a cond《(eq?mg'cAR)x) ((eq? m84 'CDR) y) cons cell or a pair. Let me stress that this is not the way that 《eq?m8 f PAIR?)# else (error pair cannot msg))))) Scheme normally represents pairs. Of course, the idea of data abstraction is that the actual implementation of a data structure should be irrelevant to the user. This example is used to drive home a conceptual point Here, we have implemented a pair as a procedure! Thus our undamental data structure is now a procedure rather than some 60015c storage in memory slots Example: Pair as a Procedure with State Slide 13.2.2 Look at this carefully. First, note that cons, as defined here involves two lambdas Remem ber that there is a hidden ((eq? m84CDR lambda inside the syntactic sugar of this definition. This ((eqr? msg 'PAIR?) #t) means that there is a second l ambda as the body of the cons and thus when we evaluate(cons x y)using this pa ntation, we get value. a procedure of one parameter, ms g So what does this say? It says that when we use cons with this implementation our representation for our fundamental way of gluing things together is now a procedure of one argument So what would that cons thing do? Since it is a procedure, if we send it a value, or if we apply the procedure to a single argument, note what it does. It uses the value of the argument, in this case a particular symbol, to decide

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 13.1.12 So what, you say! Well, we can use this idea to capture information about a data structure. In particular, we can use a procedure to represent data objects with state. What would that mean? It would say that we could use the local environment of the procedure plus its parameters to hold the values of the datum, and we could create local procedures within the data procedure to manipulate these values, to change the state of the object. This means that the only access to the values of the data object will be through the procedure representing the data. This would nicely encapsulate the data structure inside this procedure. This probably still sounds odd so let's look at a specific example. 6.001 Notes: Section 13.2 Slide 13.2.1 To illustrate this idea of using a procedure to represent a data structure, an object with state, let's look at the following, rather odd, example. Here is a very different way of implementing a cons cell or a pair. Let me stress that this is not the way that Scheme normally represents pairs. Of course, the idea of data abstraction is that the actual implementation of a data structure should be irrelevant to the user. This example is used to drive home a conceptual point. Here, we have implemented a pair as a procedure! Thus our fundamental data structure is now a procedure rather than some storage in memory slots. Slide 13.2.2 Look at this carefully. First, note that cons, as defined here, involves two lambdas. Remember that there is a hidden lambda inside the syntactic sugar of this definition. This means that there is a second lambda as the body of the cons and thus when we evaluate (cons x y) using this particular implementation, we get back as a value, a procedure of one parameter, msg. So what does this say? It says that when we use cons with this implementation our representation for our fundamental way of gluing things together is now a procedure of one argument. So what would that cons thing do? Since it is a procedure, if we send it a value, or if we apply the procedure to a single argument, note what it does. It uses the value of the argument, in this case a particular symbol, to decide

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology what value to return We call this style of programming, message passing, because the procedure accepts a message as input, and then does something based on the value of that Slide 13. 2.3 Example: Pair as a Procedure with State This looks a bit weird! Our constructor for gluing things together gives us a procedure as the actual object. Should we (lambda (cond ((eq? msg CAR) x) Of course we know that we shouldn't care. To complete the ((eq? msg 'PAIR2) #t abstraction for a pair, we simply need to create car and cdr t”m8))))) to fulfill the contract of the abstraction of a pair (odr p) (p CDR)) Each of those is itself a procedure that takes as input a pair, to a single argument, which in this case is just a symbole qure which we know is a procedure, and then applies that procedi message. Ideally, that message should get back for us the value we need to satisfy the contract. If we look at this definition for car, we see it takes as input one of these new pairs, and then applies that pair(a procedure) to the symbol carr which in principle should return for us the value we used when we created the pair Note the other procedure we built here. Our predicate for testing whether something is a pair now relies on the identifying itself. This is the version of our tag. Before we attached a tag as a symbol on a data structure. Here tags are part of the procedure Example: What is our"pair"object? Slide 13.2.4 To check it out, let,'s take this strange implementation of pairs and verify that this implementation satisfies the contract for a Slide 13. 2.5 Example: What is our"pair object? To test this, lets cons together the numbers l and 2, and give the resulting pair the name foo (det ine too (cons 1 2)) 600SC

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. what value to return. We call this style of programming, message passing, because the procedure accepts a message as input, and then does something based on the value of that message. Slide 13.2.3 This looks a bit weird! Our constructor for gluing things together gives us a procedure as the actual object. Should we care? Of course we know that we shouldn't care. To complete the abstraction for a pair, we simply need to create car and cdr to fulfill the contract of the abstraction of a pair. Each of those is itself a procedure that takes as input a pair, which we know is a procedure, and then applies that procedure to a single argument, which in this case is just a symbolic message. Ideally, that message should get back for us the value we need to satisfy the contract. If we look at this definition for car, we see it takes as input one of these new pairs, and then applies that pair (a procedure) to the symbol car, which in principle should return for us the value we used when we created the pair. Note the other procedure we built here. Our predicate for testing whether something is a pair now relies on the pair identifying itself. This is the version of our tag. Before we attached a tag as a symbol on a data structure. Here, our tags are part of the procedure. Slide 13.2.4 To check it out, let's take this strange implementation of pairs and verify that this implementation satisfies the contract for a pair. Slide 13.2.5 To test this, lets cons together the numbers 1 and 2, and give the resulting pair the name foo

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 13.2.6 Example: What is our"pair"object? So here is an environment diagram that would represent the (define foo (cons 1 2)) state of the world, before we do this definition. In the global environment, we would have a binding for cons as a procedure, based on the previous slide 6 001 SICP Slide 13.2.7 Example: What is our"pair object? What happens when we evaluate this expression? Since cons (define too (ooms 1 2))P is just a procedure, evaluating (cons 1 2) says to apply the procedure associated with cons to the arguments I and 2 Thus, we drop a frame, scope it by the environment pointer of the procedure, bind the formal parameters(X and y) of the procedure to the values of the arguments, and relative to that new frame, and evaluate the body of the procedure. That body is itself a lambda! So it makes a new procedure object whose environment pointer points to the frame El because that where the l ambda was evaluated. Then, the procedure object is returned as the value of the cons. Finally, the define binds foo in the global environment to this returned value, this procedure object Example: What is our "pair object? Slide 13.28 Notice what this does. It gives us an object in this environment, (olefine too where by object I mean the thing enclosed in red, which is a procedure that has a local frame with some bindings or values within it. Thus, x being bound to 1, and y being bound to 2 constitutes local state information. That frame is scoped by the global environment, and the procedure that points to all of this is referred to by a name in the global environment. Thus, from the perspective of a user interacting at the global environment, foo refers to a structure that has within it information about 6001Sc I what is the first part of the object(1)and what is the second part of the object (2). It should also have information about how to extract those values from the structure So this pattern: of a procedure that accepts messages, has access to a local frame with state and methods to extract that local state; is a very common pattern that we are going to use a lot

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 13.2.6 So here is an environment diagram that would represent the state of the world, before we do this definition. In the global environment, we would have a binding for cons as a procedure, based on the previous slide. Slide 13.2.7 What happens when we evaluate this expression? Since cons is just a procedure, evaluating (cons 1 2) says to apply the procedure associated with cons to the arguments 1 and 2. Thus, we drop a frame, scope it by the environment pointer of the procedure, bind the formal parameters (x and y) of the procedure to the values of the arguments, and relative to that new frame, and evaluate the body of the procedure. That body is itself a lambda! So it makes a new procedure object, whose environment pointer points to the frame E1 because that is where the lambda was evaluated. Then, the procedure object is returned as the value of the cons. Finally, the define binds foo in the global environment to this returned value, this procedure object. Slide 13.2.8 Notice what this does. It gives us an object in this environment, where by object I mean the thing enclosed in red, which is a procedure that has a local frame with some bindings or values within it. Thus, x being bound to 1, and y being bound to 2 constitutes local state information. That frame is scoped by the global environment, and the procedure that points to all of this is referred to by a name in the global environment. Thus, from the perspective of a user interacting at the global environment, foo refers to a structure that has within it information about what is the first part of the object (1) and what is the second part of the object (2). It should also have information about how to extract those values from the structure. So this pattern: of a procedure that accepts messages, has access to a local frame with state and methods to extract that local state; is a very common pattern that we are going to use a lot

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 13.2.9 Now all we have to do is check that the contract holds for thisExample: What is our"pair"object? data abstraction. In doing so, we will see how this structure of a (cons 1 2)) procedure with access to local state captures exactly the becomes(f∞tCR) behavior we want To check this, lets evaluate(car foo). We know that this"as should get converted into (foo car), so how does this happen? 6001 sICP Example: What is our"pair"object? Slide 13.2.10 aluating(car foo) in the globa ( Define foo(cons12)】 (car fod) becomes (foo 1CRR) applies the procedure that is the value associated with car to the value of foo which is the procedure object shown. Now he definition of car shows that this reduces to evaluating the body of car namely (foo 'car)with respect to some po new environment Slide 13.2.1 Example: What is our "pair object? and what does that do? It says to apply the value associated with foo, which is a procedure, so the standard environment (cons 1 2)) model says to drop a frame, and scope it by the environment ar foo) becomes (foo .CAR) pointer of foo. This is important as E3 now points to E1 Inside e3 we bind the parameter ms g to the argument car Relative to this frame we evaluate the body of the procedure epresented by foo. but that is just a cond clause that looks at the value of ms g and compares it to a set of symbols. In this case, the cond says to return the value of x with respect to 60015e this frame, which is just 1. This is exactly what I wanted, as it shows that my contract is satisfied

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 13.2.9 Now all we have to do is check that the contract holds for this data abstraction. In doing so, we will see how this structure of a procedure with access to local state captures exactly the behavior we want. To check this, lets evaluate (car foo). We know that this should get converted into (foo 'car), so how does this happen? Slide 13.2.10 Evaluating (car foo) in the global environment simply applies the procedure that is the value associated with car to the value of foo which is the procedure object shown. Now the definition of car shows that this reduces to evaluating the body of car namely (foo 'car) with respect to some new environment. Slide 13.2.11 ... and what does that do? It says to apply the value associated with foo, which is a procedure, so the standard environment model says to drop a frame, and scope it by the environment pointer of foo. This is important as E3 now points to E1. Inside E3 we bind the parameter msg to the argument car. Relative to this frame we evaluate the body of the procedure represented by foo. But that is just a cond clause that looks at the value of msg and compares it to a set of symbols. In this case, the cond says to return the value of x with respect to this frame, which is just 1. This is exactly what I wanted, as it shows that my contract is satisfied

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 13.2.12 Example: What is our"pair"object? So what does all this say? Aside from showing that our contract is fulfilled, that what we glue together using this version of cons we can get back apart using car or cdr, we have also seen this common pattern that we can create a data object represented as a procedure. The procedure has some local state captured in a frame that is accessible only by that procedure and it has the ability to accept messages and based on those messages return information from the local state So let's see how to build on that idea q60s7 Slide 13.2.13 Pair Mutation as Change in State n the case we just considered, our procedures for data (define structures could return values as a function of input messages If we are going to use this idea of message-passing procedures to represent information, we also need to have ways of ((eq? nsg 'pAIR?) it) ((eq? nsg SET-CARI) changing the value of the state captured by those procedures. In lambda (new-car)(set! x new-car))) our pair example, here is how we would do this (⊥ ambda w-cctr)(set I y nesw-cdr))) Pair Mutation as change in State Slide 13.2.14 (det ine (cons x y) Let's add two more messages, or two more ways of dealing with messages, to our constructor, cons: one for dealing with cond ((eq? nsg CAR) x) mutating the car and one for dealing with mutating the cdr mbda (newcar) (setI x new-car))) Notice that in this case we need something different If the ((eq? nsgSET-CDRI (I ambda (new-cdr) (setI y new-cdr))) cons pair (i.e. one of these procedures)gets the message talso( oror" pair cannot”重sg))) set-car! we are going to return a procedure that will take a new value for the car and change the old value to this 6 001 SICP I This is a different behavior from before. Now a message gets us back a procedure rather than a number

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 13.2.12 So what does all this say? Aside from showing that our contract is fulfilled, that what we glue together using this version of cons we can get back apart using car or cdr, we have also seen this common pattern that we can create a data object represented as a procedure. The procedure has some local state captured in a frame that is accessible only by that procedure and it has the ability to accept messages and based on those messages return information from the local state. So let's see how to build on that idea. Slide 13.2.13 In the case we just considered, our procedures for data structures could return values as a function of input messages. If we are going to use this idea of message-passing procedures to represent information, we also need to have ways of changing the value of the state captured by those procedures. In our pair example, here is how we would do this. Slide 13.2.14 Let's add two more messages, or two more ways of dealing with messages, to our constructor, cons: one for dealing with mutating the car and one for dealing with mutating the cdr. Notice that in this case we need something different. If the cons pair (i.e. one of these procedures) gets the message set-car! we are going to return a procedure that will take a new value for the car and change the old value to this new value. This is a different behavior from before. Now a message gets us back a procedure rather than a number

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 13.2.15 As a consequence the procedure set-car! must have a Pair Mutation as Change in State new form. As before, it will take a pair and a new value as arguments, but now it sends the pair(that procedure)the (oand ((eq? Bsg CAR) x) ((eq? nsg CDR) y) message set-car!, which gives us the procedure needed to change values, and we then apply that procedure to the new (lambda (new-car)(set! x new-car))) value. You can see that the definition accomplishes exactly this (dlet ine (set! p new-car) ((P SET-CARI new-car)) detine (sot-odrI p new-cdr) ((P SET-CDRL now-cdr) 6001 sICP Example: Mutating a pair object Slide 13.2.16 (define bar (cons 3 4)) So let's trace this through. Here is a definition for bar to be the cons of 3 and 4, and here is the global environment in which we are going to do this Slide 13.2.17 Example: Mutating a pair object When we evaluate this expression we simply get a structure similar to what we saw before. a binding of bar to a procedure with some local state. Thus, we have bar as a message-passing object bady: (cod 60015e Example: Mutating a pair object Slide 13.2.18 &detine bar (oons 3 0,0 So now let's mutate this object. Let's change the car part of ts thar sa - gs this object to be 0. Then evaluating (set-car! bar 0)reduces to evaluating((bar 'set-car!) 0) in some other frame. Now how does evaluating this expression effect the right mutation? body: (cund 4

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 13.2.15 As a consequence, the procedure set-car! must have a new form. As before, it will take a pair and a new value as arguments, but now it sends the pair (that procedure) the message set-car!, which gives us the procedure needed to change values, and we then apply that procedure to the new value. You can see that the definition accomplishes exactly this. Slide 13.2.16 So let's trace this through. Here is a definition for bar to be the cons of 3 and 4, and here is the global environment in which we are going to do this. Slide 13.2.17 When we evaluate this expression we simply get a structure similar to what we saw before, a binding of bar to a procedure with some local state. Thus, we have bar as a message-passing object. Slide 13.2.18 So now let's mutate this object. Let's change the car part of this object to be 0. Then evaluating (set-car! bar 0) reduces to evaluating ((bar 'set-car!) 0) in some other frame. Now how does evaluating this expression effect the right mutation?