ACM通信
研究突出了
论软件的自然性
来源:Devfloat.net
像英语这样的自然语言是丰富、复杂和强大的。莎士比亚和阿维亚尔等大师对英语和泰米尔语等语言的高度创造性和优雅的使用，当然可以令人愉悦和鼓舞。但在实践中，考虑到认知的限制和日常生活的紧迫性，大多数人类话语要简单得多，重复和可预测得多。事实上，这些话语可以用现代统计方法非常有用地建模。这一事实使统计方法在语音识别、自然语言翻译、问题回答以及文本挖掘和理解方面取得了显著的成功。
我们从猜想开始大多数软件也是自然的在某种意义上，它是由人类在工作中创造的，伴随着所有的约束和限制，因此，就像自然语言一样，它也可能是重复的和可预测的。然后我们继续询问(a)是否可以用统计语言模型对代码进行有用的建模，(b)是否可以利用这些模型来支持软件工程师。使用广泛采用的n-gram模型，我们提供了实证证据支持这两个问题的积极答案。我们展示了代码也是非常有规则的，事实上，甚至比自然语言更有规则。作为模型的一个示例，我们为Java开发了一个简单的代码完成引擎，尽管它很简单，但已经提高了Eclipse的完成能力。最后，我们对该领域的未来研究进行了展望。
1.简介
在我们所做的一切中，沟通可以说是人类最本质的行为之一。经过数百万年的文化和生物进化，语言和交流是日常生活中普通的、本能的一部分39)．尽管“自然”语言，如英语和泰米尔语，能容纳精巧复杂的表达形式，但人类的日常交流是在受噪音干扰和需求驱使的环境中演变而来的;因此，它通常是简单的、权宜之计的，甚至是重复的。这种日常人类语言行为的“自然性”，加上大量在线语料库、现代计算资源和统计创新，导致了一场语言革命自然-语言处理，我们每天都在享受它的成果，以移动设备中的语音识别和云中的自动语言翻译为形式，尤其。
然而，自然语言处理领域(“NLP”，参见Sparck-Jones46(简史)经历了几十年相当缓慢和艰苦的进展，从1960年代早期的字典和基于语法的努力开始。在20世纪70年代和80年代，逻辑学和形式语义学的思想使这一领域重新焕发生机，但事实证明，这些思想仍然过于繁琐，无法大规模执行实际任务。这两种方法基本上都是从第一原则处理NLP的语言而不是研究实际的语料库话语即人们实际写的或说的。在20世纪80年代，一个根本性的转变基于语料库，统计严谨发生的方法。大规模的在线自然语言文本语料库的可用性，包括“对齐”的文本与多种语言的翻译，一个再加上计算能力(CPU速度、主、次存储)在非常大的数据集上估计健壮的统计模型，已经带来了惊人的进展和广泛可用的实际应用，例如translate.google.com．b
我们能应用这些技术吗直接用它奇怪的语法，充斥着标点符号的软件，复制这种成功?编程的有趣之处在于它是如此之多一种交流行为从一个人到另一个人，因为这是一种告诉计算机做什么的方式。Knuth在30年前就说过:
让我们改变对程序构建的传统态度:不要想象我们的主要任务是指示计算机做什么，让我们集中精力向人类解释我们希望计算机做什么。23
那么，如果把编程看作是一种交流行为，它是由“语言本能”驱动的吗?我们说话的时候要编程吗?我们的代码是否非常简单、重复和可预测?代码是自然的吗?
确切地说，这是我们的中央假说：
编程语言，在理论上是复杂的，灵活的，强大的，但是，“自然的”程序，那些真正的人实际上写作，大多是简单和相当重复的;因此，它们具有有用的可预测的统计属性，可以在统计语言模型并利用软件工程任务。
我们认为重复出现在代码语料库中词法、句法,语义我们相信，使用现代计算数据分析方法可以捕捉和利用这一现象。我们相信这是一个通用的、有用的和实际的概念，它与非常大的公开可用的开源代码语料库一起，将为广泛的应用提供一种新的、严格的、统计的方法，包括程序分析、错误检查、软件挖掘、程序总结和代码搜索。
这份文件是我们希望这将是一个漫长而富有成果的旅程的第一步。我们作出以下贡献:
- 我们通过实例化一个简单的、广泛使用的统计语言模型，在大型软件语料库上使用现代估计技术，为我们的中心假设提供支持;
- 我们证明，使用标准的交叉熵和困惑度量，上面的模型确实捕获了存在于软件中的高级统计规律性n-gram级(令牌的概率链);
- 我们通过开发一个简单的代码建议工具来演示这种语言模型的使用，该工具已经在广泛使用的Eclipse IDE中现有的建议工具的基础上进行了实质性的改进;而且
- 我们规划了一个雄心勃勃的研究议程，利用自然软件的大语料库统计模型来帮助完成一系列不同的软件工程任务。
2.动机与背景
有许多方法可以利用自然程序的统计数据。我们从一个简单的激励例子开始。我们将在本文后面介绍更多的可能性。
考虑一个接收(有噪声的)无线电广播的语音识别器，例如今天在柏林，安吉拉总理<无线电buzz >宣布．.．一个好的语音识别器可能会猜出这个模糊的单词是默克尔从上下文。同样，考虑一个集成开发环境(IDE)，程序员在其中输入部分语句:For (i = 0;i<10。)“在这种情况下，IDE建议完成是相当合理的。”I + +) {“给程序员。
为什么这些猜测在我们看来如此合理?在第一种情况下，原因在于新闻广播的高度可预测性。新闻报道，像许多其他形式的文化背景化和风格化的自然语言表达，往往结构良好和重复。有了对这种风格的合理的先验知识，就很有可能填补空白。因此，如果我们听到“安吉拉总理”这个称呼，我们可以预期，在大多数情况下，下一个词是“默克尔”。语音识别器、自然语言翻译设备，甚至一些光学字符识别(OCR)工具都知道并利用了这一事实。第二个例子基于一个鲜为人知的事实:自然程序是相当重复的。这个事实是Gabel和Su在一项非常大规模的代码研究中首次观察到并报告的，13该研究发现，大得惊人的代码片段往往会再次出现。因此，如果我们看到片段(我= 0;< 10我们知道在大多数情况下会发生什么。一般来说，如果我们知道代码体中最可能的序列，我们通常可以帮助程序员完成代码。我们的直觉基本上相当于:我们可以使用代码语料库来估计代码片段的概率分布。如果这个分布的熵很低，而且我们可以很好地建模:然后，给定代码的部分片段(作为部分标记序列、部分AST或部分语义抽象)，我们通常可以以很高的置信度猜测剩下的内容。
这种分布的形式应该是什么?我们应该如何估计它的参数?在NLP中，这些发行版称为“语言模型”。NLP中的语言模型可以是词汇(标记序列)、语法(语法结构)或语义模型(意义的概率或向量空间表示)。令牌序列的马尔可夫模型是最简单的，我们用它们作为例证。
2.1.语言模型
语言模型给一个话语赋一个概率。对我们来说，“话语”就是程序。更正式地说，考虑一组允许的程序令牌cT，和可能的程序序列集(过于慷慨)T*;我们假设可能实现的系统集合是S T*。语言模型是一个概率分布p(.)通过系统年代年代，即，
在实践中，给出了语料库C的程序C年代，以及选择适当的参数分布p(.)，我们试图计算该分布参数的最大似然估计;这给了我们一个估计的语言模型。许多基于词汇、句法和语义层面现象的语言模型已经被开发出来(参见Manning和Schütze31书)。语言模型的选择通常是由实用性驱动的:它是否容易估计以及它有多有用。由于这些原因，最普遍的是语法模型，我们现在用它来说明我们的论文。
说明:N克模型考虑一个1一个2一个我一个n，文档中的标记序列(在我们的例子中，是系统的源代码年代)．我们可以从统计上建模令牌跟随其他令牌的可能性。因此，我们可以根据一系列条件概率的乘积来估计一个文档的概率:
这些n-gram模型假设a马尔可夫性质，也就是说，令牌的出现只受有限的长度前缀的影响n1，因此对于4克模型，我们假设
这些模型是通过使用简单的基于极大似然的标记序列频率计数从语料库中估计出来的。因此，如果“*”是通配符，我们会问，令牌的相对频率是多少一个1，一个2，一个3.紧随其后的是一个4：
在实践中，估计n-gram模型要复杂一些。主要的困难来自于数据的稀疏性，也就是说，与可用数据相比，模型的丰富性。例如，用104令牌词汇表，一个三元模型必须估计1012系数;但即使是最大的系统也只有O(108)令牌。因此，有些三元句可能永远不会出现在一个语料库中，但实际上可能出现在其他地方。这可能会导致技术上的困难;当我们遇到以前未曾见过的n从原则上讲，我们是“无限惊讶”的，因为一个“无限不可能”的事件x从以前见过的语料库估计有p（x= 0实际上发生了。平滑是处理我们没有见过的情况的技术吗n-g仍然可以产生具有足够统计严谨性的可用结果。幸运的是，有各种各样的技术可以平滑大量系数的估计，其中一些比它们应该的大，另一些更小。有时最好从三三元模型退回到双三元模型。技术细节超出了本文的范围，但可以在任何高级的NLP教科书中找到。在实践中，我们发现Kneser-Ney平滑(例如Koehn，24第7节给出了软件语料库的良好结果。然而，我们注意到这些都是该领域非常早期的努力，以及新的软件语言模型35，49估计技术在以下结果的基础上得到了改进。
但是我们怎么知道什么时候我们有一个好的语言模型呢?
2.2.什么是好的模型?
给定一个重复的和高度可预测的文档(或程序)语料库，一个好的模型可以捕获语料库中的规律。因此，一个好的模型，从一个有代表性的语料库中仔细估计，可以很有把握地预测从同一种群中提取的新文档的内容。一个更好的模型可以以更高的概率猜测新文档的内容。换句话说，模型会发现具有“典型”内容的新文档并不特别令人惊讶，或者非常“令人费解”。在自然语言处理中，这个想法被一个叫做困惑，或者它的对数变换版本，叉。d给定一个文档s =一个1．.．一个n，长度n，以及一个语言模型米，我们假设模型估计的文档的概率为p米（年代)．我们可以把交叉熵的测度写成:
并通过第2.1节所示的公式:
这是一个衡量模型对给定文档“惊讶”程度的指标。一个好的模型估计文档中大多数单词的较高概率(接近于1，因此绝对对数值较低)。如果一个人能够设法在IDE中部署一个(假设的)真正优秀的模型来帮助程序员完成代码片段，它可能能够猜测高概率，大部分的程序，这样大部分的编程工作可以通过点击一个TAB键来完成!当然，在实践中，我们可能会满足于少得多。
但是，我们能为“自然”软件实际构建的模型有多好呢?软件真的和自然语言一样“自然”吗?
3.方法和研究结果
为了探索这些问题，我们对自然语言和代码语料库进行了一系列实验，首先比较了代码与英语文本的“自然性”(使用交叉熵)，然后比较了各种代码语料库，进一步了解代码语料库之间的异同。
我们的自然语言研究基于两个非常广泛使用的语料库:布朗语料库和古登堡语料库。e对于代码，我们使用了几套语料库，包括Java项目的集合，以及来自Ubuntu的应用程序的集合，它们被分解为应用程序域。均列于表1．
删除注释之后，对C和Java项目源代码进行词法分析，以生成用于估计的令牌序列n-gram语言模型。虽然我们的实验是在C和Java上进行的，但扩展到其他语言是微不足道的，实际上后续使用Python的工作也得到了类似的结果。
Java项目是我们的中心关注点;我们使用它们进行交叉熵研究，并使用基于语言模型的Eclipse代码建议插件进行实验。表1描述了我们使用的10个Java项目。版本表示克隆项目时Git存储库中最后一次修订的日期。行是用Unix计算的wc在每个存储库中的所有文件上;从这些文件中提取令牌。独特的令牌中给出的令牌总数的不同令牌数令牌字段。对于英语，唯一的标记数对应于词汇量;对于代码，此计数包括所有标识符、关键字和操作符。
Ubuntu应用程序域在某些情况下相当大，多达900万行，4100万个令牌(100万个唯一)。唯一标记的数量是有趣的，因为它给出了项目语料库潜在的“惊喜性”的粗略指示。如果这些唯一的令牌在整个项目中均匀分布(这确实非常奇怪)，我们可以预期交叉熵为日志2(1.15E6)，或约20位。Java项目的类似计算从13位到17位不等。
3.1.代码的交叉熵
交叉熵衡量一个测试文档对从语料库估计的语言模型的惊讶程度。为了对一个语料库进行测试，必须留出语料库的一部分进行测试，并在语料库的其余部分上估计(训练)模型。在我们所有的实验中，我们通过10倍交叉验证的平均来测量交叉熵:我们将语料库随机拆分9010%(成行)，在90%上进行训练，在10%上进行测试，并测量平均交叉熵。更进一步的标记:当我们测量交叉熵的时候X来Y Y训练语料库是否用于估计分布模型的参数米y用于计算交叉熵，记为H我的（X)．
首先，我们想看看是否有证据支持软件是“自然的”，就像英语是自然的一样，也就是说，软件中的规律是否可以被语言模型捕获。
中移动1:n-gram语言模型能在软件中捕获规律吗?
为了回答这个问题，我们估计n的几个值的模型n在英语语料库和10个Java语言项目语料库上，使用超过10倍交叉验证的平均值(每个语料库对自己)，如上所述。研究结果刊登在图1．上面的单行是英语语料库10次折叠的平均值，从大约10位的unigram模型开始，到8位以下的unigram模型10克模型。10个项目的平均自交叉熵显示在箱线图中，每一个顺序从ungram模型到10克模型。我们可以观察到以下几点。首先，软件的ungram熵比在唯一标记上的均匀分布所期望的要低得多，因为标记的频率显然是非常倾斜的。
第二,交叉熵以n克量级快速下降饱和在3 - 4克左右。英语和Java项目衰落的相似之处是惊人的。这种下降表明Java语料库，像英语语料库一样，包含了大量的局部重复文本，这种重复是由语言模型有效捕获。我们认为这是非常令人鼓舞的:在自然语言中建模局部重复的能力已被证明在统计自然语言处理中非常有价值;我们希望这种规律性可以被用于软件工具(并构建一个基于nlp的代码建议工具，其成功支持上述主张)。
最后，但同样重要的是，软件比英语更常见在某些情况下，熵会下降到2位以下。
基于语料库的统计语言模型可以捕获软件中较高水平的局部规律性，甚至比英语更甚。
这就提出了一个重要的问题:我们在软件中捕捉到的越来越多的规律性仅仅是英语和Java之间的区别吗?Java当然是一种比英语简单得多的语言，具有结构化得多的语法。较低的熵值不可能只是Java语法人为简化的产物吗?如果语言模型所捕获的本地上下文的统计规律性仅仅来自Java的简单性，那么我们应该在所有项目中一致地发现这一点;特别是，如果我们在一个Java项目上训练一个模型，并在另一个Java项目上进行测试，我们应该成功地捕获语言中的局部规律性。因此，我们将上述问题重新表述为:
中移动2:统计语言模型捕获的局部规律性仅仅是特定于语言的还是特定于项目的?
对于这10个项目中的每一个，我们训练一个三单元模型，并与其他9个项目中的每个项目评估其交叉熵，并将其值与自身的平均10倍交叉熵进行比较。这幅图显示在图2．的x-axis列出了所有不同的Java项目，对于每个项目，箱线图显示了与其他9个项目的交叉熵的范围。底部的红线显示了项目与自身的平均交叉熵。可以看出，自熵总是较低的。
语言模型捕获了非常重要的局部规律性不它是编程语言语法的产物，而是源自特定于每个项目的“自然性”或规律性。
这是一个值得注意的结果:似乎每个项目都有它自己的本地类型，非特定于java的规则，由模型捕获;此外，每个项目的局部规律性是它本身是特别的，与其他项目有所不同。大多数软件工程师会觉得这很直观:每个项目都有自己的词汇表，迭代、字段访问、方法调用的特定本地模式，等．重要的是要注意，这些模型捕获的不是特定于java的项目规律性，而不仅仅是unigram词汇表中的差异。在第4节中，我们讨论模型捕获的多令牌局部规则在完成任务中的应用。正如我们在那一节中所演示的，模型能够在大约50%的情况下成功建议非语言标记(不是Java关键字的标记);这也证明了模型产生的低熵不仅仅是因为Java语言的简单性。
但项目不是孤立存在的;整个想法是产品线工程基于这样一个事实:在相似领域的产品彼此非常相似。这又引出了另一个有趣的问题:
中移动3:n-gram模型是否捕获了内部的相似性和之间的差异应用程序域?
我们通过研究Ubuntu中的应用程序域来解决这个问题。表1列出我们选择的10个应用程序域;这些领域都包含相当数量的项目。这些领域(每个领域的项目数量)分别是管理(116)、文档(22)、图形(21)、口译(23)、邮件(15)、网络(86)、声音/音频(26)、Tex/Latex相关(135)、文本处理(118)和Web(31)。对于每个域，我们计算自我域内的交叉熵其他交叉熵，域的交叉熵相对于其他的熵。跨域熵(中位数从5位到5.5位)始终且明显高于域内熵(34.5位)，在大多数情况下约为1位。在这里，就像在项目内和项目间的情况一样，我们看到似乎有很多重复的局部规则在应用程序域，而跨应用程序域的情况则少得多。有些领域，例如Web，似乎具有更大的域间规律性(交叉熵降低2位以上);这一现象值得进一步研究。
讨论我们已经看到，在代码语料库中存在着高度的局部规律性n-gram模型有效地捕获了这些局部的规则。我们发现证据表明这些规律是特定于项目和应用程序领域的。我们还发现，这些规律不仅来自Java相对更规则的语法(与自然语言相比)，还来自代码中存在的其他类型的项目和领域特定的局部规律。在下一节中，通过使用项目特定的模型来扩展Eclipse建议引擎，我们将演示这些项目特定的规则是有用的;我们也证明了n-gram模型经常(大约50%的时间)提供特定于项目的建议，而不仅仅是从上下文猜测的Java关键字。
在自然语言中，这些局部规律已被证明对诸如翻译等任务具有深远的价值。我们相信这些规则可以用于代码总结和代码搜索;我们还相信，更深层次的语义属性也常常表现为局部的规律性。这些将在以后的工作部分(第6节)中进一步讨论。
4.建议下一个令牌
极低的熵(在3到4位之间)产生的平滑n-gram模型表明，即使在局部令牌序列级别，也具有高度的“自然性”。如果我们做816次猜测(23.24)至于下一个代币是什么，我们很可能猜对了!
Eclipse建议插件我们构建了一个Eclipse插件来测试这个想法。与许多其他ide一样，Eclipse有一个内置的建议引擎，在可能的情况下建议下一个令牌。Eclipse(和其他ide)建议通常基于上下文中可用的类型信息。我们推测基于语料库n-gram模型建议引擎(为简单起见，NGSE)可以增强eclipse内置的建议引擎(为简单起见，ECSE)，通过提供代币自然从相关语料库中前面的内容中查找。
的NGSE使用从lexxed项目的语料库构建的三元模型。在代码的每一点上，NGSE使用已经输入到文本缓冲区的前两个令牌，并尝试猜测下一个令牌。从语料库构建的语言模型给出了下一个标记的特定选择的概率的最大似然估计;这个概率可以用来对可能的下一个代币进行排序。我们的实现产生排序建议的平均时间不到0.2秒。这两个NGSE而且ECSE提出许多建议。展示所有的东西会让人不知所措。因此，我们定义了一个启发式来合并来自两组的列表:给定一个可接受的数字n的建议
要显示给用户，请选择n两方面的候选人NGSE的年代,ECSE的报价。
我们观察到，总的来说，NGSE善于推荐更短的令牌,ECSE更适合于较长的标记(我们将在本节后面讨论这种现象的原因)。这就提出了一个简单的合并算法均方误差，在算法1中定义。每当Eclipse在顶部提供长令牌(根据观察，我们选择7作为盈亏平衡长度)时n，我们贪婪地摘取所有的顶端nEclipse提供的服务。否则，我们从Eclipse中选择一半，从我们的n克模型。
MSE和MSE的相对性能ECSE在实际操作中，这可能取决于许多因素，并需要进行控制良好的大规模人体研究。建议引擎可以显示更多或更少的选择;它可以提供所有的建议，也可以只提供很长的建议。建议可以通过触摸屏、鼠标或向下箭头键来选择。由于我们这里的目标是衡量基于语料库的语言模型的能力，而不是构建最用户友好的合并建议引擎(这有待将来的工作)，我们进行了一个自动化的实验，而不是一个人类主题研究。
我们在实验中控制了两个因素:建议的字符串长度l，以及选择的数量n呈现给用户。我们不断地重复这个实验n,因为n= 2,6,10和l,因为l= 3,4,5，…, 15。我们省略了少于3个字符的建议，因为没有用。此外，在合并两个建议列表时，我们选择从每个列表中至少选择一个，因此n2.我们认为10个以上的选择将是压倒性的，尽管我们的研究结果在16个和20个选择中并没有太大的变化。我们选择5个项目进行研究:Ant、Maven、Log4J、Xalan和Xerces。在每个项目中，我们留出一个由40个随机选择的文件(总共留出200个)组成的测试集，并在每个项目的其余文件上构建一个三元语言模型。然后我们使用均方误差而且ECSE算法预测40个预留文件中的每一个标记，并评估有多少更多的倍均方误差提出了一个成功的建议，当比较基本ECSE。在每种情况下，我们都评估了均方误差在ECSE，以每种因素组合下正确建议数量的增加(百分比和绝对)来衡量n而且l
语言模型如何提供帮助?图3给出了6个建议案例的结果。该图有两个y刻度:左边(黑圈点)是额外正确建议的百分比，右边(红色方框点)是原始计数。从Eclipse引擎的成功建议的原始计数开始ECSE也随长度递减，这两种方法都有用。均方误差提供可衡量的优势ECSE对于2、6和10个建议，以及对于所有令牌字符串长度;但是，这种优势通常会随着令牌长度的增加而减弱。通过6个字符的标记的增益是相当可观的，在语言模型中有3367%的额外建议是正确的;在7到15个字符之间，增益范围在3%到16%之间。与6个建议案例相比(图3)， 2个建议的增益较强，10个建议的增益较低。
来自NGSE运行整个范围，包括方法、类和从语料库中频繁的三元词中可预测的字段(例如，println，迭代器，IOException，附加，toString, assert -quals，转换)、包名称(例如，Apache, tools, util, Java)以及语言关键字(例如，导入，公开，返回，这个)．对这些符号的检查揭示了为什么n-grams方法通过更短的令牌增加最大价值。我们建立的语言模型是基于所有系统中的文件，以及最频繁的n-grams是那些在所有文件中经常出现的。在语料库中，我们发现编码员倾向于为使用更广泛、更频繁的实体选择更短的名称;这些自然会产生更强的信号，被大脑接收n-gram语言模型。这里值得重复的是，有很大一部分，即50%的成功建议不是从语言上下文猜测的Java关键字，而是特定于项目的令牌。这加强了我们的主张，即统计语言模型在项目语料库中捕获了重要级别的局部规律性。
在下面的表格中，我们提出了一种看待……的好处的不同方法均方误差；使用底座节省的击键总数ECSE，(第一行)的均方误差(第二行)和从使用中获得的百分比均方误差．在这里，我们使用一个特定的语言模型来增强一个特定的软件工具，建议引擎。通过对语法、作用域、类型和语义现象进行建模的更复杂的技术，我们期望获得更低的熵，从而在这个和其他软件工具中获得更好的性能。我们邀请读者下载我们的Eclipse建议插件CACHECAf，11基于缓存增强的位置敏感n克模型,49改进的合并启发式。
5.相关工作
有一些相关的研究领域，这一行的工作可以合理的背景。
代码完成和建议完成是完成部分输入的令牌的任务;建议建议使用完整的令牌。第4节是关于建议引擎。
现代、成熟的软件开发环境(sde)提供代码完成和代码建议，通常使用统一的接口。两个著名的基于java的开源例子是Eclipse和IntelliJ IDEA。在我们的工作中，这些工具从现有的代码中提取可能的完成，但建议的方法是根本不同的。
Eclipse和IntelliJ IDEA响应程序员的完成请求(一个键盘快捷键，如ctrl + space)，通过推断在当前语法上下文中“可能应用”的标记。在这里，这些工具主要由Java编程语言语义指导。例如，Eclipse和IntelliJ IDEA都通过解析可用的源代码和创建期望的令牌类型的简短列表来响应完成请求。如果该列表包含引用类型，则工具使用类型系统的规则将当前定义的类型名列表添加到补全列表中。类似地，如果需要变量，则工具使用符号表中可见的名称。Eclipse和IDEA为各种类型的语法构造实现了许多这样的“语法和语义规则”。作为最后一步，这两个工具都用一组明显手工编码的启发式方法对完成进行排序。
我们的方法是互补的。而不是利用语言的语义和直接语境，去猜测什么可能应用,我们的n-gram语言模型捕获了什么大多数情况下适用。我们的方法提供了更大的灵活性，也有可能更加精确:通常使用的补全空间自然比“语言允许的”补全空间小得多。此外，我们的方法可以增强(或排序)基于语义的建议和补全。值得注意的是，也许软件的“自然性”的一些最有力的证据是我们的完成原型的功能有多好尽管没有使用语义信息。
有一些方法可以说比当前ide中可用的方法更先进。Bruch等人的BMN补全算法。8专注于寻找最有可能的方法调用可能通过使用方法调用的频率和在类似情况下的预先使用来完成表达式。我们为在软件工具中使用代码语料库的语言模型提出了一个广阔的设想。我们特定的说明性完成应用程序有更广泛的完成目标，完成所有类型的令牌，而不仅仅是方法调用。后来，布鲁赫等人。7为利用语料库和人类行为记录中体现的“集体智慧”的下一代ide制定了一个愿景。我们非常赞同，并建议使用来自NLP的语言模型来获取这种智慧。
罗布斯和兰扎42比较一组以multi-开头的不同方法调用和类名称补全策略信前缀。他们介绍了一种基于历史的方法，并证明它提高了性能。我们的方法可以通过添加语言模型来补充基于历史的方法。Han等人。14使用隐马尔可夫模型(HMM)从缩写中推断可能的标记。他们利用动态规划网格方法进行回溯和建议。他们的HMM实际上是一种语言模型，但论文没有描述它的有效性，也没有描述它在没有用户提供的缩写的情况下完成任务的效果。
雅各，大拉19使用n-gram语言模型用于不同的应用程序:查找与部分编程任务相关的匹配代码克隆。语言模型建立在克隆组上(不是我们建议的整个语料库)，用于检索和呈现与部分完成的编码任务相关的候选克隆。
Hou和Pletcher17使用特定于上下文的API信息，以便使用静态类型对Eclipse代码完成进行排序。用户可以过滤掉未来的完成建议。
代码中名称的“自然性”有一项工作是自动评估代码中实体名称的质量，询问“名称是否反映了工件的含义，如果没有，如何改进它们。6，27?”由Høst和Østvold创作15，16还涉及到方法命名:他们将静态分析与基于熵的度量结合起来，对语料库中方法的简单语义属性分布进行测量，以确定哪些方法名称具有最大的歧视性，并使用它来检测使用方法与语料库不一致的名称。
总结和关注位置关于代码摘要的一行工作9，47，48使用静态分析推断出的语义属性，而不是统计模型中软件语料库的“自然”规律;它是对我们的补充:静态分析得到的属性(只要它们能有效地、大规模地完成)可以用来丰富大型软件语料库的统计模型。另一项工作是寻找与特定关注相关的代码部分(例如，“place auction bid”)，这些代码可以是本地的，也可以是横切的，基于代码名称的片段，44从代码中挖掘的事实，40或者代码中相关单词的同时出现。45
NLP和要求研究人员研究了自然语言在需求工程中的使用:“我们能否利用自然语言规范自动生成更正式的规范，甚至代码?”25，26，43其中一些方法使用了NLP工具，如解析器和词性标记器。我们的方法考虑的是……的“自然性”代码，体现在从大量工件语料库构建的统计模型中;然而，我们也考虑(在未来的工作中)使用对齐(代码/自然语言)语料库的可能性，如代码摘要或代码搜索，这可以被视为翻译任务。
软件矿业在这个非常活跃的领域工作51目的在于采矿有用的信息从软件仓库。在ICSE的MSR系列会议中可以找到许多论文，代表作包括挖掘API的使用，12，30.错误的模式，21，29主题提取,28指导修改,52还有其他几个。使用的方法各不相同。我们认为软件的“自然性”提供了一种概念上的角度为本工作，也提供了一些新颖实现方法。的概念上的角度基于这样一个观点有用的信息往往在软件中以统一、不复杂的方式表现出来;的实现方法表明可以从一个大型的、有代表性的软件语料库中确定有用事实的统一和简单的表示，在这个语料库中，所需的信息已经知道并注释了。该语料库可用于估计所需信息与容易观察到的事实之间的统计关系;这种关系可用于在与语料库相似的新程序中可靠地查找相似信息。我们将在以后的工作中进一步解释这一点(第6.3和6.4节)。
6.未来的发展方向
在大型代码语料库上估计的统计模型在软件工程应用中具有巨大的前景。我们在下面列出了一些应用。
6.1.改进的语言模型
在本文中，我们利用了一个公共语言模型(n-grams)，有效地捕捉了局部规律性。有几个扩展的途径。现有的非常大的代码体可以很容易地进行解析、类型化、限定范围，甚至进行简单的语义分析。所有这些都可以使用增强的语言模型进行建模，以捕获存在于语法、类型、范围甚至语义级别的规则。
这里有一个难点:一个模型越丰富，就需要越多的数据来为模型参数提供良好的估计;因此，当我们丰富我们的模型时，数据稀疏的风险就会增加。类似于在n-gram模型必须进行调整和应用，以建立更丰富的软件语料库模型。在后续的工作中，研究人员利用了类型模型，38语法模型,1，35范围,49简单的数据流信息，41完成各种任务。最近的工作还探索了代码建模的深度学习方法。50可以在模型中捕获并利用语法、类型、范围甚至语义属性中的规律。例如，坎贝尔等人。10通过使用工作代码训练的语言模型将会惊讶于语法错误这一事实来诊断语法错误位置。实际上，软件工程任务中有许多潜在的应用程序，其中一些我们将在下面进一步讨论。
6.2.可访问性的语言模型
有些程序员因为肢体重复性劳损或视力障碍，使用键盘有困难。先前的工作探索了使用语音识别(例如，参考文献。3.，4，18)寻求协助。然而，由于相当高的识别错误率，采用一直受到限制。33已经发布的方法都没有使用针对特定代码语料库训练的统计语言模型。使用特定于代码的语言模型肯定会降低错误率，就像传统的语音识别引擎一样。许多开发工作发生在维护或再工程上下文中，其中有足够的数据可用于模型估计。即使只有少量的相关代码存在，语言模型适应，5和缓存49可以应用。
6.3.机器翻译的应用
考虑一下用英语总结代码片段(或更改代码)的任务。再考虑一下近似的反向任务:找到/检索给出英文描述的相关代码片段(例如，方法调用)。我们把这两个问题作一个类比统计自然语言翻译（出发)．代码和英语是两种语言，基本上上面两者都是翻译任务。出发依赖于访问对齐语料库这是一组大量的句子同时以两种或两种以上的语言呈现(例如，议会议事程序，或圣经经文)。考虑一下翻译泰米尔语句子的问题T一个英语句子e .出发使用一个简单的贝叶斯公式来计算最可能的英语翻译;它在所有可能的英语句子中最大化了这个等式的右手大小艾凡:
对于一个给定的T，分母是常数，只要分子最大化。分子内部是条件分布p（T|E)估计使用E-T对齐语料库中的对;p（E)由基于英语语料库估计的语言模型提供。这个公式显然也适用于反向翻译任务。与代码摘要/检索任务的类比是显而易见的:给定一个代码片段C，写出英文摘要E；或者，相反地，检索一个代码片段C给定一个英语问题E。对于前一个(总结)任务，我们需要条件分布p（C|E)和一个语言模型p（E)．
首先，如何估计条件分布p（C|E) ?有几个有前途的对齐(英语/代码)语料库来源。考虑一个项目的版本历史。每次提交都可能提供一对匹配的日志消息(英文)和一些更改(代码)。其次，许多内联注释可以与附近的代码匹配。2堆栈溢出的帖子(包括问题和答案)通常包含密切相关的代码和文本。接下来,考虑p（E):有关代码的相关(自然语言)语料库可以在与项目相关的英文文本中找到，例如，代码注释、文档、bug报告、邮件列表讨论等。我们可以这样估计p（E)．这些p（C|E),p（E)模型然后可以选择最大可能的代码片段给出英文描述如上所示;反向任务将使用p（E|C),p（C)模型，这些模型也是类似可估的。这种方法也可以使用代码的语义属性;然而，与布斯和韦默不同的是，9谁单独记录每个更改的语义，我们将使用大型对齐的代码/文本语料库的语义属性统计。
语言或方言之间的移植是另一个潜在的应用;Nguyen及其同事34，36，37已经利用了Java和c#中的跨平台应用程序的可用性，通过方法级对齐，来训练翻译模型，并学习API映射。Karaivanov等人。20.以类似的方式进行上述工作。
6.4.软件工具
我们假设软件的“自然性”意味着软件更深层次属性的“自然性”，比如那些通常由强大但昂贵的软件工具计算出来的属性;我们假设(因为程序往往是重复的)程序的更深层次、语义属性更多也在程序中以表面相似的方式表现出来。更具体地说，我们假设语义属性是通常体现在肤浅的这些方法在检测上计算成本较低，特别是与通过可靠的(或完整的)静态分析确定这些特性的成本(甚至是不可行性)相比。如果可行，人们可以利用这个概念在各种各样的设置中构建简单、可扩展和有效的近似，就像我们现在所描述的那样。
考虑一个计算函数的软件工具的非常通用的公式f在一个系统上年代，来自系统领域年代因此:
范围在哪里D表示通过分析得到的事实，例如，一个可能的别名事实，一个挖掘的规则(例如，API协议)，一个错误消息(例如，缓冲区溢出警告)，甚至是输入系统的一个新的转换版本年代年代．我们假设函数f一般来说，计算起来很昂贵，甚至是不可行的，因此在实践中容易产生近似误差和计算延迟。我们通过估计来重新表述这个问题f用另一种公式，
，它选择最有可能的的价值f（年代)，给出一组易于计算和易于观察的证据特征e1（年代)，e2（年代),…特性e我（年代)是“症状”;他们是不决定性的，结论性的证据f（年代)有一定的性质，但仍然为概率信仰提供了不同程度的理由。
这种观点有一个贝叶斯公式。表示概率d系统持有年代，考虑到观察到的证据e我（年代)：
右边的分布可以通过大型语料库进行估计。对于一个特定的系统，分母是一个常数。分子是先验分布p（d的输出域上f，可以通过在语料库中的观察来估计(例如，“缓冲区溢出错误发生的频率是多少?”“不同的协议模式发生的频率如何?”等等)。在没有这类信息的情况下，可以选择无信息的(统一的)先验。
接下来，我们估计结论之间的关联(可能性)的强度d观察到的特征e1（年代)…en（年代)。p（e1（年代)，e2（年代),…en（年代) |d)可视为在输出域属性时语料库中特征观察的条件频率d成立。这个术语需要有一个带有属性注释的语料库d。即使在某些情况下d必须手动注释，我们认为这样的语料库可能值得投资(与Penn Tree Bank32)，可以使用志愿者开放源码社区，或者像土耳其机械这样的市场机制来构建。22
最后，假设合适的模型，使计算p（d|年代)可以估计，我们写出备选的概率函数选择最有可能的d：
我们需要补充的是，这个贝叶斯公式只是为了提供一种直观的理解，即如何以原则性的方式使用基于语料库的统计数据，以帮助构建近似的软件工程工具。在实践中，机器学习公式(如决策树、支持向量机，甚至是简单的回归模型)可能被证明更方便。
Raychev等人。41用一个在模糊代码中猜测变量有用名称的应用程序演示了这个想法。变量名由程序员选择来表示语义属性;具有明确名称的代码库可以用于培训。使用非常简单的数据流属性(很容易从语法中推导出来)作为预测特征，以及上述想法的对数线性公式，他们能够猜测出有用的变量名。
7.结论
尽管语言学家(有时)陶醉于自然语言的理论复杂性，但在实践中，大多数“自然”话语是相当规则和可预测的，实际上可以用严格的统计方法建模。这一事实彻底改变了计算语言学。我们为软件提供了支持类似主张的证据:虽然软件在理论上可能非常复杂，但在实践中，似乎即使是一个相当简单的统计模型也能捕获“自然”软件中惊人数量的规律性。这个简单的模型足够强大，可以让我们快速轻松地实现一个相当强大的建议引擎，它已经改善了最先进的IDE。我们还对未来的工作进行了展望。具体而言，我们认为自然语言翻译方法可以对称地用于代码总结和代码搜索;我们还假设，软件的“自然性”意味着软件更深层次属性的某种“自然性”，比如那些通常由强大的传统软件分析工具计算出来的属性。这些都是具有挑战性的任务，但可能会带来很高的回报，我们希望其他人能加入我们的工作。
鸣谢
本材料基于国家科学基金会资助的1445079,1247280,1414172项研究。
参考文献
1.Allamanis, M, Sutton, C.从源代码中挖掘习语。在工程师协会．ACM, 2014年。
2.Antoniol, Canfora, G, Casazza, G, Lucia, ad, Merlo, E.恢复代码和文档之间的可追溯性链接。IEEE反式。Softw。Eng。28(2002), 970983。
3.Arnold, S.， Mark, L.， Goldthwaite, J.语音编程，语音编程。在ACM辅助技术会议论文集。中国科学院学报，2000,149155。
4.软件开发的口语支持。在诉讼中,六世/肝癌。计算机工程学报，2004,27(3):447 - 447。
5.统计语言模型适应:回顾与展望。言语通讯， 1(2004)， 93108。
6.Binkley, D.， Hearn, M.， Lawrie, D.利用词性信息提高标识符的信息性。在诉讼,MSR。ACM, 2011年。
7.Bruch, M, Bodden, E, Monperrus, M, Mezini, M. Ide 2.0:软件开发中的集体智慧。在软件工程研究的未来FSE/SDP研讨会论文集。中国科学院学报，2010，
8.Bruch, M.， Monperrus, M.， Mezini, M.从实例中学习以改进代码完成系统。在ACM SIGSOFT ESEC/FSE论文集, 2009年。
9.busse, R, Weimer, W.自动记录程序更改。在诉讼,日月光半导体。Acm, 2010, 3342。
10.Campbell, j.c.， Hindle, A, Amaral, J.N.语法错误是不自然的:用语言模型改进错误报告。在MSR。ACM, 2014年。
11.Franks, C.， Tu, Z.， Devanbu, P.， Hellendoorn, V. Cacheca:基于缓存语言模型的代码建议工具。ICSE发展。跟踪(2015)。
12.贾贝尔，M，苏，Z.沙威:从动态轨迹中自动挖掘一般时间属性。在ACM SIGSOFT FSE论文集。学报，2008,339349。
13.苏卓。源代码独特性的研究。在ACM SIGSOFT FSE论文集。中国科学院学报，2010，
14.汉，华莱士，d.r.，米勒，R.C.代码完成从缩写输入。在日月光半导体。计算机工程学报，2009,36(3):359 - 361。
15.Høst, e.w.， Østvold, B.M.软件语言工程。Java程序员术语手册。斯普林格-弗拉格，柏林，海德堡，2009年。
16.Høst, E.， Østvold, B.调试方法名称。在程序ECOOP。施普林格，2009,294317。
17.为代码完成的API方法的排序、过滤和分组策略的评估。在诉讼中,ICSM, 2011年。
18.Hubbell, T, Langan, D, Hain, T.一个语音激活的语法导向编辑器，用于手动禁用程序RSACM SIGACCESS论文集。ACM, 2006年。
19.使用语言模型的代码模板推理。在第48届东南地区年会论文集,2010年。
20.卡拉万诺夫，瑞切夫，维切夫，M.基于短语的编程语言统计翻译。在向前!Acm, 2014, 173184。
21.Kim, S, Pan, K, Whitehead, E. Jr. bug修复的记忆。在ACM SIGSOFT FSE论文集。Acm, 2006, 3545。
22.Kittur, A.， Chi, E.， Suh, B.使用机械土耳其的众包用户研究。在诉讼中,太极拳。ACM, 2008年。
23.识字编程。第一版。j . 21， 2(1984)， 97111。
25.Konrad, S.， Cheng, B.实时规范模式。在诉讼ICSE,2005年。
26.Körner, S.J, Tichy, W.F.文本到软件。在关于软件工程研究未来的FSE/SDP研讨会论文集。ACM, 2010年11月。
27.劳瑞，D，莫雷尔，C，菲尔德，H，宾克利，D，名字有什么意义?标识符的研究。诉讼中,ICPC, 2006年。
28.Linstead, E.， Bajracharya, S.， Ngo, T.， Rigor, P.， Lopes, C.， Baldi, P. Sourcerer:挖掘和搜索互联网规模的软件仓库。数据挖掘知识。18。， 2(2009)， 300336。
29.Livshits, B.， Zimmermann, T. Dynamine:通过挖掘软件修订历史发现常见错误模式。ACM SIGSOFT软件。Eng。指出305(2005)。
30.Mandelin, D.， Xu, L.， Bodík, R.， Kimelman, D. Jungloid mining:帮助导航API丛林。在ACM SIGPLAN通知。40卷。ACM, 2005年。
31.C.曼宁，Schütze;统计自然语言处理基础“，”卷59。麻省理工学院出版社，1999。
32.Marcus, M.， Marcinkiewicz, M.， Santorini, B.建立一个大型的英语注释语料库:宾州树库。第一版。语言学家。19， 2(1993)， 313330。
33.米尔斯，Saadat, S. Whiting, D.语音识别是基于键盘的肢体重复性劳损的解决方案吗?在自动化大会，2006。WAC 06年。世界, 2006年。
34.Nguyen, A.T, Nguyen, H.A, Nguyen, T.T, Nguyen, T.N.用于代码迁移的API使用映射挖掘的统计学习方法。在日月光半导体, 2014年。
36.语言迁移的词汇统计机器翻译。在工程师协会, 2013年。
37.Nguyen, a.t.， Nguyen, t.t.， Nguyen, T.N.迁移代码与统计机器翻译。在ICSE同伴, 2014年。
38.Nguyen, t.t.， Nguyen, a.t.， Nguyen, H.A, Nguyen, T.N.一种用于源代码的统计语义语言模型。在ESEC工程师。ACM, 2013年。
39.平克,S。语言本能:语言与思维的新科学。7529卷。企鹅，伦敦，英国，1994年。
40.Rastkar, S.， Murphy, G.C, Bradley, A.为横切源代码问题生成自然语言摘要。在诉讼中,ICSM, 2011年。
41.瑞切夫，维切夫，M.，克劳斯，A.从大代码预测程序属性。在POPL。ACM, 2015年。
42.robes, R, Lanza, M.利用程序历史改进代码完成。奥特曼。Softw。Eng。17， 2(2010)， 181212。
43.Rolland, C, Proix, C.需求工程的自然语言方法。在高级信息系统工程“，”施普林格，1992,257277。
44.Shepherd, D.， Fry, Z.， Hill, E.， Pollock, L.， Vijay-Shanker, K.使用自然语言程序分析定位和理解面向行动的关注。在诉讼,AOSD。中国沙漠，2007,212224。
45.Shepherd, D.， Pollock, L.， Tourwé， T.使用语言线索发现横切关注点。在ACM SIGSOFT软件工程笔记。卷30。ACM, 2005年。
46.自然语言处理:历史回顾。vwin德赢AC米兰官网网址计算语言学的当前问题:纪念唐·沃克(Ed Zampolli, Calzolari和Palmer)。Kluwer，荷兰阿姆斯特丹，1994年。
47.Sridhara, G.， Hill, E.， Muppaneni, D.， Pollock, L.， Vijay-Shanker, K.为Java方法自动生成摘要注释。在诉讼中,日月光半导体,2010年。
48.Sridhara, G, Pollock, L, Vijay-Shanker, K.自动检测和描述方法中的高级操作。在诉讼中,ICSE, 2011年。
49.涂志强，苏志强，德凡布，P.论软件的本地化。在工程师协会。学报，2014,269280。
50.C. White, M. Vendome, Linares-Vásquez, M. Poshyvanyk, D.面向深度学习软件库。在MSR, 2015年。
51.谢涛，罗丹，刘聪。基于数据挖掘的软件工程。IEEE计算， 8(2009)。
52.Zimmermann, T.， Weisgerber, P.， Diehl, S.， Zeller, A.挖掘版本历史以指导软件更改。在ICSE。IEEE计算机学会，2004。
脚注
b.事实上，统计方法的著名先驱弗雷德·耶利尼克(Fred Jelenik)据说曾感叹:“每当有语言学家离开我们的小组，我们的语音识别性能就会提高!”看到http://en.wikiquote.org/wiki/Fred_Jelinek．
d。http://en.wikipedia.org/wiki/Cross_entropy；参见参考文献31，第2.2节，第75页，式(2.50)。
e.我们从http://www.nltk.org/．
f。http://macbeth.cs.ucdavis.edu/CACHECA．
本文的原始版本发表在第34届软件工程国际会议论文集(2012), 837847。这五位作者当时都在加州大学戴维斯分校。
数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.
没有找到条目