Optimization of User-Defined Abstract Data Types: A Program Transformation Approach

CMU-CS-85-166

Andy Hisgen

September 1985 - Thesis

This dissertation introduces a programming language facility for optimizing user-defined abstract data types. Current optimizing compilers have concentrated on the optimization of built-in, predefined types, for example, the integers. This work investigates the possibility of extending the benefits of program optimization to user-defined abstract data types. The programmer of an abstract data type writes transformations that state when one operation of the type or sequence of operations may be replaced by another operation or sequence of operations . A transformation may have an enabling precondition, which says that it is legitimate only in contexts in which the enabling precondition can be shown to be true. When compiling a program that is a client of the type, the compiler analyzes the client's calls on the operations of the type and attempts to apply the transformations to particular calls or sequence of calls .

This dissertation presents a language for writing transformations between the operations of an abstract data type. The transformation language also includes facilities for writing specifications for the type in a manner that caters to the task of optimization. Examples of data types that can exploit the transformation language are given. Techniques for compiling client programs are described.

237 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu