Automatic data structure selection: an example and overview <s> Prototype System <s> A high level programming language for large, complex associative structures has been designed and implemented. The underlying data structure has been implemented using a hash-coding technique. The discussion includes a comparison with other work and examples of applications of the language. <s> BIB001 </s> Automatic data structure selection: an example and overview <s> Prototype System <s> One of the persistent hopes for rapid progress in Computer Science is that standard solutions to software design problems will be developed, analyzed, and used. In particular, the hope for high-level languages has always been that enough low-level detail could be left to "the system" to allow a mere human to develop solutions for enormously complex problems. An ideal high-level language would allow a programmer to concentrate on the conceptual development of a solution for his problem, rather than on the design of a representation for his solution once he can express it. Although existing high-level languages insulate a user from many details, they still require him to do low-level design for many problems, especially for complex ones. Such cases arise either because the language provides only low-level storage structures (records, arrays, pointers, lists) with which the programmer must encode his algorithm, or because it provides a general-purpose data structure for which an arbitrary (and usually sub-optimal) representation design choice has been made a priori (LISP,! SAIL2). Any single representation choice for a general data structure is very badly matched to some problems; the user of a general data structure must often spend much time designing a way to avoid unacceptable inefficiencies. Furthermore, good storage structure design requires much clerical work, for which a person whose goal is to solve a problem will usually have little time or enthusiasm. An automatic system, on the· other hand, is well suited to the job of systematically comparing the cost and applicability of the many representations that are available for program data. In addition, an automatic system is less likely than a person to overlook possible representation candidates. <s> BIB002
A prototype system for semiautomatic selection of representations was constructed for a subset of the SAIL programming language  16] . SAIL is an Algol-60 based language with extensions including varying length strings, processes, event mechanisms, and an associative data language called LEAP BIB001 . We were interested in choosing representations for the abstract data structures of LEAP. The basic entities manipulated by LEAP are called "items." An item is a symbolic object much like a LISP atom. A variable, called a datum, may optionally be attached to the item. Datums can be either simple variables or arrays. Items are often categorized by the data type of the attached datum. Thus we have integer items (items with an integer variable as datum), set items (items with a set variable as datum), untyped items (items with no datum), and so forth. Items are allocated either at compile time via declarations or dynamically from a heap at execution time (via the built-in function called NEW). The lifetime of items and their datums does not follow Algol block structure. An item and its datum exist until explicitly deleted by the use of the D E L E T E procedure. LEAP also contains "sets" of items, "lists" of items, and a ternary relation among items. Set and list values 377 have the same lifetime as arithmetic quantities. There are set expressions, set variables local to a block, and set datums. The ternary relation is global to the entire program. The subset of SAIL which was used in the prototype system included integers, reals, strings, procedures, items, sets, and lists. Explicitly excluded from the subset were arrays, recursive procedures, go-to statements, multiprocessing, events, and the ternary relation of LEAP. A recent extension to the system BIB002 now performs selection of representations for the ternary relation. In the prototype system we chose representations only for sets of items and lists of items. A set is a conceptually unordered collection of items in which any given item appears at most once. Operations built into SAIL to manipulate sets include: union, intersection, difference, element insertion, element deletion, test for membership, and iterating through the members of a set expression. A list is a linear sequence of items. It behaves much as a flexible length array or string of items except that there are primitives for inserting or deleting items at arbitrary positions within the list. Operations on lists include: fetching or storing an item by ordinal position within the list; concatenating two lists; removing items from a list (either by ordinal number within the list or by giving the name of the item to be removed); inserting items into the LIST (before or after an ordinal position or a particular item); and iterating through the elements of a list. Let us now look at an example of a program written with sets and lists and see how the prototype system chose representations for it.