6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 11.2.7 While this looks fine, this implementation strategy has a Limitations in our stack problem: our stacks do not have an identity. What does this Stack does not have identity mean? Well consider the example shown. I can first create a stack, and s(make-stack)) s==>() give it a name. Now I insert the element a into that stack, and you can see it returns for me the stack with only the element a(insert s'a)=>(a) it. But if I ask for the value of s i get back the empty list, not =>() this stack? Unfortunately while I created a new list when I did(set! s (insert s'b)) the insertion, I didn't actually change the value pointed to by s, s=>(b) and thus that remains the empty stack Worse yet, I can manipulate pieces of the stack directly. If I 6001 sICP insert b into s, I should get a stack with b and a in it. But I can mutate the name of the stack to point to only part of this stack, thus violated my contract. The problem is that I have not isolated the stack from outside use. I would really like the stack to keep its identity, and to be manipulated only by the contract operations, and we will turn to that in the next section 6.001 Notes: Section 11.3 Slide 11.3.1 Alternative Stack Implementation- pg 1 The first thing we need to do is practice defensive Attach a type tag- defensive programmer programming, that is, put a tag at the front of the structure to Additional benefit identify it. One additional advantage is that the identity of this Provides an object whose identity remains even as the structure will remain the same, even if pieces of it mutate 4 6001 sICP Slide 11.3.2 tach a type tag- defensive programming What does that mean? Well, putting a tag on the front in the standard way would result in our object consisting of a list Provides an object whose identity remains even as the whose first element is the symbolic tag, and whose cdr points to the actual contents of the stack stack6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 11.2.7 While this looks fine, this implementation strategy has a problem: our stacks do not have an identity. What does this mean? Well consider the example shown. I can first create a stack, and give it a name. Now I insert the element a into that stack, and you can see it returns for me the stack with only the element a in it. But if I ask for the value of s I get back the empty list, not this stack? Unfortunately while I created a new list when I did the insertion, I didn't actually change the value pointed to by s, and thus that remains the empty stack. Worse yet, I can manipulate pieces of the stack directly. If I insert b into s, I should get a stack with b and a in it. But I can mutate the name of the stack to point to only part of this stack, thus violated my contract. The problem is that I have not isolated the stack from outside use. I would really like the stack to keep its identity, and to be manipulated only by the contract operations, and we will turn to that in the next section. 6.001 Notes: Section 11.3 Slide 11.3.1 The first thing we need to do is practice defensive programming, that is, put a tag at the front of the structure to identify it. One additional advantage is that the identity of this structure will remain the same, even if pieces of it mutate. Slide 11.3.2 What does that mean? Well, putting a tag on the front in the standard way would result in our object consisting of a list whose first element is the symbolic tag, and whose cdr points to the actual contents of the stack