Page 154 - 《软件学报》2021年第5期

1378 Journal of Software 软件学报 Vol.32, No.5, May 2021

Table 1 Summary of existing studies of intelligent program synthesis (Continued)
表 1 程序智能合成现有工作的总结(续)
需求规约表示方式 文献 合成模型 技术特点
Armando 等人 [37] 编码器-解码器模型 利用 Sketch 框架的
Murali 等人 [38] 编码器-解码器模型 方法生成代码片段
Navid 等人 [39] Word2Vec 模型
Alur 等人 [40] 深度神经网络 利用语法制导的
基于代码框架 Alur 等人 [41] 深度神经网络
(语法)的程序合成 Alur 等人 [42] 深度神经网络 方法生成代码片段
Sun 等人 [43] 卷积神经网络
Luan 等人 [44] 深度神经网络 利用代码结构化
Chen 等人 [45] 长短期记忆网络 信息生成代码片段
Hu 等人 [46] 长短期记忆网络
Quirk 等人 [47] 深度神经网络 利用深度学习方法
Liu 等人 [48] 深度全连接网络+Attention 生成 IFTTT 程序
Gu 等人 [49] 循环神经网络 利用深度学习方法
基于自然语言的 Gu 等人 [50] 循环神经网络 生成 API 序列
程序合成 Zhong 等人 [51] 编码器-解码器模型 利用深度学习方法
Manshadi 等人 [52] 深度神经网络 生成 SQL 查询语句
Dong 等人 [53] 编码器-解码器模型 利用深度学习方法生成逻辑形式
Desai 等人 [54] 深度神经网络 利用深度学习方法生成领域特定语言

3.1 基于输入输出示例的程序合成方法
基于输入输出示例的程序合成方法以输入输出示例作为需求规约描述.近年来,很多学者尝试将深度学习
等方法与基于输入输出示例的程序合成相结合,并取得了一定的进展.该方法首先通过大量的输入输出示例对
训练合成模型;合成模型训练好后可以进行合成任务,输入领域特定语言(domain specific language,简称 DSL)描
述的需求规格,该模型可给出与之相对应的程序.
2015 年,Reed 等人开发了一个名为“神经程序解释器(neural programmer interpreters,简称 NPI)” [30] 的框架.
该框架利用神经网络及其组合来生成程序执行所需要的语句以及参数,可以根据输入输出示例生成加法、排序
等简单程序.此后,许多研究工作基于 NPI 展开,通过对 NPI 进行改进,以提高程序生成的效率.如 Chengtao 等人
提出了 NPI 的改进模型 NPL(neural program lattices) [31] ,其对传统神经程序解释器 NPI 进行监督学习方面的改
进,使用弱监督代替大多数强监督的情况下,实现性能与 NPI 相当,使得 NPI 能够从只包含低级操作的示例中推
断出高级的程序结构.Cai 等人 [32] 提出了 NPI 的改进模型 RNPI,允许程序调用其自身,通过增加递归模块扩展了
神经网络结构,改善了神经网络的泛化能力.对给定长度的数据进行排序操作,当待排序数据个数超过 11 时,NPI
的预测正确性随着数据个数增长不断下降,而 RNPI 始终可以给出正确的数据排序结果.
2017 年,Balog 等人提出了智能化自动编程方法 DeepCoder [35] .该方法能够根据输入输出示例,使用深度神
经网络和集束搜索技术实现特定领域的代码自动合成.该方法缩小了搜索空间,用大小为 34 的 DSL 指令集进行
表示,通过将深度神经网络和集束搜索技术相结合生成简单的程序.与传统方法相比,该方法实现效率较高.虽
然 DeepCoder 的指令集和操作数有限,无法描述复杂任务,通常只能生成 10 行左右的代码,但该方法作为一种代
码自动合成方法,将深度学习技术和代码的搜索生成技术相结合,具有创新性.
2017 年,Devlin 等人提出了面向字符处理的神经网络模型 RobustFill [33] .该模型可以实现与 FlashFill [55] 相同
的字符串处理功能,使用了一种改进的 RNN 神经网络,在字符串处理测试集上的正确率更高(RobustFill 的正确
率为 92%,FlashFill 的正确率只有不到 50%).但是,由于 RobustFill 完成相同功能需要更多的数据样本(FlashFill
仅需要 1~3 个示例,Robust 需要至少 5 个示例)及计算资源,因此目前尚未在 Excel 中进行部署.
Becker 等人在 2017 年提出了能够自动生成可运行程序的 AI 系统“AI Programmer” [36] .该系统利用遗传算
法进行复杂指令的模拟,并根据程序的输入输出生成程序.该系统的指令集由 8 个基础的计算机指令构成,通过
随机初始化获得一个初始的目标程序,并根据程序的输出测试其适合度.该方法生成的程序越接近目标程序,适
应度就越高,因而越有可能继续进行下一代进化.尽管 AI Programmer 能够完成初级程序的自动生成任务,但其