FlashMeta: a framework for inductive program synthesis

By Oleksandr Polozov, Sumit Gulwani. 2015

334 citations recorded by the source corpus.

Subfields: Hardware and Architecture, Information Systems, Software, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Hardware and Architecture

In Information Systems

In Software

In Natural Language Processing

Citations in the corpus

CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis (2022, methodology): “A large body of prior research attempted to address (1) by exploring methods like stochastic search techniques (Parisotto et al., 2017; Schkufza et al., 2013) and deductive top-down search (Gulwani, 2011; Polozov & Gulwani, 2015).”
The Next Decade in AI: Four Steps Towards Robust Artificial Intelligence (2020, background): “(By comparison, Microsoft Excel’s Flash fill, a symbolic system based on inductive program synthesis, is far more effective in many cases of this variety (Polozov & Gulwani, 2015).”
CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Benchmarking on HumanEval-X (2023, methodology): “From LISP-based pioneering deductive synthesis approaches [31, 37] to modern program synthesis systems [23, 30], to end-to-end code generation via deep neural networks [19, 32, 33], tremendous efforts have been made to enable machines to automatically write correct programs as part of the quest to…”
RobustFill: Neural Program Learning under Noisy I/O (2017, methodology): “DSL-based synthesis: Non-statistical DSL-based synthesis approaches (Gulwani et al., 2012) exploit independence properties of DSL operators to develop a divide-and-RobustFill conquer based search algorithm with several hand-crafted pruning and ranking heuristics (Polozov & Gulwani, 2015).”
DeepCoder: Learning to Write Programs (2016, background): “FlashMeta (Polozov & Gulwani, 2015) describes a framework for DSLs which allow decomposition of the search problem, e.g., where the production of an output string from an input string can be reduced to ﬁnding a program for producing the ﬁrst part of the output and concatenating it with a program…”
AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (2020, neutral): “The synthesized programs—or algorithms—solve problems like sorting, addition, counting [74, 27, 70, 85], string manipulations [64, 61, 19], character recognition [38], competitionstyle programming [5], structured data QA [56, 45, 46],”
TerpreT: A Probabilistic Programming Language for Program Induction (2016, methodology): “There have been many synthesis techniques developed for a wide range of problems including data wrangling (Gulwani et al., 2012; Polozov and Gulwani, 2015), inference of efficient synchronization in concurrent programs, synthesizing efficient low-level code from partial programs (Solar-Lezama et al.”
AutoPandas: neural-backed generators for program synthesis (2019, methodology): “These class of approaches involve the design of a special-purpose DSL tailored towards the target domain [Gulwani 2011; Polozov and Gulwani 2015] such as string processing or table data extraction.”
Structural Language Models of Code (2019, background): “…avoided this issue by limiting the generation problem: program synthesis approaches are often tailored to domain-speciﬁc languages (Gulwani, 2011; Polozov & Gulwani, 2015; De-vlin et al., 2017; Ellis et al., 2019), while other recent approaches generate code in general languages like Java and 1…”
CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Evaluations on HumanEval-X (2023, methodology): “From LISP-based pioneering deductive synthesis approaches (Waldinger and Lee, 1969; Summers, 1977) to modern program synthesis systems (Solar-Lezama, 2008; Polozov and Gulwani, 2015), to end-to-end code generation via deep neural networks (Mou et al.”
Data-Driven Program Completion (2017, methodology): “e problem of program synthesis has been considered for a long time (Alur et al. 2015a; Pnueli and Rosner 1989) and recently it has been successfully applied to domain-speci c tasks (Feng et al. 2016, 2017; Polozov and Gulwani 2015; Yaghmazadeh et al. 2016).”
SQLizer: query synthesis from natural language (2017, methodology): “…recent years, there has been considerable interest in automated synthesis of programs from informal specifications, such as input-output examples [Barowy et al. 2015; Feser et al. 2015; Gulwani 2011; Le and Gulwani 2014; Osera and Zdancewic 2015; Polozov and Gulwani 2015; Yaghmazadeh et al. 2016].”
Getafix: learning to fix bugs automatically (2019, positive): “Refazer [Rolim et al. 2017] uses PROSE [Polozov and Gulwani 2015] and a DSL of program transformations to learn repetitive edits.”
SpreadsheetCoder: Formula Prediction from Semi-structured Context (2021, background): “On the other hand, in (Vijayakumar et al., 2018), they design a neural network to guide the deductive search performed by PROSE (Polozov & Gulwani, 2015), a commercial framework for input-output program synthesis.”
Leveraging Language to Learn Program Abstractions and Search Heuristics (2021, methodology): “Recent approaches to program synthesis have attempted to learn search models (Gulwani et al., 2015; Polozov & Gulwani, 2015; Balog et al., 2016; Devlin et al., 2017), program libraries, or both jointly from data (Shin et al., 2019; Dumancić & Cropper; Ellis et al., 2021; 2020; Lázaro-Gredilla et…”
Bayesian Sketch Learning for Program Synthesis (2017, background): “These constraints are imposed either by having an incomplete syntactic model, known as a program sketch [43, 44], as part of the problem instance, or by restricting synthesis to a narrowly tailored domain-specific language (DSL) [9, 19, 35].”
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].”
DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning (2021, methodology): “Inductive program synthesis ś synthesizing programs given one or more examples of their behavior ś has emerged as both a practical tool for automating end-user programming tasks [20, 43, 51], and a route to building more robust, interpretable, generalizable and sample-efficient learning systems in a”
Automatic Program Synthesis of Long Programs with a Learned Garbage Collector (2018, background): “Another difference from string processing is that strings can be broken into segments that are dealt separately [12].”