程序增强：通过众包进行程序合成

1.引用

Cochran R A, D'Antoni L, Livshits B, et al. Program boosting: Program synthesis via crowd-sourcing[C].Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2015: 677-688.

2.摘要

在本文中，我们研究了一种基于众包的程序合成方法。在众包的帮助下，我们力求捕捉“众人的智慧”，以找到解决固有棘手编程任务的好的（即使不是完美的）解决方案，这些任务缺乏易于形式化的规范，甚至连专家级开发人员都难以理解。

我们将这种方法称为“程序增强”，它将为开发人员遇到的一个棘手编程问题众包一些不够完善的解决方法，然后将这些程序融合在一起以提高其正确性。

我们在 CROWDBOOST 系统中实现了这种方法，并在我们的实验中展示了一些有趣并且且有价值的任务(例如 URL 或电子邮件地址的正则表达式)可以有效地众包。我们证明，将众包结果混合在一起可以协调一致地对程序进行增强，所产生的程序要好于任何初始的程序。我们对 465 个程序对进行实验，结果显示出一致的准确率提升，这证明了可以以相对低的成本来进行程序增强。

3.技术介绍

3.1 众包背景

在过去的几年中，我们看到在一些非技术性任务（识别图片中是否有猫，重新格式化文本数据，纠正句子中的语法）和技术性任务(根据要求提供插图或图形设计，撰写产品的简短说明)中使用众包的情况有所增加。

Amazon 的 Mechanical Turk（通常缩写为 asmturk）就是一个很好的非专业工作众包网站例子；oDeskis 是另一个广泛使用的平台，该平台主要用于技术性的任务。这两个平台均可用于众包编程任务，尽管两者都不是专门用于此目的。注意，可以将 StackOverflow 和其他类似的编程帮助站点视为一种非正式的众包类型。确实，这些站点非常擅长提供解决棘手的编程问题的方法，以至于某些开发人员在编写代码时经常浏览 StackOverflow。

Bountify（http://bountify.co）允许人们发布程序任务，其中一些涉及从头开始编写新代码（编写JavaScript函数以生成给定颜色的多种阴影），而其他则涉及修复现有代码中的错误（为什么 我的 HTML 表格看起来不符合我的期望，我应该如何调整 CSS 使其看起来正确？）。这些编程任务通常不会太耗时;一个典型的任务大约支付 5 美元。回复是公开发表的，这使得其他开发者可以从中进行学习。最后，发布者决定将奖金授予哪个开发者。

请注意，交互式众包并不是特定编程任务的唯一代码源。确实，人们可以轻松地使用代码搜索引擎来从开源项目中寻找。使用专用代码引擎搜索诸如 urlregex 之类的术语将生成一些可能的正则表达式用来过滤 URL。

3.2 程序增强

图 2 显示了我们系统的体系结构。我们从一个文本测试任务规范和（正负）示例的初始训练集（也称为“黄金集”）开始。为了将指定任务的解决方案众包，我们利用了两个人群：由开发人员组成的熟练人群和由常规计算机用户组成的未经训练的人群。前者包含通过诸如 Bountify 之类的服务进行雇佣的开发人员，他们通常精通一种或多种语言（如 Java 和 C ），而后者则由在 Mechanical Turk 上找到的常规计算机用户组成。

方法：为简单起见，本文将重点放在二分类任务上，即（1）使用单一输入的程序；（2）产生布尔值（是/否）输出；（3）对于任何输入，非专业的计算机用户都可以决定其答案应该是是或否。 此类任务的示例包括确定输入是否为格式正确的电话号码的程序，或确定输入图像是否包含长颈鹿的程序。

​ 最后一个要求是改善程序的必要条件，即在未经训练的人群的帮助下确定棘手案例的正确结果。我们的观察是，尽管未经培训的人群不会帮助我们程序，但他们将能够识别正确或不正确的程序行为。通过类推的方式，虽然外行人可能无法编写识别图像中是否存在长颈鹿的计算机视觉程序，但人类非常擅长识别给定图片中是否包含长颈鹿。这种两人群的方法有助于我们询问未经培训人群来消歧，从而既可以收集候选程序，又可以系统地扩展输入空间。

虽然存在其他合适的标准，但在这篇论文中，我们关注的是提高合成程序在正反面例子上的准确性。

3.3 通过遗传编程进行程序增强

为了实现以上示例中所提出的方法，一种常见的技术是遗传编程，它是遗传算法的一种特殊形式。遗传编程是程序领域中的一种搜索技术，其目的是在一系列迭代中提高程序的适用性。成功的遗传编程方法取决于实现两种操作：交叉和突变。

给定一组初始的众包程序，该程序增强算法需要进行多次迭代。在我们的电话号码示例的上下文中，这些初始程序可以是两个初始正则表达式。在每一代，它都将交叉和变异操作结合在一起。（在我们的示例中，这可能会将正则表达式的各个部分调整为像-和.这样的电话号码分隔符）作为一种改进形式，之后我们将新示例添加到训练集中。例如，在我们的正则表达式实现中，优化的目标是通过将非显而易见的情况例如 212.555−1212or1−)212)555−1212 作为有效或无效电话号码添加到不断发展的进化训练集中来达到 100％的状态覆盖率。最后，选择适应性最高的候选者继续下一代。

3.4 程序增强算法

