GED

Overview

GED is an attempt at grammatical evolution. Grammatical evolution is similar to genetic programming, but it is able to generate code in any arbitrary language. The actual genome representation for a generated program or algorithm is merely a sequence of 8-bit codons. Each codon represents a choice to make in a BNF for the language the final program is to be written and tested in.

Progress

I have a working program generator that uses a given BNF to generate a random program in an arbitrary language. Development so far has been fairly straightforward. My most difficult problem has been coming up with a reasonable way to limit the recursion depth of the function which generates the program from the codon. My solution to the experience is to place a cap on the number of codons (5000 by default) and to make sure that the BNF specifies enough terminators that the number of recursions converges to a number well below that. Right now repition is required in the BNF definition to increase the probability of choosing a terminator, but I intend to be able to numerically choose these probabilities instead.

The next step is going to be the addition of a Symbol type that keeps track of scoped identifiers to be used in languages that have such a concept (most). I am not sure how this will look in the language definition.