Stefan Forstenlechner

Abstract

Program synthesis is an important field that has many use cases like bug fixing, automating repetitive tasks and discovering new algorithms. One way to approach program synthesis tasks is to specify a grammar that defines all possible programs that can be created and using a search algorithm like genetic programming to create a program. Although using grammars has the advantage that created programs are syntactically correct, the grammar has to be defined for each problem tackled.

The focus of this thesis is to introduce a grammar design approach that provides the ability to tackle arbitrary program synthesis problems from input/output examples. The grammars will not be required to be tailored to a specific problem, and in contrast to many existing approaches, the code of the produced programs will be in a programming language used by practitioners. The grammar design approach is studied on a range of program synthesis problems throughout the thesis and shows results that are competitive to state of the art systems.

As the search for programs with genetic programming is often done on the syntactic representation without considering the behaviour or semantics of a program, the introduction of semantic operators for program synthesis will be investigated. While in other problem domains, semantic operators have improved search performance, no such operators are available for the program synthesis domain. A definition of semantics in program synthesis will be provided, and multiple semantic measures and operators will be studied on the basis of this definition. The results show that novel semantic crossover and mutation operators for genetic programming can outperform traditional operators that do not consider semantic information.