Difference between revisions of "GED"

From Makers Local 256
Jump to: navigation, search
m (minor edit)
(added some sample code and better progress information to GED project page)
Line 5: Line 5:
 
== Progress ==
 
== 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. (Sorry for the jargon. I'll add some resource links later.)
+
* BNF specification pretty much works.
 +
* Program generation from genome works.
  
−
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.
+
== Todo ==
 +
 
 +
* Add the ability to specify the probability for the different BNF forms.
 +
* Add identifier scoping to BNF library.
 +
* Add mutation functions for genomes.
 +
 
 +
More to be determined as I go.
 +
 
 +
== Samples ==
 +
 
 +
GED is still early in its development, but here is the BNF for a simple expression generator as used in code. Yes, I know one of the expression forms is repeated. This is necessary to keep the the average recursion depth low until I make it possible to explicitly give probabilities.
 +
 
 +
<pre>auto preop = new Nonterminal();
 +
auto op = new Nonterminal();
 +
auto expr = new Nonterminal();
 +
expr  (expr ) ( op  ) (expr )                ;
 +
expr  ( "(" ) (expr ) ( op  ) (expr ) ( ")" ) ;
 +
expr  (preop) ( "(" ) (expr ) ( ")" )        ;
 +
expr  ( "x" )                                ;
 +
expr  ( "x" )                                ;
 +
expr  ( "x" )                                ;
 +
op    ( "+" )                                ;
 +
op    ( "-" )                                ;
 +
op    ( "*" )                                ;
 +
op    ( "/" )                                ;
 +
preop ("sin")                                ;
 +
preop ("cos")                                ;
 +
preop ("tan")                                ;
 +
</pre>
 +
 
 +
And here are a few examples of expressions generated using the above BNF in this early version of GED:
 +
 
 +
<pre>cos(cos(x))*x/x</pre>
 +
<pre>sin(tan(x))</pre>
 +
<pre>x+((x+x-(((x-x)*sin(sin(x/x)))+cos(x)/x))/(((x+x/x)+x)*sin(x/(x*x))))/sin(sin(x))</pre>
 +
<pre>((cos(x)*cos(x))+x)</pre>

Revision as of 00:05, 13 March 2007

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

  • BNF specification pretty much works.
  • Program generation from genome works.

Todo

  • Add the ability to specify the probability for the different BNF forms.
  • Add identifier scoping to BNF library.
  • Add mutation functions for genomes.

More to be determined as I go.

Samples

GED is still early in its development, but here is the BNF for a simple expression generator as used in code. Yes, I know one of the expression forms is repeated. This is necessary to keep the the average recursion depth low until I make it possible to explicitly give probabilities. 

auto preop = new Nonterminal();
auto op = new Nonterminal();
auto expr = new Nonterminal();
expr  (expr ) ( op  ) (expr )                 ;
expr  ( "(" ) (expr ) ( op  ) (expr ) ( ")" ) ;
expr  (preop) ( "(" ) (expr ) ( ")" )         ;
expr  ( "x" )                                 ;
expr  ( "x" )                                 ;
expr  ( "x" )                                 ;
op    ( "+" )                                 ;
op    ( "-" )                                 ;
op    ( "*" )                                 ;
op    ( "/" )                                 ;
preop ("sin")                                 ;
preop ("cos")                                 ;
preop ("tan")                                 ;

And here are a few examples of expressions generated using the above BNF in this early version of GED: 

cos(cos(x))*x/x
sin(tan(x))
x+((x+x-(((x-x)*sin(sin(x/x)))+cos(x)/x))/(((x+x/x)+x)*sin(x/(x*x))))/sin(sin(x))
((cos(x)*cos(x))+x)
Retrieved from "https://256.makerslocal.org/wiki/index.php?title=GED&oldid=2297"