# Recent Developments in Program Synthesis with Evolutionary Algorithms

Dominik Sobania1, Dirk Schweim2, Franz Rothlauf3
Johannes Gutenberg University
Mainz, Germany
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The automatic generation of computer programs is one of the main applications
with practical relevance in the field of evolutionary computation. With
program synthesis techniques not only software developers could be supported
in their everyday work but even users without any programming knowledge could
be empowered to automate repetitive tasks and implement their own new
functionality. In recent years, many novel program synthesis approaches based
on evolutionary algorithms have been proposed and evaluated on common
benchmark problems. Therefore, we identify in this work the relevant
evolutionary program synthesis approaches and provide an in-depth analysis of
their performance. The most influential approaches we identify are stack-
based, grammar-guided, as well as linear genetic programming. Further, we find
that these approaches perform well on benchmark problems if there is a simple
mapping from the given input to the correct output. On problems where this
mapping is complex, e.g., if the problem consists of several sub-problems or
requires iteration/recursion for a correct solution, results tend to be worse.
Consequently, for future work, we encourage researchers not only to use a
program’s output for assessing the quality of a solution but also the way
towards a solution (e.g., correctly solved sub-problems).

###### Index Terms:

Program synthesis, Evolutionary algorithms, Genetic programming, Benchmarks

##  I Introduction

Automatic program synthesis differs from the conventional programming of
computer programs primarily in the definition of the specification of the
functionality. While the structures of a programming language, such as control
structures, must be known by the programmer in conventional programming,
automatic program synthesis aims, i.a., to enable also non-programmers to
define new functionality, as natural language descriptions or input/output
examples can be used for specification [1].

In evolutionary computation, especially genetic programming (GP) is known for
the automatic generation of computer programs. For the program specification
and the training process, usually input/output examples are used by GP.
However, combinations of, e.g., natural language descriptions and input/output
examples for the synthesis of programs can also be found in the GP literature
[2]. Since the first GP paper by Cramer in 1985 [3], GP has been applied to
many programming problems including sorting and searching [4], parity [5], and
even quantum computing problems [6]. Often, especially in the older GP
literature, domain-specific languages similar to S-Expressions are used [7,
8]. In recent work, real-world programming languages like C/C++ [9], Java
[10], and above all Python [11, 12] are used with higher frequency.
Nevertheless, also Push [13], a language specially designed for GP and not for
practical software development, has been used regularly in recent years for
program synthesis [14, 15].

However, evaluating the performance and ensuring the comparability of novel
approaches is still challenging in GP. This is true especially for program
synthesis, since the application possibilities are almost unlimited and the
used methods can be very complex. A step towards better comparability has been
made by Helmuth and Spector [16] in 2015 with the general program synthesis
benchmark suite. This benchmark suite consists of 29 problems of different
complexity, is not limited to a specific programming language, and has been
widely used in the literature since its publication. The program synthesis
benchmark suite is therefore well suited as a starting point for our survey
covering the recent developments in program synthesis based on evolutionary
algorithms.

In this work, we identify the currently relevant approaches for program
synthesis with evolutionary algorithms and provide an in-depth analysis of the
performance of the recent approaches on the problems defined in the general
program synthesis benchmark suite. Based on this analysis, we discover the
current challenges of program synthesis and suggest directions for future
research.

For the survey, we considered all papers citing the general program synthesis
benchmark suite. From those 89 papers, we identified 54 in-scope papers which
are studying program synthesis using problems from the benchmark suite. As
main evolutionary approaches, we identified stack-based GP (using mostly Push
as representation language), grammar-guided GP, and linear GP. For the
benchmark problems, we found that most problems from the benchmark suite can
already be solved with evolutionary computation. Only for three problems, no
successful results have yet been reported. However, the success rates
(percentage of runs where a solution was found solving all considered cases
correctly) differ from problem to problem and also depend on the program
synthesis approach used. To assist researchers as well as practitioners in the
development of novel program synthesis techniques, we provide for each
benchmark problem a list of references solving the problem. Thus, for similar
problems (e.g., similar in the used data types or complexity), one can
orientate on the methods from the literature.

⬇

A Python function that calculates the average of a list of numbers.

def average(numbers): total = 0 for number in numbers: total += number return
total/len(numbers)

A Python function that calculates the sum of a list of numbers.

def sum(numbers): total = 0 for number in numbers: total += number

Figure 1: Example of a text completed by GPT-3 using a response length of 64.
The given phrase is printed in bold font and the line breaks correspond to the
output in the GPT-3 playground.

In Sect. II, we present work on recent program synthesis approaches not based
on evolutionary algorithms, to give the reader a broader introduction into the
field. We categorize the presented approaches by the type of the definition of
the user’s intent. Section III describes the methodology used for the survey
in detail and provides some descriptive statistics about the in-scope papers.
In Sect. IV, we present the relevant evolutionary approaches used for program
synthesis identified in the survey. In Sect. V, we analyze the performance of
these approaches on the problems from the general program synthesis benchmark
suite before concluding the paper in Sect. VI.

##  II Definition of User’s Intent

In programming languages, every element has its exactly defined semantics.
However, in automatic program synthesis, we often have to deal with more
ambiguous and incomplete definitions of the user’s intent like, e.g., natural
language descriptions or input/output examples. In this section, we present
recent work from the program synthesis domain using different types of program
specifications. In contrast to the classification by Gulwani [1], we mention
and discuss in this section different approaches for program synthesis which
are possibly suitable to be combined with or to extent evolutionary algorithms
in the future. Furthermore, we focus on approaches that can also be applied by
users with little or even no programming experience.

###  II-A Natural Language Descriptions

For a user, the most intuitive way of defining the required functionality of a
computer program is giving a description in natural language. Consequently,
using natural language descriptions for program specifications is a relevant
area in program synthesis research. For example, Desai et al. [17]
automatically train a dictionary to find a relation between the words in the
given textual description and the available program elements (terminals in the
used grammar). Other work uses methods based on neural networks to process the
natural language input [18, 19].

A recent prominent example, where program synthesis was not the explicitly
intended application but which still obtains surprising results in this
domain, is the large-scale language model GPT-3 proposed by Brown et al. [20].
Figure 1 shows an example of a textual description of a programming task
completed by GPT-3. The given phrase is printed in bold font. The remaining
text (including the presented line breaks) corresponds to the output obtained
in the GPT-3 playground. In the example, the given phrase requests a Python
function that should be able to calculate the average of a given list. GPT-3
did not only complete the given phrase in a reasonable way but also continues
with presenting a useful solution for the problem. After adding the correct
line breaks and indentations, the returned program would be executable in a
Python environment. As we set the response length to 64, GPT-3’s output
continues but the most relevant output was already given in first place.
However, even if the returned program is the one most users would expect for
the given problem, the given phrase still reveals a challenging problem for
program synthesis based on natural language descriptions. The word average is
ambiguous as it could not only refer to the arithmetic mean but also, e.g., to
the harmonic or geometric mean. So the ideal program synthesis approach would
include a dialog system to resolve such ambiguities together with the user.

So in practice, the first applications for general (not domain-specific)
program synthesis will be support systems that help programmers in everyday
software development by making meaningful suggestions. A recent example is
GitHub Copilot111GitHub Copilot: https://copilot.github.com/. which was
trained on a large amount of source code.

###  II-B Input/Output Examples

To define the intended functionality for a computer program with input/output
examples, a user has to provide a set of inputs together with the related pre-
calculated outputs as training data just as for classical supervised machine
learning tasks like regression or classification. So the challenge for a
program synthesis method is to construct a program, as general as possible,
that maps correctly all given inputs to their respective outputs.

As the search space of programs is huge (and must be explored to find a
program that fulfills the input/output examples), we find in the literature
work that presents methods to reduce the search space [21, 22]. An example
where such a program synthesis method based on input/output examples is used
in practice also by non-programmers is Flash Fill [23], a tool integrated in
Microsoft Excel. With Flash Fill, a user can automate repetitive string
transformation tasks (e.g., concatenating or extracting sub-strings) by
providing examples. This synthesis process works quickly and therefore does
not interfere with the daily workflow in Excel.

For further examples and an in-depth introduction to, i.a., program synthesis
based on input/output examples, we refer the reader to the excellent online
material of a program synthesis lecture by Solar-Lezama [24].

###  II-C Other Types of Definition

An approach similar to using input/output examples, but which involves the
programmer more intensively in the process, is sketch-based program synthesis
[25, 26]. Instead of expecting that the program synthesis method generates the
entire source code from scratch, the programmer provides, in addition to a
reference implementation or assertions/unit tests for checking the program’s
correctness, also the unfinished source code of a program containing
placeholders. So the programmer provides the basic structure of the program
(including loops and conditionals) and the synthesizer solves the complex
details to substitute the placeholders.

