Syntax-guided synthesis
By Rajeev Alur, Rastislav Bodík, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, Abhishek Udupa. 2013
909 citations recorded by the source corpus.
The classical formulation of the program-synthesis problem is to find a program that meets a correctness specification given as a logical formula. Recent work on program synthesis and program optimization illustrates many potential benefits of allowing the user to supplement the logical specification with a syntactic template that constrains the space of allowed implementations. Our goal is to identify the core computational problem common to these proposals in a logical framework. The input to the syntax-guided synthesis problem (SyGuS) consists of a background theory, a semantic correctness specification for the desired program given by a logical formula, and a syntactic set of candidate implementations given by a grammar. The computational problem then is to find an implementation from the set of candidate expressions so that it satisfies the specification in the given theory. We describe three different instantiations of the counter-example-guided-inductive-synthesis (CEGIS) strategy for solving the synthesis problem, report on prototype implementations, and present experimental results on an initial set of benchmarks.
Subfields: Artificial Intelligence, Software, Natural Language Processing, Code Generation & Program Synthesis
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Percy Liang
- Mohit Bansal
- Yoshua Bengio
- Quoc V. Le
- Sergey Levine
- Jianfeng Gao
- Josh Tenenbaum
- Graham Neubig
In Software
- Rishabh Singh
- Charles Sutton
- Oleksandr Polozov
- Dawn Song
- Marc Brockschmidt
- Pushmeet Kohli
- Swarat Chaudhuri
- Daniel Tarlow
In Natural Language Processing
- Rishabh Singh
- Dawn Song
- Josh Tenenbaum
- Charles Sutton
- Swarat Chaudhuri
- Percy Liang
- Xinyun Chen
- Oleksandr Polozov
In Code Generation & Program Synthesis
- Rishabh Singh
- Charles Sutton
- Swarat Chaudhuri
- Armando Solar-Lezama
- Augustus Odena
- Josh Tenenbaum
- Oleksandr Polozov
- Pushmeet Kohli
Citations in the corpus
- Program Synthesis with Large Language Models (2021, background): “The most notable of these is the SyGuS competition [Alur et al., 2013], which includes tasks such as generating string transformations and bit-vector manipulations.”
- MultiPL-E: A Scalable and Polyglot Approach to Benchmarking Neural Code Generation (2023, background): “Code generation has long been a task of interest: there is extensive work on program synthesis [11], [12], [13] using both symbolic and neuro-symbolic approaches.”
- RobustFill: Neural Program Learning under Noisy I/O (2017, methodology): “Modern rule-based synthesis methods are typically centered around hand-crafted function semantics and pruning rules to search for programs consistent with the I/O examples (Gulwani et al., 2012; Alur et al., 2013).”
- Neuro-Symbolic Program Synthesis (2016, background): “The DSL-based program synthesis approach has also seen a renewed interest recently (Alur et al., 2015).”
- TerpreT: A Probabilistic Programming Language for Program Induction (2016, background): “We note that another recent effort SyGuS (Alur et al., 2015) aims to unify different program synthesis approaches using a common intermediate format based on context-free grammars so that different inferences techniques can be compared, but the TerpreT language allows for encoding richer programming”
- A Scalable and Extensible Approach to Benchmarking NL2Code for 18 Programming Languages (2022, background): “Code generation has long been a task of interest: there is extensive work on program synthesis (Alur et al. 2013; Chaud-huri et al. 2021) using both symbolic and neuro-symbolic approaches.”
- Bayesian Sketch Learning for Program Synthesis (2017, background): “Existing approaches to synthesis commonly frame the problem as search over a space of programs [5].”
- FlashMeta: a framework for inductive program synthesis (2015, methodology): “Syntax-guided Synthesis SyGuS [1] is a recent initiative that aims to (a) standardize the input specification language of program synthesis problems; (b) develop general-purpose synthesis algorithms for these problems, and (c) establish an annual competition of such algorithms on a standardized…”
- Snuba: Automating Weak Supervision to Label Training Data (2018, background): “The inspiration for Snuba comes from program synthesis, where programs are generated given access to a set of input-output pairs [16, 46], reference implementations [3], or demonstrations [22].”
- Neurosymbolic Programming (2021, methodology): “Sketches generated from this distribution are concretized into complete symbolic programs using classic methods for program synthesis (Alur et al., 2015).”
- A large-scale benchmark for few-shot program induction and synthesis (2021, neutral): “For SyGus, we estimated the number of tasks looking at the largest competition in 2019 and the statistics on the programs described in Alur et al. (2013).”
- Learning Compositional Rules via Neural Program Synthesis (2020, background): “There is also related work from the programming languages community, such as Sketch [23], PROSE [24], and a large class of synthesizers from the SyGuS competition [25].”
- MultiPL-E: A Scalable and Extensible Approach to Benchmarking Neural Code Generation (2022, background): “Code generation has long been a task of interest: there is extensive work on program synthesis [12, 13, 14] using both symbolic and neuro-symbolic approaches.”
- Expectation vs. Experience: Evaluating the Usability of Code Generation Tools Powered by Large Language Models (2022, background): “…different kinds of approaches: (1) program synthesis algorithms that search over a large program space defined by a domain-specific language (DSL) [2, 7, 10, 12, 14, 19, 24, 25, 30, 31, 34, 43], and (2) deep learning models that are trained on a large amount of existing code and can generate new…”
- Neural Sketch Learning for Conditional Program Generation (2017, background): “…reduce this difficulty: sketches could be generated using a limited amount of semantic information, and the concretizer could use logic-based techniques (Alur et al., 2013; Gulwani et al., 2017) to ensure that the programs synthesized from these sketches match the semantic constraints exactly.”