Thu 16 Jun 2022 10:40 - 11:00 at Cockatoo - Synthesis I Chair(s): Xinyu Wang

We present a system for inductive program synthesis called DreamCoder, which inputs a corpus of synthesis problems each specified by one or a few examples, and automatically derives a library of program components and a neural search policy that can be used to efficiently solve other similar synthesis problems. The library and search policy bootstrap each other iteratively through a variant of ``wake-sleep'' approximate Bayesian learning. A new refactoring algorithm based on E-graph matching identifies common sub-components across synthesized programs, building a progressively deepening library of abstractions capturing the structure of the input domain. We evaluate on eight domains including classic program synthesis areas and AI tasks such as planning, inverse graphics, and equation discovery. We show that jointly learning the library and neural search policy leads to solving more problems, and solving them more quickly.

Thu 16 Jun

Displayed time zone: Pacific Time (US & Canada) change

10:40 - 12:00
Synthesis ISIGPLAN Track at Cockatoo
Chair(s): Xinyu Wang University of Michigan
10:40
20m
Talk
(PLDI 2021) DreamCoder: Bootstrapping inductive program synthesis with wake-sleep library learning
SIGPLAN Track
Kevin Ellis Cornell University, Lionel Wong Massachusetts Institute of Technology, Maxwell Nye Massachusetts Institute of Technology, Mathias Sablé-Meyer PSL University; Collège de France; NeuroSpin, Lucas Morales Massachusetts Institute of Technology, Luke Hewitt Massachusetts Institute of Technology, Luc Cary Massachusetts Institute of Technology, Armando Solar-Lezama Massachusetts Institute of Technology, Joshua B. Tenenbaum MIT
11:00
20m
Talk
(POPL 2021) egg: Fast and Extensible Equality Saturation
SIGPLAN Track
Max Willsey University of Washington, Chandrakana Nandi Certora, inc., Yisu Remy Wang University of Washington, Oliver Flatt University of Utah, Zachary Tatlock University of Washington, Pavel Panchekha University of Utah
11:20
20m
Talk
(POPL 2022) Relational E-Matching
SIGPLAN Track
Yihong Zhang University of Washington, Yisu Remy Wang University of Washington, Max Willsey University of Washington, Zachary Tatlock University of Washington
11:40
20m
Talk
(OOPSLA 2020) Just-in-Time Learning for Bottom-up Enumerative Synthesis
SIGPLAN Track
Shraddha Barke University of California at San Diego, Hila Peleg Technion, Nadia Polikarpova University of California at San Diego