程序合成研究进展

张银珠 董威 刘斌斌

摘  要： 在软件工程领域中，程序自动合成是一个非常核心的研究方向，并且在软件开发活动如此普及的社会中有望成为未来软件工程变革的核心技术。随着多年该领域的研究发展，已经衍生出了很多种不同的流派与技术路线。本文针对程序合成领域的发展现状与技术研究进展做了综合叙述，并探究目前程序合成领域所面临的挑着与未来一段时间内需要解决的问题。

关键词： 程序合成;搜索排序;程序结构

中图分类号： TP311.51    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.04.005

本文著录格式：张银珠，董威，刘斌斌. 程序合成研究进展[J]. 软件，2019，40（4）：2530

【Abstract】： Automatic program synthesis has become a core research direction in the field of software engineering. And it is expected to become the core technology of future software engineering with software development becoming more and more popular in current society. There exists different schools and technical routes in the research of program synthesis. In this paper， a comprehensive description of the development status and technology progress of program synthesis is given and we also explores the challenges facing the current field of program synthesis and the problems that need to be solved in the future.

【Key words】： Program synthesis; Search and rank; Program structure

0  引言

随着软件工程的发展，软件开发愈加成为互联网以及其他软件相关企业的主要活动。因此软件开发技能成为软件从事企业人员的必备技能，即使在非必需的情况下，掌握基本的软件开发知识，也能够帮助工作人员更好的适应信息化场景的工作及要求。软件开发人员的工作通常是复杂多样并需要重复劳动，他们需要时常搜索并学习不同领域的开发方法，这对开发人员的要求大大提高，并极大增加开发人员的负担，拖累开发工作的进程。为了将软件开发人员从复杂繁重的开发工作中解放出来，程序合成成为未来软件工程的重点研究与投入方向之一。

1  程序合成的概念

程序自动合成又称程序综合技术，旨在围绕用户意图，合成出符合用户需求的软件代码的活动。程序合成的目的是让机器合成出代码，能够减轻程序员的负担，并有望将编程人员将关注点放到软件的高层设计上，而不用花费过多时间在细节实现上。研究人员Sumit Gulwani[1]指出，代码自动生成过程一般分为三个阶段，用户需求的描述，程序搜索空间的表述，设计合适的搜索排序技术。这里每个阶段都涉及到不同的方法，适用于不同的场景，例如用户需求可以利用规约形式描述，也可以用自然语言描述。需求的描述越抽象，进行程序合成越困难。也就是说利用自然语言描述的需求来生成代码面临更多的挑战，包括需要克服自然语言与程序需求之间的差距和程序需求与实际程序代码之间的鸿沟。

2  程序合成的关键要素

程序合成有三个关键要素[1]，用户意图表述，搜索空间描述以及设计合适的搜索技术。用户意图表述有多种方式，逻辑规约，输入输出数据对，程序路径以及自然语言等。该如何选择不同的需求描述取决于具体的任务背景。逻辑规约用来描述程序输入输出间的逻辑关系，可以精确又简明的描述程序所遵循的规范，但是对于用户来说很难写出完整的程序逻辑规约。终端用户通常不如专家的编码水平，因此更倾向于提供自然性的需求描述如自然语言等。搜索空间通常需要在需求符合性和程序合成效率间做一个平衡。一方面程序搜索空间需要足够大到能够囊括用户需求所有可能的程序，另一方面为了提升程序合成的效率，需要采取更有效的搜索方法将搜索空间限定在小的范围内。例如搜索空间可以被限定为所有操作组成空间的一个子集，或者在一个领域特定语言的范围内。搜索技术与排序技术类似，目的是如何更有效的搜索出与需求接近的结果程序等。常见的搜索技术有枚举搜索、基于约束求解的搜索或者两者的结合等等。枚举搜索将所有可能的程序按照某个顺序一一列举，通常效率较低，因此更常见的发方法是在传统的枚举搜索的基础上加上启发式的剪枝方法来提升搜索效率。基于约束求解的搜索通常分为两个过程，约束生成过程和具体求解过程。约束生成过程是将需求解程序搜索空间用逻辑描述其规范并转换成约束的过程，生成约束通常需要对程序可能的控制流以及控制流下行为进行编码。求解约束的过程是在约束创建完成后，在约束所描述的搜索空间内按照某种方式列举可行解的过程，例如可以单纯使用枚举的方法，也可以添加其他的约束来改变枚举的顺序。

3  程序合成的常见方法

程序自动生成分为几种不同的技术路线，他们或利用不同的需求描述语言，或针对不同的适用场景设计不同的搜索算法。从不同的角度来看，程序合成方法可以被划分为不同的类别，如圖1所示。

