Program Synthesis by Constructive Proof

135 concepts94 papers3 proposals

When we write software, we typically engage in a cycle of guessing and checking: we write code, run tests, and perhaps try to verify its correctness after the fact. But what if the act of proving a program's correctness and writing the program were the exact same thing?

This is the core insight of deductive program synthesis. Instead of treating code generation and formal verification as separate steps, it frames programming as a theorem-proving task. By proving that a valid output exists for every possible input under a given specification, we can automatically extract an executable, mathematically guaranteed program directly from the structure of the proof itself. This is known as correct-by-construction synthesis.

The Core Intuition: Proofs as Blueprints

Why does a mathematical proof contain a program? The answer lies in the nature of constructive logic. In classical logic, you can prove something exists by showing that its non-existence leads to a contradiction. However, a constructive proof is forced to actually exhibit or construct the object to prove its existence.

When we state a program specification in formal logic—asserting that for any valid input state, there exists an output state satisfying a condition—a constructive proof of that assertion must step-by-step show how to build that output state.

Early systems like PROW (PROW: A Step Toward Automatic Program Writing), developed by Richard J. Waldinger et al., demonstrated that the resulting proof tree serves as a direct template for the program's control flow. For example, a case split in a proof maps directly to an if-then-else branch in code, while an application of mathematical induction maps to a recursive function or loop.

To bridge the gap between abstract logic and concrete execution, researchers began modeling programming constructs (like variable assignments and state changes) directly as logical axioms. Jared L. Darlington demonstrated in Automatic Program Synthesis in Second-Order Logic how Hoare logic axioms could be embedded into a higher-order theorem prover. When the prover derives a path from the initial state to the target state, the sequence of logical deductions maps directly to executable instructions. Remarkably, complex algorithmic paradigms do not need to be hardcoded as templates; as shown in The Origin of the Binary-Search Paradigm, sophisticated strategies like binary search emerge naturally from the deductive steps required to resolve a mathematical specification.

Extracting Code via Interpolation and Sequents

How do we algorithmically translate a static proof tree into clean, functional code? One powerful mechanism relies on Craig's Interpolation Theorem and Beth Definability. If a specification implicitly defines an output based on its inputs, we can use a specialized sequent calculus to extract an explicit definition.

Tim S. Lyon et al. in Constructive Interpolation and Concept-Based Beth Definability for Description Logics via Sequents show how this works: by assigning partial interpolants to the initial steps of a proof and propagating them through inference rules, the final conclusion yields a concrete, computable definition.

This structural blueprinting is highly effective for data transformations. For instance, Cécilia Pradic et al. leveraged this in Synthesizing Nested Relational Queries from Implicit Specifications to synthesize complex database queries. By traversing the proof tree of a data relationship, their algorithm emits functional code in Nested Relational Calculus (NRC) for each logical step, turning a model-theoretic proof of determinacy into an executable query.

The Challenge of Loops: Co-Synthesizing Invariants

The most significant hurdle in deductive synthesis is handling loops and iteration. To prove that a loop satisfies a specification, a theorem prover needs a loop invariant—a logical property that remains true before and after every iteration of the loop. Finding these invariants manually is notoriously difficult.

To solve this, modern synthesis frameworks use co-synthesis: they search for the program logic and the inductive invariant simultaneously. Jan Leike et al. applied this to numerical loops in Synthesis for Polynomial Lasso Programs, transforming the joint search for program coefficients and inductive invariants into a non-linear constraint problem solvable by Satisfiability Modulo Theories (SMT) solvers. Similarly, for probabilistic or randomized programs, Justin Hsu et al. demonstrated in Constraint-Based Synthesis of Coupling Proofs that co-synthesizing a coupling function alongside a coupled inductive invariant allows systems to verify complex stochastic properties without manual specification of the invariant.

Scaling Up: SMT Solvers and Language Models

While early deductive synthesis was limited by the combinatorial explosion of manual theorem proving, modern tools scale the idea by integrating automated solvers and large language models (LLMs).

In the domain of syntax-guided synthesis (SyGuS), solvers can extract functional implementations directly from proofs of unsatisfiability, as detailed by Rajeev Alur et al. in SyGuS-Comp 2017: Results and Analysis.. If an SMT solver proves that no counter-example can possibly violate a specification, the structure of that refutation proof contains the conditional branches and functions needed to reconstruct the target function.

Recently, the paradigm has evolved to combine the intuitive generation capabilities of LLMs with the rigorous guarantees of formal logic. Instead of asking an LLM to write code directly—which often introduces subtle bugs—frameworks like LLMLIFT, introduced by Sahil Bhatia et al. in Verified Code Transpilation with LLMs, prompt the model to generate the program logic and formal proof annotations (such as loop invariants) simultaneously. An SMT solver then acts as an automated judge, verifying the code against the generated invariants.

Conversely, LLMs can be used to generate the formal logic itself by shifting the medium. Behrad Rabiei demonstrates in LTLCodeGen: Code Generation of Syntactically Correct Temporal Logic for Robot Task Planning that prompting an LLM to write executable Python code that constructs Linear Temporal Logic (LTL) formulas yields far higher syntactic accuracy than prompting the model to output raw logic strings. By executing this code, the system programmatically builds sound formal specifications that can be fed into downstream synthesis pipelines, bridging the gap between natural language and correct-by-construction execution.

Key Foundational Work

PROW: A Step Toward Automatic Program Writing (1969) — contributed 4 concept elements to this direction.
PROW: A Step Toward Automatic Program Writing (1969) — contributed 4 concept elements to this direction.
Application of Theorem Proving to Problem Solving (1969) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_logic_based_program_synthesis_a0feed99,
  title = {logic-based program synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logic-based-program-synthesis/rdr_a0feed99a5904255a6695a07f15c754c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_logic_based_program_synthesis_a0feed99_v1,
  title = {logic-based program synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logic-based-program-synthesis/rdr_a0feed99a5904255a6695a07f15c754c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake