Programming by Refinement, as Exemplified by the SETL Representation Sublanguage

“Pure” SETL is a language of very high level allowing algorithms to be programmed rapidly and succintly. SETL's representation sublanguage adds a system of declarations which allow the user of the language to control the data structures that will be used to implement an algorithm which has already been written in pure SETL, so as to improve its efficiency. Ideally no rewriting of the algorithm should be necessary. The facilities provided by the representation sublanguage and the run-time data structures that it can generate are described; based on this a heuristic which uses some of the methods of global program analysis and which should be capable of selecting an acceptably efficient representation automatically is given.