Another way for users to define their required functionality is to explicitly
demonstrate the specific task by giving a step-by-step instruction from
problem to solution. Here, the task for the synthesizer is to abstract from
the demonstration to provide a general solution that works also in other
situations [27]. An example, where this demonstration principle is combined
with traditional programming is Sikuli [28]. With Sikuli, programmers can
easily interact with existing graphical user interfaces by integrating
screenshots in their source code which makes it comfortable to describe
repetitive tasks.

##  III Methodology and Analysis

The general program synthesis benchmark suite by Helmuth and Spector [16]
contains a curated list of 29 benchmark problems intended for programming
novices. In addition to the problem descriptions, the benchmark suite defines
also how the training and test data sets should be structured, to ensure that
the necessary edge cases are contained in the data sets. The training/test set
definitions are described in more detail in the benchmark suite’s associated
technical report [29]. As problems from the benchmark suite have been widely
used in recent work, the paper is well suited as a starting point for our
survey.

As literature pool, we considered all work citing the benchmark suite paper
[16] or the associated technical report [29]. To find the work citing the
benchmark suite, we used Google Scholar. From this pool, we selected only
research articles and PhD theses written in English which make use of at least
one problem from the benchmark suite.

For the literature pool, we found 89 distinct papers (May 2021) citing the
benchmark suite and/or the associated technical report on Google Scholar. From
these papers, we selected 54 as in-scope papers with regard to the previous
definition. Papers that only cite the benchmark suite as related work without
using one of the benchmark problems were not considered.

Figure 2: Number of published in-scope papers from 2015 to 2020.

Figure 2 shows the number of published in-scope papers per year from 2015 to
2020. In 2015, the two papers defining the program synthesis benchmark suite
and two additional papers were published. After that, the number of
publications increased in each of the following years up to 14 published in-
scope papers in 2020, confirming the relevance of program synthesis in
evolutionary computation and the influence of the benchmark suite.

Figure 3 shows the distribution of the in-scope papers over the scientific
venues. With 27 publications, the Genetic and Evolutionary Computation
Conference (GECCO) is represented most frequently – these include 17
publications in the companion proceedings. The second most frequent venue is
the workshop Genetic Programming Theory & Practice (GPTP) with nine
publications. Furthermore, three PhD theses are also within the scope of this
survey.

Figure 3: Distribution of the in-scope papers over scientific venues.

During the analysis of the in-scope papers, we also identified the three
evolutionary computation approaches for program synthesis used most
frequently: stack-based GP, grammar-guided GP, and linear GP. Figure 4 shows
the distribution of the in-scope papers over the identified program synthesis
approaches. Papers that include only the results from other approaches
(already reported in other papers) are counted only for the group for which
they provided an in-depth analysis and/or performed own experiments. For
stack-based GP, we identified 37 papers where most of them are based on the
stack-based programming language Push as representation language. For grammar-
guided GP, we found 12 papers where mainly Python programs are evolved.
Finally, linear GP is represented by only 5 in-scope papers.

Figure 4: Distribution of the in-scope papers over program synthesis
approaches.

##  IV Program Synthesis Approaches based on Evolutionary Algorithms

During the analysis of the in-scope papers, we identified three main
approaches based on evolutionary algorithms for program synthesis. In this
section, we give an introduction to these approaches and highlight papers with
promising and novel ideas which could be relevant for future program synthesis
research.

###  IV-A Stack-Based GP

In stack-based GP, stacks are used to handle and separate the data from the
program’s instructions. When an instruction is executed, it takes its inputs
from the appropriate stacks. If an instruction’s requirements cannot be
fulfilled by the values on the stacks (e.g., if an instruction’s arity is
larger than the number of values available on the required stacks), then the
instruction is simply skipped [30, 31]. Early work on stack-based GP used only
one stack for numeric values (e.g., for regression problems) [30, 32].
However, for a broader application like general program synthesis, multiple
data types must be supported.

In the papers that are in the scope of this survey, primarily PushGP is used
as stack-based GP approach. PushGP, in turn, is based on the Push programming
language [13] which supports different data types by providing a stack for
each supported data type (e.g, INTEGER, FLOAT, BOOLEAN) as well as for the
program instructions itself (e.g., EXEC) [31].

The structure of a Push program is straightforward as it consists either of an
instruction, a literal, or a combination of both in an arbitrary length.
Furthermore, a Push program may contain brackets, provided that they are used
in a balanced way (same number of opening and closing brackets) [31].

The instructions in Push are all strongly typed and follow a simple naming
convention. An instruction’s name is a combination of the type it uses as
input (the stack from which the arguments are taken) and a phrase describing
what the instruction does. For example, the instruction INTEGER.MIN takes the
top two items from the INTEGER stack and pushes the minimum of them back to
this stack. To change the program flow during run-time (as done by control
structures in common programming languages like Java or Python), Push provides
instructions like EXEC.IF or EXEC.DO*TIMES which operate directly on the EXEC
stack [31].

To describe the execution of a Push program, we give an example using the
Smallest problem from the program synthesis benchmark suite. To solve the
Smallest problem, a program should be found that returns the smallest of four
given integer values [16]. As we already introduced the INTEGER.MIN
instruction, which calculates the minimum of two values, such a program can be
easily constructed by simply nesting the INTEGER.MIN instruction multiple
times.

⬇

((1 2 INTEGER.MIN) (3 4 INTEGER.MIN)

INTEGER.MIN)

Figure 5: Source code of an example Push program solving the Smallest problem.

Figure 5 shows the source code for a Push program that calculates the minimum
of four integer values. The subordinate steps of the program are shown in
brackets. First, the minima of 1 and 2 and then of 3 and 4 are calculated.
After that, the minimum of the two minima is returned. Figure 6 shows how this
works using an EXEC and an INTEGER stack. In the first step, the complete
program (instructions and literals) is pushed to the EXEC stack (step 1). As
the top two elements are literals of type integer, these elements are pushed
to the INTEGER stack since literals from the EXEC stack are always pushed to
their associated stack (step 2). After that, the top element on the EXEC stack
is the instruction INTEGER.MIN which takes the values 1 and 2 (the top two
elements) from the INTEGER stack as input. After the instruction is executed,
it is removed from the EXEC stack and the result ($\mathrm{min}(1,2)=1$) is
pushed to the INTEGER stack (step 3). The next steps are similar to the
previous ones. Again, the literals (values 3 and 4) are pushed to the INTEGER
stack (step 4) and then INTEGER.MIN replaces the top two items with the
resulting value. So on the INTEGER stack are now the values 3 and 1 which are
the results from the previous calculations (step 5). Next, the last
INTEGER.MIN instruction on the EXEC stack takes these intermediate results
(step 5) and replaces them with the result. So lastly, the EXEC stack is empty
and the final result is on the INTEGER stack (step 6).

(1)  (2)

(3)  (4)

(5)  (6)

Figure 6: An example Push program execution using the EXEC and the INTEGER
stack (based on the examples in [33]).

⬇

1<program> ::= def smallest(int1, int2, int3, int4): NEWLINE INDENT int5,
int6, int7 =

2 int(), int(), int() NEWLINE bool1, bool2, bool3 = bool(), bool(), bool()

3 NEWLINE <stmt> return <int>

4<stmt> ::= <stmt><stmt> | <bool_var> = <bool> NEWLINE | <int_var> = <int> NEWLINE |

5 if <bool>: NEWLINE INDENT <stmt> DEDENT | while <bool>: NEWLINE INDENT

6 <stmt> DEDENT

7<int_var> ::= int1 | int2 | int3 | int4 | int5 | int6 | int7

8<int_op> ::= + | - | * | / | %

9<int> ::= <int_var> | <int> <int_op> <int> | min(<int>, <int>) | max(<int>, <int>)

10<bool_var> ::= bool1 | bool2 | bool3

11<bool_op> ::= == | > | < | != | >= | <=

12<bool> ::= True | False | <bool_var> | <bool> <bool_op> <bool> | <int> <bool_op> <int>

Figure 7: A simplified context-free grammar suitable for the Smallest problem.
To keep the example small, the number of functions has been reduced and
numerical values have been omitted in the grammar.

For further illustrative examples (using different instructions and other data
types/stacks), we refer the reader to the slides of one of the recent GECCO
tutorials presenting the fundamentals of Push [33] as well as the online Push
programming language description [34]. Additionally, the online Push
interpreter222Online Push interpreter: https://lspector.github.io/interpush/.
can be used to illustrate the execution of small Push programs.

