Searching for a random python program generator

Question

I'm searching for a program that can generate random but valid python programs, similar to the

Random C program generator.

I was trying to do this myself giving random input to the python tokenize.untokenize() function, but of course most of the generated source code was not a valid program I could interpret with eval(). So I would like to know, if you either know a way how to generate random but valid python programs (maybe using the ast module?) or if such a generator already exists.

EDIT: I want to use the random python source code as a starting point for doing genetic programming with python. So I want to have a list of random programs, and then evolve them towards let's say a program that returns "Hello World!".

Hofmann

Answer 1

A google search for python "random program generator" turned up the Random Python Program Generator.

If you want a downloadable script, take a look at pyfuzz.

Methyl

Answer 2

Performing genetic programming to evolve imperative programs is not completely trivial.

It is probably worth some consideration as to what representation you want these programs in, because if you plan to perform crossover/mutation on them then a string representation is probably not ideal. Rather, some sort of parse tree or abstract syntax tree is probably preferable. This will allow your genetic operators to easily manipulate subtrees. Much of the difficulty is then in maintaining the validity of the programs during these operations.

One approach you may like to consider is using a grammar based evolutionary technique such as Grammatical Evolution or Whigham's CFG-GP. You can then provide the language syntax using a BNF grammar, and the programs will be generated to conform to this grammar. You will no doubt be able to find a grammar for Python online which you could adapt. There are some limitations with these techniques, since they generally use context-free grammars, and so cannot represent subtle semantic constraints but there are ways around that if necessary.

A further consideration is whether you really want the whole python language to be available to the evolutionary process. The more features you make available, the larger the search space. In traditional GP the function and terminal sets are specified according to the problem being tackled, and one of the challenges is deciding upon a syntax that is sufficiently expressive without being excessive. Using a separate grammar you will be able to use different grammars for different problems.

Abstractionist

Answer 3

I recommend PushGP. Here is a link to a python class.

Brethren

PushGP generates programs in Push not Python. – Abstractionist