C. BECKSTEIN, U. GESKE (EDS.), WORKSHOP ON DEVELOPMENT, TEST AND MAINTENANCE OF DECLARATIVE AI PROGRAMS, GMD STUDIEN NR. 238, GESELLSCHAFT F?R MATHEMATIK UND DATENVERARBEITUNG, 1994

Transformational Development of Logic Programs

from Executable Specifications

Schema-Based Visual and Textual Composition of Logic Programs

Norbert E. Fuchs, Department of Computer Science, University of Zurich
Markus P. J. Fromherz, Xerox PARC, Palo Alto

Abstract
In our method ? that we call Visual and Textual Composition of Logic Programs ? we have enhanced the schema-based construction of logic programs in two ways intended to bridge the conceptual gap between application domains and the programming domain. First, we define visual and textual views of programs that can be used to construct programs in application-specific concepts, and which can be understood as executable specifications of the programs being constructed. Second, in addition to schemata for Prolog programming constructs and techniques we introduce a repository of application-specific components. As a further enhancement of the method we have added schema-based transformations to increase the efficiency of the constructed programs. We have implemented both a program development system and a transformation system, and used these systems to develop programs for non-trivial applications like the well-known library data base problem and an automated teller machine.

1 Schema-Based Construction of Logic Programs

Since the beginning of logic programming it has been recognised that many logic programs have standard patterns of structure and employ standard patterns of control and data flow. These patterns are highly attractive for the logic programmer since they can be used for the construction of logic programs, for their transformation, and for various other purposes, e.g. tutoring or tracing.

Different sets of patterns ? called schemata, skeletons, techniques, or clich?s ? have been proposed. O'Keefe defined a set of schemata for recursive programs [O'Keefe 90], while Deville and Burnay suggested schemata as a basis for program construction derived from structural induction and generalisation [Deville & Burnay 90]. By far the most comprehensive set of schemata for list-processing programs was introduced by Gegg-Harrison in the context of a tutoring system [Gegg-Harrison 89]. Patterns can also be used to abstractly represent programs that use the same programming technique, e.g. accumulators or difference lists [Brna et al. 88].

Sterling and collaborators [Kirschenbaum et al. 94], and Robertson and his group [Bowles et al. 93] have developed systematic methods to construct logic programs, specifically Prolog programs, with the help of patterns.

Sterling and his collaborators [Kirschenbaum et al. 94] define skeletons as basic Prolog programs with well-understood control flow, e.g. the in-order traversal of a binary tree. Skeletons describe how structured terms are to be traversed. Techniques, however, are basic programming practices that extend skeletons by adding threads of computation, e.g. term construction, or an accumulator argument. A skeleton can be extended by several techniques that can be compounded into a single program. This leads to a systematic method for the construction of logic programs by step-wise enhancement. Two tools have been built for this purpose: an environment using skeletons, techniques and composition to develop recursive Prolog programs, and a tool that incorporates techniques into Prolog programs by partial evaluation.

Robertson and collaborators [Bowles et al. 93] define a programming technique as a standard code pattern used by logic programmers in a systematic way, and which is independent of any particular algorithm or application domain. Thus their notion technique overlaps with Sterling's notions skeleton and technique. Robertson and his group have isolated a number of standard techniques, e.g. the exhaustive traversal of a list, accumulator pairs, difference lists, that can be combined to systematically construct a logic program. Furthermore, they have shown that techniques can be used in various programming applications: editing, analysis, tracing, transformation, and tutoring. Several tools have been developed including the techniques editor TED.