Foundations and Trends® in Programming Languages > Vol 4 > Issue 1-2

Program Synthesis

By Sumit Gulwani, Microsoft Research, USA, sumitg@microsoft.com | Oleksandr Polozov, University of Washington, USA, polozov@cs.washington.edu | Rishabh Singh, Microsoft Research, USA, risin@microsoft.com

 
Suggested Citation
Sumit Gulwani, Oleksandr Polozov and Rishabh Singh (2017), "Program Synthesis", Foundations and Trends® in Programming Languages: Vol. 4: No. 1-2, pp 1-119. http://dx.doi.org/10.1561/2500000010

Publication Date: 11 Jul 2017
© 2017 S. Gulwani, O. Polozov and R. Singh
 
Subjects
Program Synthesis,  Program Transformations and Optimizations,  Domain Specific Languages,  Deep Learning,  Inductive logic programming,  Multimodal interaction,  Interdisciplinary influence: Artificial intelligence and the user interface
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Applications
3. General Principles
4. Enumerative Search
5. Constraint Solving
6. Stochastic Search
7. Programming by Examples
8. Future Work
Acknowledgements
References

Abstract

Program synthesis is the task of automatically finding a program in the underlying programming language that satisfies the user intent expressed in the form of some specification. Since the inception of AI in the 1950s, this problem has been considered the holy grail of Computer Science. Despite inherent challenges in the problem such as ambiguity of user intent and a typically enormous search space of programs, the field of program synthesis has developed many different techniques that enable program synthesis in different real-life application domains. It is now used successfully in software engineering, biological discovery, computeraided education, end-user programming, and data cleaning. In the last decade, several applications of synthesis in the field of programming by examples have been deployed in mass-market industrial products. This survey is a general overview of the state-of-the-art approaches to program synthesis, its applications, and subfields. We discuss the general principles common to all modern synthesis approaches such as syntactic bias, oracle-guided inductive search, and optimization techniques. We then present a literature review covering the four most common state-of-the-art techniques in program synthesis: enumerative search, constraint solving, stochastic search, and deduction-based programming by examples. We conclude with a brief list of future horizons for the field.

DOI:10.1561/2500000010
ISBN: 978-1-68083-292-1
136 pp. $90.00
Buy book (pb)
 
ISBN: 978-1-68083-293-8
136 pp. $260.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Applications
3. General Principles
4. Enumerative Search
5. Constraint Solving
6. Stochastic Search
7. Programming by Examples
Refere8. Future Work
Acknowledgements
References

Program Synthesis

Program synthesis is the task of automatically finding a program in the underlying programming language that satisfies the user intent expressed in the form of some specification. Since the inception of artificial intelligence in the 1950s, this problem has been considered the holy grail of Computer Science. Despite inherent challenges in the problem such as ambiguity of user intent and a typically enormous search space of programs, the field of program synthesis has developed many different techniques that enable program synthesis in different real-life application domains. It is now used successfully in software engineering, biological discovery, compute-raided education, end-user programming, and data cleaning. In the last decade, several applications of synthesis in the field of programming by examples have been deployed in mass-market industrial products.

This monograph is a general overview of the state-of-the-art approaches to program synthesis, its applications, and subfields. It discusses the general principles common to all modern synthesis approaches such as syntactic bias, oracle-guided inductive search, and optimization techniques. We then present a literature review covering the four most common state-of-the-art techniques in program synthesis: enumerative search, constraint solving, stochastic search, and deduction-based programming by examples. It concludes with a brief list of future horizons for the field.

 
PGL-010