Research On Neural-guided Inductive Synthesis Of Functional Programs

With the rapid development of information technology,the demand for software functionality and development efficiency is increasing day by day.Program synthesis,which aims to automatically generate programs that satisfy a given specification,has received increasing attention in recent years as an important technique to address this challenge.Among the research fields of program synthesis,Programming by Examples(PBE),also known as Inductive Synthesis,uses user-provided input and output examples as the specification for synthesizing programs,and is used in many fields such as data wrangling and code repair because of its simplicity and ease of use.The current approach to solving PBE problems is to search for the target program in the domain-specific programming language space using the input and output examples as constraints.On the one hand,the search space of the programming language is huge,so how to locate the target program efficiently is an important research work to solve the PBE problem.On the other hand,PBE problems usually require the user to provide as few input-output examples as possible,which poses a challenge to automatically synthesize programs that meet the user's expectations.In this thesis,we analyze the above-mentioned challenges faced by the PBE problem,mainly including the poor scalability of program synthesis due to the limitations existing in the input-output examples,and the ambiguity of the input-output examples leading to the non-uniqueness of the synthesized programs.And on this basis,we propose a neural-guided program synthesis method for functional language.The method achieves the synthesis of functional language programs through a pre-trained neural network model guiding the symbolic system mini Kanren to perform deductive search.The functional programming paradigm is currently supported by several mainstream high-level languages due to its advantages of safety,simplicity and modularity.In addition,it is also gradually being used in project development for blockchain platforms.The main contributions of this thesis include:1.We propose an offline supervised learning approach for training recurrent neural network models used in neural-guided synthesis,and devise some simple and effective strategies to generate high-quality datasets to ensure the accuracy of model training.2.We propose several strategies to enrich the embedding representation of model features by encoding the extra information of partial programs and state trees beside relational constraints,to make the neural network model more accurate in predicting the search path.3.We construct a relational constraint interpreter for recursive programs based on three commonly used higher-order combinators.The interpreter enables the program synthesis system proposed in this thesis to solve some challenging recursive program synthesis tasks.4.We conduct an exhaustive experimental evaluation of the performance of the proposed program synthesis system and a more comprehensive comparison with some related state-of-the-art inductive synthesizers.The experimental results show that the proposed program synthesis system performs well in both recursive and non-recursive program synthesis,and has a performance comparable to the state-of-the-art synthesizers in some aspects.