Automatic Construction of Algorithms and Data Structures Using a Knowledge Base of Programming Rules

Although large amounts of programming knowledge are available to human programmers in the form of books and articles, very little of this knowledge is available in a form suitable for use by a machine in performing programming tasks automatically. The principal goal of the research reported here is the explication of programming knowledge to a sufficient level of detail that it can be used effectively by a machine. The programming task considered in this experiment is that of constructing concrete implementations of abstract algorithms in the domain of symbolic programming. Knowledge about several aspects of symbolic programming has been expressed as a collection of four hundred refinement rules. The rules deal primarily with collections and mappings and ways of manipulating such structures, including several enumeration, sorting and searching techniques. The principal representation techniques covered include the representation of sets as linked lists and arrays (both ordered and unordered), and the representation of mappings as tables, sets of pairs, property list markings, and inverted mappings (indexed by range element). In addition to these general constructs, many low-level programming details are covered (such as the use of variables to store values).