Source-linked AI summary
Program Synthesis using Natural Language
Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, Sailesh R, Subhajit Roy
TL;DR
End-users often need small programs but struggle with precise specifications and domain-specific languages. The paper presents a framework that learns NL-to-DSL translation and ranking from a DSL definition and paired examples, achieving top-1 and top-3 retrieval of desired programs across three domains. Its applicability is bounded when the target DSL lacks a direct abstraction correspondence or when search becomes computationally expensive.
Problem
End-users struggle to express repetitive or specialized tasks in domain-specific languages and precise specifications, motivating synthesis from natural-language descriptions.
Method
The framework takes a DSL definition and English/program pairs, generates candidate programs from input words, and ranks them using learned dictionaries, classifiers, weights, and structural scores.
Results
Across three domains and 1200+ English descriptions, the synthesizers rank the desired program in the top-1 and top-3 choices for over 80% and 90% of descriptions, respectively.
Takeaways & Limitations
The framework supports constructing NL-to-DSL synthesizers for different DSLs by providing the DSL definition and translation examples.
Takeaways & Limitations
The approach works poorly when the source and target abstractions lack direct correspondence, and its worst-case cost is exponential in DSL size.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper introduces a general framework that synthesizes ranked DSL programs from natural-language descriptions, addressing the difficulty of writing precise specifications and DSL code. It learns translation and ranking components from a DSL definition and English/program pairs, and evaluates the approach across three domains.
- Motivation: Natural-language program synthesis targets DSL programs from imprecise descriptions, allowing users to inspect or execute ranked candidates rather than requiring guaranteed correctness.The interaction is compared with selecting results from a search engine or Programming by Example system.
- Framework: The framework takes a DSL definition and English-to-program training pairs, then learns a dictionary, classifiers, and weights for a generic synthesizer.Unlike techniques specialized to one DSL, the methodology is intended for multiple DSLs.
- Framework: The synthesis algorithm generates consistent DSL programs from input words and ranks them using coverage, mapping, and structure scores.These scores combine in a weighted linear model and reflect word use, likely meanings, and natural program structure.
- Training: The training procedure generates classifier data from top-level examples and smooths a discrete metric into a continuous differentiable loss for weight learning.The classifiers and score-combination weights are learned with off-the-shelf machine-learning algorithms.
2. Motivating Scenarios
The motivating scenarios span text editing, automata-based tutoring, and air-travel querying, demonstrating how natural-language synthesis can target DSLs with different structures and purposes. The examples show conditional text operations, formal language specifications, and database-style queries.
- Motivating Scenarios: The framework targets three task categories: command execution on unstructured text, constraint-based automata construction, and question answering over air-travel data.These domains vary in DSL structure, language idioms, and English-sentence complexity.
- Text Editing: Text editing requires operations such as insertion, deletion, replacement, and extraction conditioned on regular-expression matches and surrounding context.The paper motivates a command language with Insert, Remove, Print, Replace, scoped iteration, predicates, and occurrence selection.
- Automata Theory: The automata domain uses a DSL with string predicates, Boolean connectives, substring-position functions, and quantification over string positions.The DSL supports generating correct solutions and feedback for students’ automata-construction attempts.
- ATIS: ATIS queries use a DSL based on SQL-style row and column operations with predicates for air-travel locations, times, dates, and prices.ATIS consists of English queries paired with a database containing flight information.
3. Problem Definition
The paper formalizes NL-to-DSL synthesis as constructing synthesizers from a DSL and English/program training pairs. A DSL combines a context-free grammar with a checker for grammatical and semantic validity.
- Problem Definition: The training problem is to synthesize NL-to-DSL synthesizers from a DSL definition and example pairs of English sentences with intended programs.The DSL is represented as L = (G,VC), where G is a grammar and VC checks validity.
- Problem Definition: A DSL consists of a context-free grammar G, terminal symbols G_T, production rules G_R, and a syntactic/semantic checker V_C.The checker determines whether a program belongs to the grammar and is semantically meaningful.
4. NL to DSL Synthesis Algorithm
The synthesis algorithm converts an English command into consistent DSL programs, then ranks them using coverage, mapping, and structure-based scores. The combined ranking resolves ambiguities that individual scores cannot reliably distinguish.
- Algorithm overview: The algorithm maps each input word to possible DSL terminals, generates all consistent programs with the Bag algorithm, and ranks them using combined scores.The output is a ranked set of candidate programs rather than a single unqualified translation.
- Consistent programs: A program is consistent when a witness map connects some sentence word occurrences to exactly the terminals appearing in the program.UsableWords identifies words that can map to grammar terminals, while UsedWords records those actually used by a witness map.
- Bag algorithm: The Bag algorithm repeatedly combines well-typed programs while preventing different subprograms from reusing the same input words.Its restrictions preserve top-level holes, yield a finite search space, and support bottom-up computation of the fixpoint.
- Scoring: The ranking uses coverage, mapping, and structure scores to assess input-word usage, word-to-terminal likelihood, and relationships among mapped terminals.Coverage favors programs using more available information, while structure captures relations and placement that word-level scores miss.
- Coverage score: The coverage score ranks a translation higher when it uses more of the user’s available information, as illustrated by preferring P1 over P2 for a cheapest-flight query.P1 includes the desired cheapest-fare operation, whereas P2 ignores that part of the input.
- Combined ranking: Structure information distinguishes programs with identical coverage and mapping scores, and the weighted combination ranks the intended P1 above incorrect alternatives.In the text-editing example, individual scores can tie or misrank candidates, while their learned combination makes P1 the clear winner.
5. Training Phase
The training phase learns word-to-terminal mappings, component-score classifiers, and combination weights from top-level NL/DSL training pairs. It generates lower-level classifier data from candidate programs and uses a differentiable loss for weight optimization.
- Training overview: Training learns classifiers, weights, and word-to-terminal mappings used by the synthesis algorithm from the DSL designer’s top-level training data.The process addresses both classifier selection and generation of lower-level training examples.
- Mapping classifier: The mapping classifier predicts the likelihood that a word maps to a DSL terminal using its part-of-speech tag and a Naive Bayesian classifier.Its training examples are generated from witness maps constructed for the top-level programs.
- Mapping data: Witness-map likeability favors mappings that use all parts of the input sentence and penalizes reusing one sentence part across multiple subprograms.The likeability tuples combine UsedWords and Disjointedness criteria.
- Structure classifiers: Structure classifiers predict whether program combinations instantiate particular connections using seven features and Naive Bayesian classification.Training data labels combinations present in the desired program as positive and other combinations from the candidate set as negative.
- Dictionary construction: The dictionary is initialized from DSL terminal names and WordNet synonyms, then refined by learned mapping scores and user-provided seed words for unmapped domain terms.Low-scoring mappings are discarded, while missing mappings detected in training data trigger user prompts for additional seed words.
- Weight learning: The optimization function counts training benchmarks where the correct translation is ranked first, and gradient descent learns weights through a continuous differentiable loss.The loss uses a sigmoid transformation and a continuous approximation to the maximum incorrect score; saturation prevents one difficult benchmark from dominating optimization.
6. Experimental Evaluation
Across three domains, the synthesizer was evaluated with cross-validation for ranking precision, recall, computational cost, component contributions, weight learning, and cross-domain generalization.
- Evaluation setup: 10-fold cross-validation trained classifiers and weights on 90% of the data and evaluated them on the held-out 10%.Ties were handled using a ranking scheme that assigns tied items the lowest position in the ordered result list.
- Precision and recall: Over 80% of inputs in every domain had the desired program as the unambiguous top-ranked result.For ATIS, the desired program was top-ranked for 88.4% of inputs, with a 95% confidence interval of 88.4 ± 4.2%.
- Precision and recall: Over 90% of inputs across all three domains placed the desired program among the top three results.The desired program entered the top three an additional 5%-12% of the time beyond top-rank performance; fewer than 10% of inputs remained outside the top three in each domain.
- Computational cost: Average translation took 0.68 seconds for Text Editing, 1.72 seconds for Automata, and 1.38 seconds for ATIS.More than 85% of inputs took under 1 second, while very few took more than 3 seconds; unusually redundant inputs tended to be outliers.
- Individual component evaluation: 84.9% of inputs received the desired program as the top result with combined ranking, versus 17.9%, 31.0%, and 51.4% using CoverageScore, MappingScore, and StructureScore alone.The results indicate that no individual component was sufficient for ranking the desired program effectively.
- Individual component evaluation: Dropping StructureScore caused decreases as large as 81.86%, while dropping MappingScore caused smaller decreases of 2.04%-4.67%.CoverageScore also caused substantial degradation when removed, and the authors report that all components provide distinct, useful information.
7. Related Work
Related approaches span programming by demonstration, keyword programming, semantic parsing, and natural-language programming systems. The paper positions its method as combining broad recall with DSL-agnostic synthesis and learned ranking.
- PBE/PBD Techniques for Data Manipulation: Programming by demonstration and programming by example support end-user programming across domains, but examples are inefficient for some conditional operations.Conditional operations may require examples covering both true and false paths, rapidly increasing the number of examples needed.
- Keyword Programming: Keyword programming builds expression trees from keywords and ranks them with simple heuristics, but often has low precision.These systems may frequently suggest incorrect programs.
- Semantic Parsing: Semantic parsing usually offers high precision but low recall, whereas this paper targets similar precision without often returning no suggestions.Semantic-parsing systems may suggest the correct program when they return an output, but frequently produce none.
- Natural Language Based Programming: SmartSynth and NLyze are specialized to particular domains and use simpler ranking strategies than the proposed framework.The paper describes its approach as DSL-agnostic and automatically learning feature weights, while simpler ranking reduces recall and precision.
8. Conclusion
The conclusion presents natural-language program synthesis as a way to express tasks that are awkward to specify by examples, while generalizing across DSLs through translation examples. The approach remains constrained by source–DSL correspondence and worst-case search cost.
- 8. Conclusion: Natural-language synthesis addresses end users who lack programming knowledge and struggle to provide detailed, syntactically correct instructions.The paper targets small programs or specifications that can be expressed succinctly in an appropriate DSL.
- 8. Conclusion: Natural language can specify tasks for which programming-by-example is unnatural or would require too many examples.The paper contrasts this with the demonstrated adoption of programming-by-example systems such as Flash Fill.
- 8. Conclusion: The framework generates and ranks programs from terminals corresponding to words in the natural-language description.The conclusion identifies this generation-and-ranking process as the core technology.
- 8. Conclusion: Translation examples allow the framework to create synthesizers for different DSLs without redesigning the overall method.The paper presents this as the framework’s broader generalization across target languages.
- 8. Conclusion: The method works best when the DSL has functional abstractions that correspond directly to those expressed in natural language.Binding constructs and mismatched abstractions reduce effectiveness because conversion then requires non-trivial logical reasoning.
- 8. Conclusion: Worst-case cost is exponential in DSL size, although the implementation is usually under 1 second for practical DSLs.Runtime depends mainly on the dictionary subset associated with words in the input sentence.