Full text
Shortcuts: Abstract \Pointers" J. Marco [email protected] c.es X. Franch franc[email protected] c.es Dept. Llenguatges i Sistemes Informatics (LSI) Universitat Politecnica de Catalunya (UPC) Campus Nord Jordi Girona Salgado, 1-3 08034 BARCELONA Abstract In this work we present the sp ecication and the implementation of a new abstract data typ e (ADT) called STORE . This new ADT allows the storage of a given collection of elements oering an abstract mechanism that supplies a direct access to them, alternative to the metho d dened by the standard op erations of usual ADTs. The interest of the new mechanism stems from the eciency of p ointers, while avoiding the loss of mo dularity that usually o ccurs when p ointers are used. The implementation of the op erations oered by the new ADT is done by derivation from the equational sp ecication. The representation chosen for the implementation of the new ADT makes the eciency previously mentioned p ossible, even when the representation strategy requires the movement of the elements. 1
Contents 1Intro duction 3 2 The ADT STORE 4 2.1 Op erations . ... ... .. ... ... ... ... ... .. ... ... ... ... ... . 5 2.1.1 Constructor Op erations . ... ... ... ... .. ... ... ... ... ... . 5 2.1.2 Observer Op erations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.3 Mo dier Op erations ... ... ... ... ... .. ... ... ... ... ... . 6 2.2 Equational sp ecication .. ... ... ... ... ... .. ... ... ... ... ... . 6 2.2.1 Equations b etween Constructor Op erations .. .. ... ... ... ... ... . 6 2.2.2 Equations of the Observer Op erations .. ... .. ... ... ... ... ... . 8 2.2.3 Equations of Mo dier Op erations . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Implementation in Main Memory 14 3.1 The Typ e Representation . ... ... ... ... ... .. ... ... ... ... ... . 15 3.2 Deriving co de for the op erations ... ... ... ... .. ... ... ... ... ... . 19 3.2.1 Derivation of put .. ... ... ... ... ... .. ... ... ... ... ... . 19 3.3 Chosing implementations for the comp onents of the representation . ... ... ... . 25 4 An Example: The Tennis Ladder 26 4.1 Aho, Hop croft & Ullman's Solutions to the Problem . .. ... ... ... ... ... . 26 4.2 The solution with the ADT STORE . ... ... ... .. ... ... ... ... ... . 28 5 Co dications 29 6 Conclusions 30 2
1 Intro duction The presentwork deals with the metho dology of mo dular program developmentby means of abstract data typ es (ADT). The mo dular metho dology oers many imp ortant prop erties such as understanding, abstraction, reusability, etc., but, often, it implies a loss of eciency due to the imp ossibili tyof accessing implementation of ADTs from other mo dules. Often, while designing a data structure, we face the problem of reducing the space cost (i.e., minimising redundant data) or the temp oral cost (i.e., accessing more faster to data). Toovercome these problems wemay need an implementation which p ermits the access to the data by means of p ointers (see, e.g, 1, pag. 149]). Recall that the notion of pointer corresp onds to the memory address of a given ob ject (with some high-level facilities, whichvary among the dierent programming languages). Unfortunately, the use of p ointers causes in general a complete loss of mo dularity b ecause: It is necessary to know the underlying data structure used in the implementation and therefore, information hiding is not accomplished. Correctness pro ofs and software maintenance and reusability are, in general, more complicated. Also, programs are more dicult to understand. An implementation using p ointers needs to guarantee that data will not change their p osition in the structure otherwise wewould not access the desired information (unless all client mo dules keep trackof changes and this may b e imp ossible). When the implementation is done by means of p ointers not only the ADT op erations can b e used but also we can access directly to its representation and manipulate it. Therefore, it is p ossible to manipulate ADTs without resp ecting the p olicy dened by their equations. With the aim of avoiding these drawbacks, we prop ose the design of a new ADT, which not only p ermits to store data and to access them bymeans ofakey, but also allows for direct access to data without knowing how they are stored. We should mention that the addition of this mechanism will b e done by dening its formal semantics. Certainly, the idea to study this new ADT comes from the necessity of a compromise b etween mo dularity and eciency. The goal of the presentwork is to present the design of this new ADT which oers, in the one hand, functions of data storage and access bykey to data structures, indep endently of their organization 3
and of the key typ e and, on the other hand, the p ossibility of a direct access to data by means of an address we call the shortcut . Essentially,we obtain an abstract mechanism inside the ADT which corresp onds to the p ointers in b oth concept and eciency. The rest of the pap er is organized as follows. In section 2, we present the algebraic sp ecication of the new ADT showing the sorts and the op erations oered as well as the equations that dene the b ehaviour of each of them. In section 3, wecho ose rst the representation of the new data typ e, then we show the complete derivation of one of the op erations and nally we indicate the cost of each op eration, dep ending on the detailed implementation of the representation used. In section 4, we consider a classic example that requires the use of p ointers for eciency reasons, and where we can see that the use of the new ADT assures the same eciency without losing mo dularity at all. In section 5, we include several conclusions regarding the co dication of the new ADT in ADA, Mo dula-2 and C++. Finally, in section 6, we summarise the advantages of the new ADT and we present some op en questions for further research. This pap er is based on 11], where all the remaining discussions can b e found, regarding the derivation of all the op erations and details of the three implementations. 2 The ADT STORE Since wewant to obtain an ADT which p ermits to store any kind of information, wehave designed an ADT that is \generic" (\parameterized"). The new ADT, called STORE , has the data to b e stored as a parameter , decomp osed into key and information . The parameter key is used to access the data. There are no op erations required on information the sort key must have comparison op erations 1 . The ADT STORE oers two sorts: store: where the data is stored. shortcut: which supplies the direct access to the stored data. 1 From now on, we use the op eration symbol cmp to refer to the equality op eration. 4
2.1 Op erations 2.1.1 Constructor Op erations create: ;! store creates an empty store. put: store, key, information ;!h store, shortcut i returns a pair formed by the resulting store after adding the pair of key and information, and the shortcut whichgives direct access to this pair. Alternatively,we could decomp ose put into two op erations, one for each comp onent of the result. However, wehave preferred the ab ove mentioned structure for the sake of clearness of algebraic sp ecication presented in Subsection 2.2. 2.1.2 Observer Op erations getInfKey: store, key ;! information returns the information asso ciated to the key. Precondition: the key is in the store. getInfSho: store, shortcut ;! information returns the information asso ciated to the shortcut. Precondition: the shortcut has data asso ciated inside the store. getKey: store, shortcut ;! key returns the key asso ciated to the shortcut. Precondition: the shortcut has data asso ciated inside the store. isIn?: store, key ;! bool returns a b o olean value indicating whether the key is in the store. getShortcut: store, key ;! shortcut returns the shortcut asso ciated to the key. Precondition: the key is in the store. isEmpty?: store ;! bool returns a b o olean value indicating whether the store is empty. 5
2.1.3 Mo dier Op erations remove: store, shortcut ;! store returns the resulting store after removing the data asso ciated to the shortcut. Precondition: the shortcut has data asso ciated inside the store. modify: store, shortcut, information ;! store returns the resulting store after substituting the information asso ciated to the shortcut, by the new information. Precondition: the shortcut has data asso ciated inside the store. 2.2 Equational sp ecication Following the general metho d of algebraic sp ecication with initial semantics, wegive rst the equations b etween constructor op erations 4, 5, 6]. 2.2.1 Equations b etween Constructor Op erations It seems that we could assume that the stores b ehave as sets, in that the ordering in which the data are stored is not imp ortant. Actually this happ ens in \table" like ADT's 6]. In order to assure this prop ertywe should have to guarantee that, for a given key ,we obtain always the same shortcut , regardless of the moment in whichthe key and its information are stored. This would imply that dierentkeys could not have the same shortcut otherwise, storing an information and a key implies a risk of mo difying the information of another key (of the same shortcut ) whichwas stored previously. Therefore, there should b e a unique shortcut corresp onding to a key , and this, in turn, requires the number of keys and the keys themselves to b e known b efore hand. Alternatively,we can do it byan injective function from the set of keys to the set of shortcuts. The last requirementis very restrictive, if wewant the store to b e indep endent from the key . Weovercome this restriction, by letting the shortcut to dep end also on the store , and in this way dierentkeys can have the same shortcut , if they are stored in dierent stores. Therefore, the order in which data are stored is imp ortant, and thus stores will not b ehave as sets. Now, let us consider the relations b etween the two consecutive put op erations, when we store some information with a key whichwas previously in the store . Since we can have only a unique information asso ciated to each key , the result will b e that of replacing the information asso ciated to the key by the new information . The question that arises here is: whichisthe shortcut obtained? 6
Since there was a shortcut asso ciated to the key ( i.e., the shortcut obtained when stored the previous information ) and since wewant a unique shortcut corresp onding to the key , then it is precisely the former shortcut the one we will obtain. Let us see the equations which express these relations. Let us start by those related to stores we will use the op eration isIn? which tell us whether the key is in the store. This op eration is used only when the store is not empty, b ecause otherwise the store would not have this relation. In the case when the key is therein, we consider the following two cases: 1. The key is the last one added to the store. 2. The key exists but it is not the last one. In the rst case, the equation is simple it just expresses the fact that the obtained store will b e the same as if the last time we had stored the new information. h isIn?(put(st,k 1 ,i 1 ).store,k 2 ) ^ cmp(k 1 ,k 2 ) i ) put(put(st,k 1 ,i 1 ).store,k 2 ,i 2 ).store = put(st,k 2 ,i 2 ).store In the second case, the equation expresses the swap b etween the two last keys obtaining this: h isIn?(put(st,k 1 ,i 1 ).store,k 2 ) ^: cmp(k 1 ,k 2 ) i ) put(put(st,k 1 ,i 1 ).store,k 2 ,i 2 ).store = put(put(st,k 2 ,i 2 ).store,k 1 ,i 1 ).store Notice that in this case there is no a substitution of the information asso ciated to the key, but applying this equation successively,we will arrive to the rst case since the key is therein. Therefore, we can apply the rst equation and in this way to substitute the information asso ciated to the key. Let us see now the equations for shortcuts. As b efore, we distinguish two cases: 1. The key is the last one added to the store. 2. The key exists, but it is not the last one. In the rst case, we only have to express that the obtained shortcut will b e the one obtained previously. h isIn?(put(st,k 1 ,i 1 ).store,k 2 ) ^ cmp(k 1 ,k 2 ) i ) put(put(st,k 1 ,i 1 ).store,k 2 ,i 2 ).shortcut = put(st,k 1 ,i 1 ).shortcut 7
In the second case wehave to just express that the obtained shortcut will b e the same as the one that wewould have obtained, if the new key and the new information had b een stored in the previous store. h isIn?(put(st,k 1 ,i 1 ).store,k 2 ) ^: cmp(k 1 ,k 2 ) i ) put(put(st,k 1 ,i 1 ).store,k 2 ,i 2 ).shortcut = put(st,k 2 ,i 2 ).shortcut This do es not sp ecify yet completely the b ehaviour of shortcuts, b ecause wehave not considered the case in which the key is not therein in fact, in this case, put may return anyvalue as shortcut but the access to the shortcut should supply the appropriate results. The equations of the op eration getInfSho will describ e this b ehaviour, as given next. 2.2.2 Equations of the Observer Op erations Let us study now the b ehaviour of the observer op erations. The equations of getInfSho : { The rst one will b e an error equation, indicating that the op eration is not dened for an empty store . Recall that this op eration is partial. getInfSho(create,sc) = error { We also include an equation to express, the b ehaviour when the shortcut whose information wewant to consult is the same as the one returned in the last op eration of store .The information that we will obtain will b e the one of this last op eration. In order to compare the shortcuts we will use a private op eration, denoted cmp . h cmp(sc,put(st,k,i).shortcut) i ) getInfSho(put(st,k,i).store,sc) = i { The next equation indicates that, if the shortcut is not the same as the one obtained in the last op eration of put , then the result of consulting the information asso ciated to the shortcut will b e the same as consulting the previous store . h : cmp(sc,put(st,k,i).shortcut) i ) getInfSho(put(st,k,i).store,sc) = getInfSho(st,sc) 8
Notice that, if there was no information asso ciated to the shortcut ,by applying successively this equation, wewould obtain st=create , and therefore from the rst equation this is an error. Equations of getKey , similar to those of getInfSho : getKey(create,sc) = error h cmp(sc,put(st,k,i).shortcut) i ) getKey(put(st,k,i).store,sc) = k h : cmp(sc,put(st,k,i).shortcut) i ) getKey(put(st,k,i).store,sc) = getKey(st,sc) The Equations of getInfKey : { The rst equation states that, if the key to b e consulted is the last one stored then we will obtain the last the information stored. h cmp(k 1 ,k 2 ) i ) getInfKey(put(st,k 1 ,i).store,k 2 )= i { If the condition of the rst equation do es not hold then wehave a second equation, and the corresp onding result will b e that of applying getInfKey on the previous store . h : cmp(k 1 ,k 2 ) i ) getInfKey(put(st,k 1 ,i).store,k 2 )=getInfKey(st,k 2 ) { Since the op eration in question is a partial one (b ecause it is not dened when the key is not in the store )wemust also add a last equation which indicates that consulting the information asso ciated to a key in an empty store will b e an error. getInfKey(create,k) = error Equations of isIn? : { The rst equation is intuitively clear. If we apply isIn? to a key and to an empty store , then the result will b e false. isIn?(create,k) = false { In the same way, the second equation comes naturally. If the key to whichwe apply the op eration isIn? is the last one added to the store , then the result will b e true if the key is not the last one added, then the result will b e that of applying isIn? to the previous store . 9
Using this representation of the typ e store we still have an op eration of high cost, namely the put op eration. When we store the data by means of a key which is already in the store ,wehave only to obtain the shortcut asso ciated to the key and then using it to access to the array, assigning the value of the new data. In this case, the cost is that of consulting the table. However, when the key is not in the store ,wehave to search for free p osition in the array, and this, in the worst case, has linear cost. Toavoid this cost we add another structure to nd quickly a free p osition. This structure is a queue where the free p ositions of the array are stored (see Fig. 3). With this mo dication, the cost of nding a free p osition is constant (provided that the implementation of the queue is go o d enough, it corresp onds just to obtaining the rst element of the queue). The cost of putting a p osition as a free one, while removing, could b e made also constant if it just corresp onds to the cost of putting an element to the queue. k 1 k 6 k 5 k 3 k 2 k 4 1 2 3 4 5 6 7 8 9 10 11 12 13 k 5 k 1 k 3 k 6 k 4 k 2 inf 5 inf 1 inf 3 inf 6 inf 4 inf 2 j q q) - - 666I 66 Figure 3: array, table and queue 16
The representation of the new sorts of data is: store is implemented by a record consisting of three elds: 1. a : arrayof n comp onents, where the valid indices are the natural numbers between 1 and n , for a certain natural n the comp onents of the array are pairs consisting of two elds: inf (of typ e information )and key (of typ e key ). 2. f : a queue of shortcuts i.e., a queue containing the indices corresp onding to the free p ositions of the array. 3. t : is a table of pairs h k ey shor tcut i . The shortcut is implemented by a natural in the range 0 :::n . The value 0 is used as an undened value. The rest of the values will corresp ond to the indices of the array. Toverify that the implementation of the new ADT is correct with resp ect to its sp ecication we follow the metho d presented in 8]. It consists of dening the abstraction function, which transforms a value of the implementation to a value of its mo del, denoted by a term which b elongs to its asso ciated equivalence class in the quotient-term algebra 4]. Since this function is partially dened, wemust also dene the invariant of the representation which establishes the condition that the values of the implementation must satisfy so to representvalid values of the ADT. Also, we need to indicate when two dierentvalues of the implementation corresp ond to the same value of ADT under implementation, in other words, wehave to sp ecify the redenition of the equality. Here is a short description of the array, queue and table op erations, resp ectively, that we are going to use. cons ( a p ) returns the value in the p osition p of the array a ass ( a p v ) assigns the value v in the p osition p of the array a putF ir st ( q v ) puts the value v in the front of the queue q assig n ( t k v ) asso ciates the value v to the key k in the table t deassig n ( t k ) asso ciates an undened value to the key k in the table t and l ook up ( t k ) returns the value asso ciated to the key k in the table t . The Abstraction Function conv er t ( h a f t i )= 8 > > > > < > > > > : cr eate if t =TABLE.create put ( conv er t ( h a putF ir st ( f sc ) deassig n ( t k ) i ) k cons ( a sc ) :inf ) :stor e if t =assign(t',k,sc) 17
The Representation Invariant The representation invariantmust assure that every p osition of the array is free or o ccupied but not b oth of them at the same time. Therefore, it indicates that any p osition of the array, i.e., any natural between 1 and n must b e either in the queue of free p ositions (only once) or as a value asso ciated to a key in the table. In this last case, the key cannot b e whatever: it must coincide with the value of the eld of the array in this p osition. Since a shortcut cannot b e asso ciated to more than a key ,at a certain moment, wemust assure also that, given a p osition there is only one key in the table whichit is asso ciated to. But the shortcut dep ends on the store , therefore the representation invariantmust indicate which is the shortcut that will assign our representation when we store an information by means of a key that is not found in the store . Since the only condition that must satisfy the shortcut , is not to b e asso ciated to another key ,any of the queue p ositions can b e used, for instance its head. We can now write down the invariant. First we will dene a predicate that indicates whether a shortcut b elongs only once to the queue. 8 f 2 q ueue 8 sc sc 1 sc 2 2 shor tcut uniq ue ( cr eate sc )= false sc 2 cr eate = false uniq ue ( enq ueue ( f sc ) sc )= : ( sc 2 f ) sc 2 enq ueue ( f sc )= tr ue : ig ( sc 1 sc 2 )] ) : ig ( sc 1 sc 2 )] ) uniq ue ( enq ueue ( f sc 1 ) sc 2 )= uniq ue ( f sc 2 ) sc 2 2 enq ueue ( f sc 1 )= sc 2 2 f Inv Rep( h a f t i ) 8 j :1 j n : uniq ue ( f j ) ^:9 k : l ook up ( t k )= j _ : ( j 2 f ) ^9 ! k : lookup ( t k )= j ^ 8 k : l ook up ( t k ) 6 = undef ined : cons ( a l ook up ( t k )) :key = k ^ 8 k : : isI n ?( conv er t ( h a f t i ) k ): put ( conv er t ( h a f t i ) ki ) :shor tcut = head ( f ) The Equality Redenition The equality redenition expresses that the values of the array in its free p ositions (those found in the queue) are not relevant to the abstract value. This means that the same store is obtained if any free p osition of the arraywere mo died. Also, it should express that two stores are equal when two tables, constructed in dierentways, contain the same set of pairs. But this has b een contemplated in the equations of the typ e table, and therefore there is no need to include it in the equality redenition. 18
8 j :1 j n ^ ( j 2 f ): conv er t ( h a f t i )= conv er t ( h ass ( a j v al ) f t i ) 3.2 Deriving co de for the op erations In this subsection, we present the derivation of the implementation a particular op eration, put ,asa case study of the whole derivation pro cess 2 . In order to simplify the demonstrations wework under the hyp othesis that n is big enough to assure that the queue is never empty. Later, at the nal implementation, wehave considered this p ossible case of error. 3.2.1 Derivation of put According to 8] the op eration put must b e implemented by a function satisfying the following pre-p ost sp ecication: function impl put( h a:arrayf:queuet:table i k:keyi:information) return hh a 1 :arrayf 1 :queue t 1 :table i sc:shorcut i f Pre: Inv Rep( h a,f,t i ) g P f Post: Inv Rep( h a 1 ,f 1 ,t 1 i ) ^ convert( h a 1 ,f 1 ,t 1 i )=put(convert( h a,f,t i ),k,i).store ^ sc=put(convert( h a,f,t i ),k,i).shortcut g return hh a 1 ,f 1 ,t 1 i ,sc i The derivation of this function is crucial for the verication pro cess not only b ecause of its diculty but also due to the fact that wehave to prove, previously, a serie of lemmas necessary also for the derivation of the rest of the functions. The Lemmas regarding the tables Lemma 1 lookup(assign(t,k,sc),k 1 )=undened ] ): ig(k,k 1 ) Lemma 2 lookup(t,k)=undened ] ) deassign(t,k)=t Lemma 3 lookup(t,k)=undened ] ) deassign(assign(t,k,sc),k)=t Lemma 4 lookup(t,k) 6 = undened ] ) t 6 = TABLE.create 2 See 11] for the complete derivation. 19
Lemma 5 lookup(t,k) 6 = undened ] ) t=assign(t 1 ,k,lookup(t,k)) Lemma 6 lookup(deassign(t,k),k)=undened Lemma 7 t=assign(t 1 ,k 1 ,sc 1 ) ] ) t=assign(t 2 ,k 1 ,sc 1 ) ^ lookup(t 2 ,k 1 )=undened Lemma 8 isIn?(convert( h a,f,t i ),k)=(lookup(t,k) 6 = undened) The Lemmas regarding the queues Lemma 9 putFirst(dequeue(q),head(q))=q Lemma 10 head(putFirst(q,v))=v Using these lemmas let us see the derivation of the function put . The result of the op eration will dep end on whether the key to b e stored is found in the store or not. Therefore, we consider an alternative to the design of the function. Since, from Lemma 8, the result of isIn?(convert( h a,f,t i ),k) is equivalentto lookup(t,k) 6 = undened we will put this last one as a condition of the alternative. function impl put( h a:arrayf:queuet:table i k:keyi:information) return hh a 1 :arrayf 1 :queuet 1 :table i sc:shortcut i f Pre: Inv Rep( h a,f,t i ) g if lo okup(t,k)=undened then f A 1 :Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened g P 1 else f A 2 :Inv Rep( h a,f,t i ) ^ lo okup(t,k) 6 =undened g P 2 end if f Post: Inv Rep( h a 1 ,f 1 ,t 1 i ) ^ convert( h a 1 ,f 1 ,t 1 i )=put(convert( h a,f,t i ),k,i).store ^ sc=put(convert( h a,f,t i ),k,i).shortcut g return hh a 1 ,f 1 ,t 1 i ,sc i 20
Let's see what assertion we can deduce from A 1 . Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ) ( Lemma 8 ) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^: isIn?(convert( h a,f,t i ),k) ) ( Denition of Inv Rep ) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ) ( Equality Redenition and head(f ) 2 f) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ^ convert( h a,f,t i )= convert( h ass(a,head(f ), h k,i i ),f,t i ) ) ( The intro duction of the op eration put in b oth sides of the equality) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,head(f ), h k,i i ),f,t i ),k,i).store ) ( Lemma 3 ) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,head(f ), h k,i i ),f,deassign(assi gn (t,k,head(f )),k) i ),k,i).store ) ( Lemma 9 ) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,head(f ), h k,i i ),putFirst(d equeu e(f ),head(f )),deassi gn(ass ign (t,k,head(f )),k) i ),k,i).store ) ( Eq. of array cons(ass(A,i,v),i)=v ) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,head(f ), h k,i i ),putFirst(deq ueue(f ),head(f )), deassign(assign (t,k,head(f )),k) i ),k,cons(ass(a,hea d(f ), h k,i i ), head(f )).inf ).store ) ( Abstraction Function ) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ^ put(convert( h a,f,t i ),k,i).store= convert( h ass(a,head(f ), h k,i i ),dequeue(f ), assign(t,k,head(f )) i ) ) ( Inv Rep( h a,f,t i ) ^ lo okup(t,k)=unden ed] ) Inv Rep( h ass(a,head(f ), h k,i i ),dequeue(f ), assign(t,k,head(f )) i )) Inv Rep( h ass(a,head(f ), h k,i i ),dequeue(f ), assign(t,k,head(f )) i ) ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ^ put(convert( h a,f,t i ),k,i).store= convert( h ass(a,head(f ), h k,i i ),dequeue(f ), assign(t,k,head(f )) i ) Therefore, from A 1 we can deduce this last assertion, denoted A 3 . Let's see what assertion we can deduce from A 2 . Inv Rep( h a,f,t i ) ^ lo okup(t,k) 6 =undened ) ( Lemma 5 ) Inv Rep( h a,f,t i ) ^ t=assign(t 1 ,k,lo okup(t,k)) ) 21
) ( Abstraction Function ) Inv Rep( h a,f,t i ) ^ convert( h a,f,t i )= put(convert( h a,putFirst(f,lo oku p(t,k)),deassi gn(t,k) i ),k, cons(a,lo okup(t,k)).inf ).store ) ( Equality Redenition and 8 k:k 2 putFirst(f,k) ) Inv Rep( h a,f,t i ) ^ convert( h a,f,t i )= put(convert( h ass(a,lo okup (t,k), h cons(a,lo o kup (t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassig n(t,k) i ),k,cons(a,lo okup (t,k)).inf ).store ) ( The intro duction of the op eration put in b oth sides of the equality) Inv Rep( h a,f,t i ) ^ put(convert( h a,f,t i ),k,i).store= put(put(convert( h ass(a,lo oku p(t,k), h cons(a, lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn(t,k) i ),k,cons(a,l o oku p(t,k)).inf ).store,k,i).store ^ put(convert( h a,f,t i ),k,i).shortcut= put(put(convert( h ass(a,lo o kup(t,k), h cons (a, lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn(t,k) i ),k,cons(a,lo oku p(t,k)).inf ).store,k,i).shortcu t ) ( Eq. of store put(put(st,k,i 1 ).store,k,i 2 ).store= put(st,k,i 2 ).store, and put(put(st,k,i 1 ).store,k,i 2 ).shortcut=put(st,k,i 1 ).shortcut ) Inv Rep( h a,f,t i ) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,lo okup(t,k), h cons(a , lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn(t,k) i ),k,i).store ^ put(convert( h a,f,t i ),k,i).shortcut= put(convert( h ass(a,lo oku p(t,k), h cons(a, lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn(t,k) i ),k,cons(a,l o ok up(t,k)).in f ).shortcut ) ( Eq. of array cons(ass(A,i,v),i)=v ) Inv Rep( h a,f,t i ) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,lo okup(t,k), h cons(a , lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn (t,k) i ),k,cons(ass(a,lo okup (t,k), h cons(a,lo okup(t,k)).key,i i ),lo ok up(t,k)).in f ).store ^ put(convert( h a,f,t i ),k,i).shortcut= put(convert( h ass(a,lo oku p(t,k), h cons(a, lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn(t,k) i ),k,cons(a,l o oku p(t,k)).inf ).shortcu t ) ( Lemma 6 ) Inv Rep( h a,f,t i ) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,lo okup(t,k), h cons(a , lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn (t,k) i ),k,cons(ass(a,lo okup (t,k), h cons(a,lo okup(t,k)).key,i i ),lo ok up(t,k)).in f ).store ^ put(convert( h a,f,t i ),k,i).shortcut= put(convert( h ass(a,lo oku p(t,k), h cons(a, lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassig n(t,k) i ),k,cons(a,lo okup (t,k)).inf ).shortcut ^ lo okup(deassig n(t,k),k)=unde ned ) ( Lemma 8 ) Inv Rep( h a,f,t i ) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,lo okup(t,k), h cons(a , lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn (t,k) i ),k,cons(ass(a,lo okup (t,k), h cons(a,lo okup(t,k)).key,i i ),lo ok up(t,k)).in f ).store ^ 22
put(convert( h a,f,t i ),k,i).shortcut= put(convert( h ass(a,lo oku p(t,k), h cons(a, lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassig n(t,k) i ),k,cons(a,lo okup (t,k)).inf ).shortcut ^ : isIn?(convert( h ass(a,lo ok up(t,k), h cons(a, lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn(t,k) i ),k) ) (Inv Rep( h a,f,t i ) ^ lo okup(t,k) 6 =undened ] ) Inv Rep( h ass(a,lo okup(t,k), h cons(a,l o oku p(t,k)) .key,i i ), putFirst(f,lo okup(t,k)),deassi gn(t,k) i )) Inv Rep( h a,f,t i ) ^ put(convert( h a,f,t i ),k,i).shortcut=head(putFirst(f, lo okup(t,k)) ^ put(convert( h a,f,t i ),k,i).store= put(convert( h ass(a,lo okup(t,k), h cons(a , lo okup(t,k)).key,i i ), putFirst(f,lo okup(t,k)),deassi gn(t,k) i ),k,cons(as s(a,lo o kup (t,k), h cons(a,lo okup(t,k)).key,i i ),lo okup (t,k)).inf ).store ) ( Abstraction Function and Lemma 10 ) Inv Rep( h a,f,t i ) ^ put(convert( h a,f,t i ),k,i).store= convert( h ass(a,lo okup(t,k), h cons(a,lo okup (t,k)).key,i i ),f,t i ) ^ put(convert( h a,f,t i ),k,i).shortcut=lo okup(t,k) ) ( Inv Rep( h a,f,t i ) ^ lo okup(t,k) 6 =undened ] ) Inv Rep( h ass(a,lo okup(t,k), h cons(a,lo okup(t,k)).key,i i ),f,t i )) Inv Rep( h ass(a,lo okup(t,k), h cons(a,lo okup (t,k)).key,i i ),f,t i ) ^ put(convert( h a,f,t i ),k,i).store= convert( h ass(a,lo okup(t,k), h cons(a,lo okup (t,k)).key,i i ),f,t i ) ^ put(convert( h a,f,t i ),k,i).shortcut=lo okup(t,k) Therefore, from A 2 we can deduce this last assertion, denoted A 4 . By intro ducing these new assertions wehave: function impl put( h a:arrayf:queuet:table i k:keyi:information) return hh a 1 :arrayf 1 :queuet 1 :table i sc:shortcut i f Pre: Inv Rep( h a,f,t i ) g if lo okup(t,k)=undened then f A 1 :Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened g f A 3 g P 1 else f A 2 :Inv Rep( h a,f,t i ) ^ lo okup(t,k) 6 =undened g f A 4 g P 2 end if f Post: Inv Rep( h a 1 ,f 1 ,t 1 i ) ^ convert( h a 1 ,f 1 ,t 1 i )=put(convert( h a,f,t i ),k,i).store ^ sc=put(convert( h a,f,t i ),k,i).shortcut g return hh a 1 ,f 1 ,t 1 i ,sc i 23
Having these two new assertions it is easy to identify,by means of the assignment rule, which expressions should b e assigned to a 1 f 1 t 1 , and sc in each case. By doing these assignments we obtain the following implementation of the put function: function impl put( h a:arrayf:queuet:table i k:keyi:information) return hh a 1 :arrayf 1 :queuet 1 :table i sc:shortcut i f Pre: Inv Rep( h a,f,t i ) g if lo okup(t,k)=undened then f A 1 :Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened g f A 3 g a 1 := ass(a,head(f ), h k,i i ) f 1 := dequeue(f ) t 1 := assign(t,k,head(f )) sc:= head(f ) else f A 2 :Inv Rep( h a,f,t i ) ^ lo okup(t,k) 6 =undened g f A 4 g a 1 := ass(a,lo okup(t,k), h cons(a,lo okup(t,k)).key,i i ) f 1 := f t 1 := t sc:= lo okup(t,k) end if f Post: Inv Rep( h a 1 ,f 1 ,t 1 i ) ^ convert( h a 1 ,f 1 ,t 1 i )=put(convert( h a,f,t i ),k,i).store ^ sc=put(convert( h a,f,t i ),k,i).shortcut g return hh a 1 ,f 1 ,t 1 i ,sc i 24
3.3 Chosing implementations for the comp onents of the representation Once wehave derived the co de of the op erations, we study two particular implementations of the new ADT 3 . In b oth of them we use the dynamic memory zone as an array and the queue of the system as that of the free shortcuts. These two implementations dier in the implementation of the table. In the rst one, wehave used a hashing table with chaining. Using a hashing table requires the parameter KEY to include also a hashing function. In the second implementation wehave implemented the table with an AVL 4 1]. We give next the cost of the op erations of the ADT dep ending on the implementation used for table (see Table 1). Table 1: The cost of the functions COST FUNTIONS AVL HASHING TABLE create O (1) O ( r ) put O (log n ) O (1) getInfKey O (log n ) O (1) getInfSho O (1) O (1) getKey O (1) O (1) isIn? O (log n ) O (1) getShortcut O (log n ) O (1) isEmpty? O (1) O (1) remove O (log n ) O (1) mo dify O (1) O (1) As it can b e seen, the cost of the op erations getKey , getInfSho and modify is constant in b oth implementations b ecause the table is not accessed, in this case. The cost of the remaining op erations 3 See 11] for more details. 4 An AVL is a binary search tree where the diference b etween the height of its subtrees is less or equal than 1 and the subtrees are AVL in turn. 25
14] Wirth, N. ProgramminginModula-2. Springer-Verlag, 3rd. edition, 1988. 32