In standard GP [35], trees are usually used for program representation and
variation as a tree representation is inherent in computer programs in common
programming languages. This is also obvious in the exemplary Push program
presented in Fig. 5. However, tree-based variation operators introduce a bias
into the search as, e.g., the probability that a program element is changed
during variation depends on the element’s position in the tree [36].
Consequently, to enable the use of more uniform variation operators for
program synthesis, Helmuth et al. [36] introduced Plush (Linear Push) which is
based on linear genomes. With Plush, the variation operators are applied to
the linear genomes but before evaluation, the program is translated to a
standard Push program. To express a program’s structure, Plush uses so-called
epigenetic markers which are used during the translation process. Another
linear genome representation used in the literature is Plushi, introduced by
Pantridge and Spector [37], which uses a similar strategy to describe a
program’s structure. Also in terms of the achieved success rates, Plush and
Plushi perform similar for program synthesis when used with PushGP [38].

Based on linear genomes, also a new mutation operator has been introduced:
Uniform Mutation by Addition and Deletion (UMAD) [39]. In contrast to
classical mutation operators (like sub-tree mutation) which always replace
existing code blocks, UMAD adds code to the existing program instead of
replacing it and randomly deletes code items in a second step. This means that
a program can be supplemented or changed in several places without simply
replacing large parts of the program. As the success rates could be notably
improved with UMAD on several benchmark problems, it became the quasi-standard
mutation operator in PushGP for program synthesis (i.a., it is used in [40],
[41], and [42]).

In addition to representation and variation, also the selection of favorable
individuals is substantial for the success of a program synthesis method based
on evolutionary computation. Common selection methods like tournament
selection are based on a fitness function which, in the program synthesis
domain, combines the error achieved on the training cases. The disadvantage
here is that the structural information of the training data is lost due to
the compression to a single fitness value [43]. Contrary, with lexicase
selection [44, 45], the information of the individual training cases is used.
For the selection of a solution, the training cases are shuffled and every
solution in the population is evaluated on the first one. Only the solutions
with the exact lowest error are kept and tested on the next training case.
This procedure continues until either all training cases have been used for
evaluation or only one single solution is left. If there is still more than
one solution, a random solution of the remaining ones is selected, otherwise
the last remaining solution is the selected one.

Using PushGP, lexicase selection variants have been in recent work often
compared to other selection methods (e.g., tournament selection) and achieved
best success rates on many program synthesis benchmark problems [16, 29, 46,
47, 48, 49, 50, 51, 52, 53, 45].

In summary, stack-based GP has made a lot of progress in the past few years.
However, a weakness of approaches like PushGP, is the used representation
language (Push), as it is not relevant in practical software development. An
encouraging counterexample is the work by Pantridge and Spector [54]
presenting Code Building GP. Although the approach is based on stack-based
principles, the authors demonstrate that simple Python code can also be
generated. For future research, we therefore suggest to focus more on the
generation of code in practically relevant programming languages, so that
programmers in real-world software development can also benefit from the
success achieved by stack-based approaches for program synthesis.

###  IV-B Grammar-Guided GP

With grammar-guided GP approaches [55, 56], programs can be evolved in a
programming language relevant in real-world software development (e.g.,
Python) in a relatively simple manner. Using a context-free grammar, elements
like functions, variable assignments, and control structures can be easily
supported.

Figure 7 shows an example context-free grammar supporting Python functions,
where the non-terminals are shown in angle brackets (e.g., <program>) and
choices are separated by the pipe symbol. To keep the example grammar small,
it supports only a few functions/operators and individual numeric values have
been omitted in the grammar. However, the grammar is still expressive enough
to support a solution for the Smallest problem from the benchmark suite
similar to the example presented for Push (see Figs. 5 and 6). The first
production rule (lines 1-3) defines the function’s signature, the body
(<stmt>), the return type (<int>), and the initialization for the supported
variables. The second production rule (lines 4-6) defines variable
assignments, as well as control structures (if and while). In order to enable
functions with any number of code lines, the first choice allows to double the
non-terminal <stmt> which can be repeated as often as needed to generate the
desired number of code lines. To define code blocks as well as code lines and
to support the indentation style of the Python programming language, the
grammar contains NEWLINE, INDENT, and DEDENT markers just as used in the
official Python grammar specification333Python grammar:
https://docs.python.org/3/reference/grammar.html.. These markers are of course
replaced accordingly before a program is evaluated. The remaining production
rules (lines 7-12) provide the supported variables, functions and operators.

⬇

[

12, 25, 30, 42, 20, 0, 80, 15,

26, 16, 2, 92, 17, 44, 11, 34

]

Figure 8: An example GE genome encoding a solution for the Smallest problem.

A well-known grammar-guided GP approach suitable for program synthesis is
grammatical evolution (GE) [57, 58]. For program representation, GE uses a
linear genome consisting of numbers which can then be mapped to the phenotype
(the resulting program) using the context-free grammar. An example genome,
encoding a solution for the Smallest problem by nesting the min() function
multiple times, is given in Fig. 8.

To build a program based on this genome and the grammar in Fig. 7, we start
with the first production rule (lines 1-3). As this rule has only one choice
(no decision needed), no gene of the genome is used. So in the current state,
the phenotype contains two non-terminals: <stmt> and <int>. As we satisfy the
non-terminals always from left to right, we consider <stmt> first. The
production rule for <stmt> (lines 4-6) has five choices and the first gene is
12, so we calculate $12\;\mathrm{mod}\;5=2$ to find the choice which replaces
the non-terminal. As we start to count with zero, we replace <stmt> with
<int_var> = <int> NEWLINE. So the next non-terminal to replace is <int_var>.
As the next gene is 25 and the production rule for <int_var> (line 7) has
seven choices, we calculate $25\;\mathrm{mod}\;7=4$ and replace the non-
terminal which leads to int5 = <int> NEWLINE. In the next step, we replace
<int> with min(<int>, <int>) as the relevant gene is 30 and the production
rule (line 9) has four choices. The next gene (42) nests the second min()
function inside the first one which leads to int5 = min(min(<int>, <int>),
<int>) NEWLINE. With the next four genes (20, 0, 80, and 15), the nested min()
function is filled with variables so the current state is int5 = min(min(int1,
int2), <int>) NEWLINE. With the next gene (26), the third and last min()
function is added and again with the next four genes (16, 2, 92, and 17) the
missing variables are added which leads to int5 = min(min(int1, int2),
min(int3, int4)). Finally, the last non-terminal <int> after the given return
statement is still missing. As the next genome contains the value 44 and the
relevant production rule (line 9) has four choices, we calculate
$44\;\mathrm{mod}\;4=0$ and select <int_var>. After that, we calculate
$11\;\mathrm{mod}\;7=4$ and replace the last non-terminal with int5 as the
production rule (line 7) has seven choices and the current gene is 11. Figure
9 shows the resulting Python source code with replaced markers. Since there
are no open non-terminals in the source code, the remaining genes of the
genome are not used.

⬇

def smallest(int1, int2, int3, int4):

int5, int6, int7 = int(), int(), int()

bool1, bool2, bool3 = bool(), bool(), bool()

int5 = min(min(int1, int2), min(int3, int4))

return int5

Figure 9: Resulting Python function based on the given grammar solving the
Smallest problem.

As GE’s genotype-phenotype mapping uses linear genomes, the standard variation
operators of genetic algorithms can be used [57]. However, the mapping process
is not always successful as it is possible that all genes of the genome are
consumed but the phenotype still contains unresolved non-terminals. Such
invalid solutions are likely if the grammar contains many non-terminals (e.g.,
because of many high-arity functions in the grammar) [59]. In recent work,
Sobania and Rothlauf [60] showed that consecutively applying small mutations
(randomly replacing one gene) to a GE genome, encoding a correct solution for
a program synthesis problem, leads to a high percentage of invalid solutions
after just a few mutation steps.

A possibility to prevent invalid solutions through an unsuccessful genotype-
phenotype mapping is to use a tree representation which is already given by
the grammar’s structure. Hence, tree representations have been often used in
recent work using grammar-guided GP approaches (i.a., they are used in [11],
[61], and [62]).

Additionally, the size of the grammar is also important for the quality of the
grammar-guided GP system, as with an increasing grammar the search space grows
rapidly. To provide small grammars that are still suitable for program
synthesis, Forstenlechner et al. [11] suggested to define grammars for each
data type together with a main grammar covering a program’s basic structure.
These grammars can then be put together according to the modular principle,
e.g., based on the input and output data types defined for the considered
problem. Hemberg et al. [2] incorporated the textual problem descriptions to
optimize their grammar-guided GP approach. For example, they use specific
words in the problem’s description text as an indicator for functions that are
required more likely for a working solution.

Also for grammar-guided GP approaches, the choice of the right selection
method is important for the quality of the found solutions. Just like for the
stack-based approaches (see Sect. IV-A), on average best success rates are
achieved using variants of lexicase selection [11, 63, 62, 64]. However,
recent work shows that for some benchmark problems with a low output
cardinality (especially for problems with a Boolean return value) the
solutions that are found on the training cases often generalize poorly to
unseen test cases. In particular, the generalization rate is low on these
benchmark problems when lexicase selection is used [62]. This is not
surprising, as lexicase selection makes use of the individual training cases
during the selection process. In contrast, for selection methods that are
based on a compressed fitness value (like tournament selection) the fitness
value serves as a built-in regularization technique that makes it difficult to
overfit to individual training cases as the individual performance on certain
training cases is unknown. However, since we also find on average most
successful solutions with lexicase selection, future research should focus
more on improving the generalizability of lexicase to enable an even broader
application of this selection method.

