Automatic Data Structure Selection: An Example and Overview

The use of several levels of abstraction has proved to be very helpful 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.