Type-driven Neural Programming by Example

Abstract

In this thesis we look into programming by example (PBE), which is about finding a program mapping given inputs to given outputs. PBE has traditionally seen a split between formal versus neural approaches, where formal approaches typically involve deductive techniques such as SAT solvers and types, while the neural approaches involve training on sample input-outputs with their corresponding program, typically using sequence-based machine learning techniques such as LSTMs [41]. As a result of this split, programming types had yet to be used in neural program synthesis techniques. We propose a way to incorporate programming types into a neural program synthesis approach for PBE. We introduce the Typed Neuro-Symbolic Program Synthesis (TNSPS) method based on this idea, and test it in the functional programming context to empirically verify type information may help improve generalization in neural synthesizers on limited-size datasets. Our TNSPS model builds upon the existing Neuro-Symbolic Program Synthesis (NSPS), a tree-based neural synthesizer combining info from input-output examples plus the current program, by further exposing information on types of those input-output examples, of the grammar production rules, as well as of the hole that we wish to expand in the program. We further explain how we generated a dataset within our domain, which uses a limited subset of Haskell as the synthesis language. Finally we discuss several topics of interest that may help take these ideas further. For reproducibility, we release our code publicly.

References in corpus (25)

• Adam: A Method for Stochastic Optimization
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Neural Machine Translation by Jointly Learning to Align and Translate
• Neural Programmer-Interpreters
• Neural GPUs Learn Algorithms
• RobustFill: Neural Program Learning under Noisy I/O
• Neuro-Symbolic Program Synthesis
• Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing
• Making Neural Programming Architectures Generalize via Recursion
• Programmatically Interpretable Reinforcement Learning
• Programming with a Differentiable Forth Interpreter
• TerpreT: A Probabilistic Programming Language for Program Induction
• Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples
• Neural Programmer: Inducing Latent Programs with Gradient Descent
• A Simple Differentiable Programming Language
• SyGuS-Comp 2016: Results and Analysis
• Learning Efficient Algorithms with Hierarchical Attentive Memory
• HOUDINI: Lifelong Learning as Program Synthesis
• Lecture notes on the lambda calculus
• Learning to Represent Programs with Property Signatures
• Recent Advances in Neural Program Synthesis
• Neural Program Search: Solving Programming Tasks from Description and Examples
• Towards Proof Synthesis Guided by Neural Machine Translation for Intuitionistic Propositional Logic
• Towards Neural-Guided Program Synthesis for Linear Temporal Logic Specifications
• Neural Program Synthesis By Self-Learning