Just like for all program synthesis methods, also for grammar-guided GP
approaches the quality of the generated source code is an important factor for
its practical usage. To actively use grammar-guided GP for program synthesis
in real-world software development projects, human programmers expect the
synthesized source code to be clearly structured, readable, and maintainable.
However, the source code generated by state-of-the-art GP methods strongly
differs from human-generated source code [65]. So in addition to finding
semantically correct programs, a challenge for future GP-based program
synthesis research is it also to generate programs that follow a human-like
coding style as suggested in [65] and [66].

###  IV-C Linear GP and Further Approaches

In the third relevant group of approaches in the in-scope papers, methods
based on linear GP are used to solve problems from the program synthesis
benchmark suite [67, 68, 69, 70, 71]. Similar as in Assembler programming, the
data is stored in registers and the provided functions operate on these
registers. E.g., the value stored in a register can be incremented or
decremented by an Inc or Dec function, respectively, or a value can be
explicitly stored in a specific register with a SetReg function [67]. As small
changes in a genome may easily destroy the connection between functions and
the related registers, Lalejini and Ofria [69] used a tag-based memory in
their linear GP approach. Instead of directly accessing a memory cell by its
index (as in index-based memory), the memory cell with the smallest Hamming
distance compared to a given binary address (e.g., defined in the program) is
selected which makes programs more stable to small changes during evolution.

In addition to the previously mentioned approaches stack-based GP, grammar-
guided GP, and linear GP, we also identified a paper by Lynch et al. [72] that
proposes an approach that could be a relevant direction for future program
synthesis research. The authors use a variational autoencoder [73] to learn
the representation of programs which are sampled using a context-free grammar
definition. After that, they search with an EA in the autoencoder’s latent
space for programs that solve the considered benchmark problem.

TABLE I: In-scope papers reporting successful solutions for problems from the benchmark suite. Benchmark problem |  Stack-based GP |  Grammar-guided GP | Linear GP & other | $\Sigma$
---|---|---|---|---
Number IO |  [16], [29], [74], [48], [39], [75], [76], [40], [42], [54], [38], [77] |  [11], [12], [78], [2], [63], [60], [54] | [69] | 20
Small or Large |  [16], [29], [74], [48], [39], [75], [76], [40], [42], [41], [38] |  [11], [61], [79], [12], [2], [63] | [68] | 18
For Loop Index |  [16], [29], [74], [48], [39], [75], [76], [40], [42], [38] |  [11], [61], [12], [2], [63] |  [68], [69], [70] | 18
Compare String Lengths |  [16], [29], [74], [48], [39], [75], [51], [76], [52], [40], [53], [42], [41], [80], [45], [54], [38] |  [11], [61], [79], [78], [2], [63] | [68] | 24
Double Letters |  [16], [29], [46], [47], [74], [48], [39], [75], [51], [81], [15], [76], [52], [40], [42], [80], [45], [38] |  [2] | - | 19
Collatz Numbers |  - |  - | - | 0
Replace Space with Newline |  [16], [29], [46], [82], [47], [74], [48], [39], [75], [36], [83], [50], [51], [81], [84], [15], [76], [52], [40], [42], [80], [45], [85], [54], [38], [77], [49] |  [12], [63], [54] | - | 30
String Differences |  [40] |  - | - | 1
Even Squares |  [16], [29], [74], [48], [75], [40] |  [11], [61], [2], [63] | - | 10
Wallis Pi |  - |  - | - | 0
String Lengths Backwards |  [16], [29], [46], [82], [47], [74], [48], [39], [75], [50], [81], [15], [76], [52], [40], [42], [80], [45], [38] |  [11], [86], [12], [2], [63] | - | 24
Last Index of Zero |  [16], [29], [74], [48], [39], [75], [50], [51], [76], [52], [40], [53], [42], [41], [80], [45], [38] |  [11], [61], [12], [2], [63], [72] | [72] | 24
Vector Average |  [16], [29], [82], [47], [74], [48], [39], [75], [50], [51], [76], [52], [40], [42], [80], [45], [54], [38], [77] |  [61], [79], [2], [63] | - | 23
Count Odds |  [16], [29], [46], [47], [74], [48], [39], [75], [36], [15], [76], [40], [42], [38] |  [11], [61], [12], [2], [63] | - | 19
Mirror Image |  [16], [29], [47], [74], [48], [39], [75], [50], [51], [76], [52], [40], [42], [80], [45], [85], [38] |  [11], [61], [12], [2], [63] | - | 22
Super Anagrams |  [39], [76], [40], [42], [38] |  [11], [61], [78], [2] | - | 9
Sum of Squares |  [16], [29], [74], [48], [39], [75], [76], [40], [42], [41], [38] |  [11], [61], [79], [12], [2], [63] | - | 17
Vectors Summed |  [16], [29], [74], [48], [39], [75], [76], [40], [42], [38] |  [11], [12], [2], [63], [72] | [72] | 16
X-Word Lines |  [16], [29], [47], [74], [48], [39], [75], [36], [50], [51], [81], [76], [52], [40], [42], [80], [45], [38] |  [63] | - | 19
Pig Latin |  - |  [12], [63] | - | 2
Negative to Zero |  [16], [29], [46], [82], [47], [74], [48], [39], [75], [36], [50], [51], [76], [52], [40], [42], [80], [45], [54], [38], [77] |  [11], [12], [2], [63], [54], [72] | [72] | 28
Scrabble Score |  [16], [29], [74], [48], [39], [75], [51], [76], [52], [40], [42], [80], [45], [38] |  [61], [12], [63] | - | 17
Word Stats |  - |  - | - | 0
Checksum |  [74], [39], [75], [76], [40], [42], [38] |  [2] | - | 8
Digits |  [16], [29], [74], [48], [39], [75], [36] [76], [40], [53], [42], [41], [38] |  [2] | - | 14
Grade |  [16], [29], [74], [48], [39], [75], [40], [42] |  [11], [61], [79], [12], [78], [2], [63], [72] |  [69], [70] | 18
Median |  [16], [29], [74], [48], [39], [75], [76], [40], [87], [42], [54], [38], [77] |  [11], [86], [12], [2], [63], [54], [72] |  [68], [69], [70], [72] | 24
Smallest |  [16], [29], [74], [48], [39], [75], [76], [52], [40], [87], [42], [80], [54], [38], [77] |  [11], [86], [12], [2], [63], [60], [54], [72] |  [68], [69], [70], [72], [67] | 28
Syllables |  [16], [29], [46], [82], [47], [74], [48], [39], [75], [36], [50], [51], [81], [84], [15], [76], [52], [40], [42], [80], [45], [38] |  [12], [2], [63] | - | 25

##  V Benchmark Problems: Status Quo

Over the last decades, the benchmark problems used for program synthesis with
evolutionary algorithms are often very similar (e.g., in terms of complexity)
and related to the problems used today. For example, Krawiec and Swan [88]
searched, i.a., for programs that count the number of zeroes or determine the
maximum value of a stack of integers, Shirakawa et al. [89] used basic
problems like Fibonacci or reversing a list, and Pillay [90] used, as in the
general program synthesis benchmark suite [16], also benchmark problems
suitable for programming lectures. However, due to the different benchmark
problems used in publications, it is difficult to achieve comparability
between different approaches. A first step towards better comparability was
made by Helmuth and Spector [16] with the curation of 29 problems of different
complexity suitable for state-of-the-art program synthesis approaches, as the
suite gives not only exact problem descriptions but also defines how the
training and test data should be structured.

Since the complexity of the problems in the benchmark suite is similar to
real-world problems (as individual functions should be kept small in software
development), methods that are successful on specific benchmark problems can
serve as a blueprint for the development of new methods suitable for similar
problems. Therefore, we present in this section a collection of all papers
that reported to have found successful solutions for certain benchmark
problems. Furthermore, we analyze the reported success rates for each
benchmark problem to determine the difficulty of the problems and discuss
factors that make certain program synthesis problems difficult for methods
based on evolutionary algorithms.

###  V-A A Collection of Successful Program Synthesis Approaches

