Genetic programming: pygene, pygp, AST, or (gasp) Lisp?

[Erik Max Francis]

John Ladasky wrote:

> Why not do genetic programming directly on Python code?  Maybe my code
> tree data structure is redundant to something which already exists?
> But apparently Python's "_ast" module offers only one-way access -- it
> will generate an AST from a piece of code, but you can't modify an
> AST, and turn it back into executable code?  I would definitely need
> this latter feature.
> 
> ALTERNATELY -- and I don't mention this to start a flame war -- in
> pondering this problem I've noticed the frightening fact that Lisp
> seems set up to handle genetic programming by design.  The s-
> expression syntax IS essentially a parse tree.  Now, I've spent a few
> hours with Lisp so far, and I can't make it do much of anything -- but
> I DO see how Lisp could be helpful.  Still, I'm reluctant to pursue a
> language I don't know, and which I'm finding much harder to grasp than
> any language I've tried before.

The main advantages that Lisp has to a structural language like Python 
are that in Lisp there is no distinction between code and data -- 
they're represented in the same way -- and the syntatic uniformity of 
the language.  Originally the idea with Lisp was that s-expressions were 
a lower-level syntax that a more Algol-like syntax would be translated 
to ... then it became aware that the syntax was actually a benefice in 
many ways, not a hindrance.

> Is there a way to interface Lisp to Python, so that I can do all the
> interface programming in the language I already know best -- and just
> do the genetic parts in Lisp?  I haven't seen exception handling in
> Lisp, a feature I've come to love in Python.  Since it is fairly easy
> for a randomly-generated program to generate illegal output (I already
> know this from my initial experiments in Python), I don't think I can
> live without exception handling.

It is not likely you want to do this.  Genetic programming systems are 
probably best run in a sandbox, for reasons which should be pretty 
reasonable.  The point of genetic programming is to manipulate programs 
into new programs; thus, complicated syntax for those programs only 
increases the chances that either 1. you have to do an awful lot of 
extra work to make sure that you end up with valid programs or 2. you 
end up with an awful lot of syntactically invalid programs.  Both of 
these waste large amounts of processing cycles that you could be 
focusing on creating new, valid programs from old ones.

> I also think that Python has a higher-level understanding of a
> variable's "type" or an object's "class" than Lisp does -- if I'm
> hacking at a parse tree and I want to minimize syntax errors, I need
> to know more than the fact that an element in an expression is an atom
> or a list.

If you're interested in typed genetic programming systems, then you 
might want to check out some of the stack-based genetic programming 
languages like Push or PushGP.  These are in effect a stack-based form 
of Lisp, but which use different data stacks for different types.

> Producing human-readable code from my genetic programming search would
> be a great bonus -- and for me, at this moment, this seems to mean
> Algol-style syntax.  (Sigh.)  But it's not a requirement.

Well, you could always translate s-expressions into m-expressions ...

-- 
Erik Max Francis && max at alcyone.com && http://www.alcyone.com/max/
  San Jose, CA, USA && 37 18 N 121 57 W && AIM, Y!M erikmaxfrancis
   It isn't important to come out on top, what matters is to be the one
    who comes out alive. -- Bertolt Brecht, 1898-1956