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

顾斌 等:程序智能合成技术研究进展 1379

生成的程序可读性差,且算法模型仅能针对单一任务.此外,AI Programmer 运行过程时间开销巨大,且容易陷入
死循环和状态空间爆炸,因此,暂时还无法达到工业化的应用标准.
Jha 等人提出了 Oracle 指导的归纳合成(OGIS) [56] .当程序合成存在程序模板,将大大降低程序合成的难度.
然而在大多数情况下,相关领域特定的模板是不具普适性的.基于 Oracle 指导的程序合成就试图解决这一难题:
首先,使用简化的规约搜索候选程序;然后,验证该候选程序 Oracle 的有效性.为了降低验证的难度,该团队提出
通过一个 I/O Oracle,可以在任意给定的输入上生成有效的程序输出的方法 [57] .该方法认为:一个正确的候选程
序如果与整个规约ϕ一致,那么它将与有限数量的有效输入/输出对一致.首先,通过公式对所有可能的程序空间
进行编码;再给出一组输入-输出对,然后进一步约束该公式,以便它能仅对正确运行的程序进行编码;最后,通过
此约束生成候选解决方案.
Guo 等人提出了反例指导的归纳合成方法 [31,38] .该方法分为求解器和验证器两部分:首先,将原始的二阶规
约简化为一阶规约,将一阶规约输入到求解器中,产生满足该规约的候选程序;验证器判断候选程序是否满足原
始二阶规约,如果不满足,验证器将生成一个反例,然后将其返回给求解器.求解器重复搜索以寻找满足此反例
的新候选程序.此过程将反复进行,直到某候选程序被接受,或者求解器找不到与当前规约相符的候选程序(即
无解).
Emilio 等人提出了两个新的神经模块进行神经程序合成 [37] :第 1 个模块称为互相关 I/O 网络(the cross
correlation I/O network),它给出了一组输入输出示例,生成一组 I/O 示例的连续表示;第 2 个模块是递归神经网络
(R3NN),给出了实例的连续表示,并通过增量展开部分程序来合成一个程序.通过将该方法应用于基于正则表
达式的字符串转换领域,展示了该方法的有效性.实验表明,R3NN 模型能够从新的输入输出实例中构造程序.
3.2 基于代码框架(语法)的程序合成方法

基于代码框架(语法)的程序合成方法主要利用程序结构或者语法框架信息,将程序代码转换为抽象语法
树、控制流图和数据流图、程序框架草图等某种结构化表示.该方法主要由 3 部分组成:需求规格说明、结构/
语法限制、合成器.软件开发人员一般很难写出完整的需求规格说明,但在结构/语法限制的补充下,可以不断丰
富软件需求信息.结构/语法的限制条件同时可以限制合成器的输入,以提高合成效率.使用程序合成器来生成
程序,成功地将程序合成问题转换为约束求解问题.目前,常用的合成器有 SAT(Boolean satisfiability problem)求
解器和 SMT(satisfiability modulo theories)求解器.
Armando 等人于 2008 年提出了基于 Sketch 的程序合成方法 [38] .该方法提供一个待填充的程序框架,再由合
成器根据需求规约填充程序空白.合成阶段,Sketch 根据部分输入输出示例合成出一个可能的解.验证阶段,若发
现当前解能够满足所有输入输出示例,则合成成功;若存在不满足的输入输出示例,则进入下一次的“合成验证
循环”.该方法可实现简单 Sketch 框架下的程序合成,然而对于复杂 Sketch 框架下的程序合成依然无法实现.将
用户意图转换为 Sketch 语言的过程比较繁琐,同时合成速度较为缓慢,因此,基于 Sketch 的合成目前更多的是作
为辅助程序合成的工具.在此基础上,2017 年,Murali 等人提出一种神经网络与代码框架 Sketch 相结合的进行程
序合成方法 [40] ,利用神经网络模型建立代码框架与标签(API 调用、代码 Token 或数据类型)之间的联系.在软件
开发过程中,模型会根据程序员输入的标签信息生成 Java 代码框架.该方法可以在编程过程中为开发人员提供
辅助参考,提升开发效率.
Alur 等人于 2013 年提出了一种基于语法制导(syntax-guided synthesis)的程序合成方法 [41] .该方法的输入包
括一组由逻辑表达式描述的需求语义规范和一组符合语法规则的候选实现集,允许用户使用语法来补充候选
集,并找到一个满足给定需求的解.该团队同时在基于语法制导的程序合成方法基础上加入了多种技术,如增加
反例技术、激活学习技术、随机搜索技术等 [44,45] ,这些方法利用语法进行程序搜索,大大缩小了代码空间,从而
提升了搜索效率.目前,基于语法制导的程序合成还处于理论研究阶段,对于复杂系统用户意图的表达还需进一
步研究.
Navid 等人于 2017 年提出了一种面向数据库应用的程序合成方法 [42] .该方法将用户给出的自然语言需求
描述转换为 Sketch 语言,然后基于 Sketch 语言合成 SQL 程序.该方法同时提供了错误修复功能,以保证自然语