SPLASH 2020
Sun 15 - Sat 21 November 2020 Online Conference
Fri 20 Nov 2020 11:00 - 11:20 at SPLASH - F-3B
Fri 20 Nov 2020 23:00 - 23:20 at SPLASH - F-3B

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 \emph{ahead of time} we show how to bootstrap one \emph{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 \emph{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.

Fri 20 Nov
Times are displayed in time zone: Central Time (US & Canada) change

11:00 - 12:20: F-3BOOPSLA at SPLASH +12h
11:00 - 11:20
Talk
OOPSLA
Shraddha BarkeUniversity of California, San Diego, Hila PelegUniversity of California, San Diego, Nadia PolikarpovaUniversity of California, San Diego
11:20 - 11:40
Talk
OOPSLA
John Peter Campora IIIUniversity of Louisiana at Lafayette, Sheng ChenUniversity of Louisiana at Lafayette
11:40 - 12:00
Talk
OOPSLA
Yu WangDepartment of Computer Science and Technology, Nanjing University, Ke WangVisa Research, Fenjuan GaoNanjing University, Linzhang WangNanjing University
12:00 - 12:20
Talk
OOPSLA
Ifaz KabirUniversity of Alberta, Canada, Yufeng LiUniversity of Waterloo, Ondřej LhotákUniversity of Waterloo
23:00 - 00:20: F-3BOOPSLA at SPLASH
23:00 - 23:20
Talk
OOPSLA
Shraddha BarkeUniversity of California, San Diego, Hila PelegUniversity of California, San Diego, Nadia PolikarpovaUniversity of California, San Diego
23:20 - 23:40
Talk
OOPSLA
John Peter Campora IIIUniversity of Louisiana at Lafayette, Sheng ChenUniversity of Louisiana at Lafayette
23:40 - 00:00
Talk
OOPSLA
Yu WangDepartment of Computer Science and Technology, Nanjing University, Ke WangVisa Research, Fenjuan GaoNanjing University, Linzhang WangNanjing University
00:00 - 00:20
Talk
OOPSLA
Ifaz KabirUniversity of Alberta, Canada, Yufeng LiUniversity of Waterloo, Ondřej LhotákUniversity of Waterloo