1 16.001 SICPData abstraction revisited• Data structures: association list, vector, hash table• Table abstract data type• No implementation of an ADT isnecessarily "best"• Abstract data types are a techniquefor information hiding• in the types as well as in the codeCONCRETEABSTRACTCONCEPT 2Table: a set of bindings• binding: a pairing of a key and a value• Abstract interface to a table:• make create a new table• put! key valueinsert a new bindingreplaces any previous binding of that key• get keylook up the key, return the corresponding value• This definition IS the table abstract data type• Code shown later is a particular implementation of theADT 3Examples of using tablesFredJohnBillPeople3448Age200019991998AgeJobPay34Values associated with keys might be data structures..Values might be shared by multiple structures 4Traditional LISP structure: association list• A list where each element is a list of the key and value.15x20yx: 15y: 20 • Represent the table as the alist: ((x 15) (y 20)) 5Alist operation: find-assoc(define (find-assoc key alist) (cond ((null? alist) #f) ((equal? key (caar alist)) (cadaralist)) (else (find-assoc key (cdr alist)))))(define a1 '((x 15) (y 20)))(find-assoc 'y a1) ==> 2015x20y 6An aside on testing equality• = tests equality of numbers• Eq? Tests equality of symbols• As will see, also tests equality of list structures• Equal? Tests equality of symbols, numbers or lists ofsymbols and/or numbers that print the same• Eqv? Tests equality of list as actual structures, not just prints the same2 7Alist operation: add-assoc(define (add-assoc key val alist) (cons (list key val) alist))(define a2 (add-assoc 'y 10 a1))a2 ==> ((y 10) (x 15) (y 20))(find-assoc 'y a2) ==> 10We say that the new binding for y“shadows” the previous one – you can seehow the find-assoc procedure does this 8Alists are not an abstract data type• Missing a constructor:• Use quote or list to construct(define a1 '((x 15) (y 20)))• There is no abstraction barrier:• Definition in scheme language manual:"An alist is a list of pairs, each of which is called anassociation. The car of an association is called the key."• Therefore, the implementation is exposed. User may operateon alists using list operations.(filter (lambda (a) (< (cadr a) 16)) a1)) ==> ((x 15)) 9Why do we care that Alists are not an ADT?• Modularity is essential for software engineering• Build a program by sticking modules together• Can change one module without affecting the rest• Alists have poor modularity• Programs may use list ops like filter and map on alists• These ops will fail if the implementation of alists change• Must change whole program if you want a different table• To achieve modularity, hide information• Hide the fact that the table is implemented as a list• Do not allow rest of program to use list operations• ADT techniques exist in order to do this 1 0Table1: Table ADT implemented as an Alist(define table1-tag 'table1)(define (make-table1) (cons table1-tag nil))(define (table1-get tbl key) (find-assoc key (cdr tbl)))(define (table1-put! tbl key val) (set-cdr! tbl (add-assoc key val (cdr tbl)))) 1 1Compound 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! 1 2Example 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)3 1 3Example 2: Pair/List Mutation(define x (list 'a 'b))a bxX21(set-car! (cdr x) (list 1 2))1. Eval (cdr x) to get apair object2. Change car pointer ofthat pair object• How mutate to achieve theresult at right? 1 4Table1 example(define tt1 (make-table1))(table1-put! tt1 'y 20)(table1-put! tt1 'x 15)tt1table115x(table1-get tt1 ‘y)(define (table1-get tbl key) (find-assoc key (cdr tbl)))(define (table1-put! tbl key val) (set-cdr! tbl (add-assoc key val (cdr tbl))))(define (add-assoc key val alist) (cons (list key val) alist))(define (find-assoc key alist) (cond ((null? alist) #f) ((equal? key (caar alist)) (cadaralist)) (else (find-assoc key (cdr alist)))))20y 1 5How do we know Table1 is an ADT implementation• Potential reasons:• Because it has a type tag No• Because it has a constructor No• Because it has mutators and accessors No• Actual reason:• Because the rest of the program does not apply anyfunctions to Table1 objects other than the functionsspecified in the Table ADT• For example, no car, cdr, map, filter done to tables• The implementation (as an Alist) is hidden from the rest ofthe program, so it can be changed easily 1 6Information hiding in types: opaque names• Opaque: type name that is defined but unspecified• Given functions m1 and m2 and unspecified type MyType: (define (m1 number) ...) ; number → MyType (define (m2 myt) ...) ; MyType → undef• Which of the following is OK? Which is a type mismatch?(m2 (m1 10)) ; return type of m1 matches; argument type of m2(car (m1 10)) ; return type of m1 fails to match; argument type of car; car: pair<A,B> → A• Effect of an opaque name:no functions will match except the functions of the ADT 1 7Types for table1• Here is everything the rest of the program knowsTable1<k,v> opaque typemake-table1 void → Table1<anytype,anytype>table1-put! Table1<k,v>, k, v → undeftable1-get Table1<k,v>, k → (v | null)• Here is the hidden part, only the implementation knows it:Table1<k,v> = symbol × Alist<k,v>Alist<k,v> = list< k × v × null > 1 8Lessons so far• Association list structure can represent the table ADT• The data abstraction technique (constructors, accessors,etc) exists to support information hiding• Information hiding is necessary for modularity• Modularity is essential for software engineering• Opaque type names denote information hiding4 1 9Hash tables• Suppose a program is written using Table1• Suppose we measure that a lot of time is spent intable1-get• Want to replace the implementation with a faster one• Standard data structure for fast table lookup: hash table• Idea:• keep N association lists instead of 1• choose which list to
View Full Document
Unlocking...