https://github.com/michaelmelanson/autocoder
My theory is that by reducing the search space enough, it should be possible for a computer to generate source code to pass unit tests. The key is from a blog post by Robert "Uncle Bob" Martin where he describes his 'Transformation priority premise' as a way of doing code kata exercises. I think this gives the basis for an automated code generation by presenting unit tests one at a time, and searching for transformations to make the tests pass (while not breaking any earlier ones of course). I have no idea if it'll be a practical way to write software, but I think it's an interesting problem to solve. I'm currently working through some kata exercises, producing the list of transformations manually, to make sure it has the vocabulary of transformations it needs.
https://github.com/michaelmelanson/autocoder/blob/master/src...
After that I'll add a search algorithm to find the sequence of transformations automatically. Then we'll see if my theory is right! :)
My vision is that this would be incorporated into an IDE such that you as the programmer write the unit tests, and the IDE works in the background to write the corresponding code to pass them.
From my own experience doing some research into it, I found the lack of 'common sense' to be the biggest stumbling block; it is hard to detect if the program you generated is a nonsensical 'catchall' solution.
Incidentally, this led me to the paper with the best ever title: How to Wreck a Nice Beach You Sing Calm Incense http://web.media.mit.edu/~lieber/Publications/Wreck-a-Nice-B...
1) The solver tries to make the tests pass one at a time: it finds a solution that passes test 1, then one that passes tests 1 and 2, then one that passes tests 1, 2 and 3, and so on. So the human-written unit test suite guides the solution quite directly.
2) The search algorithm will be fairly shallow, somewhere between 2 and 3 steps probably. If it can't find a way to get from tests n to n+1 then it'll throw its hands up and ask you to insert a new test in the middle to help it.
3) Rather than trying arbitrary AST mutations or something, each step will be chosen from a vocabulary of transformations that move the solution from specific to generic -- things like "turn this constant into a variable" or "turn this if statement into a while loop" or things like that -- with simpler transformations preferred over more complicated ones (see the Uncle Bob blog post I mentioned).
In addition to making it computationally tractable, my hunch is that constraining the search like this will also make the solutions similar to what a human would write.