A key challenge in program synthesis is the astronomical size of the search
space the synthesizer has to explore. In response to this challenge, recent
work proposed to guide synthesis using learned probabilistic models. Obtaining
such a model, however, might be infeasible for a problem domain where no
high-quality training data is available. In this work we introduce an
alternative approach to guided program synthesis: instead of training a model
ahead of time we show how to bootstrap one just in time, during synthesis, by
learning from partial solutions encountered along the way. To make the best use
of the model, we also propose a new program enumeration algorithm we dub guided
bottom-up search, which extends the efficient bottom-up search with guidance
from probabilistic models.
We implement this approach in a tool called Probe, which targets problems in
the popular syntax-guided synthesis (SyGuS) format. We evaluate Probe on
benchmarks from the literature and show that it achieves significant
performance gains both over unguided bottom-up search and over a
state-of-the-art probability-guided synthesizer, which had been trained on a
corpus of existing solutions. Moreover, we show that these performance gains do
not come at the cost of solution quality: programs generated by Probe are only
slightly more verbose than the shortest solutions and perform no unnecessary
case-splitting.

本文提出了一种新的指导程序综合的方法：在程序综合过程中根据遇到的部分解来学习启动模型，同时提出了一种称之为指导自下而上搜索的程序枚举算法来最大限度地利用模型。这种方法在基准测试中取得了非常显著的性能提升，且所生成的程序与最短解相比几乎一致。