CodeWisdom-技术分享
基于优化搜索的API序列推荐
开发人员经常依赖于各种应用程序编程接口(Application Programming Interface,API)来实现所需要的软件的功能特性,从而完成自己的开发任务。开发人员有时候需要的是包含多个API的API序列而非单个API。从而,API序列推荐场景也成为了一种需求场景。与单个API推荐场景相比,API序列推荐能够一次性为开发人员提供包含多个API的API 序列,从而为开发人员一次性提供更丰富更完整的API 用法,但同样对API 序列推荐的准确率也带来了挑战。
复旦大学CodeWisdom团队提出了一种基于优化搜索的API序列推荐方法COOK。基于该方法的研究论文“More Than Deep Learning: Post-Processing for API Sequence Recommendation”(作者:Chi Chen, Xin Peng, Bihuan Chen, Jun Sun, Zhenchang Xing, Xin Wang, Wenyun Zhao)被CCF B类期刊《Empirical Software Engienering》录用。
论文地址:https://rdcu.be/cAoJ8
研究动机
现有的基于模式挖掘的方法通常首先从代码中挖掘得到API使用模式,然后在挖掘得到的API 使用模式中搜索与开发人员提供的部分代码最相似的API使用模式作为推荐。然而,基于模式挖掘的方法仅能推荐挖掘得到的API使用模式,并且挖掘到的API 使用模式的数量通常限制在数百个。因此,基于模式挖掘的方法能够推荐的API 使用模式有限,并且不能推荐挖掘到的API 使用模式之外的模式。
现有的基于特征匹配的方法通常首先定义代码中的特征(例如变量使用特征以及标识符特征等)并通过特征提取将代码转换为某种代码特征表示。在进行代码推荐时,将开发人员正在编写的代码中的特征与从代码库中提取到的代码中的特征进行搜索匹配,从而推荐特征较为匹配的包含API序列的代码。然而,基于特征匹配的方法受限于定义和提取的代码特征的质量,并且当能够提取到的特征较少时,该类方法不能提供给开发人员有效的推荐。
如果使用单个API推荐的方法来推荐API序列,那么需要进行多步推荐,从而有比较大的累计误差。鉴于编码器-解码器模型在代码搜索场景中的成功应用以及API 序列推荐场景本身的特性,基于深度学习的单个API 推荐的方法可以通过应用编码器-解码器模型并结合束搜索来实现API序列推荐。然而,一方面,束搜索是一种简单的贪婪策略,在解码得到API序列的每一步解码步,束搜索仅根据每一步解码步的候选API的概率选择相应候选API作为当前解码步的解码。显而易见,束搜索基于的假设为编码器-解码器模型在每一步解码步给出的候选API的概率足以导向完成整个解码过程。然而,开发人员在进行候选API的选择时除了会参考模型给出的候选API的概率,还会考虑代码其他方面的特性(例如代码语法等)。另一方面,解码得到的API序列按照概率由高到低排序在API序列推荐列表中并展示给开发人员。显而易见,将API序列按照概率由高到低排序进行展示的方式基于的假设为开发人员能够从按照概率排序的API序列中选择所需要的API序列。仅以概率为导向,基于束搜索解码得到的API序列之间的相似度较高,在有限的API序列推荐列表中忽略了API序列所蕴含意图或解决方案的开放性与多样性。因此,在API序列推荐列表的顶部位置可能均为相似度较高的API序列,而蕴含不同意图或解决方案的API序列可能展示在API 序列推荐列表的底部,甚至不在API序列推荐列表中。这就使得开发人员不能有效地选择和对比蕴含不同意图或解决方案的API序列。此外,开发人员在进行选择时,希望理解不同的API序列之间的共性以及差异,从而有助于选择所需要的API序列。然而,仅以概率为导向的排序对理解不同的API序列之间的共性以及差异毫无帮助。
我们的方法COOK
鉴于基于深度学习方法相对传统方法的优越性以及上述分析,我们提出了一种基于优化搜索的API序列推荐方法COOK。我们不再试图进一步改进或增强现有的已经非常复杂的编码器-解码器模型,而是希望通过后处理策略来提升编码器-解码器模型的API序列推荐效果。因此,我们提出的方法与深度学习模型是正交的,普遍适用于不同的深度学习模型。我们提出了三种后处理策略,包括启发式增强的束搜索用于优化深度学习模型解码阶段生成API序列的搜索和选择排序的过程、结合文本相似度及API词嵌入相似度的层次聚类算法用于对API序列进行聚类、以及基于关键API抽取的概要生成方法用于为API序列生成概要。
对束搜索进行启发式增强
我们基于代码语法(包括句法结构以及变量可访问性)以及推荐多样性两方面提出了相应的启发式规则来增强原始的束搜索,即在每一步解码步中过滤违反代码语法的候选API,并过滤生成的API序列中具有较高相似度的API序列。
满足代码语法有利于生成并推荐高质量的语法正确的API序列。例如,ElseIf为某一步解码步中的候选API,然而在当前代码上下文以及直至该解码步所解码得到的API序列中并不包含If控制结构,那么ElseIf则是一个非法的候选API。在这种情况下ElseIf应该被过滤,因为ElseIf不满足If的句法结构。再如,java.io.OutputStream.write(byte[])为某一步解码步中的候选API,然而在当前代码上下文以及直至该解码步所解码得到的API序列中并不包含任何实例化的java.io.OutputStream 对象,那么java.io.OutputStream.write(byte[])就是一个非法的候选API,应该被过滤掉。因为,在调用一个非静态的API 方法前,需要先声明并创建该API类的一个实例化对象。
推荐多样性对于API 序列推荐而言也是相当重要的。如果一个API序列包含另一个API序列,我们称这两个API序列之间存在包含关系。在将解码得到的API序列添加进最终的API序列推荐列表前,我们会将解码得到的API序列与API序列推荐列表中的API序列逐一进行包含关系检查。如果解码得到的API序列与API序列推荐列表中的某个API序列之间存在包含关系,那么我们将保留生成概率高的API序列,而过滤掉生成概率低的API序列。如图1与图2分别展示了没有多样性启发式规则的推荐结果以及加入多样性启发式规则的推荐结果。
图 1
图 2
对推荐的API进行聚类
我们通过结合API 序列之间的文本相似度(即text similarity)以及API词嵌入相似度(即API embedding similarity)作为API序列之间的语义相似度,从而用于计算两个API 序列在进行聚类时的距离D(𝑌 , 𝑌’)。
其中,𝑎𝑒(𝑌 , 𝑌’)表示API序列𝑌与API序列𝑌’之间的API词嵌入相似度,𝑡𝑒𝑥𝑡(𝑌 , 𝑌’) 表示API序列𝑌与API序列𝑌’之间的文本相似度。
对推荐的API序列生成概要
对于经过聚类后的每一类API序列,我们首先提取出每一类API序列中包含控制结构的最长公共子序列。其次,我们识别出最长公共子序列中的关键API用于生成概要。如图3所示,我们构建提取得到的最长公共子序列对应的控制流数据流图并利用PageRank算法来识别最长公共子序列中的关键API。最后,对于识别出的关键API中的每一个API,我们提取其对应的API文档描述中的第一句话作为该API的概要。
图 3
实验结果
我们通过GitHub收集了一个庞大的代码语料库用于训练三个实例化的编码器-解码器模型(即Seq2Seq模型、Transformer模型以及GGNN2Seq模型)。我们采用CIDEr-k值作为API序列推荐质量的评估指标。实验结果表明所有使用我们提出的启发式增强的束搜索的编码器-解码器模型在测试项目上评估得到的CIDEr-k值在绝大部分情况下比使用原始的束搜索的编码器-解码器模型评估得到的CIDEr-k值大。在一些情况下,使用我们提出的启发式增强的束搜索的编码器-解码器模型甚至比使用更复杂先进的深度学习模型(使用原始的束搜索)所取得的效果更好。此外,我们的聚类实验以及用户研究实验结果表明,我们提出的聚类算法以及概要生成方法能够有效地对推荐的API序列进行聚类并且生成能够帮助用户进行API序列选择的概要。
CodeWisdom
欢迎关注CodeWisdom,Codewisdom平台由复旦大学软件工程实验室运营,提供智能化软件开发平台及线上沙龙相关资讯,关注可了解更多智能化软件开发的最新消息~
点击【阅读原文】可阅读论文全文~