Rigorous Systems Research Group (RSRG) Seminar

Program synthesis, the problem of automatically discovering programs that implement specified procedural tasks, is a long-standing goal in computer science. The last decade has seen a resurgence of interest in this area. Many new algorithms and applications have been discovered, and tools for program synthesis have begun to make their way into industrial practice.

In an exciting development, recent research has identified a mutually beneficial connection between the areas of program synthesis and deep learning. Two problems with traditional approaches to program synthesis are that they require precise formal specifications, and struggle with searching vast combinatorial spaces of programs. Learning can help with both challenges, allowing synthesis algorithms to interpret ambiguous specifications as well as discover effective search heuristics from experience. Conversely, the discovery of deep learning models can be formulated as the synthesis of differentiable programs. Such a formulation can lead to "high-level" models that are performant, but at the same time more interpretable, verifiable, and transferable than traditional neural networks.

These results open up a new area of "neurosymbolic" program synthesis, where the goal is to learn high-level, programmatic representations of procedural tasks that capture various aspects of cognition, through a process that is itself guided by data-driven learning. In this talk, I will present recent results in this area from my research group and collaborators. I will introduce a class of functional programming languages in which programs have neural and symbolic components, and pose the problem of synthesizing programs in such languages. I will present a "neurosymbolic" synthesis procedure in which effective strategies for discovering programs are automatically learned from data. I will justify these methods using empirical results on programming tasks traditionally studied in the programming language community, as well as tasks from machine learning that combine reasoning, perception and exploration of unknown environments.  The takeaway is that a union of program synthesis and deep learning is possible, a fertile playground for new ideas, and has the potential for significant practical impact.