Interactive Program Synthesis

The core mechanism is a bidirectional feedback loop. The synthesizer proposes a candidate program based on the current specification. The user then provides feedback, which can be:

• A counterexample showing where the candidate fails.
• A partial correction or hint.
• A specification refinement (e.g., adding a new constraint). The synthesizer uses this feedback to generate a new, improved candidate, repeating until satisfaction. This loop bridges the intention gap between the user's high-level goal and the formal requirements needed for synthesis.

Unlike batch synthesis, the initial specification is often incomplete or ambiguous. The human's role is to progressively disambiguate and concretize requirements through interaction. Common specification modalities refined during interaction include:

• Input-Output Examples: The user critiques or adds new examples.
• Natural Language Descriptions: The user clarifies intent or corrects misinterpretations.
• Partial Sketches: The user fills in parts of a program sketch to guide the search.
• Logical Constraints: The user adds or modifies formal properties the program must satisfy. This turns specification from a one-time input into a collaborative discovery process.

The synthesizer actively queries the user to resolve ambiguities efficiently, a technique derived from oracle-guided synthesis. Query types include:

• Membership Queries: "Does this input/output pair match your intent?"
• Equivalence Queries: "Is this candidate program correct? If not, provide a counterexample."
• Preference Queries: "Which of these two candidate behaviors do you prefer?" This transforms the user into an oracle, allowing the system to explore the hypothesis space more strategically than passive refinement, significantly reducing the number of iterations required.

A critical form of feedback is the counterexample. When a user rejects a candidate program, they often provide a specific input where the output is incorrect. This counterexample is a powerful constraint that:

• Prunes the search space by eliminating all programs that produce the wrong output for that input.
• Guides generalization by forcing the synthesizer to hypothesize a rule that works for both previous examples and the new counterexample. This process is formalized in algorithms like Counterexample-Guided Inductive Synthesis (CEGIS), where a verifier (or the user) generates counterexamples to guide an inductive synthesizer.

Control alternates intelligently between the human and the synthesizer. The system is not purely reactive; it takes initiative by:

• Proposing multiple distinct alternatives for the user to choose from.
• Identifying and highlighting ambiguities in the current specification.
• Suggesting likely completions or next steps based on partial input. The user, in turn, can override, steer, or accept these suggestions. This cooperative dynamic balances the user's domain expertise and intent with the synthesizer's ability to search vast program spaces and deduce logical implications.

Because the process is interactive, the synthesizer must make its reasoning transparent and debuggable. Key features include:

• Presenting candidate programs in a human-readable form (e.g., code, visual diagrams).
• Explaining why a candidate was proposed (e.g., "This program fits all your examples.").
• Localizing the cause of errors (e.g., "The failure on your counterexample suggests the condition on line 3 is too weak.").
• Maintaining a history of the interaction for the user to review and backtrack. This transparency builds user trust and enables more effective debugging of both the candidate program and the user's own evolving specification.

A foundational paradigm for interactive synthesis where the user provides concrete input-output pairs as the specification. The synthesizer infers a general program that satisfies all examples. This is highly interactive, as users often refine the program by adding or correcting examples.

• Core Mechanism: Inductive generalization from specific instances.
• Primary Use Case: Data transformation tasks, like the FlashFill system in Microsoft Excel for spreadsheet manipulations.
• Interaction Loop: User provides examples → Synthesizer generates candidate → User validates or provides counterexamples.

A formal, iterative algorithm that structures the core interaction loop between a synthesizer and a verifier. It does not require a human in every cycle but models the refinement process.

• Algorithmic Loop: 1. Synthesize a candidate program from examples. 2. Verify it against a formal spec. 3. If verification fails, extract a counterexample. 4. Add the counterexample to the set of examples and repeat.
• Role of Interaction: In interactive synthesis, the human often acts as the oracle that provides the counterexample or validates the verifier's output.
• Key Benefit: Converges provably to a correct program by systematically eliminating incorrect candidates.

A technique where interaction begins with a partial program sketch provided by the user. The sketch contains intentional holes (syntactic placeholders) and high-level control structure, constraining the synthesizer's search space.

• User's Role: Provides domain expertise via the sketch's structure.
• Synthesizer's Role: Fills the holes with concrete code fragments (e.g., expressions, function calls) to satisfy a specification.
• Example: A developer sketches a sorting algorithm's loop structure but leaves the comparison logic as a 'hole'; the synthesizer finds the correct predicate.
• Advantage: Balances user control with automation, making it effective for synthesizing complex, idiomatic code.

A paradigm where the specification is defined by an oracle—a black-box entity that can answer queries about desired behavior. In interactive synthesis, the human user is the oracle.

• Query Types: The synthesizer can ask membership queries ('Does this input produce this output?') or equivalence queries ('Is this candidate program correct?')
• Interaction Model: The synthesizer actively drives the interaction by generating the most informative queries to reduce uncertainty, an approach known as active learning.
• Contrast with PBE: In PBE, the user provides examples proactively. In oracle-guided synthesis, the system interrogates the user reactively.

A synthesis methodology that uses rich, expressive type systems to guide the search. The types themselves constitute a partial specification, and the synthesizer uses type inference and checking to prune invalid candidates.

• Mechanism: Treats synthesis as a proof-search problem within a type theory. Generating a program is equivalent to constructing a proof that a term of the specified type exists.
• Interactive Context: Integrated Development Environments (IDEs) use this for type-aware code completion (e.g., suggesting functions that fit a required parameter type). More advanced systems allow users to write type signatures as 'specifications' and request implementations.
• Formal Guarantee: Programs are correct-by-construction with respect to the type specification.

The use of models like GPT-4 or Code Llama as the core synthesizer, with interaction occurring through natural language dialogue and in-context examples.

• Interaction Mode: User provides an initial natural language instruction; the LLM generates code. The user then provides iterative feedback in natural language (e.g., 'add error handling,' 'make it faster').
• Key Differentiator: Leverages few-shot prompting and massive pre-training on code, allowing it to handle ambiguous, high-level intent without a formal specification.
• Challenge & Role of Interaction: LLMs are prone to subtle bugs and hallucinations. The interactive loop is crucial for debugging and refinement, where the user acts as a tester and specifier, often providing example executions or unit tests as subsequent prompts.