Building a Program Synthesizer
homes.cs.washington.edu
Building a Program Synthesizer
1–10 of 27 posts
Re: Building a Program Synthesizer
#2His 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!
Re: Building a Program Synthesizer
#3With these techniques - how complex a program can practically be created in 2018?
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?
Re: Building a Program Synthesizer
#4With these techniques - how complex a program can practically be created in 2018? 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 wit…
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...
Re: Building a Program Synthesizer
#5Once 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.
Re: Building a Program Synthesizer
#6With these techniques - how complex a program can practically be created in 2018? 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 wit…
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...
Re: Building a Program Synthesizer
#7Once 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 insta…
[deleted]
Re: Building a Program Synthesizer
#8With these techniques - how complex a program can practically be created in 2018? 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 wit…
Barliman is pretty neat for filling in functions given a few examples:
Re: Building a Program Synthesizer
#9Once 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 insta…
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.
Re: Building a Program Synthesizer
#10With these techniques - how complex a program can practically be created in 2018? 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 wit…
Incidentally there is a workshop this Sunday at ICML about program synthesis https://uclmr.github.io/nampi/