Functional Program Synthesis
Program synthesis is the process of generating a computer program following a set of specifications, which can be a high-level description of the problem and/or a set of input-output examples.
The synthesis can be modeled as a search problem in which the search space is the set of all the programs valid under a grammar.
As the search space is vast, brute force is usually not viable, and search heuristics, such as genetic programming, also have difficulty navigating it without guidance.
This text presents two novel genetic programming algorithms that synthesize pure, typed, and functional programs: HOTGP and Origami.
HOTGP leverages the knowledge provided by the rich data types associated with the specification and the built-in grammar to constrain the search space and improve the performance of the synthesis.
Its grammar is based on Haskell's standard base library (the synthesized code can be directly compiled using any standard Haskell compiler) and includes support for higher-order functions, $\lambda$-functions, and parametric polymorphism.
Experimental results show that HOTGP is competitive with the state of the art.
Additionally, Origami is an algorithm that tackles the challenge of effectively handling loops and recursion by exploring Recursion Schemes.
The main advantage of writing a program using Recursion Schemes is that the programs are composed of well-defined templates with only a few parts that need to be synthesized.
To highlight the advantages and disadvantages of this approach, we manually solved the entire PSB1 benchmark using recursion schemes, highlighting the parts that should be evolved compared to alternative implementations.
We present preliminary results on a prototype implementation, which show that, once the choice of which recursion scheme is made, the synthesis process can be simplified as each of the missing parts of the template is reduced to simpler functions, which are further constrained by their own input and output types.