Logic Program Synthesis via Proof Planning

Abstract We propose a novel approach to automating the synthesis of logic programs: Logic programs are synthesized as a by-product of the planning of a verification proof. The approach is a two-level one: At the object level, we prove program verification conjectures in a sorted, first-order theory. The conjectures are of the form \( \forall \xrightarrow[{\arg s. }]{}prog(\xrightarrow[{\arg s}]{}) \leftrightarrow spec(\xrightarrow[{\arg s}]{}). \). At the meta-level, we plan the object-level verification with an unspecified program definition. The definition is represented with a (second-order) meta-level variable, which becomes instantiated in the course of the planning. This technique is an application of the Clam proof planning system [Bundy et al 90c]. Clam is currently powerful enough to plan verification proofs for given programs. We show that, if Clam’s use of middle-out reasoning is extended, it will also be able to synthesize programs.

Authors

• Ina Kraan
• David A. Basin
• Alan Bundy

Keywords

No keywords are indexed for this paper.