Abstract
Automated program synthesis remains a significant challenge in formal methods, particularly when dealing with complex data structures and existential quantifiers. This paper presents Constructive Matching (CM), a novel methodology for inductive theorem proving designed specifically for program synthesis. Unlike traditional "simplification" methods that strip formulas down to find a proof, CM uses a "complication" approach to progressively build up constraints, successfully synthesizing a recursive solution for the classic AI planning problem: "How to Clear a Block."
Introduction
The challenge of automated program synthesis—the process of automatically generating a computer program from a formal specification—is central to AI. Most existing inductive theorem provers, such as the Boyer-Moore prover, rely on "simplification" or rewriting techniques. While effective for verifying existing programs, these methods often struggle to construct new programs, especially when specifications involve existential quantifiers (e.g., "find an output $z$ such that condition $Q(x, z)$ holds").
Franova and Kodratoff identify a gap in handling Well-Founded Domains (WFD)—complex data structures that aren't just simple recursive types. They aim to provide a strategy that can handle "unspecified variables" and existentially quantified lemmas, which are often necessary to solve real-world planning and manipulation tasks.
The Constructive Matching Methodology
The core of the CM-methodology is the contrast between classical "simplification" and the proposed "complication" approach. While classical methods try to transform a formula into TRUE through reduction, CM starts with an abstract version of the goal and progressively builds a set of constraints that describe the conditions under which the formula is valid.
Instead of treating the filling of predicate arguments as a single step, CM performs a piece-wise construction. It introduces an "abstract argument" ($\xi$) and then works to "concretize" it using axioms and induction hypotheses.
The CM algorithm follows five key steps:
- Evaluate: Apply axioms to the terms in the goal.
- Define Validity: Determine the conditions (the set $C$) under which the formula would be true.
- Concretize: Use induction hypotheses to replace the abstract $\xi$ with a concrete term.
- Verify: Ensure the concrete term actually belongs to the valid set $C$.
- Simplify: Perform final clean-up of the resulting program.
Case Study: "How to Clear a Block"
The authors apply this methodology to the "How to Clear a Block" (HCB) problem using situational logic (the "row-plan theory"), where states are transformed by actions like put(u, v). Originally proposed by Manna and Waldinger (1987), this serves as the primary test case for synthesizing a recursive plan in a "blocks world" environment.
The paper successfully demonstrates the synthesis of a recursive program for makeclear(s, b) (clearing block $b$ in state $s$):
- Base Case: If the block is already clear, the plan is the "empty plan" ($\Lambda$).
- Recursive Step: If the block is not clear, find the block $hat(s, b)$ that is currently on top of $b$, recursively clear that block, and then move it to the table.
Key Insights
- Existential Quantifiers are Key: Program synthesis is fundamentally an inductive theorem-proving problem involving existential quantifiers. By allowing these "unspecified variables" to exist during the proof process, CM can solve problems that more restrictive systems cannot.
- Top-Down vs. Bottom-Up: Simplification is a top-down approach where the final leaf is
TRUE. CM is more bottom-up; it constructs the solution through the proof itself. - Strategic Search Reduction: By providing a "couple" (what has to be achieved vs. what it is achieved from) at each step, CM significantly reduces the search space compared to purely deductive approaches.
- Generalizing "Rippling": CM is a more general version of Alan Bundy’s "rippling-out" tactics, as it can handle theorems containing existential quantifiers, which were a limitation in Bundy's earlier work.
Conclusion and Future Work
While the CM methodology successfully bridges the gap between high-level logic specifications and executable recursive procedures, it currently faces implementation constraints. At the time of writing, full automation only worked for Constructible Domains (CD). While the theory for Well-Founded Domains (WFD) is presented, automating the discovery of well-founded orderings remains a challenge. Future work aims to reduce the dependency on human-provided heuristics and well-foundedness verifications by integrating automated tools like the Boyer-Moore prover.
Summary updated