Browse Prior Art Database

Automatic Data Structure Selection An Example and overview Disclosure Number: IPCOM000128607D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 16 page(s) / 53K

Publishing Venue

Software Patent Institute

Related People

James R. Low: AUTHOR [+2]


James R. Low Department of Computer Science The University of Rochester P ,ochester, New York TR,14 September 1976

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 16


Automatic Data Structure Selection An Example and overview

James R. Low Department of Computer Science The University of Rochester P ,ochester, New York

TR,14 September 1976


The use of several levels of abstraction has proved to be very heI-pful in constructing and maintaining programs. Abstract data types such as sets and lists reduce programmer time by relieving him from the petty details of low-level implementations. In the past, programming systems have provided only a single general purpose implementation for an abstract type. Thus the programs produced using abstract types were often inefficient in. space or time. In this paper a system for automatically choosing efficient implementations for abstract types from a library.of implementations is discussed. An example program is processed in detail.

Key Words and Phrases: abstract data types, automatic programming, data structures, optimizing compilers, sets, lists.

CR Categories: 4.12, 4.22, 4.6

The preparation of this paper was supported by the National Science Foundation under grant number MCS76-10825. Automatic Selection of Data Structures


In the past several years computer scientists have realized that the use of several levels of abstraction in programming often gives improved results in terms of clarity, correctness, and ease of maintenance of the resulting programs. one important aspect of abstraction is the use of types such as stacks, queues, sets and so forth. The properties of abstract types can often be described axiomatically (13). This aids in constructing formal or informal proofs of program correctness. Several systems have gone further and shown the benefits of "hiding" the low level implementations of the abstract types. Thus a programmer might deal with a stack only in terms of a small number of primitives upon it such as PUSHing an element, POPing an element off the stack, testing if the stack were EMPTY and so forth. The programmer would not have to concern himself with whether the underlying representation were a linked list, an array, or some hybrid.

When a program is written using only primitives on an abstract type without using any knowledge of the underlying representation, the underlying representation may be changed without affecting the operation of the program except possibly for resource requirements. Given a programming system which provides the abstract type stack, a natural thing to do would be to have a number of alternative implementations of stacks and choose the implementation which is most efficient (by some criteria) for any individual program. An "intelligent" compiler would pick

University of Rochester Page 1 Dec 31, 1976

Page 2 of 16

Automatic Data Structure Selection An Example and overview

the "best" set of implementations for the abstract types of an individual program from a fixed library of implementations for the types.

For the purpose of t...