Taliere: An interactive system for data structuring SETL programs

Candidate: Straub,Robert Michael

Abstract

This thesis describes a system designed to aid SETL programmers in the selection of data structures for the representation of program variables. The system uses information from the SETL optimizer, and provided interactively by the programmer, to select from the set and map representations which are available to implement SETL objects. We begin by describing previous work on data structure selection for very high level languages, including the data structure selection performed by the SETL optimizer. We then present a general description of a system for data structure selection for SETL programs. We describe techniques used to obtain useful information from a source program. This includes obtaining symbolic estimates of the execution frequencies of individual program operation, and estimates of the sizes of program objects. The data structures considered by the system are then described. We present a detailed description of the data structure selection algorithm, along with optimizations and heuristics used to improve the execution efficiency of the data structuring system. We conclude with examples comparing choices made by the system with choices made by a competent programmer and speculate on the eventual success of semi-automatic structuring systems.