Synthesizing data structure transformations from input-output examples

By John K. Feser, Swarat Chaudhuri, Işıl Dillig. 2015

364 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Information Systems, 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 Computational Theory and Mathematics

In Information Systems

In Software

In Natural Language Processing

In Code Generation & Program Synthesis

Citations in the corpus

SPoC: Search-based Pseudocode to Code (2019, background): “In contrast, program synthesis in the programming languages community emphasizes producing programs with the correct semantics, typically captured by a set of input-output test cases that the program must compute correctly [11, 10].”
DeepCoder: Learning to Write Programs (2016, methodology): “This approach can be combined with pruning based on types and other logical reasoning (Feser et al., 2015).”
Programmatically Interpretable Reinforcement Learning (2018, background): “One of the key ideas to make this search tractable is to provide the synthesizer a sketch of the desired program in addition to the examples, for example in (Solar-Lezama, 2009) and (Feser et al., 2015).”
Component-based synthesis for complex APIs (2017, methodology): “Similar to many programming-byexample (PBE) approaches, SYPET requires users to provide partial specifications as input-output examples [2, 7, 11, 14, 18, 31, 39].”
Neural Functional Programming (2016, methodology): “Additionally, we show results for λ(2) (Feser et al., 2015), a strong program synthesis baseline from programming languages research, because of its built-in support for list-processing programs.”
Learning higher-order logic programs (2019, methodology): “The L2 system (Feser et al. 2015) synthesises recursive functional algorithms.”
Neural Sketch Learning for Conditional Program Generation (2017, methodology): “We approach this problem with a combination of neural learning and type-guided combinatorial search (Feser et al., 2015).”
Neural Guided Constraint Logic Programming for Program Synthesis (2018, methodology): “The method λ(2) [11] is most similar to miniKanren, but specializes in numeric, statically-typed inputs and outputs.”
Neurosymbolic Program Synthesis (neutral): “In top-down enumerative search [23,24], one repeatedly applies the rules of a DSL’s grammar, starting with the initial nonterminal, until complete programs are generated.”
In-IDE Code Generation from Natural Language: Promise and Challenges (2021, background): “Besides visual no-code or low-code programming interfaces, there has also been much progress on program synthesis [11, 28, 30, 105], which uses input-output examples, logic sketches, etc.”
Synthesizing transformations on hierarchically structured data (2016, methodology): “However, there is also an emerging body of work on the synthesis of programs over recursive data structures [5, 13, 23, 28].”
Expectation vs. Experience: Evaluating the Usability of Code Generation Tools Powered by Large Language Models (2022, background): “…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 code given…”
Bayesian Sketch Learning for Program Synthesis (2017, methodology): “For example, in the popular paradigm of synthesis from input-output examples [14, 19], a synthesizer could simply generate a monolithic if -statement that replays the outputs present in the example set on the corresponding inputs.”
Data-Driven Program Completion (2017, positive): “…splicing is inspired by “sketches” (Solar-Lezama et al. 2006) and “templates” from previous approaches to synthesis (Srivastava et al. 2012). e sort of combinatorial search that our synthesis algorithm uses has parallels in enumerative approaches to synthesis (Feser et al. 2015; Udupa et al. 2013).”
Learning to Represent Programs with Property Signatures (2020, methodology): “Our baseline synthesizer is very similar to that in Feser et al. (2015) and works by ﬁlling in typed holes 9 .”
Generative Code Modeling with Graphs (2018, background): “For example, program synthesis tools based on enumeration and deduction [8, 9, 18, 23] are successful at generating programs that satisfy some (usually incomplete) formal speciﬁcation but are often obviously wrong on manual inspection, as they cannot distinguish unlikely from likely, “natural”…”