6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 1l.2.1 Now. lets see how mutation can be used to build efficient data Stack Data Abstraction structures. We are first going to build a very useful data abstraction without mutation, then see how mutation changes its behavior The abstraction we are going to build is a stack, and it behaves just like a stack of dishes in a cafeteria. You can push a new plate onto the top of the stack and you can remove a plate from the top of the stack, but these are the only two operations you can execute on a stack. This is also referred to as a last in first out data structure. for the obvious reason 6001 sICP Stack Data Abstraction Slide 11.2.2 Here is our data abstraction template for a stack. Our retums an empty stack constructor creates an empty stack, and our single selector gets selectors. retums current top element from a stack he value of the top element of the stack (t。pat The operations on the stack will help change its status. We have apatit tank at) retum a e stack wth the lemen an operation for pushing a new element onto the top of the stack, returning a new stack. We have an operation for popping ment remeved from the stack the top element from the stack, and returning the new, smaller tempty-atack?stack)retums # if no elements. *f othenwise stack. And we have a predicate for testing whether the stack is 601 SICP Notice that the selector gets the value of an element of the stack, while the operations create new stacks as a whole Slide 11.2.3 Stack Contract To be careful. we should define the contract for a stack especially the relationship between the constructor, the selector mber of⊥n当ext⊥c number of delet and the operations that manipulate a stack. Here is a somewhat formal definition but we can trace through the intuitive idea If we let s be a stack constructed initially to be empty, and we 2, then (empty-stack? s)is true, and Ktop s)and (delete s)are errors have performed i insertions, and j deletions, then here is the If y<f then (empty-stack? s) is false and contract on the stack's behavior If we have tried to do more deletions than insertions this must 4,旷y=then《top( next8val))=va be an error; we can't more things out that we put in If we have made exactly the same number of insertions and 6001se deletions, then clearly the stack should be empty and trying to l d ither get the top element or delete something from the stack should be an error importantly, if we insert something, then delete it the top element of the stack after this pair of operations shoulo a If on the other hand we have made more insertions than deletions, then clearly the stack should not be empty. me be the same as it was before this pair of operations. That is, nothing has changed in the stack below this point Finally, if we have a legal stack, then if we push an element onto the stack and look at the top element of the stack, we see exactly this element that we just pushed So we see that the stack contract describes exactly the "last in first out" behave we want6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 11.2.1 Now, lets see how mutation can be used to build efficient data structures. We are first going to build a very useful data abstraction without mutation, then see how mutation changes its behavior. The abstraction we are going to build is a stack, and it behaves just like a stack of dishes in a cafeteria. You can push a new plate onto the top of the stack and you can remove a plate from the top of the stack, but these are the only two operations you can execute on a stack. This is also referred to as a last in, first out data structure, for the obvious reason. Slide 11.2.2 Here is our data abstraction template for a stack. Our constructor creates an empty stack, and our single selector gets the value of the top element of the stack. The operations on the stack will help change its status. We have an operation for pushing a new element onto the top of the stack, returning a new stack. We have an operation for popping the top element from the stack, and returning the new, smaller stack. And we have a predicate for testing whether the stack is empty. Notice that the selector gets the value of an element of the stack, while the operations create new stacks as a whole. Slide 11.2.3 To be careful, we should define the contract for a stack, especially the relationship between the constructor, the selector and the operations that manipulate a stack. Here is a somewhat formal definition, but we can trace through the intuitive idea. If we let s be a stack constructed initially to be empty, and we have performed i insertions, and j deletions, then here is the contract on the stack's behavior. If we have tried to do more deletions than insertions, this must be an error; we can't more things out that we put in. If we have made exactly the same number of insertions and deletions, then clearly the stack should be empty, and trying to either get the top element or delete something from the stack should be an error. If on the other hand we have made more insertions than deletions, then clearly the stack should not be empty. More importantly, if we insert something, then delete it, the top element of the stack after this pair of operations should be the same as it was before this pair of operations. That is, nothing has changed in the stack below this point. Finally, if we have a legal stack, then if we push an element onto the stack and look at the top element of the stack, we see exactly this element that we just pushed. So we see that the stack contract describes exactly the "last in, first out" behave we want