3.1  从规约选取角度进行分类

如图1所示，从规约选取的角度来看，程序合成可以被分为基于示例（Programming by Examples）、基于框架（Sketch）、基于自然语言以及基于逻辑规约的程序合成方法。

（1）基于示例的程序合成（Programming by Examples）

基于示例的程序合成需要用户提供输入输出示例作为需求描述，例如一个广为人知的应用就是在Excel中的Flash Fill[4，18]功能。用户在表格中填写需求相关的多个输入输出对，在有解的情况下，工具能够有限时间内找出合适的实现代码，如图2所示。

Mehdi Manshadi[9]等提出了使用<输入-输出>测试对和自然语言需求描述结合的方式来指导程序自动合成，该方法能够提升仅在单一方法进行程序合成的效果。首先利用<输出-输出>测试对搜索得到一个满足所有数据对的程序集合，据此指导程序合成的过程。此外他们还提出可以利用群体智能来指导基于自然语言的程序自动生成[14]，类似于“众包”的思想，利用大量不同用户为同一个自然语言描述的需求来提供不同的<输入-输出>测试对，然后进行程序合成，因此该方法能够更好的捕捉到自然语言所描述的真实需求。

（2）基于Sketch（框架）的程序合成

基于框架（Sketch）的程序合成通常更加关注程序结构，例如while，if等循环语句，一个Sketch是不完整的部分程序，代表一个需要填充的程序框架。基于Sketch的程序合成允许用户提供不完整的程序框架，合成工具通过语法指导或者其他方式进行程序合成。例如Rastislav Bodik等人[10]对基于Sketch的程序合成进行了总结并提出一些方法有助于程序合成在复杂Sketch上的合成过程，例如他们提出可以允许用户提供部分程序框架的时候扩展描述语言，也可以通过增加反例的形式来对程序合成过程加速。基于Sketch的程序合成还可以与机器学习的方法学习起来，通过抽取大量Sketch与其实现代码的数据对，利用机器学习模型学习其中的映射关系，例如Vijayaraghavan Murali等人[11]提出利用深度学习中的RNN时序模型通过训练从大量Android代码抽取出的<证据，Sketch>数据对，得到能够根据用户提供的证据预测程序Sketch的模型，然后通过语法指导的填充过程，得到填充后的程序。

（3）基于自然语言的程序合成

基于自然语言的程序合成需要用户提供自然语言作为需求描述，程序合成利用自然语言或者将自然语言与别种形式的需求描述相结合生成出程序。由于自然语言通常与程序代码之间有着较大的鸿沟，因此该方法的挑战主要在于如何克服自然语言与机器语言之间的跨度上。相关工作如Aditya Desai等人[12]提出可以通过大量的<自然语言，领域特定语言>数据训练出通过用户给与的自然语言描述翻译出领域特定语言，然后利用领域特定语言进行程序合成的方法。并通过在文本编辑，智能助手系统等领域的程序合成中验证了其效果。Navid Yaghmazadeh等人[13]提出可以将自然语言处理，程序合成与自动程序修复领域结合起来，允许用户给出一个自然语言描述，首先利用语义分析功能将其转换为一个SQL查询的Sketch，然后利用类型指导的程序合成方法合成出具体的SQL语句。由于用户自然语言通常过于抽象，不能精确的反映出数据库的机制，于是他们在方法中使用了错误修复技术，对得到的SQL Sketch进行合理性的修复知道得到高质量的SQL查询语句为止。

（4）基于逻辑规约的程序合成

基于逻辑规约的程序合成方法需要用户针对程序功能提供完整的规约描述，规约可能用某种语法表示成公式。对于复杂需求，一般用户来说写出完整的程序规约比较困难，因此这种方法在应用中很少被用到，实用性不够好。

3.2  从搜索策略角度进行分类

从采用的搜索策略的角度进行分类，程序合成方法又可以分为，基于语法指导的、基于代码搜索的、基于深度学习以及基于API（组件）的程序合成。

（1）基于语法指导的程序合成

基于语法指导的程序合成一般需要用户提供程序的输入输出规约或者语法框架，程序合成工具通过具体搜索策略或者符号搜索找到满足用户规约的程序，符号搜索需要从用户规约中抽取出程序需要满足的约束，然后利用约束求解器得到解。Kangjing Huang[17]等人提出可以将两种搜索策略结合，利用决策树的高度枚举从短到长的程序代码，在每个固定长度的枚举过程中，通过举反例的形式达到更精确的搜索。他们在一系列的benchmark上证明了该方法具有优秀的效果。Rajeev Alur[19]等人描述了几种方法针对语法指导的程序合成，包括激活学习、增加反例以及随即搜索等，并执行合理的benchmarks对比不同方法的效果。他们还对比了语法指导的程序合成比赛中验证过1500个benchmark的6个新的工具[20]，并分析了其效果。

