Lecture Notes on Interfaces 15 122 Principles of Imperative Computation Frank Pfenning Lecture 14 March 1 2011 1 Introduction The notion of an interface to an implementation of an abstract data type or library is an extremely important concept in computer science The interface defines not only the types but also the available operations on them and the pre and postconditions for these operations For general data structures it is also important to note the asymptotic complexity of the operations so that potential clients can decide if they data structure serves their purpose For the purposes of this lecture we call the data structures and the operations on them provided by an implementation the library and code that uses the library the client What makes interfaces often complex is that in order for the library to provide its services it may in turn require some operations provided by the client Hash tables provide an excellent example for this complexity so we will discuss the interface to hash tables in details before giving the hash table implementation Binary search trees discussed in provides another excellent example 2 Generic Hash Tables We call hash tables generic because the implementation should work regardless of the type of keys or elements to be stored in the table We start with the types The implementations of which types are provided by the library Clearly the type of hash tables L ECTURE N OTES M ARCH 1 2011 Interfaces L14 2 library side types typedef ht where we have left it open for now indicated by how the type ht of hash tables will eventually be defined That is really the only type provided by the implementation In addition it is supposed to provide three functions library side functions ht ht new int m requires m 0 elem ht search ht H key k void ht insert ht H elem e requires e NULL O 1 avg O 1 avg The function ht new int m takes the initial size of the hash table as an argument which must be strictly positive and returns a new hash table without any elements The function ht search ht H key k searches for an element with key k in the hash table H If such an element exists it is returned If it does not exist we return NULL instead From these decisions we can see that the client must provide the type of keys and the type of elements Only the client can know what these might be in any particular use of the library In addition we observe that NULL must be a value of type elem The function ht insert ht H elem e inserts an element e into the hash table H which is changed as an effect of this operation But NULL cannot be a valid element to insert because otherwise we would know whether the return value NULL for ht search means that an element is present or not We therefore require e not to be null To summarize the types we have discovered will have to come from the client client side types typedef elem typedef key We have noted the fact that elem must be a pointer by already filling in the in its definition Keys in contrast can be arbitrary L ECTURE N OTES M ARCH 1 2011 Interfaces L14 3 Does the client also need to provide any functions Yes Any function the hash table requires which must understand the implementations of the type elem and key must be provided by the client since the library is supposed to be generic It turns out there are three First and most obviously we need a hash function which maps keys to integers We also provide the hash function with a modulus which will be the size of array in the hash table implemention client side functions int hash key k int m requires m 0 ensures 0 result result m The result must be in the range specified by m For the hash table implementation to achieve its advertised asymptotic complexity the hash function should have the property that its results are evenly distributed between 0 and m Interestingly it will work correctly albeit slowly as long as hash satisfies its contract even for example if it maps every key to 0 Now recall how lookup in a hash table works We map the key to an integer and retrieve the chain of elements stored in this slot in the array Then we walk down the chain and compare keys of the stored elements with the search key This requires the client to provide two additional operations one to compare keys and one to extract a key from an element client side functions bool key equal key k1 key k2 key elem key elem e requires e NULL Key extraction works only on elements that are not null L ECTURE N OTES M ARCH 1 2011 Interfaces L14 4 This completes the interface which we now summarize client side interface typedef elem typedef key int hash key k int m requires m 0 ensures 0 result result m bool key equal key k1 key k2 key elem key elem e requires e NULL library side interface struct ht typedef struct ht ht ht ht new int m requires m 0 elem ht search ht H key k void ht insert ht H elem e requires e NULL 3 O 1 avg O 1 avg A Tiny Client Our sample application is to count word occurrences in the collected works of Shakespeare In this application the keys are the words represented as strings Data elements are pairs of words and word counts the latter represented as integers L ECTURE N OTES M ARCH 1 2011 Interfaces L14 5 client side implementation struct wcount string word int count int hash string s int m return hash string s m from hash string c0 bool key equal string s1 string s2 return string equal s1 s2 string elem key struct wcount wc return wc word We can now fill in the types in the client side of the interface typedef struct wcount elem typedef string key 4 A Universal Hash Function One question we have to answer is how to hash strings that is how to map string to integers so that the integers are evenly distributed now matter how the input strings are distributed Pseudorandom number generators satisfy a similar criterion They have to generate numbers that are uniformly distributed over the range of integers here 231 to 231 1 Their interface is pretty simple library file rand h0 typedef struct rand rand t rand t init rand int seed int rand rand t gen One can generate a random number generator type rand t by initializing it with an arbitrary seed Then we can generate a sequence of random numbers by repeatedly calling rand on such a generator L ECTURE N OTES M ARCH 1 2011 Interfaces L14 6 We now show a so called linear congruential pseudorandom number generator It stores a last random number or the seed at the start and generates the next number by just one …