6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide lll14 Sharing, Equivalence and Identity These ideas of mutation and testing of equality raise some How can we tell if two things are equivalent? Interesting For example, if we mutate an object, do Well, what do you mean by""? still have the same object when we are done? The answer is yes 1. The same object: test with eq provided we maintain the same pointer to the object. For 2. Objects that "look"the same: test with equal? cample, if we have some list structure with a pointer to its equa1?(1st12)(1⊥st12))=> (eq?(1st12)(1ist12))=> beginning, and we then mutate the contents of some of the cells If we change an object, is it the same object? in the structure, so long as we keep hold of the pointer to the Yes, if we retain the same pointer to the object beginning of the structure, we consider it to be the same. Its value has changed, but the object's identity is maintained 6 001 SICP his tells us how to keep track of a particular object. A related Sharing, Equivalence and Identity Slide 11.1.15 question is deciding when two objects share a common part How can we tell if two things are equivalent? Well, what do you mean by"equivalent? The answer is that if we mutate one object, and see the same hange occur in the other object, then we can deduce that these (eq?ab)一> 2. Objects that look"the same: test with equal? objects share parts. Because of our notion of equality as eqa1?(1st12)(1ist12))=> pointing to the same object, this means that changing that = shared object through one name will be reflected when seen If we change an object, is it the same object? through the second name If we mutate one, see if the other also changes Sharing, Equivalence and Identity Slide 11.1.16 How can we tell if So what we see is that introducing mutation into our language Well, what do y"equivalent"? has caused us to change how we think about equality, how we 1. The same st with eq? think about the finest level of detail in our representations. That (eq?ab)一># 2. Objects that look"the test with equal has raised interesting issues about identity, equivale equa1?(1ist12)(1st12))= equality and sharing of structure eq?(1s12)(1ist12))=> f an object, is it the same object? Yes, if we retain the same pointer to the object How tell if parts of an object is shared with another? If we mutate one, see if the other also changes Slide 1l.1.17 Your Turn To see if you are catching on to this, here are two definitions for list structure, with the names x and y. What is the value of x=(2) x一山 X after each sequence of evaluations? When you are ready, (set-car! x y) move on to the next slide to check your answers (set-cdr! y (cdr x)
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 11.1.14 These ideas of mutation and testing of equality raise some interesting issues. For example, if we mutate an object, do we still have the same object when we are done? The answer is yes, provided we maintain the same pointer to the object. For example, if we have some list structure with a pointer to its beginning, and we then mutate the contents of some of the cells in the structure, so long as we keep hold of the pointer to the beginning of the structure, we consider it to be the same. Its value has changed, but the object's identity is maintained. Slide 11.1.15 This tells us how to keep track of a particular object. A related question is deciding when two objects share a common part. The answer is that if we mutate one object, and see the same change occur in the other object, then we can deduce that these objects share parts. Because of our notion of equality as pointing to the same object, this means that changing that shared object through one name will be reflected when seen through the second name. Slide 11.1.16 So what we see is that introducing mutation into our language has caused us to change how we think about equality, how we think about the finest level of detail in our representations. That has raised interesting issues about identity, equivalence, equality and sharing of structure. Slide 11.1.17 To see if you are catching on to this, here are two definitions for list structure, with the names x and y. What is the value of x after each sequence of evaluations? When you are ready, move on to the next slide to check your answers
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide lll18 Your turn When we evaluate the set-car! expression, we first get 4+- the value of x, which we know points to the top list structure We also evaluate y, which points to the second list structure Then, we find the car box of the structure pointed to by x, and ((12) break the existing pointer in that box. We replace it with a pointer to the value of y, namely the second list structure as If we now evaluate x, we can see it points to a list of two elements. The first element happens to be a list of two elements, 6 001 SICP Ma I and 2, and the second element is just the number 4.Thus, the value of x prints out as shown Slide 1l.1. 19 Your turn Now remember that time becomes important once mutation is allowed. Thus the change we have just made to x stays in place y==>(1 2) x彐 when we go to evaluate the next mutation. This says to get the value of y, which still points to the second list structure, and car! x y) (12)4) we break the pointer in the cdr part of the cons pair pointed to by y. In its place, we insert a pointer to the value of the set-cdr! y (cdr x) second argument, which is just the cdr pointer of the cons ((14)4) pair pointed to by x If we then evaluate x again we now get the form shown. simply by tracing through the list structure. Notice that due to the sharing of structure, the value of x has changed, even though no explicit expression involving a change in x was evaluated Slide ll1.20 So here is a summary of the key points of this part of the Scheme provides built-in mutators set! to change a binding lecture set-car! and set-cdr! to change a pair Mutation introduces substantial complexity Substitution model is no longer sufficient to explain behavio 6.001 Notes: Section 11.2
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 11.1.18 When we evaluate the set-car! expression, we first get the value of x, which we know points to the top list structure. We also evaluate y, which points to the second list structure. Then, we find the car box of the structure pointed to by x, and break the existing pointer in that box. We replace it with a pointer to the value of y, namely the second list structure as shown. If we now evaluate x, we can see it points to a list of two elements. The first element happens to be a list of two elements, 1 and 2, and the second element is just the number 4. Thus, the value of x prints out as shown. Slide 11.1.19 Now remember that time becomes important once mutation is allowed. Thus the change we have just made to x stays in place when we go to evaluate the next mutation. This says to get the value of y, which still points to the second list structure, and we break the pointer in the cdr part of the cons pair pointed to by y. In its place, we insert a pointer to the value of the second argument, which is just the cdr pointer of the cons pair pointed to by x. If we then evaluate x again, we now get the form shown, simply by tracing through the list structure. Notice that due to the sharing of structure, the value of x has changed, even though no explicit expression involving a change in x was evaluated. Slide 11.1.20 So here is a summary of the key points of this part of the lecture. 6.001 Notes: Section 11.2