scieee AI-readable full text Open interactive document viewer

Shortcuts: abstract "pointers''

Marco Gómez, Jordi,Franch Gutiérrez, Javier

Abstract

In this work we present the specification and the implementation of a new abstract data type (ADT) called STORE. This new ADT allows the storage of a given collection of elements offering an abstract mechanism that supplies a direct access to them, alternative to the method defined by the standard operations of usual ADTs. The interest of the new mechanism stems from the efficiency of pointers, while avoiding the loss of modularity that usually occurs when pointers are used. The implementation of the operations offered by the new ADT is done by derivation from the equational specification. The representation chosen for the implementation of the new ADT makes the efficiency previously mentioned possible, even when the representation strategy requires the movement of the elements.

Full text

Shortcuts: Abstract \Pointers" J. Marco [email protected] c.es X. Franch franc[email protected] c.es Dept. Llenguatges i Sistemes Informatics (LSI) Universitat Politecnica de Catalunya (UPC) Campus Nord Jordi Girona Salgado, 1-3 08034 BARCELONA Abstract In this work we present the sp ecication 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 oering an abstract mechanism that supplies a direct access to them, alternative to the metho d dened by the standard op erations of usual ADTs. The interest of the new mechanism stems from the eciency 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 oered by the new ADT is done by derivation from the equational sp ecication. The representation chosen for the implementation of the new ADT makes the eciency 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 dier Op erations ... ... ... ... ... .. ... ... ... ... ... . 6 2.2 Equational sp ecication .. ... ... ... ... ... .. ... ... ... ... ... . 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 dier 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 dications 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 oers many imp ortant prop erties such as understanding, abstraction, reusability, etc., but, often, it implies a loss of eciency 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 dierent 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 dicult 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 dened 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 dening its formal semantics. Certainly, the idea to study this new ADT comes from the necessity of a compromise b etween mo dularity and eciency. The goal of the presentwork is to present the design of this new ADT which oers, 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 eciency. The rest of the pap er is organized as follows. In section 2, we present the algebraic sp ecication of the new ADT showing the sorts and the op erations oered as well as the equations that dene 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 eciency reasons, and where we can see that the use of the new ADT assures the same eciency without losing mo dularity at all. In section 5, we include several conclusions regarding the co dication 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 oers 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 ecication 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 dier 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 ecication Following the general metho d of algebraic sp ecication 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 dierentkeys 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 dierentkeys can have the same shortcut , if they are stored in dierent 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 dened 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 dened 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 dication, 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 undened 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 ecication we follow the metho d presented in 8]. It consists of dening 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 dened, wemust also dene 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 dierentvalues of the implementation corresp ond to the same value of ADT under implementation, in other words, wehave to sp ecify the redenition 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 undened 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 dene 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 ) ki ) :shor tcut = head ( f ) The Equality Redenition The equality redenition 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 died. Also, it should express that two stores are equal when two tables, constructed in dierentways, 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 redenition. 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 ecication: function impl put( h a:arrayf:queuet:table i  k:keyi:information) return hh a 1 :arrayf 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 verication pro cess not only b ecause of its diculty 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 )=undened ] ): ig(k,k 1 ) Lemma 2  lookup(t,k)=undened ] ) deassign(t,k)=t Lemma 3  lookup(t,k)=undened ] ) deassign(assign(t,k,sc),k)=t Lemma 4  lookup(t,k) 6 = undened ] ) t 6 = TABLE.create 2 See 11] for the complete derivation. 19 Lemma 5  lookup(t,k) 6 = undened ] ) t=assign(t 1 ,k,lookup(t,k)) Lemma 6 lookup(deassign(t,k),k)=undened Lemma 7  t=assign(t 1 ,k 1 ,sc 1 ) ] ) t=assign(t 2 ,k 1 ,sc 1 ) ^ lookup(t 2 ,k 1 )=undened Lemma 8 isIn?(convert( h a,f,t i ),k)=(lookup(t,k) 6 = undened) 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 = undened we will put this last one as a condition of the alternative. function impl put( h a:arrayf:queuet:table i  k:keyi:information) return hh a 1 :arrayf 1 :queuet 1 :table i  sc:shortcut i f Pre: Inv Rep( h a,f,t i ) g if lo okup(t,k)=undened then f A 1 :Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened g P 1 else f A 2 :Inv Rep( h a,f,t i ) ^ lo okup(t,k) 6 =undened 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)=undened ) ( Lemma 8 ) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^: isIn?(convert( h a,f,t i ),k) ) ( Denition of Inv Rep ) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ put(convert( h a,f,t i ),k,i).shortcut=head(f ) ) ( Equality Redenition and head(f ) 2 f) Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened ^ 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)=undened ^ 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)=undened ^ 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)=undened ^ 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)=undened ^ 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)=undened ^ 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)=unden 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 =undened ) ( 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 Redenition 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 =undened ] ) 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 =undened ] ) 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:arrayf:queuet:table i  k:keyi:information) return hh a 1 :arrayf 1 :queuet 1 :table i  sc:shortcut i f Pre: Inv Rep( h a,f,t i ) g if lo okup(t,k)=undened then f A 1 :Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened g f A 3 g P 1 else f A 2 :Inv Rep( h a,f,t i ) ^ lo okup(t,k) 6 =undened 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:arrayf:queuet:table i  k:keyi:information) return hh a 1 :arrayf 1 :queuet 1 :table i  sc:shortcut i f Pre: Inv Rep( h a,f,t i ) g if lo okup(t,k)=undened then f A 1 :Inv Rep( h a,f,t i ) ^ lo okup(t,k)=undened 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 =undened 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 dier 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