Building a Program Synthesizer(homes.cs.washington.edu)
homes.cs.washington.edu
Building a Program Synthesizer
https://homes.cs.washington.edu/~bornholt/post/building-synthesizer.html
5 comments
10-50 lines of code. You have to pick the right domain. Sumit is doing a lot of work [1] on integrating these ideas into Microsoft's products, e.g., Excel's flash fill. Ras [2] is synthesizing biology models and architecture design. Sanjit, Armando, Emina, Rishabh, are all doing excellent work getting them to scale.
[1] https://www.microsoft.com/en-us/research/video/flash-fill-fl...
[2] https://www.frontiersin.org/articles/10.3389/fbioe.2014.0007...
[1] https://www.microsoft.com/en-us/research/video/flash-fill-fl...
[2] https://www.frontiersin.org/articles/10.3389/fbioe.2014.0007...
The higher-order framework is you!
Most of the recent work in this field seems to be based around the idea of program "sketching", i.e. the programmer sketches a high-level specification, and the algorithms progressively synthesise and evaluate small functions / programs to efficiently implement the sketch.
No doubt machine learning researchers will have something to say about this though...
Most of the recent work in this field seems to be based around the idea of program "sketching", i.e. the programmer sketches a high-level specification, and the algorithms progressively synthesise and evaluate small functions / programs to efficiently implement the sketch.
No doubt machine learning researchers will have something to say about this though...
Incidentally there is a workshop this Sunday at ICML about program synthesis https://uclmr.github.io/nampi/
Barliman is pretty neat for filling in functions given a few examples:
https://youtube.com/watch?v=5vtC7WEN76w
https://youtube.com/watch?v=5vtC7WEN76w
Once upon a time I thought of this and came to a conclusion that in the future software is not written, it is grown.
A big hall with computers, churning on calculations to end up with reusable modules/components for some predescribed purpose. These are combined and eventually larger systems emerge.
The inputs to the calculations were to be descriptions of what the program should do, no details on the "how". For instance, "make an input box for name and snailmail address, with cancel and ok buttons".
It was obviously warp engine level stuff when it comes to feasibility and I thought it would be very far away, like 100 years away... But maybe it is closer than that.
A big hall with computers, churning on calculations to end up with reusable modules/components for some predescribed purpose. These are combined and eventually larger systems emerge.
The inputs to the calculations were to be descriptions of what the program should do, no details on the "how". For instance, "make an input box for name and snailmail address, with cancel and ok buttons".
It was obviously warp engine level stuff when it comes to feasibility and I thought it would be very far away, like 100 years away... But maybe it is closer than that.
This is happening now for mechanical design. They call it generative design. You give inputs (volume/shape, loading cases, other parameters) and then the software iteratively solves for the optimum geometry to meet the goals.
And there is also ``form parameter design'' for ship hull geometry. It is also generative, but perhaps it more typically makes use of deterministic (nonlinear optimization) solvers to generate the geometry itself. (Implementations vary - I show my bias (or just inability to shut up) here as I am trying to finish a PhD in this as we speak)
The main similarity I'm going for in this comment is that the user specifies design constraints and the program generates ship hull shapes that meet those requirements.
Tie generative methods in with solvers for hydrodynamics, motions, structures, stability, etc, and one can conceive of automating the ship hull design spiral, or sections of it anyway. That's not to say that some of this is not already out there in commercial software.
Tie generative methods in with solvers for hydrodynamics, motions, structures, stability, etc, and one can conceive of automating the ship hull design spiral, or sections of it anyway. That's not to say that some of this is not already out there in commercial software.
Example: antennas have been evolved to meet specific special criteria ...
https://en.wikipedia.org/wiki/Evolved_antenna
https://en.wikipedia.org/wiki/Evolved_antenna
[deleted]
In a way, programs have evolved, just very slowly because the evolutionary pressure was from developers, whose speed and effectiveness is a bit random. Most codebases are like little cells, with pockets of non-coding technical debt still influencing the epigenetics of the software's future designs...
[deleted]
In case anybody is reading this post and wants an idea of how to get started with the basics of logic programming (upon which one might build toy constraint solvers) I recommend this:
https://codon.com/hello-declarative-world#programming-paradi...
https://codon.com/hello-declarative-world#programming-paradi...
Of course, being a new old thing, it's not complete without referencing it by it's actual name ... Genetic Programming.
http://www.genetic-programming.com/johnkoza.html
http://www.genetic-programming.com/johnkoza.html
Well, genetic programming is a subset of program synthesis, not a same set.
I’m not sure how the use of an SMT solver could be considered a genetic programming method.
I’m not sure how the use of an SMT solver could be considered a genetic programming method.
Ah, I read the first link in the comments first, which really does imply they're using GP methods.
https://homes.cs.washington.edu/~bornholt/post/synthesis-exp...
However they're using a SMT solver as part of the fitness function of the program.
You know - it needs the correct output, but you need to prevent overfitting, and if you have a formal proof of the program generated you can expend greater effort into reducing its complexity and optimising.
Again, it's an old new thing and possibly going to start getting hyped like neural networks have been of late.
https://homes.cs.washington.edu/~bornholt/post/synthesis-exp...
However they're using a SMT solver as part of the fitness function of the program.
You know - it needs the correct output, but you need to prevent overfitting, and if you have a formal proof of the program generated you can expend greater effort into reducing its complexity and optimising.
Again, it's an old new thing and possibly going to start getting hyped like neural networks have been of late.
I’m sure the term program synthesis precedes the term genetic programming. Neither of these are new things. This (https://www.sri.com/sites/default/files/uploads/publications...) is from 1971, for example. The earliest reference I can find to genetic programming is in the early 90s.
There are plenty of program synthesis techniques (maybe not this one) that do not use fitness functions and get the program straight from a solver. If they have anything written up, I’m sure the related work section would make the context more clear.
As for the accusation of band wagoning, it seems to come straight from the community that has been doing synthesis for years, not the ones that do GP.
There are plenty of program synthesis techniques (maybe not this one) that do not use fitness functions and get the program straight from a solver. If they have anything written up, I’m sure the related work section would make the context more clear.
As for the accusation of band wagoning, it seems to come straight from the community that has been doing synthesis for years, not the ones that do GP.
Ah, I read the first link in the comments first, which really does imply they're using GP methods.
And the evidence to back up your assertion, is where?
Here's mine... (excuse my lack of formatting.)
The synthesis step of stochastic superoptimisation finds the next candidate program P’ by drawing an MCMC sample based on the previous candidate program P. It proposes P’ by randomly applying one of a few mutations to P:
* changing the opcode of a randomly selected instruction
* changing a random operand of a randomly selected instruction
* inserting a new random instruction
* swapping two randomly selected instructions
* deleting an existing randomly selected instruction
The MCMC sampler uses the cost function, which measures how “close” to the target program P’ is and how fast P’ is, to decide whether to accept the candidate P’. A candidate is more likely to be accepted if it is close to the target or very fast. But even programs that are slow or distant from the target have some probability of being accepted, ensuring we explore novel programs
Here's mine... (excuse my lack of formatting.)
The synthesis step of stochastic superoptimisation finds the next candidate program P’ by drawing an MCMC sample based on the previous candidate program P. It proposes P’ by randomly applying one of a few mutations to P:
* changing the opcode of a randomly selected instruction
* changing a random operand of a randomly selected instruction
* inserting a new random instruction
* swapping two randomly selected instructions
* deleting an existing randomly selected instruction
The MCMC sampler uses the cost function, which measures how “close” to the target program P’ is and how fast P’ is, to decide whether to accept the candidate P’. A candidate is more likely to be accepted if it is close to the target or very fast. But even programs that are slow or distant from the target have some probability of being accepted, ensuring we explore novel programs
There's nothing "genetic" about how MCMC works. AFAIK, usually with GP, you keep multiple candidates that you evolve together, which is not the case here (it's much closer to metaheuristics such as Simulated Annealing), e.g.:
let candidate be some random program
while candidate not correct (per your SMT solver):
new_candidate = mutate candidate
let cost be cost of new_candidate
(varies by different techniques;
some just measure the number of bits differ
from expected output of testcases)
if cost is improved:
candidate = new_candidate
else, with some probability (the lower the cost, the higher the prob.):
candidate = new_candidate
That looks to me almost exactly like a (1,1) evolution strategy [1]. Our field frequently has invented almost the same ideas multiple times in different subfields, with different mathematical analogies and different terminology. It's useful to identify these connections, and it helps not to be automatically dismissive of people who seem to be using the "wrong" terminology.
[1] https://en.wikipedia.org/wiki/Evolution_strategy
[1] https://en.wikipedia.org/wiki/Evolution_strategy
Perhaps I should not have been so hasty.
It's just annoying that the implication is that the 'reinventors' haven't done their research. It's almost as bad as my original feeling of "that's an new old thing", and assuming malicious intent/plagiarism.
It's just annoying that the implication is that the 'reinventors' haven't done their research. It's almost as bad as my original feeling of "that's an new old thing", and assuming malicious intent/plagiarism.
That looks very GP-ish, but - as with all GP - the usefulness of the outputs depends on the sophistication of the cost function.
What does "close" mean here? I don't see that explained.
If you're trying to match outputs, then this is just old-fashioned GP with a minor twist - i.e. including speed in the fitness function, which has the potential to find some novel local maxima, which produce outputs that are close to the target AND very fast.
If you're trying to match instruction sequences - then I don't see the point at all.
GP often fails because it runs out of steam before producing a definitively correct solution.
It's easy to design cost/fitness functions that get close but not close enough, and slightly harder to design functions that solve a non-trivial problem some of the time.
It's incredibly hard to design functions that find an answer reliably without getting lost in the problem space.
What does "close" mean here? I don't see that explained.
If you're trying to match outputs, then this is just old-fashioned GP with a minor twist - i.e. including speed in the fitness function, which has the potential to find some novel local maxima, which produce outputs that are close to the target AND very fast.
If you're trying to match instruction sequences - then I don't see the point at all.
GP often fails because it runs out of steam before producing a definitively correct solution.
It's easy to design cost/fitness functions that get close but not close enough, and slightly harder to design functions that solve a non-trivial problem some of the time.
It's incredibly hard to design functions that find an answer reliably without getting lost in the problem space.
+1
His previous post was probably the best overview on program synthesis paradigms (circa 2015):
https://homes.cs.washington.edu/~bornholt/post/synthesis-exp...
It's a much broader overview of the field so read that first if you need an intro!
https://homes.cs.washington.edu/~bornholt/post/synthesis-exp...
It's a much broader overview of the field so read that first if you need an intro!
And if you want a deeper dive after that, here's a 100-page survey of all the techniques, principles, and applications of program synthesis circa 2017:
https://www.microsoft.com/en-us/research/publication/program...
https://www.microsoft.com/en-us/research/publication/program...
A lot of the example programs mentioned feel more like functions (stateless + deterministic mapping of a tuple of inputs to a single output).
In contrast, I think of a 'program' as having a longish lifecycle comprising a stream of inputs and outputs.
Relatedly, I'm not clear how well the approaches detailed here actually would scale with complexity - is this a meaningful building block in building more complex applications? Or is some higher-order framework needed that 'knows' how to apply this in a rich context?