Program Inference from Traces using Multiple Knowledge Sources

Program Inference from Traces using Multiple Knowledge Sources

Jorge V. Phillips

Artificial Intelligence Laboratory Stanford University Stanford, California 94305

ABSTRACT: This paper presents an overview of a framework for the synthesis of high-level program descriptions from traces and example pairs in an automatic programming system. The framework is described in terms of a methodology and a rule base for generating control and data structure specifications for the program to be synthesized, in a format suitable for transformation into program code in a given target language.

KEYWORDS: Automatic Programming, Program Inference, Informal Program S peciftcations

One of the ways to specify a program is by the use of traces and example pairs of the program's behavior. A trace is basically a mixed sequence of operator applications, information structure states, and holdings of relations between these. Example pairs are a particular instance of traces, in which the only information present Is states of program data structures. A methodology for the synthesis of programs from such descriptions must provide a means for the transformation of such descriptions into actual program code. In the past proposed methodologies have been closely tied to the coding process and have had no programming domain support [Bauer-75, Shaw-75). In an automatic programming system, such as the PSI system being developed at Stanford [Green-761 It is highly undesirable to transform directly a program specification Into code for several reasons: it is hard for the system to explain the reasoning that leads to the target program and hard for the user to verify that the system really understood the program description. It is also imperative to use some domain support to disambiguate the user's intentions. A framework has been devised for the synthesis of programs from traces and examples that copes with these constraints by using information about the target program's domain and by being totally decoupled from the coding process. TX, a program embodying this framework, has been Implemented in INTERLISP, and Is currently one of the constituent modules of the PSI system.

TX transforms input traces into partial loose descriptions (called fragments} which in turn are transformed by PSI's Model Builder [McCune-77) into a consistent and complete high-level program description. This description is suitable for use by PSI's Coder [Barstow-77) to produce LISP or SAIL code. The process of transformation of input traces Into fragments is accomplished in several stages. The input trace components are classified and mapped into an internal trace representation using domain knowledge. This representation is a linear sequence of instantiated templates that describe interactions between the target program and its environment, transformation of data objects by the program and conditions arising in the . interaction of program components. Control structure loops and tests are formed by a set of rules that detect possible iterations and associate holdings of conditions with activation of operators, using a combination of matching, unification and other inductive inference tecl:miques. Data structures are obtained from example Instances based on the syntax of the example itself and domain information, by a process of description, unification and generalization, that goes from the primitive components of the data structure to Its top level description. Rules are currently available for the inference of arbitrarily complex compositions of sets, tuples, multisets correspondences and plexes, and primitive objects (strings, atoms, numbers}. These partial control and data descriptions are the input to the synthesis phase of the PSI system.

Currently TX has synthesized several different classes of simple learning programs and set manipulation programs. A facility is being added to use PSI's natural language parser [Ginsparg-77) .as the front end of TX to enable the user to mix freely natural language dialogues and traces. Research Is being directed towards isolating a base of programming knowledge about traces and examples and attempting the synthesis of more complex and sophisticated programs. The possibility of using the structure of such a system for the acquisition of domain knowledge is under study. For further details the reader is referred to [Phillips-77)