image part 005

Program Synthesis

Program synthesis is the problem of automatically discovering programs from specifications of their intended functionality. Such specifications can take various forms, including noisy input-output examples, desired program trajectories, behavioral constraints written in first-order or temporal logic, and visual or textual descriptions of the program’s goals. Program synthesis cuts across most of our lab’s research. In some cases, we are motivated by the potential of program synthesis to make programming more productive. In other cases, our goal is to synthesize programs that model, and help us understand better, the real world.

In either case, one faces two basic issues. First, a program synthesizer needs to search through a space of programs that is combinatorial and quickly explodes. Second, specifications are often ambiguous or incomplete, and this means that not all programs that meet the specification are interesting. Over the years, we have developed many approaches to these challenges. For example, some of our methods prune a search space of programs using automated deduction techniques. Others guide a discrete search over programs using learned statistical models. Yet others relax the space of programs into a continuous space that can be explored with scalable gradient-based optimization.


Selected Publications

Yeming Wen Rohan Mukherjee, Dipak Chaudhari; Jermaine, Chris

Neural Program Generation Modulo Static Analysis Journal Article

In: Neural Information Processing Systems (NeurIPS), 2021., 2021.

BibTeX

Shah, Ameesh; Zhan, Eric; Sun, Jennifer J.; Verma, Abhinav; Yue, Yisong; Chaudhuri, Swarat

Learning Differentiable Programs with Admissible Neural Heuristics Inproceedings

In: Larochelle, Hugo; Ranzato, Marc'Aurelio; Hadsell, Raia; Balcan, Maria-Florina; Lin, Hsuan-Tien (Ed.): Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.

Links | BibTeX

Verma, Abhinav; Le, Hoang Minh; Yue, Yisong; Chaudhuri, Swarat

Imitation-Projected Programmatic Reinforcement Learning Inproceedings

In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 15726–15737, 2019.

Links | BibTeX

Murali, Vijayaraghavan; Qi, Letao; Chaudhuri, Swarat; Jermaine, Chris

Neural Sketch Learning for Conditional Program Generation Inproceedings

In: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018.

Links | BibTeX

Feser, John K.; Chaudhuri, Swarat; Dillig, Isil

Synthesizing data structure transformations from input-output examples Inproceedings

In: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, OR, USA, June 15-17, 2015, pp. 229–239, 2015.

Links | BibTeX