Most state-of-the-art evolutionary program synthesis approaches focus on
generating solutions at the function-level. Structures above, such as class
hierarchies or the general software architecture, are left to human
programmers. A property of functions that are implemented in real-world
software development is that their structure is kept simple. Regularly, they
consist only of a few lines of code (LOC) and are often limited to a low
number of loops and conditionals, which can be confirmed by analyzing the
source code from software repository hosting services like GitHub [65].
However, the automatic generation of such small programs is still a
challenging task even if the required structure (LOC, number of loops, and
conditionals) for the benchmark problems used in the literature is similar to
the functions implemented in practice. To support researchers and programmers
in developing novel program synthesis approaches, we selected from all in-
scope papers and for every of the 29 benchmark problems a list of papers that
report to have found successful solutions. Table I shows the references to
these papers for every benchmark problem ordered by the used evolutionary
program synthesis approach. In addition, we present for each benchmark problem
the number of assigned papers. The benchmark problems are presented in the
same order as in the benchmark suite paper [16].

We see that there are in-scope papers that report successful solutions for
almost all benchmark problems. Most successes are reported for the Replace
Space with Newline problem with 30 occurrences. With 28, the second most
number of successes are reported for the Negative to Zero and the Smallest
problem. For the problems Collatz Numbers, Wallis Pi, and Word Stats, there is
so far no paper that reports that a working solution has been found.

The distribution of the number of in-scope papers solving individual benchmark
problems offers already a first approximation for the difficulty level of
these problems. Based on the reported successes, we expect the problems for
which so far no successful solutions have been found to be the most difficult
ones. We also expect the problems String Differences, Pig Latin, Checksum, and
Super Anagrams to be challenging, as only a low number of in-scope papers
report to have found successful solutions.

So far, for the other benchmark problems, we cannot make an estimation of
their difficulty level, as Table I contains no information about the exact
success rates. Furthermore, the number of in-scope papers could possibly also
be related to the personal preferences of the respective researchers.
Consequently, we provide in the next part an in-depth analysis of the success
rates achieved on the benchmark problems in the literature.

TABLE II: Median, interquartile-range (IQR), and maximum of the success rates reported by the in-scope papers, as well as the defined input and output types for each problem from the benchmark suite. Furthermore, we mark for each benchmark problem if a successful solution requires iteration or recursion (or a specialized function). Benchmark problem | Success rate | Input types | Output types | Iteration/Recursion
---|---|---|---|---
| Median (IQR) | Maximum |  |  |
Number IO | 96.0 (12.0) | 100.0 |  int, float | float | ✗
Small or Large | 6.0 (7.5) | 92.0 | int | str | ✗
For Loop Index | 40.0 (53.5) | 88.0 |  int, int, int | int[] | ✓
Compare String Lengths | 20.0 (38.75) | 95.0 |  str, str, str | bool | ✓
Double Letters | 1.0 (16.0) | 87.0 | str | str | ✓
Collatz Numbers | 0.0 (0.0) | 0.0 | int | int | ✓
Replace Space with Newline | 51.0 (56.0) | 100.0 | str |  str, int | ✓
String Differences | 0.0 (0.0) | 1.0 |  str, str | str | ✓
Even Squares | 0.0 (1.0) | 15.0 | int | int[] | ✓
Wallis Pi | 0.0 (0.0) | 0.0 | int | float | ✓
String Lengths Backwards | 35.0 (57.0) | 100.0 | str[] | int[] | ✓
Last Index of Zero | 30.0 (40.0) | 96.0 | int[] | int | ✓
Vector Average | 32.5 (72.25) | 100.0 | float[] | float | ✓
Count Odds | 5.0 (10.0) | 22.0 | int[] | int | ✓
Mirror Image | 71.5 (75.0) | 100.0 |  int[], int[] | bool | ✓
Super Anagrams | 2.0 (25.0) | 82.0 |  str, str | bool | ✓
Sum of Squares | 7.0 (12.25) | 41.0 | int | int | ✓
Vectors Summed | 7.5 (18.5) | 93.0 |  int[], int[] | int[] | ✓
X-Word Lines | 6.0 (56.75) | 98.0 |  int, str | str | ✓
Pig Latin | 0.0 (0.0) | 5.0 | str | str | ✓
Negative To Zero | 58.0 (60.0) | 98.0 | int[] | int[] | ✓
Scrabble Score | 4.0 (17.0) | 90.0 | str | int | ✓
Word Stats | 0.0 (0.0) | 0.0 | str |  int[], int, float | ✓
Checksum | 0.0 (1.0) | 56.0 | str | str/char | ✓
Digits | 10.0 (28.0) | 100.0 | int | int[] | ✓
Grade | 23.2 (67.5) | 100.0 |  int, int, int, int, int | str/char | ✗
Median | 62.0 (39.5) | 100.0 |  int, int, int | int | ✗
Smallest | 78.0 (50.0) | 100.0 |  int, int, int, int | int | ✗
Syllables | 12.5 (19.5) | 76.0 | str | int | ✓

###  V-B Analyzing Problem Difficulty

To assess the difficulty of the benchmark problems and to discuss current
challenges in program synthesis based on evolutionary algorithms, we analyze
for each benchmark problem the success rates reported by the in-scope papers.
Here, the success rate denotes the percentage of runs in which a program is
found that works correctly on all considered cases. All in-scope papers that
report the exact success rates in numerical form (e.g., in tables) are taken
into account for the analysis. Success rates that are only reported in
graphical form (e.g., plotted) and therefore cannot be determined exactly are
not included. Results that were re-used in follow-up papers or only cited
(duplicated results) are also not included. Since some of the in-scope papers
do not describe how exactly the success rates are calculated, e.g., whether
they are determined on the training or the test set, the results of all papers
are included (including also the results of papers that explicitly describe
that only the training data is used as for example in [46]) in order to be
able to achieve a consistent evaluation. If a paper reports success rates for
the training and the test set, we use only the results reported for the test
set. We do not expect this to have a significant impact on the overall results
but we should keep in mind that the averaged results may tend to be better
then they really are.

Table II shows the median, the interquartile-range (IQR), and the maximum of
the success rates in percent reported by the in-scope papers for every
benchmark problem. In order to be able to discuss the connection between a
problem’s structure and its difficulty, the table shows also the input and
output types defined for each problem (as used in frameworks like PonyGE2
[91]). Furthermore, we mark for each benchmark problem if a successful
solution requires iteration/recursion or at least a specialized function that
abstracts from the required iteration/recursion (like for example a replace()
function for strings).

As expected, the results show that the benchmark problems for which no or only
a small number of in-scope papers report to have found successful solutions
(see Table I) are among the problems with the lowest median success rates.
Additionally, also for Small Or Large, Double Letters, Even Squares, Count
Odds, Vectors Summed, X-Word Lines, and Scrabble Score, we observe median
success rates below 10. Best median success rates are achieved for Number IO,
Smallest, and Median with 96, 78, and 62, respectively. But where does this
huge difference come from? Why can some benchmark problems be reliably solved
while for other problems solutions are only found by chance? What is the
difference between the easy and the more difficult problems?

It is notable, that for none of the three easiest problems (Number IO,
Smallest, and Median) iteration or recursion is required for a correct
solution. Additionally, an explanation for the high success rates of Number IO
is certainly that the source code of a correct solution is very short since
only two numbers must be added [16]. A driving factor for the high success
rates observed for the Smallest and the Median problem, where a program should
be found that returns the smallest/median value for some given integers [16],
is that the correct output is already a part of the given input values.
Therefore, the input can be mapped directly to the output without any
interference and including any new input value (into the program’s output) is
rewarded with a positive fitness signal. Therefore, such problems are simple
for guided search methods like evolutionary algorithms as a solution can be
build step by step [60]. An example is given in Figs. 5 and 9 which show a
straightforward solution for the Smallest problem where a min() function
accepting two inputs is nested multiple times such that four inputs can be
processed. Whenever a min() function is added in a correct way, the fitness
(or the correct cases if lexicase selection is used) improves and guides the
search to a working solution.

In contrast, for the more difficult problems, a direct mapping from the inputs
to the outputs is not possible as iterative or recursive structures are
required and/or the input types differ from the output types which requires
several intermediary steps in the source code to transform the given input
values. These intermediary steps, like loops (or recursion), several function
calls, or type conversions, are necessary for a correct solution but they
interfere the mapping from the inputs to the outputs. Such complex structures
make problems difficult for most current evolutionary program synthesis
approaches as only the output is used to assess a program and to guide the
search while the program itself is treated like a black box. A first step to
lighten up this black box was made by introducing lexicase selection, as it
considers the individual training cases instead of only a compressed fitness
value that leads to a heavy loss of information [44, 43].

In the next step, research must go beyond the naïve evaluation of the training
cases to assess a program. We need to know what is going on inside a program
to enable proper guided search methods for general program synthesis. This
idea is not new, as already Cramer [3] (in the very first GP paper) considers
the semantics of a program for calculating the fitness value. For example, it
is checked whether initial values have changed or if there are working loops
in the program. However, such simple approaches will not be sufficient to
achieve the goal of general program synthesis, but it illustrates in which
direction researchers must think of in the future when designing novel methods
for program synthesis based on evolutionary algorithms.

