Program Synthesis with A*

Abstract

Search based synthesis has emerged as a powerful tool in program synthesis, the process of automatically generating implementations for software programs given some form of semantic specification. Search based synthesis involves a search over the space of candidate programs that can be derived from a given grammar. A recently developed new inductive logic programming system called Brute demonstrates how the introduction of example-dependent loss functions can dramatically improve the effectiveness of the search.
However, as problem sizes grow its performance drops and at the same time Brute produces programs that are not optimally concise. To overcome this problem, we develop an alternative to Brute that uses A* search and we make it available in an imperative setting (Python). We study to what extent A* search can aid the synthesis of highly accurate and more concise programs in a shorter amount of time using several bench-marking problems, i.e. string manipulation, robot planning and pixel art. We initially find A* to have a higher accuracy. However, when we introduce the use of a new improved heuristic both methods end up with an equally high performance. These results emphasize the importance of the choice of heuristic and that both methods excel in solving distinct problems and can therefore complement each other.