Neural-Guided Inductive Synthesis of Functional Programs on List Manipulation by Offline Supervised Learning

Abstract

Synthesizing intended programs from user-specified input-output examples, also known as Programming by Examples (PBE), is a challenging problem in program synthesis, and has been applied to a wide range of domains. A key challenge in PBE is to efficiently discover a user-intended program in the search space that can be exponentially large. In this work, we propose a method for automatic synthesis of functional programs on list manipulation, by using offline-trained Recurrent Neural Network (RNN) models to guide the program search. We adopt miniKanren, an embedded domain-specific language for flexible relational programming, as an underlying top-down deductive search engine of candidate programs that are consistent with input-output examples. Our approach targets an easy and effective integration of deep learning techniques in making better PBE systems and combines two technical ideas on generating diverse training dataset and designing rich feature embeddings of probable subproblems for synthesis generated by deductive search. The offline-learned model is then used in PBE to guide the top-down deductive search with specific strategies. To practically manipulate data structures of lists, our method synthesizes functional programs with popular higher-order combinators including $\texttt {map}$ , $\texttt {foldl}$ and $\texttt {foldr}$ . We have implemented our method and evaluated it with challenging program synthesis tasks on list manipulation. The experiments show promising results on the performance of our method compared to related state-of-the-art inductive synthesizers.

Keywords

• Programming by examples
• functional programs
• miniKanren
• relational programming
• deep learning
• deductive search