Slide 1Office Hours Location…OverviewDesigning a data abstractionDesigning a data abstraction: constructorsDesigning a data abstraction: accessorsDesigning a data abstraction: operatorsHow constructor choices affect operatorsMany different representations are possibleRepresentation mattersRepresentations also have implicit assumptionsPain Error Checking is Your FriendRespect abstraction boundariesSummary of data abstraction design1 6.001 Recitation 7: Data Abstraction II28 Feb 2007RI: Gerald Dalley ([email protected]) Announcements•Solutions, handouts, etc.:•http://people.csail.mit.edu/dalleyg/6.001/SP2007/•primes-in-range discussion & orders of growth•Office Hours•Thursdays, 2-3PM, 32-D4072 Office Hours Location…from Gates TowerRecitation room (3rd floor) /west side of campusElevatorsFaculty Lunch Area3 Overview•Today: prime factorization, an extended example•This is a nice example for several reasons:•Interesting design decisions•Practice with writing types –(using prime and pf as new types)•Related to primality testing from yesterday’s lecture•primes are also important to Project 1…which is due next Friday.4 Designing a data abstraction•Prime factorization: representing an integer as the product of its prime factors 2 = 2 = 21 4 = 2∙2 = 22 6 = 2∙3 = 21∙31 40 = 2∙2∙2∙5 = 23∙51187 = 11∙17 = 111∙171What about 1? What about 0? What about negative integers?5 (make-prime-factors n): (make-prime-factors 40) 2*2*2*5prime-factors-of-1: (add-prime-factor p pf): (add-prime-factor 5 (add-prime-factor 2 prime-factors-of-1)) 2*5(make-prime-factors p): (add-prime-factor p pf): (make-prime-factors 2) => 2 (add-prime-factor 5 (make-prime-factors 2)) 2*5(make-prime-factors factors): (make-prime-factors (list 2 2 2 5)) 2*2*2*5Designing a data abstraction: constructorsNew typesprime = subset of integers that are primepf = prime factorization data typeinteger pflist<prime> pfprime pfprime, pf pfpfprime, pf pf6 Designing a data abstraction: accessorsFor now, assume our constructor is (make-prime-factors n)(get-unique-factors pf):(get-multiplicity pf p): contract: let (p0 ... pi) = (get-unique-factors (make-prime-factors n)) and mi = (get-multiplicity (make-prime-factors n) pi) then n = product of pimi (get-all-factors pf): contract: product of (get-all-factors (make-prime-factors n)) = n(get-number pf): contract: (get-number (make-prime-factors n)) = npf intpf list<prime>pf list<prime>pf, prime integer7 Designing a data abstraction: operators+pf, -pfNot really appropriate for this data type. The only way to do it is converting to integer and then factorizing again.(*pf pf1 pf2): returns factorization of n1*n2(/pf pf1 pf2): returns factorization of n1/n2 if n2 divides n1(gcd-pf pf1 pf2): returns factorization of greatest common divisor of pf1 and pf2(=pf pf1 pf2): tests whether two factorizations are the same(divides-pf? pf1 pf2): tests whether pf1 divides evenly into pf2(has-factor? pf p): tests whether p is a prime factor of pfpf,pf booleanpf,pf booleanpf,prime booleanpf,pf pfpf,pf pfpf,pf pf8 How constructor choices affect operatorsOne constructorSuppose our only constructor is (make-prime-factors n)How do I write *pf: pf,pf pf ?(define (*pf pf1 pf2) (make-prime-factors (* (get-number pf1) (get-number pf2))))(define (*pf pf1 pf2) : pf,pf pf (let ((combined-factors (append (get-all-factors pf1) (get-all-factors pf2)))) ... how do I make a pf out of the resulting list of factors?))Let's provide two constructors:(factorize n) : integer pf(make-prime-factors lst) : list<prime> pf(define (*pf pf1 pf2) (make-prime-factors (append (get-all-factors pf1) (get-all-factors pf2)))9 Many different representations are possible(factorize 40); 40 = 2*2*2*5(2 2 2 5) 2*2*2*5 (sorted order)(2 5 2 2) 2*5*2*2 (order doesn't matter)((2 3) (5 1)) 23 * 51(40 (2 5)) stores n and its unique factors10 Representation matters; representation (2 2 2 5)(define (get-multiplicity pf p) (cond ((null? pf) 0) ((= (car pf) p) (+ 1 (get-multiplicity (cdr pf) p))) ((> (car pf) p) 0) (else (get-multiplicity (cdr pf) p)))); representation ((2 3) (5 1)) (sorted order)(define (get-multiplicity pf p) (cond ((null? pf) 0) ((= (caar pf) p) (get-multiplicity (cadar pf) p)) ((> (car pf) p) 0) (else (get-multiplicity (cdr pf) p)))); representation (40 (2 5))(define (get-multiplicity pf p) (define (multiplicity-of-p-in m) (if (divides? p m) (+ 1 (multiplicity-of-p-in (quotient m p))) 0)) (multiplicity-of-p-in (car pf)))11 Representations also have implicit assumptions(define (make-prime-factors lst) lst)(define (*pf pf1 pf2) (append pf1 pf2)) ... assumes order doesn't matter(define (get-multiplicity pf p) (cond ((null? pf) 0) ((= (car pf) p) (+ 1 (get-multiplicity (cdr pf) p))) ((> (car pf) p) 0) (else (get-multiplicity (cdr pf) p)))) ... assumes sorted order12 Pain Error Checking is Your Friend•Pain •Lets you know you’re alive•Lets you know right away when something bad is happening•Error checking•Lets you know right away when something bad is happening•Pain •Lets you know you’re alive•Lets you know right away when something bad is happening•Error checking•Lets you know right away when something bad is happening(define (add-prime-factor p pf) (if (not (prime? p)) (error "p is not prime") (cons p pf)))(get-multiplicity (add-prime-factor 24 (make-prime-factor 1)) 2)Photo from:http://wongkk.com/13 Respect abstraction boundaries(define (*pf-clean pf1 pf2) (make-prime-factors (append (get-all-factors pf1) (get-all-factors pf2)))(define (*pf-dirty pf1 pf2) (append pf1 pf2))make-prime-factorsget-all-factorsProcedures inside the abstractionboundary "know" that the real representation is (2 5 2 2), and depend on it*pf-clean*pf-dirtyProcedures outside don't care about the representationAbstraction boundary14 Summary of data abstraction design1. Choose constructors and accessors that are useful to clients and that make it possible to write the operators you need•Constructors and accessors should be complete: you need to be able to construct every possible object in the domain, and you need to be able to get out enough data to reconstruct the object •Write down the contract between the
View Full Document
Unlocking...