3 ms·

There is a good body of research around 'Programming by Demonstration' or 'Programming by Example': https://en.wikipedia.org/wiki/Programming_by_demonstration

There is a good body of research around 'Programming by Demonstration' or 'Programming by Example': https://en.wikipedia.org/wiki/Programming_by_demonstration https://en.wikipedia.org/wiki/Programming_by_demonstration 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-Beach.pdf http://web.media.mit.edu/~lieber/Publications/Wreck-a-Nice-B...

a-priori 10y ago
My hope is that constraining the search space, you'll also solve the 'common sense' problem. I'm constraining it in three ways: 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.

a-priori 10y ago

My hope is that constraining the search space, you'll also solve the 'common sense' problem. I'm constraining it in three ways: 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.