Evoperl  --  Lithium GP Toolkit  --  Henry Strickland

Evoperl is an extreme subset of Perl, with roughly the same capabilities
as Lithium4 and Genetic2005 (actually, a little less capable, since it
doesn't have subroutines and they do).

Programs are generated from a grammar at the top of the file "perl.tcl".
This includes several forms of Statement Productions (S), Expression
Productions (E), and some GlobalVariable Productions (V).

We generate random Abstract Syntax Trees using these productions.
It is easy to convert from the AST to the actual Perl program.  The Perl
program is needed for execution (we exec /usr/bin/perl (with a ulimit
of 1 CPU second) to execute it.  However we retain the AST form of the
program for the sake of mutation and crossbreeding.

Here's an excerpt from the grammar:

 Produces Name		Args	PerlCode
 -------- ---------     -----   -------------------------

	S assign1	{V E}	{ $1 = $2; }
	S while		{E S}	{ while ( $1 ) { $2 } }
	S sequence1	{E S}	{ $1 ; $2 }
	S putchar	{E}	{ printf "%d ", 255&($1); ++`numout; if (`numout>256) {exit} }

	E 1		{}	1
	E var1		{V}	{ $1 }
	E add		{E E}	{( ($1) + ($2) )}
	E sub		{E E}	{( ($1) - ($2) )}
	E incr		{V}	{( ++($1) )}
	E decr		{V}	{( --($1) )}

	V b		{}	{ `b }
	V c		{}	{ `c }


The first line of the grammar is one way to produce a Statement (S).
It is given the name "assign1", for the sake expressing a grammar.
It requires two subproduction arguments, a Variable (V) and an Expression (E)
(which are in {braces} because Tcl likes it that way).
The final column is the equivalent PerlCode for an assignment statement,
(also written inside {braces}):

			 $1 = $2; 

The dollar variables $1 and $2 are to be filled in with the Perl code
for the arguments: $1 must name a variable, and $2 must be an expression.

Since "$" is used for argument substitution, we use the Funny Backwards Quote (`)
where actual Perl needs a dollar mark.  So the Variable Production named "b"
is written  `b  instead of  `c  -- the  `  will change to  $  .

Here's the grammar simple while loop:

		 (S)
		while
	    /         \
	(E)		(S)
	incr		putchar
	 |		 |
	(V)		(V)
	 b		 b

	
Written PreOrder DepthFirst, it can be expressed linearly as

	while incr b putchar b

and the Perl code it generates looks like this:

	while ( $b ) {  printf "%d ", 255&($b); ++$numout; if ($numout>256) {exit}  }

As an optimization, the final putchar generates a couple of extra Perl
statements to make the program stop after writing 256 numbers, since
that is all that is needed in the current Lithium Toolkit.

When Evoperl is evolved, the linear form of the grammar is used to pick
productions to mutate or crossover.  Only the same kind of production
-- S, E, or V -- will be substituted, so the resulting program will be
syntactically correct Perl.