Table a set of bindings 6 001 SICP Data abstraction revisited Data structures association list vector hash table CONCRETE put key value insert a new binding replaces any previous binding of that key get key look up the key return the corresponding value Table abstract data type No implementation of an ADT is necessarily best Abstract data types are a technique for information hiding in the types as well as in the code binding a pairing of a key and a value Abstract interface to a table make create a new table This definition IS the table abstract data type Code shown later is a particular implementation of the ADT ABSTRACT CONCEPT 1 2 Examples of using tables Traditional LISP structure association list People A list where each element is a list of the key and value Fred John Age Job Bill Represent the table 34 2000 1999 Pay x 15 y 20 as the alist x 15 y 20 1998 Age 34 48 Values associated with keys might be data structures x Values might be shared by multiple structures 15 3 An aside on testing equality define find assoc key alist cond null alist f equal key caar alist cadar alist else find assoc key cdr alist Eq Equal Eqv x 15 y 20 4 Alist operation find assoc define a1 x 15 y 20 find assoc y a1 20 y tests equality of numbers Tests equality of symbols As will see also tests equality of list structures Tests equality of symbols numbers or lists of symbols and or numbers that print the same Tests equality of list as actual structures not just prints the same 20 5 6 1 Alist operation add assoc Alists are not an abstract data type define add assoc key val alist cons list key val alist Missing a constructor Use quote or list to construct define a1 x 15 y 20 define a2 add assoc y 10 a1 a2 y 10 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 an association The car of an association is called the key find assoc y a2 10 Therefore the implementation is exposed User may operate on alists using list operations We say that the new binding for y shadows the previous one you can see how the find assoc procedure does this filter lambda a cadr a 16 a1 x 15 7 Why do we care that Alists are not an ADT 8 Table1 Table ADT implemented as an Alist Modularity is essential for software engineering Build a program by sticking modules together Can change one module without affecting the rest define table1 tag table1 Alists have poor modularity Programs may use list ops like filter and map on alists define table1 get tbl key find assoc key cdr tbl define make table1 cons table1 tag nil These ops will fail if the implementation of alists change Must change whole program if you want a different table define table1 put tbl key val set cdr tbl add assoc key val cdr tbl 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 9 Compound Data constructor cons x y selectors car p cdr p 10 Example 1 Pair List Mutation define define a 1 b 1 creates a new pair p returns car part of pair returns cdr part of pair a list 1 2 b a 2 2 a X b 1 set car a 10 b 10 2 Compare with 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 a X define a list 1 2 1 b 1 2 11 2 10 define b list 1 2 set car a 10 2 10 b 1 2 12 2 define table1 get tbl key find assoc key cdr tbl Example 2 Pair List Mutation Table1 example define tt1 make table1 define x list a b x a table1 put tt1 y 20 X b set car cdr x list 1 2 define add assoc key val alist cons list key val alist table1 put tt1 x 15 table1 get tt1 y How mutate to achieve the result at right define find assoc key alist cond null alist f equal key caar alist cadar alist else find assoc key cdr alist tt1 1 define table1 put tbl key val set cdr tbl add assoc key val cdr tbl 2 table1 1 Eval cdr x to get a pair object 2 Change car pointer of that pair object x 15 y 20 13 How do we know Table1 is an ADT implementation Potential reasons Because it has a type tag Because it has a constructor Because it has mutators and accessors 14 Information hiding in types opaque names Opaque type name that is defined but unspecified No No No Given functions m1 and m2 and unspecified type MyType define m1 number number MyType define m2 myt MyType undef Actual reason Because the rest of the program does not apply any functions to Table1 objects other than the functions specified in the Table ADT For example no car cdr map filter done to tables 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 The implementation as an Alist is hidden from the rest of the program so it can be changed easily Effect of an opaque name no functions will match except the functions of the ADT 15 16 Types for table1 Lessons so far Here is everything the rest of the program knows Association list structure can represent the table ADT Table1 k v make table1 table1 put table1 get The data abstraction technique constructors accessors etc exists to support information hiding opaque type void Table1 anytype anytype Table1 k v k v undef Table1 k v k v null Information hiding is necessary for modularity Here is the hidden part only the implementation knows it Modularity is essential for software engineering Table1 k v symbol Alist k v Alist k v list k v null Opaque type names denote information hiding 17 18 3 Hash tables Example hash function Suppose a program is written using Table1 Suppose we measure that a lot of time is spent in table1 get A table where the keys are points 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 search using a hash function given the key hash function computes a number x where 0 x N 1 point graphic object 5 5 circle 4 10 6 square 8 define hash a point point N modulo x coor point y coor point N modulo …
View Full Document
Unlocking...