Improving Enumerative Program Synthesis Performance by Extending Grammar from Solutions to Simpler Synthesis Problems
How can such approach be implemented in a synthesis system that cannot benefit from in-advance refinement of the synthesis algorithm parameters
M.B. İnevi (TU Delft - Electrical Engineering, Mathematics and Computer Science)
R.J. Gardos Reid (TU Delft - Algorithmics)
Sebastijan Dumancic (TU Delft - Algorithmics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Program synthesis is an important problem in computer science. One method often employed is enumerative program synthesis, which produces a sequence of programs in the target language until one solves the required input-output examples. This can yield undesirable runtimes for some problems that require complex programs to solve them. This research is about how simpler problem solutions can be used to build a library of useful helper functions and to use it for further synthesis in order to reduce the depth of the enumerative search for more complex problems. Drawing inspiration from the work by Ellis, et al on DreamCoder, this research describes ways of obtaining simpler programs, and extending the grammar using parts of the solutions. Experiments have been performed on the proposed synthesis algorithm, which is implemented using the Herb.jl framework, and results for each part of the synthesis algorithm being replaced by different strategies are provided. Allowing holes in the new grammar substitutions and using smaller size or frequency as their utility has proven superior. There needs to be more work done about the conciseness of the produced programs.