DOC PREVIEW
MIT 6 001 - Data Mutation

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 6 001 - Data Mutation

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Data Mutation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Data Mutation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Data Mutation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?