6.001 Data MutationElements of a Data AbstractionPrimitive DataAssignment -- set!Compound DataExample 1: Pair/List MutationExample 2: Pair/List MutationSharing, Equivalence and IdentitySlide 9Your TurnSlide 11End of part 1Stack Data AbstractionStack ContractStack Implementation StrategyStack ImplementationLimitations in our StackAlternative Stack Implementation – pg. 1Alternative Stack Implementation – pg. 2Alternative Stack Implementation – pg. 3Queue Data Abstraction (Non-Mutating)Queue ContractSimple Queue Implementation – pg. 1Simple Queue Implementation – pg. 2Simple Queue - Orders of GrowthQueue Data Abstraction (Mutating)Better Queue Implementation – pg. 1Queue Helper ProceduresBetter Queue Implementation – pg. 2Queue Implementation – pg. 3Queue Implementation – pg. 4Mutating Queue - Orders of GrowthSummary1/336.001 Data Mutation•Primitive and Compound Data Mutators•Stack Example•non-mutating•mutating •Queue Example•non-mutating•mutating2/33•A data abstraction consists of:•constructors •selectors •mutators •operations •contractElements of a Data Abstraction-- makes a new structure-- changes an existing structure3/33Primitive Data (define x 10) creates a new binding for name;special form x returns value bound to name •To Mutate: (set! x "foo") changes the binding for name;special form4/33Assignment -- set!•Substitution model -- functional programming:(define x 10)(+ x 5) ==> 15 - expression has same value... each time it evaluated (in(+ x 5) ==> 15 same scope as binding)•With assignment:(define x 10)(+ x 5) ==> 15 - expression "value" depends... on when it is evaluated(set! x 94)...(+ x 5) ==> 995/33Compound Data•constructor: (cons x y) creates a new pair p•selectors: (car p) returns car part of pair (cdr p) returns cdr part of pair•mutators: (set-car! p new-x) changes car pointer in pair (set-cdr! p new-y) changes cdr pointer in pair ; Pair,anytype -> undef -- side-effect only!6/33Example 1: Pair/List Mutation(define a (list 1 2))(define b a)a (1 2)b (1 2)1 2ba(set-car! a 10)b ==> (10 2)10XCompare with:(define a (list 1 2))(define b (list 1 2))1 2a1 2b10X(set-car! a 10)b (1 2)7/33Example 2: Pair/List Mutation(define x (list 'a 'b))a bxX21(set-car! (cdr x) (list 1 2))1. Eval (cdr x) to get a pair object2. Change car pointer of that pair object•How mutate to achieve the result at right?8/33Sharing, Equivalence and Identity•How can we tell if two things are equivalent?-- Well, what do you mean by "equivalent"?1. The same object: test with eq?(eq? a b) ==> #t2. Objects that "look" the same: test with equal?(equal? (list 1 2) (list 1 2)) ==> #t(eq? (list 1 2) (list 1 2)) ==> #f1 21 2(1 2) (1 2)9/33Sharing, Equivalence and Identity•How can we tell if two things are equivalent?-- Well, what do you mean by "equivalent"?1. The same object: test with eq?(eq? a b) ==> #t2. Objects that "look" the same: test with equal?(equal? (list 1 2) (list 1 2)) ==> #t(eq? (list 1 2) (list 1 2)) ==> #f•If we change an object, is it the same object? -- Yes, if we retain the same pointer to the object•How tell if part of an object is shared with another? -- If we mutate one, see if the other also changes10/33 x ==> (3 4) y ==> (1 2) (set-car! x y) x ==>followed by (set-cdr! y (cdr x)) x ==> Your Turn3 4x1 2y11/33 x ==> (3 4) y ==> (1 2) (set-car! x y) x ==>followed by (set-cdr! y (cdr x)) x ==> Your Turn3 4x1 2y((1 2) 4)X((1 4) 4)X12/33End of part 1•Scheme provides built-in mutators•set! to change a binding•set-car! and set-cdr! to change a pair•Mutation introduces substantial complexity•Unexpected side effects•Substitution model is no longer sufficient to explain behavior13/33Stack Data Abstraction•constructor: (make-stack) returns an empty stack•selectors: (top stack) returns current top element from a stack•operations: (insert stack elt) returns a new stack with the elementadded to the top of the stack (delete stack) returns a new stack with the topelement removed from the stack (empty-stack? stack) returns #t if no elements, #f otherwise14/33Stack Contract•If s is a stack, created by (make-stack)and subsequent stack procedures, where i is the number of insertions and j is the number of deletions, then1. If j>i then it is an error2. If j=i then (empty-stack? s) is true, and (top s) and (delete s) are errors.3. If j<i then (empty-stack? s) is false and(top (delete (insert s val))) = (top s)4. If j<=i then (top (insert s val)) = val for any val15/33Stack Implementation Strategy•implement a stack as a listdba•we will insert and delete items off the front of the stack16/33Stack Implementation(define (make-stack) nil)(define (empty-stack? stack) (null? stack))(define (insert stack elt) (cons elt stack))(define (delete stack) (if (empty-stack? stack) (error "stack underflow – delete") (cdr stack)))(define (top stack) (if (empty-stack? stack) (error "stack underflow – top") (car stack)))17/33Limitations in our Stack•Stack does not have identity(define s (make-stack))s ==> ()(insert s 'a) ==> (a)s ==> ()(set! s (insert s 'b))s ==> (b)18/33•Attach a type tag – defensive programming•Additional benefit: •Provides an object whose identity remains even as the object mutatesAlternative Stack Implementation – pg. 1•Note: This is a change to the abstraction! User should know if the object mutates or not in order to use the abstraction correctly.acdstacksX(delete! s)19/33Alternative Stack Implementation – pg. 2(define (make-stack) (cons 'stack nil))(define (stack? stack) (and (pair? stack) (eq? 'stack (car stack))))(define (empty-stack? stack) (if (not (stack? stack)) (error "object not a stack:" stack) (null? (cdr stack))))20/33Alternative Stack Implementation – pg. 3(define (insert! stack elt) (cond ((not (stack? stack)) (error "object not a stack:" stack)) (else (set-cdr! stack (cons elt (cdr stack))) stack)))(define (delete! stack) (if (empty-stack? stack) (error "stack underflow – delete") (set-cdr! stack (cddr stack))) stack)(define (top stack) (if (empty-stack? stack) (error "stack underflow – top") (cadr stack)))21/33Queue Data Abstraction (Non-Mutating)•constructor: (make-queue) returns an empty queue•accessors: (front-queue q) returns the object at the front of thequeue. If queue is empty signals error•mutators: (insert-queue q elt) returns a new queue with
View Full Document