图 3 用伪代码显示了我们的程序增强算法。Σ 为所有程序集，Φ 为所有输入集。在每次迭代中，我们更新当前考虑的程序和当前的示例.

请注意，该算法本质上是迭代的：增强收益的过程类似于通常执行遗传编程的方式。总体目标是在 Σ 中找到最适合的程序。每代产生一个新的 Φ 样本并发送给人群以取得共识。

​ 稍后我们将展示如何使用 SFA 实现与正则表达式的函数 β，μ，δ 和 η 相对应的运算。请注意，在实践中，为了更快地完成代码，我们通常将迭代次数限制在一个设置的限制（例如 10）中。

我们的实现受益于并行运算。在特殊情况下，我们使算法的第 6 行和第 12 行的两个循环并行进行。尽管我们在执行过程中需要小心谨慎，以避免出现共享状态，但这种相对简单的更改最终会能够几乎完全利用具有 8 或 16 个内核的计算机。

1 有限符号自动机：尽管正则表达式简洁明了，相对容易理解，但对代数来说却不容易操纵。特别是，没有直接的算法可以互补或相交。因此，我们选择了有限自动机。经典确定性有限自动机（DFA）具有许多闭包性质和友好的复杂性，但是每个 DFA 转换只能携带一个字符，从而导致 DFA 中的转换数量与字母的大小成比例。当字母表很大（UTF16 具有 2 的 16 次方个元素）时，这种表示不切实际。

符号有限自动机（SFA）扩展了带有符号字母的经典自动机。在 SFA 中，每个边都标记有谓词，而不是单个输入字符，这使自动机可以简洁地表示多个具体转换。例如，在图 7 的 SFA 中，从状态 10 到状态 11 的转换用谓词[^＃- /？ s]标记。由于 UTF16 集的大小，经典自动机中的这个转换将由数千个具体转换来表示。

2 适应度计算 ：作为用于程序增强的遗传程序设计方法的一部分，我们需要能够评估特定程序的适用性。对于正则表达式，这相当于在训练集上计算精度。适应度计算过程本身可能会非常耗时。原因是当我们考虑成千上万的 SFA 和数百个例子时，运行一些大的例子，并计算有多少被 SFA 正确接受是一个扩展性很差的过程。相反，我们构造 SFA P 和 N，分别表示所有肯定组和所有否定组的语言。对于任何 SFA A，我们计算交集的基数（参见图 4 中的虚线区域），两者都可以使用 SFA 操作来快速计算。然后可以将精确度计算限制在范围为 0 到 1。我们的改进技术固有的挑战是我们进化的示例集可能会与最初的黄金集大相径庭。尽管不完美，但我们仍然希望将黄金集视为更可靠的真理来源，为此，我们使用加权为整体适应度计算中的黄金集赋予更高的权重。在我们的实验评估中，如果将黄金：进化示例权重设置为 9：1，我们将获得可靠的良好结果。

3 交叉 交叉操作是将两个 SFA 通过混合他们的行为，交叉成单个 SFA。这个操作的说明示例如图 6 所示。给定两个 SFA A 和 B，交叉算法通过重定向两个转换（一个从 A 到 B，一个从 B 到 A）来创建新的 SFA。此类操作的目标是使用包含 A 的 B 的组件。

4 变异 在其经典定义中，变异算子会更改输入程序的一个或多个值，并产生一个变异的值。SFA 的值要更改的太多（每个转换都可以携带 2 的 16 次方个元素），“盲目”方法会产生太多变异。相反，我们考虑使用引导方法，其中将变异作为 SFA A 的输入和反例 s（s 是一个正例子但它不属于 L(A)或者 s 是一个反例但它属于 L(A)）。使用这些额外的信息，我们仅以会导致正确分类的方式进行变异。这种操作背后的直觉是执行最小的语法改变以正确分类反例。

5 示例生成 生成一个字符串通常不足以描述 SFA 的语言。在生成示例中，我们遵循下列不变式：为了生成 SFA 的全覆盖，我们需要进行下一个迭代。迭代算法示例如图 8 所示；给定包含 k 个状态的 SFA，它最多迭代 k 轮终止。该算法只是在每次迭代中生成一个新的字符串，强制覆盖至少一个尚未覆盖的状态。

4.本文主要贡献

本文提出了一种新颖的众包方法来进行程序合成，称为程序增强。我们主要关注即使是最熟练的开发人员存在困难的编程任务。我们的见解是，可以将群众的智慧集中到这些艰巨的任务上。在本文中，我们展示了如何使用两个人群：一群熟练的开发人员和一群未经培训的计算机工作者来成功地为涉及拟定正则表达式的复杂任务生成解决方案。

我们已经在名为 CROWDBOOST 的工具中实现了程序增强，并进行了测试。在四个复杂的任务上，我们从 Bountify 和其他几个来源众包了 33 个正则表达式，并对其进行成对增强。我们发现我们的程序增强技术是稳定的：当在 465 对众包程序上进行测试时，它产生了一致性的精确性增强。即使是从合格的开发人员众包而来的高质量初始程序开始合成，我们也始终如一地能够提高准确率，平均达到 16.25％。

致谢

国家重点研发计划课题：基于协同编程现场的智能实时质量提升方法与技术（2018YFB1003901）和国家自然科学基金项目：基于可理解信息融合的人机协同移动应用测试研究（61802171）

本文由南京大学软件学院 2020 级硕士王一博转述