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. Some functional programming languages has the potential of limiting the search space of the programs by exploiting some interesting properties such as function purty, type level information, recursive patterns. In this project we aim at creating an algorithm that generates programs in Haskell, a pure functional programming language, exploiting many useful programming patterns and the type leve information extracted from the program specification.
Desired knowledges: programmin (Haskell), genetic programming