Are there programs that iteratively write new programs?

Asked 2010-06-15T18:14:26.997

For about a year I have been thinking about writing a program that writes programs. This would primarily be a playful exercise that might teach me some new concepts. My inspiration came from negentropy and the ability for order to emerge from chaos and new chaos to arise out of order in infinite succession.

To be more specific, the program would start by writing a short random string. If the string compiles the programs will log it for later comparison. If the string does not compile the program will try to rewrite it until it does compile. As more strings (mini 'useless' programs) are logged they can be parsed for similarities and used to generate a grammar. This grammar can then be drawn on to write more strings that have a higher probability of compilation than purely random strings.

This is obviously more than a little silly, but I thought it would be fun to try and grow a program like this. And as a byproduct I get a bunch of unique programs that I can visualize and call art.

I'll probably write this in Ruby due to its simple syntax and dynamic compilation and then I will visualize in processing using ruby-processing.

What I would like to know is:

Is there a name for this type of programming?
What currently exists in this field?
Who are the primary contributors?
BONUS! - In what ways can I procedurally assign value to output programs beyond compiles(y/n)?
I may want to extend the functionality of this program to generate a program based on parameters, but I want the program to define those parameters through running the programs that compile and assigning meaning to the programs output. This question is probably more involved than reasonable for a bonus, but if you can think of a simple way to get something like this done in less than 23 lines or one hyperlink, please toss it into your response.

Edit Report

2 Answers

Have you heard of nanopond? The concept is similar to yours. Every pixel is given a randomly generated string that is run through a compiler. Usually, this doesn't produce any valid program. However, every once in a while, a randomly generated string will somehow be formatted just perfectly to be able to reproduce itself into a neighboring pixel. Soon, it becomes a battle for which program can reproduce better than the other.

What you are talking about is a genetic algorithm, yes, but maximizing one thing and one thing alone: The ability to reproduce.

This is the essential origin to all naturally-occurring negentropic phenomenon: a randomly formed complex entity has the ability to reproduce.

Classical genetic algorithms impose artificial reproduction criteria -- the program that does a job the best is artificially chosen to reproduce.

What you are implying is a sort of computational natural selection. That is, programs will evolve based on their ability to reproduce themselves, and nothing more.

Will this create something useful? Perhaps not. Unless you, maybe, gave your programs access to the internet or some other external API that they can randomly access, and maybe spread over the internet.

Unfortunately, your described system still has somewhat artificial reproduction criteria: the ability to compile.

Because ability to compile = ability to reproduce, you have artificially set your programs to evolve towards compiling.

Compiling what? It doesn't matter, because any program that compiles is as likely to reproduce as the last. Let's say you somehow generated a program that would output the Fibonacci Sequence. Or a program that could beat a chess Grandmaster. Cool! Unfortunately, would it be reproduced? Would it be special?

Not at all; it'd be tr

answered 2010-06-16T01:38:14.030

A different project you could do is work on something that mutates from not passing a certain unit test to passing a unit test.

For example, given an implementation

def add(a,b)
  a
end

You could add a test

assert_equal 3, Foo.new.add(1,2)

and ask your program to try any combination of methods on a within add (for example, a.-(b), a.to_s, a.+(b)) until one of the mutants passes that test and existing tests.

You may want to look at heckle (or Zentest?) for examples of changing code being tested.

answered 2010-06-16T01:01:27.050

Are there programs that iteratively write new programs?

2 Answers

Your Answer