Automating computer programming is a long-standing goal in computer science. In spite of significant progress in automated program synthesis in recent times, we remain very far from achieving this goal. Indeed, on almost all everyday programming tasks, a freshman CS major would perform vastly better than today's best program synthesizers.
Two critical components of the gap between human programmers and program synthesizers are that humans learn from experience, i.e., data, and can easily generalize from incomplete problem definitions. In this talk, I will present a new framework for program synthesis, based on Bayesian statistical learning, that aims to eliminate these differences. In our framework, the description of a programming task is seen to consist of a set of "clues" towards a hidden (probabilistic) specification that fully defines the task. Large corpora of real-world programs are used to construct a statistical model that correlates specifications with the form and function of their implementations. The framework can be implemented in a variety of ways, but in particular, through a neural architecture called variational Bayesian encoder-decoders. Inferences made using the framework can be used to guide algorithms for synthesis that search a combinatorial space of programs.
I will show that this data-driven approach can lead to giant leaps in the scope and performance of automated program synthesis. Specifically, I will give a demo of Bayou, a system for Bayesian synthesis of Java programs that goes significantly beyond the state of the art in program synthesis. I will also show that our framework has applications beyond synthesis -- in particular, that it can be used to find bugs in programs without any kind of formal correctness specification.
(Joint work with Vijay Murali and Chris Jermaine.)
Swarat Chaudhuri is an Associate Professor of Computer Science at Rice University. His research interests span formal methods, programming systems, and increasingly, the interface of these areas with artificial intelligence.