Program Synthesis Using Natural Language

By Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, R. Sailesh, Subhajit Roy. 2015

161 citations recorded by the source corpus.

Interacting with computers is a ubiquitous activity for millions of people. Repetitive or specialized tasks often require creation of small, often one-off, programs. End-users struggle with learning and using the myriad of domain-specific languages (DSLs) to effectively accomplish these tasks. We present a general framework for constructing program synthesizers that take natural language (NL) inputs and produce expressions in a target DSL. The framework takes as input a DSL definition and training data consisting of NL/DSL pairs. From these it constructs a synthesizer by learning optimal weights and classifiers (using NLP features) that rank the outputs of a keyword-programming based translation. We applied our framework to three domains: repetitive text editing, an intelligent tutoring system, and flight information queries. On 1200+ English descriptions, the respective synthesizers rank the desired program as the top-1 and top-3 for 80% and 90% descriptions respectively.

Subfields: Artificial Intelligence, Information Systems, 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

In Information Systems

In Natural Language Processing

In Code Generation & Program Synthesis

Citations in the corpus

A systematic evaluation of large language models of code (2022, methodology): “, 2014) and synthesizing code from natural language descriptions (Desai et al., 2016).”
Measuring Coding Challenge Competence With APPS (2021, neutral): “Raza et al. (2015) and Desai et al. (2016) generate short programs using ad-hoc programming languages to solve speciﬁcations such as “Any 2 letters followed by any combination of 6 whole numbers.””
Learning to Mine Aligned Code and Natural Language Pairs from Stack Overflow (2018, background): “…on natural language processing (NLP) techniques, for code completion [9], source code summarization [2], automatic documentation of source code [44], deobfuscation [16, 34, 40], cross-language porting [27, 28], code retrieval [3, 42] and even code synthesis from natural language [7, 21, 32, 47].”
NL2Bash: A Corpus and Semantic Parser for Natural Language Interface to the Linux Operating System (2018, background): “…language as a programming medium would be universally accessible and would support the automation of highly repetitive tasks such as ﬁle manipulation, search, and application-speciﬁc scripting (Wilensky et al., 1984; Wilensky et al., 1988; Dahl et al., 1994; Quirk et al., 2015; Desai et al., 2016).”
Big Code != Big Vocabulary: Open-Vocabulary Models for Source Code (2020, background): “Precise scoring of code fragments is essential for tasks such as translating a program from one programming language to another [54, 66], code completion [32, 76], and code synthesis from natural language and vice versa [7, 27, 67, 73].”
Program Synthesis from Natural Language Using Recurrent Neural Networks (2017, methodology): “Recently, machine learning techniques have been developed to build probabilistic models to represent the joint distribution of text and programs [5, 10, 13].”
Studying the effect of AI Code Generators on Supporting Novice Learners in Introductory Programming (2023, unknown): “Various methods have been employed, such as using semantic parsers [4, 9, 11, 18, 33, 34, 47, 50, 51, 56, 68, 80] and machine learning [5, 54, 71–73, 93, 95].”
Leveraging Language to Learn Program Abstractions and Search Heuristics (2021, background): “…2017; Ye et al., 2020b; Goyal et al., 2020; Liang et al., 2020; Mu et al., 2019; Luketina et al., 2019), and as a high-level specification for program synthesis tasks (Ye et al., 2020a; Nye et al., 2019; Polosukhin & Skidanov, 2018; Ye et al., 2020b; Desai et al., 2016; Srivastava et al., 2017).”
SQLizer: query synthesis from natural language (2017, methodology): “Towards this goal, we used queries for a mock database accompanying a databases textbook [Elmasri and Navathe 2011].”
Investigating Math Word Problems using Pretrained Multilingual Language Models (2021, background): “This task therefore can be seen as a special case of code synthesis (Desai et al., 2016; Lin et al., 2018; Shin et al., 2019; Wang et al., 2020) in a restricted domain, where the code to be synthesized is the expression tree.”
Program Synthesis (2017, background): “The user intent can be expressed in various forms including logical specification, examples [44], traces, natural language [28, 46, 79], partial Full text available at: http://dx.”
Maybe Deep Neural Networks are the Best Choice for Modeling Source Code (2019, unknown): “f code fragments is essential for tasks like translating a program from one programming language to another [45, 56], code completion [29, 64], and code synthesis from natural language and vice versa [7, 14, 23, 25, 57, 61]. Theintrinsicmetricthatweuseiscrossentropy,whichisastandard measure employed”
Parsel: A Unified Natural Language Framework for Algorithmic Reasoning (2022, background): “Program synthesis is the long-standing challenge of generating programs from high-level speciﬁcations (Gulwani et al., 2017), such as input-output examples (Bauer, 1979; Gulwani, 2016) and/or natural language descriptions (Raza et al., 2015; Yin & Neubig, 2017; Desai et al., 2016).”
Learning to Solve Complex Tasks by Talking to Agents (2021, background): “Program Synthesis has traditionally focused on constructing executable programs from high-level speciﬁcations (Manna and Waldinger, 1980) or intentions given input-output examples (Gulwani, 2011) and other pieces of evidence including nat-ural language (Desai et al., 2016) (see Gulwani (2010)).”