（2）基于代码搜索的程序合成

基于搜索的程序合成方法结合了经典的代码搜索过程，在程序合成初期，利用代码搜索得到与需求最接近的代码结果，在此基础上再进行程序合成。基于搜索的程序合成方法能有效利用程序代码搜索的结果缩小程序合成的时间复杂度和空间复杂度，该方法首先需要针对用户需求进行代码搜索，可针对自然语言或代码片段、程序关键词进行搜索，得到搜索出的代码片段之后，再利用现有程序综合技术得到符合需求的程序。相关工作例如Swim[2]，能够针对用户提供的需求规约，检索出相关的API名称，然后通过检索API使用模式集合找到最可能用的API模式序列，并据此包装生成代码片段。相关工作还有Hunter[3]，能够根据用户提供的自然语言描述，检索出相关代码，并根据类型距离对检索结果排序，最后通过整数线性规划（Integer Linear Programing）将程序综合问题转化为基于API的代码生成过程，并利用现有工具生成出符合需求的程序。基于搜索的程序自动生成的效果与前期代码搜索结果息息相关，如何设计合理的搜索排序技术有效的找出与用户需求最匹配的代码成为该方法的关键点之一。基于搜索的程序合成技术利用代码搜索的结果，能够有效的缩小程序综合的空间，提升程序合成的时间效率，成为很多程序合成技术的首要過程。

（3）基于深度學习的程序合成

近几年，人工智能行业迅猛发展，研究人员开始研究如何使用更加智能化的方法实现程序自动生成。机器学习等相关方法一般需要大量数据集来训练，而随着互联网的繁荣发展，Github等代码托管平台上存储了大量的项目代码使得利用机器学习来学习如何写代码成为了可能。根据方法的风格不同，基于深度学习的程序合成方法一般分为两种类别，一种是模型原理不可解释的“黑盒”方法，另一种是能够直接生成可解释代码的“代码生成派”方法。黑盒的方法类似于一个黑箱子，直接利用大量数据集训练得到代码生成的规则，规则被表示为模型的参数，因此具有不可解释性。“黑盒派”方法对用户来说不易于使用和修改，因为用户并不能理解模型到底学习出了什么样的编程规则。而“代码生成派”则能够直接根据需求生成出显示的程序代码，更加符合人类所想象的机器自动编程的状态。在模型的使用阶段，用户只需提供一至多个输入输出数据对，模型能够根据输入输出数据对，提取高层特征，预测出需求所需要的各种操作原语的概率，结果概率越高的操作原语，越有可能在任务的实现代码中用到。相关工作如DeepCoder[5]，一种使用输入输出样本的深度学习解决编程竞赛风格的方法。该方法属于典型的代码生成派工作，能够通过训练神经网络来预测有输入到输出的程序属性。Facebook在该领域也有所研究，例如其选择层级生成CNN网络结构[6]（Hierarchical Generative Convolutional Neural Network，又称为HGCNN），利用随机生成的程序，给定一些输入，运行程序得到输出来构造数据集，因此属于无监督学习的过程。

（4）基于API（组件）的程序合成

基于API的程序合成旨在根据用户意图生成出纯API的程序代码。其特点是结果程序中只包含API以及控制结构，不包含常量的声明、运算等语句。由于软件模块化程度是软件开发过程中衡量项目质量的一个重要标准，因此在软件开发过程中，提倡将不同功能封装起来，降低软件代码的耦合性，以减少模块之间的依赖，因此基于API的程序合成方法无疑是顺应软件开发的趋势并且更方便用户来复用代码。典型的基于API的程序自动合成工作如Ye Feng[7]等题出利用PetriNet来对API中方法间的关系进行建模，用户需要提供函数声明和测试用例作为需求描述，该方法能够遍历PetriNet的可达性图来找到符合用户声明的API序列，并执行测试用例直到找到满足需求的解为止。此外他们也提出可以由示例驱动的基于API的程序合成方法[15]，可以处理特定领域任务例如表格等文档的处理与转换，该方法将基于SMT的约束求解方法和基于API的程序合成相结合，并采取局部评估的方法，能够针对小规模的java程序取得一定的效果。Sumit Gulwani等人[16]提出利用用户提供的规约描述，在组件库中生成出loop-free的研究，通过将用户的规约抽取成约束，然后利用约束求解的过程生成程序。该研究能够做到探索超过2010的大小的程序搜索空间，例如能够合成出长达20行的loop-free的位运算程序代码。

