Ape: An Expert System for Automatic Programming from Abstract Specifications of Data Types and Algorithms

Abstract

The APE (Automatic Programming Expert) system constructs executable and efficient programs from algebraic specifications of abstract data types, and abstract algorithms given as conditional term-rewrite-rule-systems with terms built up from operation symbols of the abstract data types involved. The APE is an experimental system devised to develop methods for codifying a rather Broad extent of programming knowledge required to construct implementations of data types and algorithms. For data type specifications, the APE admits hidden operations, conditional axioms, and parameterized data types. The APE automatically implements algebraic specifications of all commonly known data types in terms of clusters of INTERLISP-functions. The APE constructs executable implementations of a variety of sorting and searching algorithms. As an experimental prototype, the APE demonstrates that a knowledge-based programming paradigm provides a useful tool for partially automating an important phase of software development.