(1) Mirror Image (2) Vector Average

Figure 10: Box-plots comparing the success rates from the literature for the
Mirror Image (left) and the Vector Average problem (right) for stack-based GP
and grammar-guided GP.

In addition to the varying performance achieved for different benchmark
problems, Table II often shows also a high variance in the success rates
reported for the same benchmark problems. E.g., for some of the problems the
IQR is even larger than 50. To study this further, we analyze the distribution
of the reported success rates separated by the used approach for the two
benchmark problems with the largest variance, which are Mirror Image and
Vector Average with an IQR of 75 and 72.25, respectively. For the Mirror Image
problem, a synthesizer should find a program that returns true for two given
integer lists if one list is the inverted form of the other one, and for the
Vector Average problem a program should be found that returns the average of a
given list of numbers rounded to four decimal places [16]. Figure 10 shows
box-plots comparing the success rates for the Mirror Image (left) and the
Vector Average problem (right) for stack-based GP and grammar-guided GP.

TABLE III: Program trace showing all variable states of the implementation for the Checksum problem for the input 'ProgSys'. Step |  Line |  input0 |  result0 |  str0 | list0
---|---|---|---|---|---
1 |  2 |  'ProgSys' |  0 |  '' | []
2 |  4 |  'ProgSys' |  0 |  'P' | [80]
3 |  4 |  'ProgSys' |  0 |  'r' | [80, 114]
4 |  4 |  'ProgSys' |  0 |  'o' | [80, 114, 111]
5 |  4 |  'ProgSys' |  0 |  'g' | [80, 114, 111, 103]
6 |  4 |  'ProgSys' |  0 |  'S' | [80, 114, 111, 103, 83]
7 |  4 |  'ProgSys' |  0 |  'y' | [80, 114, 111, 103, 83, 121]
8 |  4 |  'ProgSys' |  0 |  's' | [80, 114, 111, 103, 83, 121, 115]
9 |  5 |  'ProgSys' |  727 |  's' | [80, 114, 111, 103, 83, 121, 115]
10 |  6 |  'ProgSys' |  23 |  's' | [80, 114, 111, 103, 83, 121, 115]
11 |  7 |  'ProgSys' |  55 |  's' | [80, 114, 111, 103, 83, 121, 115]
12 |  8 |  'ProgSys' |  '7' |  's' | [80, 114, 111, 103, 83, 121, 115]

For these two benchmark problems, we see a huge difference in performance
between the stack-based and the grammar-guided GP approaches which influences
the high variance in the results. For the Mirror Image problem, stack-based GP
achieves a median success rate of nearly 100 while the grammar-guided GP
approaches fail most of the time. The results are similar for Vector Average,
where stack-based GP has a median success rate of around 70 and grammar-guided
GP achieves only a median success rate lower than 10. Certainly we cannot
conclude from these two results that stack-based GP generally performs better
than grammar-guided GP, as grammar-guided GP, e.g., performs best on the Pig
Latin problem (see Table I). Nevertheless, it shows that a comparison of
different methods is still challenging despite all the efforts made in the
benchmark suite as small differences in program synthesis approaches may lead
to huge differences in performance. For example, program synthesis approaches
often considerably differ with regard to the supported functions and
structures which is problematic as the choice of the right functions has a
huge impact on the problem solving performance. Forstenlechner et al. [12]
already made the point that by adding specialized functions, a benchmark
problem may become quite easy. For example, adding Python’s reverse(),
round(), and sum() functions to a grammar would turn Mirror Image and Vector
Average into simple problems. However, the quality of a program synthesis
approach that finds working solutions without such specialized functions
should be rated higher, as such an approach must be able to construct complex
structures such as loops and conditionals which is more valuable in practice.
For future research, we recommend not only to provide the used grammar (or
function set), but also making sure that the range of the used functions is
similar when comparing different methods. In addition, we recommend not to
search explicitly for specialized functions which make a solution for the
benchmark problems simple, but to strive for more general program synthesis
methods. The recently published expansion of the benchmark suite [92] may also
help to achieve this goal, as we expect that a larger number of benchmark
problems will direct the focus of program synthesis research towards
generalizing approaches that work on many different problem types.

###  V-C In-Depth Analysis of a Complex Benchmark Problem

To illustrate the main challenges in program synthesis with evolutionary
algorithms in detail, we consider a complex problem from the benchmark suite
as example. Figure 11 shows an exemplary hand-written Python function
implementing a solution for the Checksum problem where the majority of the
studied approaches fail to find a successful solution (see Table II). The
given example code consumes more LOC than necessary but this allows us to
analyze the code line by line. The Checksum problem consists of several steps.
For a successful solution, a given input string (input0, line 1) is converted
to a list containing the ASCII value for every character of the input string
(line 3-4). Then, the list is summed (line 5) and the resulting sum is taken
modulo 64 (line 6). Finally, the ASCII value of the space character is added
(line 7) and then the temporary value is converted back to a character (line
8) before the result is returned (result0, line 9) [16].

⬇

1def checksum(input0):

2 result0, str0, list0 = 0, ”, []

3 for str0 in input0:

4 list0.append(ord(str0))

5 result0 = sum(list0)

6 result0 %= 64

7 result0 += ord(’␣’)

8 result0 = chr(result0)

9 return result0

Figure 11: Reference implementation in Python for the Checksum problem.

It is not surprising that this program synthesis problem is quite challenging
for evolutionary algorithms as it consists of many individual sub-problems.
For a given set of input/output examples, we would not even expect to get a
correct solution from an experienced human programmer as without additional
information it is nearly impossible to identify the process required to map
the input to a correct output.

In order to illustrate the program flow for a specific example input, Table
III presents a program trace showing all variable states of the reference
implementation for the Checksum problem (Fig. 11) for the input 'ProgSys'. We
see that several differently typed variables have to match exactly such that a
correct result can be returned. Additionally, it is noticeable that it is not
possible to assess the quality of the program based on the variable states in
the first eleven execution steps. In the first eight execution steps the
variable result0 = 0 which gives us no information about already correctly
solved sub-problems. Also the integer values in steps 9-11 for input0 give us
no information as we only have input/output examples (where the known output
is a character) for training and during the evolutionary search we cannot see
what happens inside the program. This is problematic as sub-problems that have
already been solved correctly may be lost again during a continued search.

However, with the current evolutionary search strategies a guided search for
solutions to problems like the Checksum problem is not possible as they belong
to the class of needle-in-a-haystack problems where finding a correct solution
is strongly influenced by chance [60]. Consequently, we recommend to focus
research on uncovering these hidden sub-problems such that solutions can be
generated step by step during evolution. A software development method that
may be suitable for a combination with evolutionary algorithms is test-driven
development [93], where the software tests and the functional code are
developed in parallel and large problems are regularly divided into several
smaller sub-problems. Using this approach, program synthesis could be a real
support for programmers in practice, since only the tests for the sub-problems
have to be provided.

##  VI Conclusions

The automatic generation of computer programs is one of the applications with
practical relevance in evolutionary computation and especially in the field of
GP. With program synthesis techniques programmers could be supported in
everyday software development and also users without any knowledge in
programming could easily automate their repetitive tasks.

To ensure comparability while studying the performance of novel evolutionary
program synthesis approaches, in recent years usually the general program
synthesis benchmark suite by Helmuth and Spector [16] is used. The benchmark
suite consists of 29 curated introductory programming problems of different
complexity and also defines the structure of the training and test data.

Using the program synthesis benchmark suite as starting point, we identified
in this work the relevant approaches for program synthesis with evolutionary
algorithms and provided an in-depth analysis of the performance of the recent
approaches on the benchmark problems.

As most relevant evolutionary approaches for program synthesis, we identified
and described stack-based GP, grammar-guided GP as well as linear GP. Mainly,
these three approaches differ in their way of representing the solutions,
which results in individually different challenges and opportunities like,
e.g., genotype-phenotype mapping or novel variation operators, respectively.
However, for all three approaches, we see that in future research it will be
necessary to generate programs that are structurally similar to programs
written by human programmers such that the resulting programs can be used in
real-world software.

Further, we analyzed the performance of the recent program synthesis
approaches on the individual benchmark problems reported in the literature. We
found, that the approaches perform well on problems where a correct solution
is small or if a program’s input maps directly to its output. Problems are
difficult for the recent program synthesis approaches if they consist of
several sub-problems, need type changes, or require iterative/recursive
structures which interfere the mapping process from the inputs to the outputs.
In such cases, there exists no strong fitness signal that guides the
evolutionary search towards a correct solution. To overcome these problems, we
encourage researchers to study methods that consider and assess also what
happens inside a program such that useful solutions for sub-problems or
working loops and conditionals are also rewarded instead of only evaluating a
program’s output.

## Acknowledgments

We thank Marcel Hauck for the helpful discussion about large-scale language
models and for providing access to the GPT-3 playground.