4  程序合成面临的挑战

现有研究工作[1]指出，程序合成主要面临来自于两个维度的挑战，一个是难掌控的程序搜索空间，一个是用户意图的多样性。

任何程序合成方法都包含着在搜索空间搜索的过程，而程序对应的搜索空间都随着其程序规模的增加呈指数增加趋势，大量有可能的候选结果，如何有效排序，提升程序合成的效率，也是研究人员不停在钻研的问题。随着过去二十年里一些技术和算法上的突破，摩尔定理和约束求解的发展使得在合理时间内可以搜索更大的搜索空间。但尽管现在的程序合成能够产生一些符合需求的代码片段，程序合成依然不能产生大规模的现实世界的代码，并且在工业界应用也非常受限。例如右Phothilimthana等人[8]提出的能够合成出更短的程序的超优化技术可以探索1079大小的程序空间。而一个能够实现MD5哈希函数的合成器就需要探索多达一万五千多个程序，远远超过现在程序合成方法所能探索的空间。因此在程序合成领域，新的搜索算法以及领域特定研究仍然面临着艰巨的挑战并有待于进一步探索。

如何精准的表达并解释用户意图是程序合成面临的第二大挑战，最初的用户意图通常用程序逻辑规约来表示，这通常是针对一些演绎合成方法。最简单的功能例如字符串操作，针对一些输入输出规约通常会有数百万的程序与之一致，需要用户提供简单的逻辑规约即可。但一旦问题变得稍微复杂，用户很难想象需求会有怎样完整的规约，编写完整的规约对用户来说就像编写程序一样复杂，非常不友好。近些年程序需求描述更加偏向自然语言化的趋势，用户可以很轻松的用自然语言描述其所需要的功能，但这也带来了需求描述和实现代码之间的距离更加远，需要研究更有效的算法来将自然语言程序翻译成符合需求的代码。如何在减轻用户负担的基础上探索更好的用户意图表述方式成为程序自动合成研究所面临的另一挑战。

5  讨论与展望

近年来，程序合成技术取得了多方面的进步，从搜索算法到程序和成框架上都在随着计算机研究热点而有所改变。就目前整体取得的进展和面临的挑战来说，我们认为从以下几个方面是未来一段时间内程序合成技术有待于解决的阶段性难题。

（1）人机交互

程序合成技术通常面临的用户水平参差不齐，对于一些刚刚使用程序合成工具的用户来说很难一次性提供完整的需求描述，因此良好的人机交互和阶段性反馈能够给程序合成工具带来更好的用户体验和使用效果。并且经过用户反复修改规约描述得到的合成代码，往往能够更加接近用户需求的解。现有的程序合成方法鲜有可方便用户反馈调式的工作出现，而程序合成技术要想更好的落地实施，在其研究中占主要的不应该仅仅是内部算法，更不能缺少的是良好的用户体验和易用性。

（2）多元化需求描述

過去的程序合成算法中探索了多种用户意图描述的方法，从最初的程序规约到后来更加易用的自然语言。然而只使用一种输入作为需求描述往往不具有普适性，比如初级用户难以写出完美的程序规约来约束程序合成过程，而仅使用自然语言虽然减轻了用户负担却又给程序合成过程带来了较为不确定的空间描述，导致用户意图过于抽象，合成不出理想的代码结果。正如如今的软件开发过程讲究的是协同合作而不是单一决策一样，未来一段时间内程序合成有必要探索如何结合多种形式的输入，达到一种资源汇聚的效果。将自然语言、规约描述、关键词描述等多种输入结合能够更好的减轻用户负担，避免用户难以针对一种需求描述方法写出完善的规约。

（3）智能化程序合成

随着人工智能的火热发展，研究学者们更希望能够用智能化的方法来合成程序。虽然已经产生了“黑盒派”以及“代码生成派”等相关研究工作，但这些方法都处于研究的初期阶段，无法很好的在现有需求上产生应用，因此机器自动编码领域仍有很长一段路要走。类似于Github等互联网代码托管平台已经存储了大量的项目代码，这给以深度学习训练为核心来实现程序合成的方法提供了良好的契机。因此未来很长一段时间内将会有大量的研究工作将重心放在基于深度学习的程序自动合成上，如何更好的挖掘出先验知识中的编码规范来指导程序自动合成，成为软件工程领域当前一个热点研究领域。

6  结束语

