# Program Synthesis using Natural Language

arXiv: https://arxiv.org/abs/1509.00413 · HTML: https://mlsanity.com/paper/1509.00413/

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Sep 2015.

## Built on by (most cited first, 30 of 41)

- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [A Systematic Evaluation of Large Language Models of Code](https://mlsanity.com/paper/2202.13169/) (2022)
- [Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generation](https://mlsanity.com/paper/2310.02304/) (2023)
- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [Large Language Models for Test-Free Fault Localization](https://mlsanity.com/paper/2310.01726/) (2023)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [Leveraging Language to Learn Program Abstractions and Search Heuristics](https://mlsanity.com/paper/2106.11053/) (2021)
- [Communicating Natural Programs to Humans and Machines](https://mlsanity.com/paper/2106.07824/) (2021)
- [Interactive Grounded Language Understanding in a Collaborative Environment: IGLU 2021](https://mlsanity.com/paper/2205.02388/) (2022)
- [Investigating Math Word Problems using Pretrained Multilingual Language Models](https://mlsanity.com/paper/2105.08928/) (2021)
- [Pix2Code: Learning to Compose Neural Visual Concepts as Programs](https://mlsanity.com/paper/2402.08280/) (2024)
- [NeurIPS 2021 Competition IGLU: Interactive Grounded Language Understanding in a Collaborative Environment](https://mlsanity.com/paper/2110.06536/) (2021)
- [InstructExcel: A Benchmark for Natural Language Instruction in Excel](https://mlsanity.com/paper/2310.14495/) (2023)
- [Training Language Models via Neural Cellular Automata](https://mlsanity.com/paper/2603.10055/) (2026)
- [VerMCTS: Synthesizing Multi-Step Programs using a Verifier, a Large Language Model, and Tree Search](https://mlsanity.com/paper/2402.08147/) (2024)
- [Hey AI, Can You Solve Complex Tasks by Talking to Agents?](https://mlsanity.com/paper/2110.08542/) (2021)
- [Transforming Human-Centered AI Collaboration: Redefining Embodied Agents Capabilities through Interactive Grounded Language Instructions](https://mlsanity.com/paper/2305.10783/) (2023)
- [Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search](https://mlsanity.com/paper/2405.16450/) (2024)
- [Where Does My Model Underperform? A Human Evaluation of Slice Discovery Algorithms](https://mlsanity.com/paper/2306.08167/) (2023)
- [AIOS Compiler: LLM as Interpreter for Natural Language Programming and Flow Programming of AI Agents](https://mlsanity.com/paper/2405.06907/) (2024)
- [Test Case-Informed Knowledge Tracing for Open-ended Coding Tasks](https://mlsanity.com/paper/2410.10829/) (2024)
- [Natural Language Commanding via Program Synthesis](https://mlsanity.com/paper/2306.03460/) (2023)
- [ProgramAlly: Creating Custom Visual Access Programs via Multi-Modal End-User Programming](https://mlsanity.com/paper/2408.10499/) (2024)
- [Natural Language-Guided Programming](https://mlsanity.com/paper/2108.05198/) (2021)
- [GPT-based Open-Ended Knowledge Tracing](https://mlsanity.com/paper/2203.03716/) (2022)
- [AI for Low-Code for AI](https://mlsanity.com/paper/2305.20015/) (2023)
- [From Idea to Implementation: Evaluating the Influence of Large Language Models in Software Development -- An Opinion Paper](https://mlsanity.com/paper/2503.07450/) (2025)
- [GAP-Gen: Guided Automatic Python Code Generation](https://mlsanity.com/paper/2201.08810/) (2022)
- [SemSup: Semantic Supervision for Simple and Scalable Zero-shot Generalization](https://mlsanity.com/paper/2202.13100/) (2022)
- [L^*LM: Learning Automata from Examples using Natural Language Oracles](https://mlsanity.com/paper/2402.07051/) (2024)

## Abstract (arXiv)

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.