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.
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 subrotines are found, and then they are included as building blocks for more high level complex programs.
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?
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...
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.
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.
32 comments
[ 0.20 ms ] story [ 75.0 ms ] threadFrom my perspective most web development could be replaced by an advanced synthesizing algorithm and a product owner who understands the dsl.
I feel like the majority of web development work these days is just stringing together apis, which could easily be automated.
Coupled with next gen design tools for the front end I predict a huge reduction in development resources required for most projects.