## References

  * [1] S. Gulwani, “Dimensions in program synthesis,” in _Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming_ , 2010, pp. 13–24.
  * [2] E. Hemberg, J. Kelly, and U.-M. O’Reilly, “On domain knowledge and novelty to improve program synthesis performance with grammatical evolution,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2019, pp. 1039–1046.
  * [3] N. L. Cramer, “A representation for the adaptive generation of simple sequential programs,” in _proceedings of an International Conference on Genetic Algorithms and the Applications_ , 1985, pp. 183–187.
  * [4] A. Arcuri and X. Yao, “Coevolving programs and unit tests from their specification,” in _Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering_ , 2007, pp. 397–400.
  * [5] T. Yu, “Hierarchical processing for evolving recursive and modular programs using higher-order functions and lambda abstraction,” _Genetic Programming and Evolvable Machines_ , vol. 2, no. 4, pp. 345–380, 2001.
  * [6] L. Spector, _Automatic Quantum Computer Programming: a genetic programming approach_. Springer Science & Business Media, 2004.
  * [7] J. R. Koza, “Automated discovery of detectors and iteration-performing calculations to recognize patterns in protein sequences using genetic programming,” in _IEEE Computer Society Conference on Computer Vision and Pattern Recognition_. Institute of Electrical Engineers Inc (IEEE), 1994, pp. 684–684.
  * [8] J. R. Koza and D. Andre, “Evolution of iteration in genetic programming.” in _Evolutionary Programming_. Citeseer, 1996, pp. 469–478.
  * [9] G. Chennupati, R. M. A. Azad, and C. Ryan, “Synthesis of parallel iterative sorts with multi-core grammatical evolution,” in _Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation_ , 2015, pp. 1059–1066.
  * [10] A. Correia, J. Iyoda, and A. Mota, “Combining model finder and genetic programming into a general purpose automatic program synthesizer,” _Information Processing Letters_ , vol. 154, p. 105866, 2020.
  * [11] S. Forstenlechner, D. Fagan, M. Nicolau, and M. O’Neill, “A grammar design pattern for arbitrary program synthesis problems in genetic programming,” in _European Conference on Genetic Programming_. Springer, 2017, pp. 262–277.
  * [12] S. Forstenlechner, D. Fagan, M. Nicolau, and M. O’Neill, “Extending program synthesis grammars for grammar-guided genetic programming,” in _International Conference on Parallel Problem Solving from Nature_. Springer, 2018, pp. 197–208.
  * [13] L. Spector and A. Robinson, “Genetic programming and autoconstructive evolution with the Push programming language,” _Genetic Programming and Evolvable Machines_ , vol. 3, no. 1, pp. 7–40, 2002.
  * [14] T. Helmuth and L. Spector, “Word count as a traditional programming benchmark problem for genetic programming,” in _Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation_ , 2014, pp. 919–926.
  * [15] H. Ahmad and T. Helmuth, “A comparison of semantic-based initialization methods for genetic programming,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2018, pp. 1878–1881.
  * [16] T. Helmuth and L. Spector, “General program synthesis benchmark suite,” in _Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation_ , 2015, pp. 1039–1046.
  * [17] A. Desai, S. Gulwani, V. Hingorani, N. Jain, A. Karkare, M. Marron, and S. Roy, “Program synthesis using natural language,” in _Proceedings of the 38th International Conference on Software Engineering_ , 2016, pp. 345–356.
  * [18] J. Bednarek, K. Piaskowski, and K. Krawiec, “Ain’t nobody got time for coding: Structure-aware program synthesis from natural language,” _arXiv preprint arXiv:1810.09717_ , 2018.
  * [19] K. Chen, Q. Huang, H. Palangi, P. Smolensky, K. Forbus, and J. Gao, “Mapping natural-language problems to formal-language solutions using structured neural representations,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 1566–1575.
  * [20] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei, “Language models are few-shot learners,” in _Advances in Neural Information Processing Systems_ , vol. 33. Curran Associates, Inc., 2020, pp. 1877–1901.
  * [21] A. Albarghouthi, S. Gulwani, and Z. Kincaid, “Recursive program synthesis,” in _International conference on computer aided verification_. Springer, 2013, pp. 934–950.
  * [22] P.-M. Osera and S. Zdancewic, “Type-and-example-directed program synthesis,” in _Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation_ , ser. PLDI ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 619–630.
  * [23] S. Gulwani, J. Hernández-Orallo, E. Kitzelmann, S. H. Muggleton, U. Schmid, and B. Zorn, “Inductive programming meets the real world,” _Communications of the ACM_ , vol. 58, no. 11, pp. 90–99, 2015.
  * [24] A. Solar-Lezama, “Introduction to program synthesis,” _Lecture_ , 2018, https://people.csail.mit.edu/asolar/SynthesisCourse/index.htm (visited: 2021-07-24).
  * [25] A. Solar-Lezama, “The sketching approach to program synthesis,” in _Asian Symposium on Programming Languages and Systems_. Springer, 2009, pp. 4–13.
  * [26] A. Solar-Lezama, “Program sketching,” _International Journal on Software Tools for Technology Transfer_ , vol. 15, no. 5, pp. 475–495, 2013.
  * [27] D. Kurlander, A. Cypher, and D. C. Halbert, _Watch what I do: programming by demonstration_. MIT press, 1993.
  * [28] T. Yeh, T.-H. Chang, and R. C. Miller, “Sikuli: using GUI screenshots for search and automation,” in _Proceedings of the 22nd annual ACM symposium on User interface software and technology_ , 2009, pp. 183–192.
  * [29] T. Helmuth and L. Spector, “Detailed problem descriptions for general program synthesis benchmark suite,” _School of Computer Science, University of Massachusetts Amherst, Tech. Rep._ , 2015.
  * [30] T. Perkis, “Stack-based genetic programming,” in _Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence_. IEEE, 1994, pp. 148–153.
  * [31] L. Spector, J. Klein, and M. Keijzer, “The Push3 execution stack and the evolution of control,” in _Proceedings of the 7th annual conference on Genetic and evolutionary computation_ , 2005, pp. 1689–1696.
  * [32] K. Stoffel and L. Spector, “High-performance, parallel, stack-based genetic programming,” _Genetic Programming_ , pp. 224–229, 1996.
  * [33] L. Spector, N. F. McPhee, L. Spector, D. M. Clark, I. Lindsay, B. Barr, and J. Klein, “Push: genetic programming for finite algebras,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2019, pp. 1175–1196.
  * [34] L. Spector, C. Perry, J. Klein, and M. Keijzer, “Push 3.0 programming language description,” _Technical Report_ , 2004,
