Program synthesis automatically generates a program that meets a specification. Often, the specification is a small set of input–output examples: the program must produce the required outputs for the given inputs. Rather than writing that program by hand, a search process tries candidate programs until it finds one that fits. section 19.4.4
Figure 19.14 A schematic view of program synthesis: given a program specification and a set of building blocks, a search process assembles the building blocks into candidate programs, which are then tested against the specification. The search continues until a valid program is found.
Follow the loop from specification and building blocks to candidate programs, tests, and a valid result. section 19.4.4
The resemblance to machine learning is useful: both can start with input–output examples and seek a rule that works on new inputs. The crucial difference is what changes. Neural-network training adjusts parameters in an existing program; program synthesis searches for source code, such as a new arrangement of programming-language operators. This discrete search can work with just a few examples, but exploring a vast space of programs is a bottleneck. section 19.4.4 section 20.3
Table 19.2 Machine learning vs. program synthesis
|
Machine learning
|
Program synthesis
|
|---|---|
|
Model: differentiable parametric function
|
Model: graph of operators from a programming language
|
|
Engine: gradient descent
|
Engine: discrete search (such as genetic search)
|
|
Requires a lot of data to produce reliable results
|
Data-efficient; can work with a couple of training examples
|
Compare each approach’s model, search or optimization engine, and stated data needs. section 19.4.4
One possible use is test-time adaptation: given a new task, search through symbolic, verifiable programs instead of relying only on a fixed model. The hoped-for payoff is program-centric abstraction—reusable structures for reasoning and planning—alongside deep learning’s pattern recognition. Program synthesis is therefore proposed as a complement to deep learning, not a replacement. section 19.3.6 section 19.4.5
Today’s hybrid systems illustrate the distinction, not completed program synthesis: AlphaGo combines learned networks with human-coded search, while a self-driving vehicle combines learned perception with a human-designed world model. A proposed next step is to learn the algorithmic parts too, using deep learning to guide program search and libraries of reusable subroutines to assemble models for new tasks. That remains a long-term vision. section 19.4.5 section 19.4.7
