Program Synthesis
Program Synthesis
复制标题
DOI：
10.1561/2500000010
复制
发表时间：
2017-01-01
影响因子：
0.4
通讯作者：
Singh, Rishabh
中科院分区：
文献类型：
--
作者：
Gulwani, Sumit;Polozov, Oleksandr;Singh, Rishabh
程序综合是自动在基础编程语言中自动找到一个以某种规范形式表达的用户意图的程序。自1950年代AI成立以来，这个问题被认为是计算机科学的圣杯。尽管问题的含糊不清以及程序的巨大搜索空间，但程序综合领域已经开发了许多不同的技术，这些技术在不同的现实应用程序域中启用程序综合。现在，它成功用于软件工程，生物发现，计算机辅助教育，最终用户编程和数据清洁。在过去的十年中，在大众市场工业产品中已部署了示例编程领域中合成的几种应用程序。这项调查是对程序合成，其应用程序和其应用程序和其应用程序和其应用，其应用和其应用程序的最先进方法的一般概述子场。我们讨论了所有现代合成方法所共有的一般原理，例如句法偏见，甲骨文指导的归纳搜索和优化技术。然后，我们介绍了文献综述，其中涵盖了程序合成中最常见的最新最新技术：枚举搜索，约束解决，随机搜索和基于扣除的编程示例。我们以该领域的未来视野简要列表结束。
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.