信息化发达的互联网时代已经持续了很多年，使得软件开发活动在社会发展中一直占有重要地位并不断演化前进。现如今软件开发规模的复杂性使得人们更加追求良好的编程规范和高效的编码效率，因此程序自动合成领域在近年重新成为软件工程领域的研究热点。但程序自动合成距离能够产生工业应用的那天还很遥远，无论在搜索空间效率上，还是在用户交互的可用性上都没有达到一个良好的效果。而人工智能的发展给程序自动合成带来了新的方法流派，未来程序合成技术还有更多方向需要继续探索前进。

参考文献

[1] S. Gulwani， O. Polozov and R. Singh. Program Synthesis. Foundations and Trends? in Programming Languages， vol. 4， no. 1-2， pp. 1–119， 2017.

[2] Raghothaman M， Wei Y， Hamadi Y. SWIM： synthesizing what I mean： code search and idiomatic snippet synthesis. In： Proc. of the 38th Intl Conf. on Software Engineering. ACM， 2016： 357-367.[doi： 10. 1145/2884781. 2884808]

[3] Wang Y， Feng Y， Martins R， et al. Hunter： next-generation code reuse for Java. In： Proc. of the 24th ACM SIGSOFT Intl Symp. on Foundations of Software Engineer. ACM， 2016： 1028-1032.[doi： 10. 1145/2950290. 2983934]

[4] Gulwani S， Esparza J， Grumberg O， et al. Programming by Examples （and its applications in Data Wrangling）. Verific-ation and Synthesis of Correct and Secure Systems. IOS Press， 2016.

[5] Balog M， Gaunt A L， Brockschmidt M， et al. DeepCoder： Learning to Write Programs. In： Proc. of the 5th Intl Conf. on Learning Representations. 2017.

[6] Gong Q， Tian Y， Zitnick C L. Unsupervised Program Induction with Hierarchical Generative Convolutional Neural Networks. In： Proc. Of the 5th Intl Conf. on Learning Representations.

[7] Feng Y， Martins R， Wang Y， et al. Component-based synthesis for complex APIs. In： Proc. of the 44th Annual ACM SIGPLANSIGACT Symp. on Principles of Progra-mming Languages. 2017： 599-612. [doi：10.1145/3093333. 3009851]

[8] Phitchaya Mangpo Phothilimthana， Aditya Thakur， Rastislav Bodík， and Dinakar Dhurjati. Scaling up superoptimization. In Proceedings of the 21st International Conference on Architectural Support for Programming Languages and Operating System （ASPLOS）， pages 297-310， 2016.

[9] Manshadi M H， Gildea D， Allen J F. Integrating Programming by Example and Natural Language Programming. In： Proc. of the 27th AAAI Conf. on Artificial Intelligence. 2013. AAAI Conf. on Artificial Intelligence. 2013.

[10] Bodik R， Solar-Lezama A. Program synthesis by sketching[J]. Dissertations & Theses - Gradworks， 2008.

[11] Murali V， Chaudhuri S， Jermaine C. Bayesian Sketch Learning for Program Synthesis[J]. 2017.

[12] Desai A， Gulwani S， Hingorani V， et al. Program Synthesis using Natural Language[J]. 2016.

[13] Yaghmazadeh N， Wang Y， Dillig I， et al. Type- and Content-Driven Synthesis of SQL Queries from Natural Language[J]. 2017.

[14] Manshadi M， Keenan C， Allen J. Using the crowd to do natural language programming. In： Proc. of the 26th AAAI Conf. on Artificial Intelligence， Workshop on Human-Com-puter Interaction. 2012.

[15] Feng Y， Martins R， Van Geffen J， et al. Component-based synthesis of table consolidation and transformation tasks from examples. In： Proc. of the 38th ACM SIGPLAN Conf. on Programming Language Design and Implementation. ACM， 2017： 422-436.[doi： 10. 1145/3062341. 3062351]

[16] Gulwani S， Jha S， Tiwari A， et al. Synthesis of loop-free programs[J]. ACM SIGPLAN Notices， 2011， 46（6）： 62.

[17] Huang K， Qiu X， Tian Q， et al. Reconciling Enumerative and Symbolic Search in Syntax-Guided Synthesis[J]. 2018.

[18] Gulwani， S.， Harris， W. R.， Singh， R.： Spreadsheet data manipulation using examples. Commun. ACM 55（8）， 97–105 （Aug 2012）， http：//doi.acm.org/10.1145/2240236.2240260

[19] Alur R， Bodik R， Juniwal G， et al. Syntax-guided synthesis[C]// Formal Methods in Computer-aided Design. IEEE， 2013.

[20] Alur R， Fisman D， Singh R， et al. SyGuS-Comp 2017： Results and Analysis[J]. 2017.