Toward automatic program synthesis

By Zohar Manna, Richard J. Waldinger. 1971

How researchers see this paper

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

In Natural Language Processing

Citations in the corpus

Competition-level code generation with AlphaCode (2022, methodology): “A notable example is the deductive synthesis approach (Green, 1969; Manna and Waldinger, 1971), that transforms the task specification into constraints, uses a theorem prover to find a proof that satisfies all the constraints, and extracts the program from the proof.”
Program Synthesis with Large Language Models (2021, background): “Program synthesis is a longstanding goal of artificial intelligence research [Manna and Waldinger, 1971, Waldinger et al., 1969, Summers, 1977, Shaw et al., 1975, Pnueli and Rosner, 1989, Manna and Waldinger, 1975], dating as far back as the 1940s and 50s [Copeland, 2012, Backus et al., 1957].”
Evaluating Large Language Models Trained on Code (2021, background): “More recently, language models have also fueled progress towards the longstanding challenge of program synthesis (Simon, 1963; Manna & Waldinger, 1971), spurred by the presence of code in large datasets (Husain et al., 2019; Gao et al., 2020) and the resulting programming capabilities of language…”
CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis (2022, background): “Program Synthesis While program synthesis has a long history, two inherent challenges remain unsolved: (1) intractability of the program space and (2) difficulty in accurately expressing user intent (Manna & Waldinger, 1971; Gulwani et al., 2017).”
Programming with a Differentiable Forth Interpreter (2016, background): “Program Synthesis The idea of program synthesis is as old as Artiﬁcial Intelligence, and thus has a long history in computer science [16].”
From program verification to program synthesis (2010, background): “Categories and Subject Descriptors I.2.2[Automatic Programming]: Program Synthesis; F.3.1[Logics and Meanings of Programs]: Specifying andVerifying and Reasoning about Programs GeneralTerms Languages, Theory.”
Synthetic Data for Deep Learning (2019, background): “Learning-based program synthesis (earlier attempts were based on logical inference [392]) began with learning string manipulation programs [218] and soon branched into deep learning, using recurrent architectures to guide search-based methods [614] or to generate programs in encoder-decoder architec”
Structural Language Models of Code (2019, background): “equires reasoning over an unbounded number of syntactic structures and potential symbols. Previous approaches have avoided this issue by limiting the generation problem: program synthesis approaches (Manna and Waldinger, 1971) are tailored to domain-speciﬁc languages (Gulwani, 2011), semantic parsin”
Large Language Models for Software Engineering: Survey and Open Problems (2023, background): “Automated code generation has a long history, tracing its origins back to early visions of automated program synthesis [41], which have continued to develop and have generated impressive results [42].”
Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples (2018, methodology): “In this work, we build upon deductive search, ﬁrst studied for synthesis by Manna & Waldinger (1971), and primarily used for program synthesis from formal logical speciﬁcations (Puschel et al., 2005; Chaudhari & Damani, 2015).”
Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation (2023, methodology): “program synthesis techniques have been developed, including deductive synthesis [18, 31, 53], programming by examples [19, 48] and neural-guided synthesis [25].”
A Conversational Paradigm for Program Synthesis (2022, background): “Some have called it the holy grail of computer science (Manna and Waldinger, 1971; Gulwani et al., 2017).”
An Empirical Study of the Non-Determinism of ChatGPT in Code Generation (2023, methodology): “Relatively early work includes deductive synthesis approaches [19, 45] and inductive synthesis approaches [8, 56–58].”
Combinatorial sketching for finite programs (2006, background): “On the contrary, systems based on domain-specific rewrite rules are often incomplete [2, 6, 8, 9].”
Neurosymbolic Programming (2021, background): “Deductive search (Manna and Waldinger, 1971; Polozov and Gulwani, 2015) is an extension of top-down enumerative search that recursively decomposes the spec φ into smaller sub-specs {φj}j s.t. (a) the solution to the synthesis problem e |= φ can be reconstructed out of the sub- 44 Learning…”
The Robots Are Coming: Exploring the Implications of OpenAI Codex on Introductory Programming (2022, background): “The concept of computer programs being generated by computer programs goes back several decades [23], but has only gained significant ground very recently.”