Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples

Abstract

Synthesizing user-intended programs from a small number of input-output examples is a challenging problem with several important applications like spreadsheet manipulation, data wrangling and code refactoring. Existing synthesis systems either completely rely on deductive logic techniques that are extensively hand-engineered or on purely statistical models that need massive amounts of data, and in general fail to provide real-time synthesis on challenging benchmarks. In this work, we propose Neural Guided Deductive Search (NGDS), a hybrid synthesis technique that combines the best of both symbolic logic techniques and statistical models. Thus, it produces programs that satisfy the provided specifications by construction and generalize well on unseen examples, similar to data-driven systems. Our technique effectively utilizes the deductive search framework to reduce the learning problem of the neural component to a simple supervised learning setup. Further, this allows us to both train on sparingly available real-world data and still leverage powerful recurrent neural network encoders. We demonstrate the effectiveness of our method by evaluating on real-world customer scenarios by synthesizing accurate programs with up to 12x speed-up compared to state-of-the-art systems.

arXiv commentPublished in ICLR 2018, International Conference on Learning Representations (2018)

References in corpus (5)

• Adam: A Method for Stochastic Optimization
• DeepCoder: Learning to Write Programs
• Neural GPUs Learn Algorithms
• Making Neural Programming Architectures Generalize via Recursion
• Programming with a Differentiable Forth Interpreter

Cited by in corpus (26)

• Verification for Machine Learning, Autonomy, and Neural Networks Survey
• Just-in-Time Learning for Bottom-Up Enumerative Synthesis
• Write, Execute, Assess: Program Synthesis with a REPL
• Learning to Represent Programs with Property Signatures
• Neural-Guided Symbolic Regression with Asymptotic Constraints
• Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis
• Closed Loop Neural-Symbolic Learning via Integrating Neural Perception, Grammar Parsing, and Symbolic Reasoning
• Fusion 360 Gallery: A Dataset and Environment for Programmatic CAD Construction from Human Design Sequences
• Programming-by-Demonstration for Long-Horizon Robot Tasks
• Algebra-Based Reasoning for Loop Synthesis
• Program Synthesis with Pragmatic Communication
• A Survey on Neural-symbolic Learning Systems
• Program Synthesis Guided Reinforcement Learning for Partially Observed Environments
• Sketch-Driven Regular Expression Generation from Natural Language and Examples
• Algebra-based Synthesis of Loops and their Invariants (Invited Paper)
• Program Synthesis with Best-First Bottom-Up Search
• Robot Action Selection Learning via Layered Dimension Informed Program Synthesis
• Synthesizing Queries via Interactive Sketching
• Learning Execution through Neural Code Fusion
• Optimal Neural Program Synthesis from Multimodal Specifications
• BF++: a language for general-purpose program synthesis
• Type-driven Neural Programming by Example
• Latent Execution for Neural Program Synthesis
• Learning to Combine Per-Example Solutions for Neural Program Synthesis
• Comparison of Syntactic and Semantic Representations of Programs in Neural Embeddings
• Grammar Filtering For Syntax-Guided Synthesis