http://faculty.hampshire.edu/lspector/push3-description.html
(visited: 2021-06-29).

  * [35] J. R. Koza and J. R. Koza, _Genetic programming: on the programming of computers by means of natural selection_. MIT press, 1992, vol. 1.
  * [36] T. Helmuth, L. Spector, N. F. McPhee, and S. Shanabrook, “Linear genomes for structured programs,” in _Genetic Programming Theory and Practice XIV_. Springer, 2018, pp. 85–100.
  * [37] E. Pantridge and L. Spector, “Plushi: an embeddable, language agnostic, push interpreter,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2018, pp. 1379–1385.
  * [38] E. Pantridge, T. Helmuth, and L. Spector, “Comparison of linear genome representations for software synthesis,” in _Genetic Programming Theory and Practice XVII_. Springer, 2020, pp. 255–274.
  * [39] T. Helmuth, N. F. McPhee, and L. Spector, “Program synthesis using uniform mutation by addition and deletion,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2018, pp. 1127–1134.
  * [40] T. Helmuth and L. Spector, “Explaining and exploiting the advantages of down-sampled lexicase selection,” in _Artificial Life Conference Proceedings_. MIT Press, 2020, pp. 341–349.
  * [41] A. K. Saini and L. Spector, “Why and when are loops useful in genetic programming?” in _Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion_ , 2020, pp. 247–248.
  * [42] T. Helmuth, E. Pantridge, G. Woolson, and L. Spector, “Genetic source sensitivity and transfer learning in genetic programming,” in _Artificial Life Conference Proceedings_. MIT Press, 2020, pp. 303–311.
  * [43] K. Krawiec, _Behavioral program synthesis with genetic programming_. Springer, 2016, vol. 618.
  * [44] L. Spector, “Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report,” in _Proceedings of the 14th annual conference companion on Genetic and evolutionary computation_ , 2012, pp. 401–408.
  * [45] T. Helmuth, E. Pantridge, and L. Spector, “On the importance of specialists for lexicase selection,” _Genetic Programming and Evolvable Machines_ , vol. 21, no. 3, pp. 349–373, 2020.
  * [46] T. Helmuth, N. F. McPhee, and L. Spector, “Lexicase selection for program synthesis: a diversity analysis,” in _Genetic Programming Theory and Practice XIII_. Springer, 2016, pp. 151–167.
  * [47] T. Helmuth, N. F. McPhee, and L. Spector, “The impact of hyperselection on lexicase selection,” in _Proceedings of the Genetic and Evolutionary Computation Conference 2016_ , 2016, pp. 717–724.
  * [48] T. Helmuth, “General program synthesis from examples using genetic programming with parent selection based on random lexicographic orderings of test cases,” 2015.
  * [49] N. F. McPhee, D. Donatucci, and T. Helmuth, “Using graph databases to explore the dynamics of genetic programming runs,” in _Genetic programming theory and practice XIII_. Springer, 2016, pp. 185–201.
  * [50] T. Helmuth, E. Pantridge, and L. Spector, “Lexicase selection of specialists,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2019, pp. 1030–1038.
  * [51] L. Jundt and T. Helmuth, “Comparing and combining lexicase selection and novelty search,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2019, pp. 1047–1055.
  * [52] T. Helmuth and A. Abdelhady, “Benchmarking parent selection for program synthesis by genetic programming,” in _Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion_ , 2020, pp. 237–238.
  * [53] A. K. Saini and L. Spector, “Effect of parent selection methods on modularity,” in _European Conference on Genetic Programming (Part of EvoStar)_. Springer, 2020, pp. 184–194.
  * [54] E. Pantridge and L. Spector, “Code building genetic programming,” in _Proceedings of the 2020 Genetic and Evolutionary Computation Conference_ , 2020, pp. 994–1002.
  * [55] P. A. Whigham, “Grammatically-based genetic programming,” in _Proceedings of the workshop on genetic programming: from theory to real-world applications_ , vol. 16, no. 3, 1995, pp. 33–41.
  * [56] S. Forstenlechner, M. Nicolau, D. Fagan, and M. O’Neill, “Grammar design for derivation tree based genetic programming systems,” in _European Conference on Genetic Programming_. Springer, 2016, pp. 199–214.
  * [57] C. Ryan, J. J. Collins, and M. O. Neill, “Grammatical evolution: Evolving programs for an arbitrary language,” in _European Conference on Genetic Programming_. Springer, 1998, pp. 83–96.
  * [58] M. O’Neill and C. Ryan, “Grammatical evolution,” _IEEE Transactions on Evolutionary Computation_ , vol. 5, no. 4, pp. 349–358, 2001.
  * [59] D. Schweim, A. Thorhauer, and F. Rothlauf, “On the non-uniform redundancy of representations for grammatical evolution: the influence of grammars,” in _Handbook of Grammatical Evolution_. Springer, 2018, pp. 55–78.
  * [60] D. Sobania and F. Rothlauf, “Challenges of program synthesis with grammatical evolution,” in _European Conference on Genetic Programming (Part of EvoStar)_. Springer, 2020, pp. 211–227.
  * [61] S. Forstenlechner, D. Fagan, M. Nicolau, and M. O’Neill, “Towards understanding and refining the general program synthesis benchmark suite with genetic programming,” in _2018 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, 2018.
  * [62] D. Sobania, “On the generalizability of programs synthesized by grammar-guided genetic programming.” in _EuroGP_ , 2021, pp. 130–145.
  * [63] S. Forstenlechner, “Program synthesis with grammars and semantics in genetic programming,” _Ph. D. dissertation_ , 2019.
  * [64] D. Sobania and F. Rothlauf, “A generalizability measure for program synthesis with genetic programming,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2021, pp. 822–829.
  * [65] D. Sobania and F. Rothlauf, “Teaching GP to program like a human software developer: using perplexity pressure to guide program synthesis approaches,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2019, pp. 1065–1074.
  * [66] D. Schweim, E. Hemberg, D. Sobania, U.-M. O’Reilly, and F. Rothlauf, “Using knowledge of human-generated code to bias the search in program synthesis with grammatical evolution,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2021, pp. 331–332.
  * [67] E. Dolson, A. Lalejini, and C. Ofria, “Exploring genetic programming systems with MAP-Elites,” in _Genetic Programming Theory and Practice XVI_. Springer, 2019, pp. 1–16.
  * [68] J. G. Hernandez, A. Lalejini, E. Dolson, and C. Ofria, “Random subsampling improves performance in lexicase selection,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2019, pp. 2028–2031.
  * [69] A. Lalejini and C. Ofria, “Tag-accessed memory for genetic programming,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2019, pp. 346–347.
  * [70] A. J. Ferguson, J. G. Hernandez, D. Junghans, A. Lalejini, E. Dolson, and C. Ofria, “Characterizing the effects of random subsampling on lexicase selection,” in _Genetic Programming Theory and Practice XVII_. Springer, 2020, pp. 1–23.
  * [71] E. L. Dolson, _On the Constructive Power of Ecology in Open-Ended Evolving Systems_. Michigan State University, 2019\.
  * [72] D. Lynch, J. McDermott, and M. O’Neill, “Program synthesis in a continuous space using grammars and variational autoencoders,” in _International Conference on Parallel Problem Solving from Nature_. Springer, 2020, pp. 33–47.
  * [73] D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” _arXiv preprint arXiv:1312.6114_ , 2013.
  * [74] T. Helmuth, N. F. McPhee, E. Pantridge, and L. Spector, “Improving generalization of evolved programs through automatic simplification,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2017, pp. 937–944.
  * [75] E. Pantridge, T. Helmuth, N. F. McPhee, and L. Spector, “On the difficulty of benchmarking inductive program synthesis methods,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2017, pp. 1589–1596.
  * [76] T. Helmuth, E. Pantridge, G. Woolson, and L. Spector, “Transfer learning of genetic programming instruction sets,” in _Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion_ , 2020, pp. 241–242.
  * [77] L. Spector, W. La Cava, S. Shanabrook, T. Helmuth, and E. Pantridge, “Relaxations of lexicase parent selection,” in _Genetic Programming Theory and Practice XV_. Springer, 2018, pp. 105–120.
  * [78] S. Forstenlechner, D. Fagan, M. Nicolau, and M. O’Neill, “Semantics-based crossover for program synthesis in genetic programming,” in _International Conference on Artificial Evolution (Evolution Artificielle)_. Springer, 2017, pp. 58–71.
  * [79] S. Forstenlechner, D. Fagan, M. Nicolau, and M. O’Neill, “Towards effective semantic operators for program synthesis in genetic programming,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2018, pp. 1119–1126.
  * [80] T. Helmuth, L. Spector, and E. Pantridge, “Counterexample-driven genetic programming without formal specifications,” in _Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion_ , 2020, pp. 239–240.
  * [81] N. F. McPhee, T. Helmuth, and L. Spector, “Using algorithm configuration tools to optimize genetic programming parameters: A case study,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2017, pp. 243–244.
  * [82] W. La Cava, T. Helmuth, L. Spector, and K. Danai, “Genetic programming with epigenetic local search,” in _Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation_ , 2015, pp. 1055–1062.
  * [83] E. Pantridge and L. Spector, “PyshGP: PushGP in Python,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2017, pp. 1255–1262.
  * [84] S. A. Troise and T. Helmuth, “Lexicase selection with weighted shuffle,” in _Genetic Programming Theory and Practice XV_. Springer, 2018, pp. 89–104.
  * [85] L. Spector and E. Moscovici, “Recent developments in autoconstructive evolution,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2017, pp. 1154–1156.
  * [86] J. Kelly, E. Hemberg, and U.-M. O’Reilly, “Improving genetic programming with novel exploration-exploitation control,” in _European Conference on Genetic Programming_. Springer, 2019, pp. 64–80.
  * [87] J. Deglman, “Summed batch lexicase selection on software synthesis problems,” _Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal_ , vol. 7, no. 1, p. 3, 2020.
  * [88] K. Krawiec and J. Swan, “Pattern-guided genetic programming,” in _Proceedings of the 15th annual conference on Genetic and evolutionary computation_ , 2013, pp. 949–956.
  * [89] S. Shirakawa, S. Ogino, and T. Nagao, “Graph structured program evolution,” in _Proceedings of the 9th annual conference on Genetic and evolutionary computation_ , 2007, pp. 1686–1693.
  * [90] N. Pillay, “A genetic programming system for the induction of iterative solution algorithms to novice procedural programming problems,” in _ACM International Conference Proceeding Series_ , vol. 150, 2005, pp. 66–77.
  * [91] M. Fenton, J. McDermott, D. Fagan, S. Forstenlechner, E. Hemberg, and M. O’Neill, “PonyGE2: Grammatical evolution in Python,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2017, pp. 1194–1201.
  * [92] T. Helmuth and P. Kelly, “PSB2: the second program synthesis benchmark suite,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2021, pp. 785–794.
  * [93] K. Beck, _Test-driven development: by example_. Addison-Wesley Professional, 2003.