  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 any guidance. In this paper we present HOTGP, a new genetic
programming algorithm that synthesizes pure, typed, and functional programs.
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. The 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, when compared to $6$ state-of-the-art algorithms using a standard set of
benchmarks, HOTGP is competitive and capable of synthesizing the correct
programs more frequently than any other of the evaluated algorithms.

Neural and Evolutionary Computing;Artificial Intelligence