Inductive inference algorithm to synthesize prolog programs from specification by example

By utilizing an inductive inference method, we developed an automatic programming system LIPS (LIst-processing Program Synthesizer). This system synthesizes Prolog programs from its specification by example. LIPS employs three unique data structures in the program synthesis process. They are Data Metamorphosis History (DMH), Constant Argument Clause Set (CACS), and Variable Argument Clause Set (VACS). DMH shows the runtime behavior of arguments of the specification by example, when it was evaluated by a target program. CACS is generated from DMH and shows the runtime behavior of the target program when the data of the specification by example is entered. VACS, which shows the general runtime behavior of the target program, is a general form of CACS. In this paper, we show the details of these three data structures and some algorithms in order to generate them from the specification by example. The comparison of LIPS with other systems and future prospects of LIPS are also described.