This post is about one of the most simple and straightforward methods of automatic program synthesis: inductive synthesis based on input-output examples specification and brute-force enumerative search.
an alternative approach is to use an SMT solver, finding a valid program that satisfies some constraints (like, program syntax).
Also deep learning has been showing promising results.
But the most impressive results that I have seen are still implemented a brute force search, for example, winning entry for ARC challenge what implemented this way:
https://www.kaggle.com/c/abstraction-and-reasoning-challenge...
thanks for posting this, I've been meaning to start looking into program synthesis as it'll be useful for a program I'm working on at a later date. What kind of search methods are useful for this? Is it just a case of using hill climbing type searches to get closer to a solution or are there more program-synthesis-specific search techniques?
Hill climbing works in some cases, but not very well. eventually it still goes towards full direct search.
One of the interesting approaches, is hierarchical search, where first some smaller subroutines are found, and then they are included as building blocks for more high level complex programs.
Interesting - is the division of the larger program into smaller subroutines done by the search function or is that something you have to do in the process of specifying the problem?
Hill climbing works in some cases, but not very well. eventually it still goes towards full direct search.
One of the interesting approaches, is hierarchical search, where first some smaller subrotines are found, and then they are included as building blocks for more high level complex programs.
This interesting method also brings some interesting bugs. On the last example (find max element in array) the following solution was generated:
function run(input) {
let output = []
for (let i0 in input) {
// block
let n2 = input[i0];
let n1 = n2 - i0;
if(n1 > i0) {
// block
output[0] = n2;
}
}
return output
}
console.log(run([4,3,8,2,5,1]))
console.log(run([1,1,1,1,1,20,0,0]))
// my counter example:
console.log(run([10, 9]))
It seems you still need to inspect the program to check if the program actually does what you expect it to do. This seems much harder to do with the generated code in the article.
Yes, I hope so, first I hope that we will be using more DSLs (with easier ways to design them), and with DSLs program synthesis becomes more tractable.
