Interactive Program Synthesis

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 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.