From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE, MSGID_SHORT autolearn=no autolearn_force=no version=3.4.4 Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!amdcad!ames!mailrus!purdue!rjh From: rjh@cs.purdue.EDU (Bob Hathaway) Newsgroups: comp.lang.ada Subject: Self-Modifying Abstract Data Types Message-ID: <6224@medusa.cs.purdue.edu> Date: 12 Mar 89 00:57:45 GMT Sender: news@cs.purdue.EDU Organization: Department of Computer Science, Purdue University List-Id: This is a copy of a long paper on self-modifying abstract data types which is being mailed to comp.sw.components since a method being proposed could apply to an implementation technique which was used here. My apologies for anyone getting this twice, I posted to comp.lang.sigplan first and apparently because that newsgroup is moderated, the message wasn't sent to comp.lang.ada. (Readers uninterested in abstract data types can skip this article) ABSTRACT Last September I developed a program for an Icon subset which implemented a self-modifying abstract data type using a transparent multi-level design to allow simultaneous, multiple implementations. I considered writing a journal article on the technique at the time and will eventually get around to it, but for now I'll give a quick description. Part of the technique presented could roughly correspond to a "synthesis" approach and should be appropriate to the current discussion. Since this is essentially a rough draft, comments and criticisms are welcome. TOP LEVEL SPECIFICATION OF TABLES Icon subset tables are arrays indexed by strings and have a polymorphic basetype, i.e. the elements are heterogeneous. In the subset, table elements contained objects (1. objects could also be tables, resulting in a recursive definition). It was simple to devise a top level design specification for tables as an abstract data type, which is repeated below without documentation (2. the description and operation semantics aren't relevant to the example). TOP LEVEL SPECIFICATION Icon Table Operations (interface) CreateIconTable Initialize Lookup Insert Print GetDefaultValue LOWER LAYER DESIGN OF TABLES There were several alternatives for the design and representation of the table's lower layer. It was desirable and sufficient to meet the above interface in a general way. A linked list would provide a simple but inefficient implementation, a tree implementation would allow future slicing extensions, and a hash table implementation would be more complex but allow constant time lookup. To provide the necessary generality to allow any representation, the lower level design of the Adt was based on a generic dictionary. This dictionary provided the usual lookup and insert operations and a print routine was later added to simplify debugging. All operations in the top level design were implemented in terms of dictionary operations with the exception of GetDefaultValue, which is specific to tables. Dictionaries An Adt had to provide the following (necessary and sufficient) operations to satisfy the dictionary operations required to implement tables: Initialize Insert Lookup Print Any Adt providing these operations could be used as the dictionary. This implementation of the table's lower layer resulted in: TABLE SPECIFICATION GRAPH 1. >-------> table: Create Initialize Lookup Insert Print | /|\ GetDefaultValue | / | \ | / | \ | / | \ 2. | list tree hash table ...: Initialize Insert Lookup Print | / | \ 3. ^__ ... ... ... : objects Here, layer 2 corresponds to both the implementation of tables and the specification of dictionaries because the table implementation is an application of the dictionary specification (there are actually four layers). Since layer 2 is hidden in the lower layer of the table Adt, it should be transparent, i.e. completely hidden from applications using tables. This scheme views tables as indexed containers of objects. Layer 1 table operations and layer 2 dictionary operations should then return objects and not the internal elements used to store objects. Since the implemented Icon subset allows tables to change dictionary (layer 2) representations dynamically, an insecurity would result if the table returned an internal element type and then changed representation. By returning objects, tables are free to undergo changes in representation without concern for the context of operations, i.e. self-modifying tables should be stateless. Since objects are implemented by reference, the semantics of table entries and returned objects are preserved. For example, if a lookup operation returned an internal element type and the table subsequently changed representation, the returned element would be undefined because the table entry corresponding to that element had changed. Change of representation (self-modification) occurs in layer 2 when a table operation detects a specific condition such as a dramatic size change. The table then extracts all elements from the current dictionary and inserts them into a new dictionary which then composes the table representation. If the Adt is implemented as a lightweight process (task or thread), any condition or event could trigger self-modification. The same applies to abstract data objects. LOWER LAYER IMPLEMENTATION The table implementation used a record consisting of a pointer and a set of operations implemented as procedural variables. In Ada the operations correspond to generic subprogram parameters. Any Adt which provided the dictionary operations described above was suitable to implement the lower layer. In Modula, initializing the table involved assigning the operations provided by the dictionary Adts to the procedural variables and setting the pointer variant to the dictionary Adt variable. In Ada, generic subprogram and type parameters are sufficient for the simplist case. For example, the hash table Adt provided lookup, insert, print, and initialize operations which were assigned to the procedural variables. The pointer (3. actually a variant record with the dictionary and ADDRESS types as alternatives) was then interpreted as an instance of a hash table Adt. The lower layer of the hash table was implemented as a pointer to an array but this was only consequential to the initialize routine. TABLE IMPLEMENTATION Layer 1 Layer II Layer III Create >------>|-----------| Initialize | |Initialize | (Dictionary Operations) Lookup | |Insert | Insert | |Lookup | Print | |Print | (Dictionary Representations) GetDefaultValue | |table |--->|--->linked list value ------------^ |-----------| | |--->tree | |--->hashtable | |--->other In Ada, layer 2 instantiates the dictionary with the object type (4. implemented as an Adt encapsulating a pointer to a variant record containing all Adts representing the object). Polymorphic variables would have provided better table elements, and in fact, the above scheme uses non-polymorphic Adts to implement polymorphic table variables. A Next operation was also used to implement self-modifying tables. SUMMARY A technique to allow simultaneous, multiple implementations of self-modifying abstract data types was presented. Two distinct advantages of the technique are ease of modification and efficient representation. Since no single representation is "hard-wired" into the lower layer of an Adt, they are easy to change. Experiments with alternate representations can discover optimal lower layers for particular applications. New representations can also be added easily. Self-modification allows efficient representations for each Adt variable or object. In the presented example, small tables could use a list dictionary representation and convert themselves into trees or hash tables as necessary, e.g. during dramatic size changes. EARLIER DISCUSSIONS In the "synthesis" terminology, if I follow it correctly, the dictionary corresponds to a class structure and the list, tree, and hash tables correspond to types satisfying the dictionary class. The table operations would then invoke dictionary class operations to invoke the appropriate type operation for any dictionary representation; a high level view of the above implementation technique. For discussion, is this view of synthesis correct? What solutions would inheritance provide? In regard to the earlier discussion in which I proposed dynamically parameterized Adt operations, Ada generic subprogram parameters could allow an instance to be programmed in the context of an instantiation but the operation would not be defined outside that scope except by default. For this case procedural variables are necessary as memory to store a new operation. I don't know if the "synthesis" class can provide change of operations, it appears classes could allow complete change of representation (type) as described above but not of selected operations. Bob Hathaway rjh@purdue.edu