New version page

CMU CS 15122 - Lecture Notes on Interfaces

Upgrade to remove ads

This preview shows page 1-2-3-4 out of 11 pages.

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

Upgrade to remove ads
Unformatted text preview:

Lecture Notes onInterfaces15-122: Principles of Imperative ComputationFrank PfenningLecture 14March 1, 20111 IntroductionThe notion of an interface to an implementation of an abstract data type or li-brary is an extremely important concept in computer science. The interfacedefines not only the types, but also the available operations on them and thepre- and postconditions for these operations. For general data structures itis also important to note the asymptotic complexity of the operations sothat potential clients can decide if they data structure serves their purpose.For the purposes of this lecture we call the data structures and the op-erations on them provided by an implementation the library and code thatuses the library the client.What makes interfaces often complex is that in order for the library toprovide its services it may in turn require some operations provided by theclient. Hash tables provide an excellent example for this complexity, so wewill discuss the interface to hash tables in details before giving the hashtable implementation. Binary search trees, discussed in provides anotherexcellent example.2 Generic Hash TablesWe call hash tables generic because the implementation should work re-gardless of the type of keys or elements to be stored in the table.We start with the types. The implementations of which types are pro-vided by the library? Clearly, the type of hash tables.LECTURE NOTES MARCH 1, 2011Interfaces L14.2/* library side types */typedef ___ ht;where we have left it open for now (indicated by ___) how the type ht ofhash tables will eventually be defined. That is really the only type pro-vided by the implementation. In addition, it is supposed to provide threefunctions:/* library side functions */ht ht_new(int m)//@requires m > 0;;elem ht_search(ht H, key k); /* O(1) avg. */void ht_insert(ht H, elem e) /* O(1) avg. *///@requires e != NULL;;The function ht_new(int m) takes the initial size of the hash table as anargument (which must be strictly positive) and returns a new hash tablewithout any elements.The function ht_search(ht H, key k) searches for an element withkey k in the hash table H . If such an element exists, it is returned. If it doesnot exist, we return NULL instead.From these decisions we can see that the client must provide the type ofkeys and the type of elements. Only the client can know what these mightbe in any particular use of the library. In addition, we observe that NULLmust be a value of type elem.The function ht_insert(ht H, elem e) inserts an element e into thehash table H, which is changed as an effect of this operation. But NULLcannot be a valid element to insert, because otherwise we would knowwhether the return value NULL for ht_search means that an element ispresent or not. We therefore require e not to be null.To summarize the types we have discovered will have to come from theclient:/* 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.LECTURE NOTES MARCH 1, 2011Interfaces L14.3Does the client also need to provide any functions? Yes! Any functionthe hash table requires which must understand the implementations of thetype elem and key must be provided by the client, since the library is sup-posed to be generic.It turns out there are three. First, and most obviously, we need a hashfunction which maps keys to integers. We also provide the hash functionwith a modulus, which will be the size of array in the hash table implemen-tion./* 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 imple-mentation to achieve its advertised asymptotic complexity, the hash func-tion should have the property that its results are evenly distributed be-tween 0 and m. Interestingly, it will work correctly (albeit slowly), as longas 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 in-teger and retrieve the chain of elements stored in this slot in the array. Thenwe walk down the chain and compare keys of the stored elements with thesearch 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.LECTURE NOTES MARCH 1, 2011Interfaces L14.4This 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); /* O(1) avg. */void ht_insert(ht H, elem e) /* O(1) avg. *///@requires e != NULL;;3 A Tiny ClientOur sample application is to count word occurrences in the collected worksof Shakespeare. In this application, the keys are the words, representedas strings. Data elements are pairs of words and word counts, the latterrepresented as integers.LECTURE NOTES MARCH 1, 2011Interfaces 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 FunctionOne question we have to answer is how to hash strings, that is, how to mapstring to integers so that the integers are evenly distributed now matterhow the input strings are distributed.Pseudorandom number generators satisfy a similar criterion. They haveto generate numbers that are uniformly distributed over the range of inte-gers, here −231to 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


View Full Document
Download Lecture Notes on Interfaces
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 Lecture Notes on Interfaces 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 Lecture Notes on Interfaces 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?