Before LLMs became really good at generating code, Genetic Programming was considered the most promising approach for general-purpose program synthesis.

Genetic Algorithms

For those who are not aware, Genetic Algorithms are a family of evolutionary algorithms that use a linear representation, typically an array of integers, encoding a solution. My hello world is the knapsack problem, when you are trying to find the combination of items that maximizes the value of the combination while keeping the total weight of the selected objects. In Genetic Programming, you can represent each combination as an array ([True, False, ..., False]). The algorithm creates a population of combinations and assesses their quality (e.g., -weight if it's overweight and value if not). Genetic Algorithms create a new generation of the population by selecting individuals with a probability proportional to their fitness (quality). First, two parents are selected, and (with a random crossover point), the first half is copied from parent 1 and the second half from parent 2. Then there is a chance that a mutation occurs, and a random position is switched.

Genetic Programming and its representations

Genetic Programming is a cousin¹ of Genetic Algorithms, but each solution is a program, typically represented as a tree. In GeneticEngine, we have added support for multiple representations of programs. In GeneticProgramming you have the genotype (the internal representation where crossover and mutation operate) and the phenotype (the ready-to-run program representation).

class Representation(Generic[g, p]):
    def create_genotype(self, random: RandomSource, **kwargs) -> g:
        ...

    def genotype_to_phenotype(self, genotype: g) -> p:
        ...

    def mutate(self, random: RandomSource, genotype: g, **kwargs) -> g:
        ...

    def crossover(self, random: RandomSource, parent1: g, parent2: g) -> tuple[g, g]:
        ...

The default representation is a Tree-based representation (gp), in which the genotype is an AST of the final program. The genotype and phenotype are exactly the same.

The Grammatical Evolution representation (ge) uses a list of integers to represent a program. Considering a context-free grammar (X -> a | bX | z), the first number will represent which of the tree productions one will choose, the second the next one and so on. So the array [1,1,2,0,0] will correspond to bX after processing the first 1, then bbX after the second 1, then bbz after the last 2. Because there are no more non-terminals to expand, the program is completed. Grammatical Evolution increases the distance between the genetic operators (mutation and crossover) and the problem domain. This is also called the cascading effect or low locality. We also support Dynamic Structured Grammatical Evolution, but the behavior is very similar. Grammatical Evolution is also a really bad name and marketing move for something that is just an indirect representation.

Stack-based representation (gp_stack) is another alternative where each individual is also a list of integers that encode a stack machine. The first stack-based representation I learned was PushGP, which executed the list of integers as operations in a stack-machine that produced the final result of the program. It's author, Lee Spector was especially interested in that combination, but because I wanted the library to be parameterized with the language, I wanted to separate the creation of an AST using a stack machine, from the operational semantics of the language itself. It ended up being very similar to Code Building GP.

Benchmarking representations

The authors of Code Building GP (Ed Pantridge and Thomas Helmuth) were complaining that it was not very efficient in languages with polymorphic types. This was something I have been thinking about for a long time, so I decided to conduct some benchmarking to confirm my suspicions.

I asked my favorite agent that week to write the same programs they used in their paper in aeon, the programming language we are developing in my lab that contains high-order functions, polymorphic types (both à lá Haskell and à lá LiquidHaskell, because it supports Liquid Types as well).

I ran 30 executions for each representation and benchmark pairs. The plot below shows the ratio of the 30 executions that completed until a given time point (xx-axis). I compared tree-based representation (gp), grammatical evolution (ge), stack-based representation (gp_stack) against random_search, which did not use genetic programming at all.

Conclusions

We can conclude two things from these plots: non-stack-based Genetic Programming has the same coarse-grained performance as Random Search. This means that the magic of evolutionary algorithms does not apply to general-purpose programming with high-order functions and polymorphism. The poster child of Genetic Programming is symbolic regression, where GP does outperform random search. GP shines when you can swap the right side of a tree with the left, and with other parts of the program. In practice this means that it works well with a language that has a single type and operators have commutativity and associativity. Which is the case of symbolic regression, where each node of the AST is of type Float, and you get syntactically valid programs when you swap any part of a mathematical expression with another. The same is true for the knapsack problem. But for a general-purpose programming language with lots of types and dependencies between the left-hand side of a program and the right, GP is not better than random search. So it's not a problem of which representation to use.

The second conclusion is that even though the representation will not make it better, it can decrease performance. Grammatical Evolution creates programs starting with the return type and going backwards. (<int> -> <int> + <int> -> x + <int> -> x + 3). Each expansion makes useful progress in creating a valid program. This is not true in stack-based representations. Let us consider push 4; push 3; push x; add; return. This program is exactly the same as the one produced by Grammatical Evolution, except that it push a 4 onto the stack that is never used. Stack-based representations can waste time creating parts of the program that will be discarded. The more complex the language (like aeon), the more probable wasting time is. Therefore, you do not want to use a stack-based representation if you care about performance or speed.

Sorry guys!