Genetic Algorithm for Program Synthesis
This work addresses the efficiency challenge in program synthesis for developers, but it is incremental as it builds on existing methods.
The authors tackled the problem of large search spaces in deductive program synthesis by improving the search strategy of the SuSLik tool using evolutionary computation, resulting in improved generalization to unforeseen problems.
A deductive program synthesis tool takes a specification as input and derives a program that satisfies the specification. The drawback of this approach is that search spaces for such correct programs tend to be enormous, making it difficult to derive correct programs within a realistic timeout. To speed up such program derivation, we improve the search strategy of a deductive program synthesis tool, SuSLik, using evolutionary computation. Our cross-validation shows that the improvement brought by evolutionary computation generalises to unforeseen problems.