没有合适的资源?快使用搜索试试~ 我知道了~
程序修复:类型错误反馈分析
160通过分析程序修复提供类型错误反馈0Georgios Sakkas计算机科学与工程加利福尼亚大学圣地亚哥分校洛杉矶,美国gsakkas@eng.ucsd.edu0Madeline Endres计算机科学与工程 密歇根大学安娜堡,美国endremad@umich.edu0Benjamin Cosman计算机科学与工程加利福尼亚大学圣地亚哥分校洛杉矶,美国blcosman@eng.ucsd.edu0Westley Weimer计算机科学与工程 密歇根大学安娜堡,美国weimerw@umich.edu0Ranjit Jhala 计算机科学与工程加利福尼亚大学圣地亚哥分校洛杉矶,美国 jhala@cs.ucsd.edu0摘要我们引入了分析程序修复,这是一种通过修复错误程序来提供类型错误反馈的数据驱动策略。我们的策略基于相似的错误有相似的修复的洞察力。因此,我们展示了如何使用一组训练数据对不正确类型的程序及其修复版本进行训练,以:(1)通过将训练集中的编辑抽象和分区为一组代表性的模板,学习一组候选修复模板;(2)通过在训练集中使用的修复模板上训练多类分类器,预测给定错误的适当模板;(3)通过枚举和排名与预测模板匹配的正确(例如,良好类型的)术语,从模板中合成具体修复。我们已经在OCaml程序的类型错误报告工具Rite中实现了我们的方法。我们对来自一个入门编程课程的两个实例的4,500个不正确类型的OCaml程序的准确性和效率进行了评估,并进行了用户研究,评估了生成的错误消息的质量,结果显示位置和最终修复质量优于现有工具,具有统计显著性。0CCS概念:∙软件及其工程→通用编程语言;自动编程;∙计算方法→机器学习;∙计算理论→抽象。0允许个人或课堂使用者制作本作品的全部或部分数字或硬拷贝,无需付费,前提是不得为了盈利或商业优势而制作或分发拷贝,并且拷贝必须带有本通知和第一页的完整引用。必须尊重ACM以外的其他人拥有的本作品组成部分的版权。允许带有信用的摘要。要进行其他复制、再发表、在服务器上发布或重新分发到列表中,需要事先获得特定的许可和/或费用。请向permissions@acm.org请求权限。PLDI'20,2020年6月15日至20日,英国伦敦,英国©2020年计算机协会。ACM ISBN 978-1-4503-7613-6/20/06...$15.00https://doi.org/10.1145/3385412.33860050关键词:类型错误反馈,程序合成,程序修复,机器学习0ACM参考格式:Georgios Sakkas,Madeline Endres,BenjaminCosman,Westley Weimer和RanjitJhala。2020年。通过分析程序修复提供类型错误反馈。在第41届ACMSIGPLAN国际编程语言设计和实现会议(PLDI'20)论文集中,2020年6月15日至20日,英国伦敦。ACM,美国纽约,纽约,15页。https://doi.org/10.1145/3385412.338600501引言具有Hindley-Milner风格的基于统一的推理的语言提供了静态类型的好处,但注释开销很小。然而,问题在于程序员必须首先攀登与理解编译器生成的错误消息相关的陡峭学习曲线。虽然专家通常可以轻松解读这些错误,并将其视为程序开发和重构的宝贵辅助工具,但新手通常感到困惑和沮丧,对问题没有明确的了解[41]。由于这个问题的重要性,一些作者提出了帮助调试类型错误的方法,通常是通过将程序切片到有问题的位置[12,31],通过枚举可能的原因[6,21],或者通过使用MAX-SAT[30],贝叶斯[43]或统计分析[37]对可能的位置进行排名。尽管有价值,但这些方法最多只能帮助定位问题,但学生仍然对如何修复他们的代码一无所知。0修复作为反馈。最近的几篇论文提出了一个鼓舞人心的新攻击反馈问题的方法:使用综合技术提供修复作为学生改进代码的反馈。这些修复可以通过在专家定义的修复模型所限定的候选程序空间中进行符号搜索来找到。然而,对于类型错误,候选修复的空间是巨大的。目前还不清楚是否存在一小组修复模型,甚至如果存在,它们是什么样子的。更重要的是,为了扩展,关键是170PLDI '20,2020年6月15日至20日,英国伦敦,Georgios Sakkas,Madeline Endres,Benjamin Cosman,Westley Weimer和Ranjit Jhala0我们消除了专家精心策划一些候选修复的要求。或者,我们可以通过观察到相似的程序具有相似的修复来生成修复,即通过计算从学生解决方案到最接近的正确程序的差异。然而,这种方法需要一组相似的程序,其语法树或执行跟踪可以用来将每个错误程序与一个被用于提供反馈的“正确”版本进行匹配。具有静态类型错误的程序没有执行跟踪。更重要的是,我们希望为新的由新手编写的程序生成反馈,因此不能依赖于与某个(现有的)正确程序进行匹配。0分析性程序修复。在这项工作中,我们提出了一种新颖的错误修复策略,称为分析性程序修复,它使用监督学习而不是手工制作的修复模型或与正确代码语料库的匹配。我们的策略基于一个关键的洞察:相似的错误有相似的修复,并通过使用一组有类型错误程序和它们的修复版本的训练数据集来实现这个洞察:(1)通过将训练集中的编辑抽象和分区为一组代表性的模板,学习一组候选修复模板;(2)通过在训练集中使用的修复模板上训练多类分类器,预测给定错误的适当模板;(3)通过枚举和排名与预测模板匹配的正确(例如,有类型的)术语,从模板中合成具体的修复,从而为候选程序生成修复。关键是,我们展示了如何将特定程序从具体错误抽象为抽象错误,通过将程序表示为抽象术语的集合(BOAT),即语法和语义特征的数值向量。这种抽象使我们能够在高级代码特征上训练预测器,即学习导致错误和相应修复之间的相关性,使分析方法能够推广到与现有程序的匹配之外。0Rite。我们已经在Rite中实现了我们的方法:一种用于OCaml程序的类型错误报告工具。我们在一个包含超过4500个有类型错误的OCaml程序集上对Rite进行训练(和评估),这些程序来自于两年的入门编程课程。给定一个新的有类型错误的程序,Rite会生成一个按可能性排名的潜在解决方案列表和一个编辑距离度量。我们以几种方式评估Rite。首先,我们衡量其准确性:我们展示了当考虑前三个模板时,Rite在69%的情况下正确预测正确的修复模板,并且当考虑前六个模板时超过80%。其次,我们衡量其效率:我们展示了Rite能够在20秒内70%的时间内合成一个具体的修复。最后,我们通过一个包含29名参与者的用户研究来衡量生成的消息的质量,并展示人们认为Rite的编辑位置和最终修复质量都比生成的那些更好。0通过Seminal,一种最先进的OCaml修复工具[21]以统计显著的方式。02概述我们首先概述了我们通过学习初学者程序员修复程序的过程来建议故障程序的修复方法的方法。01 let rec mulByDigit i l = 2 match l with 3 | [] -> [] 4 | hd::tl-> (hd * i) @ mulByDigit i tl01 let rec mulByDigit i l = 2 match l with 3 | [] -> [] 4 | hd::tl-> [hd * i] @ mulByDigit i tl0图1.(顶部)一个类型不正确的OCaml程序,应该将列表中的每个元素乘以一个整数。(底部)学生修复的版本。0问题。考虑图1顶部显示的mulByDigit程序,该程序由一位本科编程课程的学生编写。该程序旨在将列表中的所有数字与整数位相乘。学生错误地错误使用了列表追加运算符(@),将其应用于数字和列表,而不是两个列表。对于那些仍在建立类型检查器工作原理心智模型的初学者学生来说,编译器的错误消息经常让他们困惑[26]。因此,初学者通常需要很长时间才能得出适当的修复方法,例如图1底部所示的修复方法,其中使用@与包含头部hd和i的乘法的单例列表。我们的目标是利用程序员在修复其程序中类似错误时的历史数据,自动快速地引导初学者提出类似上述修复方法的候选解决方案。0解决方案:分析性程序修复。一种方法是将候选修复的搜索视为综合问题:综合出一组(小)的程序编辑,以产生一个良好的(例如,类型正确的)修复。关键挑战是确保综合是可行的,通过将修复限制在一个可有效搜索的空间内,并且精确,以便搜索不会错过错误程序的正确修复。在这项工作中,我们提出了一种称为分析性程序修复的新策略,它通过将问题分解为三个步骤来实现可行和精确的搜索:首先,学习一组广泛使用的修复模板。其次,预测每个错误程序应用的正确修复模板。第三,从预测的模板中综合候选修复。在本节的其余部分,我们通过描述如何:1.通过修复模板抽象地表示修复(见2.1节),180通过分析性程序修复解决类型错误反馈问题PLDI '20,2020年6月15日至20日,英国伦敦02.获取一组带有标签的类型不正确的程序和修复的训练集(见2.2节),3.通过对训练集进行分区来学习一小组候选修复模板(见2.3节),4.通过从训练集中训练多类分类器来预测适当的模板应用(见2.4节),以及5.通过枚举和检查从预测模板中的术语来综合修复,以向程序员提供局部化反馈(见2.5节)。02.1 表示修复0我们对修复的概念定义为在特定程序位置将现有表达式替换为新的候选表达式。例如,mulByDigit程序通过将(hd *i)替换为表达式[hd *i]来修复。我们专注于AST级别的替换,因为它们既紧凑又足够表达修复。0通用抽象语法树。我们通过称为通用抽象语法树(GAST)的抽象修复模板来表示不同可能的候选表达式,每个模板对应于许多可能的表达式。GAST是通过两个步骤从具体的AST中获得的。首先,我们抽象具体的变量、函数和运算符名称。然后,在特定深度�处修剪GAST,仅保留修复的顶层更改。修剪的子树被替换为“空洞”,可以表示语言中的任何可能表达式。这些步骤确保GAST仅包含有关修复的结构信息,而不是变量和函数的具体更改。例如,在mulByDigit示例中,修复[hd *i]由表达式[_ ⊕_]的GAST表示,其中变量hd和i被抽象为空洞(例如,通过在深度�=2处修剪GAST),*由抽象二元运算符⊕表示。我们的方法类似于Lerner等人的方法[21],其中使用AST级别的修改,但是我们提出的GAST表示更抽象的修复模式。02.2获取修复标记的训练集以前的工作使用专家创建一组有错误类型的程序及其修复版本[21,22],或者手动创建修复模板[16],可以产生修复补丁[24,25]。这些方法很难扩展以生成适用于机器学习的数据集。而且,它们无法发现新手错误类别及其修复在实践中的频率。相比之下,我们展示了这样的修复模板可以从一个大型的、自动构建的带有修复标记的错误类型程序训练集中学习得到。我们的数据集中的修复表示为学生在错误类型程序中更改的表达式的AST,将其转化为正确解答。0交互追踪。根据[37]的方法,我们从交互追踪中提取了一个带有错误程序和其修复版本的标记数据集。通常学生会编写多个版本的程序,直到达到编程作业的正确解答。我们使用一个带有仪器的编译器来捕获这些学生程序的序列(或追踪)。这个序列中的第一个类型正确的解答被认为是之前所有解答的修复版本,因此为每个解答对将其添加到数据集中。对于每个程序对,我们生成它们的抽象语法树(AST)的差异,并将修复标签分配为正确和错误尝试之间发生变化的最小子树。0直到他们达到编程作业的正确解答为止。使用一个带有仪器的编译器来捕获这些序列(或追踪)的学生程序。这个序列中的第一个类型正确的解答被认为是之前所有解答的修复版本,因此为每个解答对将其添加到数据集中。对于每个程序对,我们生成它们的抽象语法树(AST)的差异,并将修复标签分配为正确和错误尝试之间发生变化的最小子树。02.3 学习候选修复模板0我们的数据集中的每个带有标签的程序都包含一个修复,我们将其抽象为一个修复模板。例如,对于图1中的mulByDigit程序,我们得到候选修复[hd * i],因此修复模板为[_ ⊕_]。然而,一个包含许多不同解决方案的修复标记程序的大型数据集可能会引入大量的修复模板,这可能不适合预测用于最终程序修复的正确模板。因此,我们方法的下一步是学习一组足够小的修复模板,以自动预测应用于给定错误程序的哪个模板,同时涵盖实践中出现的大多数修复。0修复模板的分区。我们通过对从数据集中获得的所有模板进行分区,然后选择一个单一的GAST来代表每个修复模板集中的修复模板,从而学习一组合适的小型修复模板。分区有两个目的。首先,它识别出一小组最常见的修复模板,从而使得可以使用离散分类算法来预测应用于新程序的模板。其次,它允许根据修复相似性关系将学生提交的非标准或个人化解决方案等异常值有原则地移除,这些异常值我们不希望用于建议修复。与以前使用聚类将相似程序分组在一起的修复方法不同(例如[11,42]),我们根据修复相似性关系将修复模板集合分区为它们的等价类。02.4通过多分类预测模板接下来,我们训练能够正确预测给定错误类型程序的错误位置和修复模板的模型。我们使用这些模型生成候选表达式作为可能的程序修复。为了降低预测正确修复模板和错误位置的复杂性,我们将这些问题分开,并将它们编码为两个不同的监督分类问题。0监督式多类别分类。我们提出使用监督式多类别分类问题来预测修复模板。监督式学习问题是指在给定标记的训练集的情况下,学习一个函数的任务。1let rec mulByDigit i l =2match l with3| []-> []4| hd::tl -> [𝑣1 * 𝑣2] @ mulByDigit i tl190PLDI '20,2020年6月15日至20日,英国伦敦,Georgios Sakkas,Madeline Endres,Benjamin Cosman,Westley Weimer和Ranjit Jhala0准确地将输入映射到输出标签,并且可以推广到未来的输入。在分类问题中,我们试图学习的函数将输入映射到两个或多个输出标签的离散集合,称为类别。因此,我们将将类型不正确的程序的子表达式映射到一小组候选修复模板的函数学习任务编码为多类分类(MCC)问题。0特征提取。我们将训练用于解决MCC问题的机器学习模型期望输入为带有标签的固定长度向量的数据集。因此,我们定义了将修复标记的程序转换为固定长度向量的转换。类似于Seidel等人[37],我们定义了一组特征提取函数�1,...,��,将程序的子表达式映射到数值(或仅用{0,1}编码布尔属性)。给定一组特征提取函数,我们可以通过将AST的�分解为其组成子表达式的集合{�1,...,��},然后用�维向量[�1(��),...,��(��)]这种方法在先前的工作中被称为抽象术语包(BOAT)表示法[37]。0通过MCC预测模板。我们可以更新我们的修复标记数据集,使标签表示修复每个位置的相应模板,这些模板来自通过分区获得的最小修复模板集。然后,我们在更新后的模板标记数据集上训练一个深度神经网络(DNN)分类器。神经网络的优点是将每个类别与置信度分数相关联,该分数可以解释为模型根据估计的分布对于给定输入的每个类别正确的概率。因此,置信度分数可以用于对新程序的修复模板预测进行排序,并在综合修复时按降序使用它们。利用机器学习的最新进展,我们使用深度和密集的架构[34]来进行更准确的修复模板预测。0错误定位。我们将在新程序中找到错误位置的问题视为二元分类问题。与模板预测问题相反,我们希望学习一个将程序的子表达式映射到表示错误存在与否的二进制输出的函数。因此,这个问题等价于只有两个类别的MCC问题,因此我们使用类似的深度神经网络架构。对于给定程序中的每个表达式,学习的模型输出一个置信度分数,表示它是一个需要修复的错误位置的可能性有多大。我们利用这些分数按置信度降序为每个位置综合候选表达式。02.5 从模板中合成反馈接下来,我们使用经典的程序综合技术来合成候选表达式,用于提供反馈。0向用户提供反馈。此外,综合过程是由预测的修复模板和一组可能的错误位置引导的,并将一个排名列表的最小修复返回给用户作为反馈。0程序综合。给定一组位置和这些位置的候选模板,我们试图解决程序综合的问题。对于每个程序位置,我们在语言的语法中搜索所有可能的表达式,找到一小组候选表达式,这些表达式与固定模板匹配并使程序通过类型检查。在综合过程中,还使用来自类型不正确的程序的表达式来修剪候选表达式的搜索空间。0多位置综合。通常情况下,不止一个位置需要修复。因此,我们不仅考虑综合的单个错误位置的有序集合,而是考虑其幂集。为简单起见,我们将不同的程序位置修复视为独立的;我们分配给一组位置需要修复的概率是它们各自置信度分数的乘积。这与最近的多块程序修复方法[33]不同,其中修改是相互依赖的。0修复排序。最后,我们通过两个指标,树编辑距离和字符串编辑距离,对每个解决方案进行排序。以前的工作[11,21,42]使用这些指标来考虑最小更改,即尽可能接近原始程序的更改,以便向初学者程序员提供更连贯的反馈。0图2. mulByDigit 程序的候选修复。0例子。我们在图2中看到了我们的方法可能返回的最小修复(第4行中的 [ � 1 * � 2]),该修复使用了第2.3节中讨论的模板进行综合。虽然这个解决方案不是我们的实现返回的排名最高的解决方案(与人类解决方案相同),但它展示了合成器的相关方面。特别是,这个解决方案有一些抽象变量,� 1 和�2。我们的算法建议用户可以用两个不同的变量替换这两个变量,并将整个表达式插入到列表中,以获得正确的程序。我们假设我们的算法产生的这种解决方案可以为初学者提供有价值的反馈,并在第6.3节中进行了实证研究。03 学习修复模板我们首先介绍从包含错误和修复程序对的训练数据集中提取有用修复模板的方法。我们表达这些模板𝑒::=𝑥 | 𝜆𝑥.𝑒 | 𝑒 ¯𝑒 | let 𝑥 = 𝑒 in 𝑒|𝑛 | 𝑏 | 𝑒 + 𝑒 | if 𝑒 then 𝑒 else 𝑒|⟨𝑒,𝑒⟩ | match 𝑒 with ⟨𝑥,𝑥⟩ → 𝑒|[] | 𝑒 :: 𝑒 | match 𝑒 with�[] → 𝑒𝑥 :: 𝑥 → 𝑒𝑛::=0, 1, −1, . . .𝑏::=true | false𝑡::=𝛼 | bool | int | 𝑡 → 𝑡 | 𝑡 × 𝑡 | [𝑡]𝑒::=_ | ˆ𝑥 | 𝜆 ˆ𝑥.𝑒 | ˆ𝑥 ¯𝑒 | let ˆ𝑥 = 𝑒 in 𝑒|ˆ𝑛 | 𝑒 ⊕ 𝑒 | if 𝑒 then 𝑒 else 𝑒|⟨𝑒,𝑒⟩ | match 𝑒 with ⟨ˆ𝑥, ˆ𝑥⟩ → 𝑒|[] | 𝑒 :: 𝑒 | match 𝑒 with�[] → 𝑒ˆ𝑥 :: ˆ𝑥 → 𝑒::*[]::__[]200通过分析性程序修复提供类型错误反馈 PLDI '20,2020年6月15日至20日,英国伦敦0图3. � �� 的语法0图4. � ��� 的语法0从允许我们以简洁方式表示修复的语言的角度来看,这种语言捕捉了初学者在实践中使用的各种修复模式的基本结构。然而,从程序对数据集中的每个修复中提取单个修复模板会产生太多的模板,以进行准确的预测。因此,我们定义了模板之间的相似性关系,用于将提取的模板划分为一个小而具有代表性的集合,这将使训练精确的模型来预测修复更容易。03.1通过分析程序修复表示用户修复修复模板语言。图4描述了我们的修复模板语言 ����,它是一个带有整数、布尔值、对和列表的λ演算,扩展了我们的核心ML语言 � ��(图3)的语法抽象形式:01. 抽象变量名 ˆ �用于表示函数、变量和绑定器的变量出现,即 ˆ � 在 � ���中表示未知的变量名;2. 抽象字面值 ˆ �可以表示任何整数、浮点数、布尔值、字符或字符串;3.抽象运算符 ⊕ 同样表示未知的一元或二元运算符;4.通配符 表达式 _ 用于表示 � ���中的任何表达式,即程序中的空缺。0从第2.1节中回顾,我们将修复定义为在特定程序位置用新的候选表达式替换表达式。因此,我们使用����上的候选表达式来表示修复模板。0泛化AST。泛化抽象语法树(GAST)是����中的一个术语,表示���中的许多达式。GAST是从���的标准AST中使用抽象函数抽象出来的,该函数以���表达深度�作为输入,并返回����表达式,即具有���的所有变量,文字和运算符的,并且所有深度大于�的子表达式都被修剪并替换为占位符_。0hd0i0(a)修复AST0⊕0(b)模板GAST0图5(左)示例1的修复和(右)该修复的可能模板0将���表达式和深度�作为输入,抽象函数abstract返回����表达式,即具有���的所有变量,文字和运算符的GAST,并且所有深度大于�的子表达式都被修剪并替换为占位符_。0例子。回想一下我们的示例程序mulByDigit0图1。表达式[hd * i]替换了第4行中的(hd *i),因此是用户的修复,其AST在图5a中给出。给定此AST和深度�=2作为输入,abstract的输出将是图5b中的GAST,其中运算符*已被替换为抽象运算符⊕,深度为2的子项hd和i已被抽象为通配符表达式_。因此,����术语[_⊕_]表示mulByDigit的潜在修复模板。0从数据集中提取修复模板0我们的方法通过从程序对的训练集中提取一组修复模板来完全自动化修复的提取。给定数据集中的程序对(����,����),我们使用表达式级别的diff[20]函数提取每个在����中发生变化的位置的唯一修复。我们将这些提取的更改抽象为我们的修复模板。0上下文修复。根据Felleisen等人的[8],设C是表达式�在程序�中出现的上下文,即将表达式�替换为一个空洞_的程序�。我们写�=C[�],意味着如果我们用原始表达式�填充空洞,我们将得到原始程序�。通过这种方式,diff找到了一个最小(节点数最少)的表达式替换����,用于替换����中的表达式����,使得����=C����[����],且C����[����]=����。可能有多个这样的表达式,diff返回所有这些更改。0例子。如果��被重写为��,则上下文为C=_�,修复为�,因为C[�]=��。如果��被重写为(��)+1,则上下文为C=_,修复为整个表达式(��)+1,因此C[(��)+1]=(��)+1。(即使��在原始程序和修复程序中都出现,我们认为应用表达式��Ð而不是�或�Ð被+运算符替换。)210PLDI '20,2020年6月15日至20日,英国伦敦,Georgios Sakkas,Madeline Endres,Benjamin Cosman,Westley Weimer和Ranjit Jhala0划分模板程序在���上强制相似的修复,例如变量名的更改,具有相同的GAST。我们的下一步是定义程序修复相似性的概念。我们的定义支持形成一组小而广泛适用的修复模板。这个小集合用于训练修复预测器。0GAST相似性。当根节点相同时,两个GAST是相似的,并且它们的子树(如果有)可以被排序,使得它们成对相似。例如,� + 3和7−�产生相似的GASTsˆ�⊕ˆ�和ˆ�⊕ˆ�,其中根节点都是抽象二元运算符,一个子节点是抽象文字,一个子节点是抽象变量。0划分。GAST相似性定义了一个自反的,对称的,传递的关系,因此是一个等价关系。现在我们可以将划分定义为根据GAST相似性计算我们提取的修复模板的所有可能的等价类。每个类可以由多个成员表达式组成,其中任何一个都可以被视为类的代表。然后,每个代表可以用作修复模板,用于为类型不正确的程序生成修复。例如,ˆ�⊕ˆ�和ˆ�⊕ˆ�属于同一类,可以选择任何一个作为代表。第5节中的修复算法在修复具有此模板的错误程序时将同时考虑两者。最后,我们的划分算法根据数据集中成员表达式的频率返回前�个等价类。�是算法的一个参数,并且被选择为尽可能小,同时前�个类代表了数据集的足够大的部分。04在给定候选模板集的情况下预测修复模板,我们的下一个任务是训练一个模型,当给定一个(错误的)程序时,可以预测在该程序的每个位置上使用哪个模板。我们通过定义一个函数predict来实现这一目标,该函数接受以下输入:(1)特征提取函数Features,(2)程序对(perr,pfix)的数据集DataSet,以及(3)修复模板列表T。它的输出是一个修复模板预测器,给定一个错误的程序,返回可能修复的位置和要应用的模板。我们使用三个辅助函数来构建predict,执行每个高级步骤。首先,extract函数从程序对数据集中提取特征和标签。然后,这些特征向量被分组并输入到train中,产生两个模型LModel和TModel,分别用于错误定位和预测修复模板。最后,rank接收新的(错误的)程序的特征,并查询训练好的模型,返回可能的修复位置和相应的修复模板。接下来,我们将介绍Figure6中的关键数据类型,我们对这三个关键步骤的实现方式,以及它们如何组合以得到predict算法。0置信度、数据和标签。如图6所示,我们将EMapa定义为从表达式e到类型a的映射,将TMapa定义为从模板T到这些值的映射。例如,TMapC是从模板T到其置信度得分C的映射。Data表示用于训练我们的预测模型的特征向量,而LabelB是用于训练的数据集标签,LabelC是输出的置信度得分。最后,Pair是一个程序对(perr,pfix)。0特征和预测器。我们将特征定义为一个函数,该函数为输入程序的每个子表达式生成特征向量数据。这些特征向量以EMapData的形式给出,将输入程序的所有子表达式映射到其特征向量数据。预测器是从我们的算法返回的学习到的固定模板预测器,用于为输入程序生成置信度得分映射。具体而言,它们返回一个将输入程序的每个子表达式与置信度得分LabelC相关联的映射EMap (Label C)。0架构。首先,extract函数接受特征提取函数Features、模板列表[T]和单个程序对Pair作为输入,并生成一个EMap (Data× LabelB)的特征向量和布尔标签的映射,用于从Pair中的错误输入程序的所有子表达式中提取特征。然后,所有特征向量Data和标签LabelB都被累积到一个列表中,作为输入传递给train,并用于训练用于预测错误位置和修复模板的两个模型LModel和TModel。接下来,两个训练好的模型LModel和TModel,以及来自新的和之前未见过的程序的Data,可以输入到rank中。这将产生一个预测器Predictor,可以将新程序的子表达式映射到可能的错误位置和修复模板。04.1 特征和标签提取0我们用于预测修复模板和错误位置的机器学习算法期望输入固定长度的特征向量Data。然而,我们希望修复变长的���程序。因此,我们使用extract函数将程序转换为特征向量。按照Seidel等人的方法,我们选择将程序建模为一组特征向量,其中每个元素对应程序中的一个子表达式。因此,给定一个错误的程序perr,我们首先将其分割为其组成的子表达式,然后将每个子表达式转换为单个特征向量,即Features perr :: EMapData。我们只考虑最小类型错误切片内的表达式。我们在这里展示了使用的五个主要特征类别。0局部句法特征。这些特征描述了每个表达式�的句法类别。换句话说,对于图3中�的每个产生规则,我们引入一个特征。220通过分析性程序修复的类型错误反馈PLDI '20,2020年6月15日至20日,英国伦敦0C ∈ R | 0 ≤ r ≤ 1 B ∈ R | b = 0 or b = 1 T ∈eRTL0EMap � → � → � TMap � → T→ � Data → [C] Label � → � ×TMap � Pair → � × � DataSet→ [Pair]0Features � → EMap Data Predictor �→ EMap(Label C)0abstract: � → T diff: Pair →[�]0extract: Features → [T] → Pair → EMap(Data × LabelB) train: [Data × Label B] → LModel × TModel rank:LModel → TModel → Data → Label C0predict: Features → [T] → DataSet → Predictor0图6.将程序对转换为特征向量和模板标签的高级API。0如果表达式是使用该产生式构建的,则启用(设置为1),否则禁用(设置为0)。0上下文句法特征。表达式出现的上下文可能对于正确预测错误源和修复模板至关重要。因此,我们包括上下文特征,这些特征类似于局部句法特征,但描述了表达式的父级和子级。例如,Is-[]-C1特征描述了一个表达式的第一个子级是否为[]。这类似于语言模型中使用的n-gram [9, 15]。0表达式大小。我们还包括表示每个表达式大小的特征,即它包含多少个子表达式?这使得模型可以学习到,例如,离叶子节点更近的表达式比离根节点更近的表达式更容易修复。0类型特征。我们试图修复的程序是不可类型化的,但是来自类型检查器的部分类型推导仍然可以为模型提供有用的信息。因此,我们在表示中包括类型特征。由于参数化类型构造函数∙→∙,∙×∙和[∙],存在无限可能的类型集合,但我们必须有有限的特征集。我们为每个抽象类型构造函数添加特征,描述给定类型是否使用该构造函数。例如,类型int→int→bool将启用∙→∙,int和bool特征。我们为父表达式和子表达式添加这些特征以总结上下文,但也为当前表达式添加这些特征,因为表达式的类型在语法上并不总是清晰的。0类型错误切片。我们希望区分可能修复错误的更改和不可能修复错误的更改。因此,我们为程序计算一个最小的类型错误切片(例如[12,40]),即对错误有贡献的表达式集合,并且如果程序包含多个类型错误,则为每个错误计算一个最小切片。然后,我们有一个后处理步骤,丢弃所有不包含在这些切片中的表达式。0标签。回想一下,我们使用两个预测模型,LModel用于错误定位,TModel用于预测修复模板。因此,我们需要与每个特征向量相关联的两组标签,由LabelB给出。LModel使用集合[Data ×B]进行训练,而TModel使用集合[Data × TMapB]进行训练。LModel的类型为B的标签在程序perr中的每个子表达式中被设置为true,该子表达式在pfix中发生了变化。对于perr的子表达式,标签TMap B映射到修复模板T。TMapB将所有子表达式与给定的一组模板[T]关联起来,作为输入提供给extract。因此,从模板预测的角度来看,TMapB可以被视为一个固定长度的布尔向量,表示用于修复每个子表达式的修复模板。这个向量最多有一个插槽设置为true,表示用于修复perr的模板。这些标签是使用diff和abstract提取的,类似于在第3.2节中提取模板的方式。04.2训练预测模型我们的train函数的目标是训练两个独立的分类器,给定一个带有标签的训练集[Data × LabelB]。LModel预测错误位置,TModel预测修复模板,用于新的输入程序perr。关键是,我们要求错误定位分类器输出一个置信度得分C,表示子表达式是需要修复的错误的概率。我们还要求修复模板分类器为每个修复模板输出一个置信度得分C,该得分衡量分类器对于使用该模板修复输入程序perr的相关位置的确定程度。我们考虑使用标准的学习算法生成我们的模型:神经网络。神经网络的详细介绍超出了本文的范围[13,28]。0神经网络。我们使用的模型是一种称为多层感知机的神经网络。多层感知机可以表示为一个有向无环图,其节点按层排列,层与层之间由加权边连接。第一层对应于输入特征,最后一层对应于输出。内部节点的输出是前一层的加权输出经过非线性函数(称为激活函数)处理后的和。神经网络的层数、每层节点数以及层之间的连接构成了神经网络的架构。在这项工作中,我们使用相对较深的神经网络(DNN)。我们可以训练一个名为LModel的DNN作为二进制分类器,用于预测是否需要修复程序perr中的位置。2:𝐷𝑀𝐿 ← ∅3:for all 𝑝𝑒𝑟𝑟 × 𝑝𝑓 𝑖𝑥 ∈ 𝐷 do4:𝑑 ← Extract(𝐹, 𝑇𝑠, 𝑝𝑒𝑟𝑟 × 𝑝𝑓 𝑖𝑥)5:𝐷𝑀𝐿 ← 𝐷𝑀𝐿 ∪ InSlice(𝑝𝑒𝑟𝑟, 𝑑)6:𝑀𝑜𝑑𝑒𝑙𝑠 ← Train(𝐷𝑀𝐿)7:𝐷𝑎𝑡𝑎 ← 𝜆𝑝. InSlice(𝑝, Extract(𝐹, 𝑇𝑠, 𝑝 × 𝑝))8:𝑃𝑟 ← 𝜆𝑝. Map(𝜆 ˜𝑝. Rank(𝑀𝑜𝑑𝑒𝑙𝑠, ˜𝑝[0]), 𝐷𝑎𝑡𝑎(𝑝))9:return 𝑃𝑟230PLDI '20,2020年6月15日至20日,英国伦敦,Georgios Sakkas,Madeline Endres,Benjamin Cosman,Westley Weimer和Ranjit Jhala0算法1 预测模板算法0输入:特征提取函数F,修复模板Ts,程序对数据集D输出:预测器Pr 1:预测过程Predict(F, Ts, D)0分类器,将预测程序perr中的位置是否需要修复。0多类别DNNs。虽然上述模型足以进行错误定位,但在模板预测的情况下,我们必须从超过两个类别中进行选择。我们再次使用DNN进行模板预测TModel,但我们调整输出层,使其具有N个节点,对应于N个选择的模板类别。对于使用神经网络解决的多类别分类问题,通常在输出层使用softmax函数[5,10]。Softmax为每个类别分配概率,这些概率必须加起来等于1。这个额外的约束加快了训练速度。04.3 预测修复模板0我们的最终目标是能够确定错误程序的哪些部分应该修复,以及应该使用哪些修复模板。因此,predict函数使用rank来预测所有子表达式的置信度得分C作为错误位置,以及每个修复模板的置信度得分TMap C。我们在这里展示了如何将Figure6中的所有函数组合起来,为新程序p生成最终的置信度得分列表。Algorithm 1展示了我们的高级predict算法。0预测算法。我们的算法首先从程序对数据集D中提取适用于机器学习的数据集DM。对于D中的每个程序对,Extract返回一个从错误程序的子表达式到特征和标签的映射。然后,InSlice仅保留类型错误切片中的表达式,并计算相应的特征和标签向量列表,将其添加到DM数据集中。Train函数使用该数据集生成我们的预测模型,即LModel和TModel。此时,我们希望为一个新的未知程序p生成一个预测器。我们使用Extract对p进行特征提取,并使用InSlice将其限制为p的类型错误切片中的表达式。结果由����(�)给出。然后,对由����(�有子表达式应用Rank,使用Map创建将表达式与置信度关联的类型EMap(Label C)的映射。0分数。我们对与类型错误切片 �相对应的每个特征向量应用Rank。这些向量是 ˜ � ∈ ���� ( � )的第一个元素,类型为 Data × Label B 。最后,返回预测器Predictor �� ,我们的综合算法在第5节中使用它将 �中的子表达式与其置信度得分相关联。04.4 讨论0与两个独立的预测模型 LModel 和 TModel相比,另一种选择是使用一个联合模型来预测错误位置和修复模板。可以简单地将一个“空”修复模板添加到提取的 �个模板集合中。然后,可以在数据集上训练一个多类别DNN,使用 � + 1个类别。当预测到“空”修复模板时,表示该位置没有错误,而其余的类别表示错误以及要使用的修复模板。虽然使用一个联合模型的方法非常直观,但我们在早期的实验中发现它不能像两个独立的模型那样产生准确的预测。学习表示是DNN的一个显著优势,因此通常不鼓励手动提取特征。最近,有一些关
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功