Recently I've been reading "Test-Driven Development by Example" to improve my understanding of how to write tests while developing packages. The book is extremely insightful and even fun to read, and It made me think the following tangent: Could tests be used as a guideline to drive a self-programming system?
A few months ago I was thinking about how to develop a system that could create a program. Genetic Programming as much as I love it, is more commonly used to create functions (insert number A, get number B). My musings is how could we go from functions to more fully featured programs, including control and data structures?
One of the key pieces of an evolutionary computation system is the fitness function, so I was thinking if whether a set of tests could not be used as the fitness function of an evolutionary system. The fitness of a candidate, in this system, would be how many tests the program passed.
Now, the other key piece of an GP system the set of primitives that can be used to generate a program. One simple idea would be to have a set of tokens from a programming language. However, your regular programming language is highly structured, which means that the vast majority of token combinations will simply generate a compilation error. Since a program that generates a compilation error can never pass any tests, this idea would generate a huge number of invalid candidates, too many for your run-of-the-mill GP system.
A long time ago, I remember seeing papers where the authors used machine language directly in their automatic programming generation algorithms. In many machine languages, each instruction is self-contained, which means that a random string of instructions will in principle run (even if the result is garbage). So in principle, a GP system that generates random strings of assembly commands, and evaluates programs based on the number of tests that they pass, might work. We can imagine that limiting the number of commands that the system can use, and limiting the number of registers available might even help, by curtailing the search space.
But is there a better way? While assembly language in theory can do whatever a higher level language can, the higher level abstractions exist for reasons other than simply making it easier for humans to write computer programs. So I started wondering if higher level "computer" languages exist. These languages would allow for structures such as classes to be used, but at the same time have a very permissible sintax, that would not reject random strings of tokens out of hand.
Since it took me all of an hour to think of the above, I'm pretty sure someone must already have done this before. I wonder what the state of the art in this area is.