析取程序合成：一种通过示例编程的健壮方法( 三 ) 摘要通过示例编程（PBE）系统

文章插图
文章插图
程序合成算法：在本节中，我们描述用于从输入输出示例中学习析取程序的合成算法，以及针对文本和 Web DSL 的实例化。我们描述的算法与任何特定的 DSL 无关，因为它将 DSL 和其他特定于域的属性作为特定域实例化的配置参数。总而言之，该算法基于 DSL 中的程序表达式学习，方法是将基于任意示例的约束传播到子表达式的任意表达式上。约束传播是使用 DSL 运营商的特定于域的属性完成的，该属性在配置参数中提供。在描述完整算法之前，我们会首先讨论这些属性。
领域特定参数：该算法的配置参数 C 包含该算法所需的四个特定于域的组件：DSL ， InferSpec ， Synth 和 Ranker 。 DSL 是特定于领域的语言，程序将在其中进行合成。 InferSpec 是从 DSL 中的操作员规则到该规则的规范推断功能的映射。规范推断功能基于（Polozov and Gulwani 2015）中详细介绍的 witness function 。
DSL 中用于操作符规则的规范推断函数是在给定操作符本身规范的情况下计算操作符参数规范的功能。
尽管可以为 DSL 中的大多数操作符提供规范推断功能，但对于某些 DSL 符号（尤其是终端符号），我们可能具有特定于域的学习策略来直接推断程序。这是我们不再向下传播规格的基本情况。例如，对于文本 DSL 中的原子正则表达式令牌 t ，我们可能会从位置运算符向下传播一个规约，即正则表达式必须在输入 s 上具有匹配项，该匹配项在 s 中的位置 i 处结束。在这种基本情况下，我们将不进一步传播此规约，而仅检查满足此约束的 DSL 中可能的原子正则表达式并返回这些正则表达式。
配置参数 c 的最后一个组件是排名函数 Ranker ，它输入一组程序并返回根据某些排名标准排序的程序列表。对于文本 DSL ，我们使用（Gulwani 2011）中定义的排名标准，该排名标准通常首选“简单”程序。在网络案例中，先前的方法（Polozov 和 Gulwani 2015）（以及我们的基线比较）是基于首选最具体的程序来选择节点的，但是我们将在概述主要算法之后详细描述对此的改进。
文章插图
合成算法：合成算法在图 7 中定义。在第一阶段，算法将计算满足规约的程序 Prog（第 3 至 17 行）。如果已经在 C 语言中为此符号提供了特定的合成功能，则仅使用该功能（第 5 行）。否则，它将使用规约传播方法执行合成。对于带有 head 的 DSL 中的每个运算符规则，我们计算在顶层使用此运算符的候选程序（第 8 至 17 行）。为此，我们将构建运算符的参数实例化列表（存储在变量 S 中），直到获得运算符所有参数的实例化结果为止。
? 对于每个参数，我们使用已经计算出的先前参数的实例来推断该参数的规约（第 13 行），然后使用该规约通过递归调用合成算法来合成该参数的程序（第 14 行），并使用这些程序将增长参数实例化列表 S（第 15 行）。在第 17 行，我们使用此规则运算符将所有可能的程序添加到集合 Progs 中。请注意，在实践中，我们对该概述进行了各种优化，包括将特定合成结果的缓存存储在经常重复的给定规约中，将程序聚集在一起以产生相同的输出，并设置递归限制以限制程序的大小。
该算法的下一个阶段是选择排名最高的程序，并在需要时构造一个析取程序（第 18 至 32 行）。我们首先使用排名函数从集合 Progs 中获得排名最高的程序。如果该符号不是 DSL 中的析取符号，那么我们只需返回该排名最高的集合（第 20 行）。否则，我们将为符号合成一个析取程序。
我们首先获得特征计算器符号 f ，然后初始化特征计算器向量 F 和目标特征值向量 V（第 22 至 24 行）。合成器现在必须选择将包含在析取程序中的功能，以便在不同的析取之间进行选择。选择这些功能作为在提供给该算法的所有训练示例中产生相同值的所有功能。这是因为目标是合成一个析取程序，该析取程序将首选析取结果与训练示例最相似的析取结果。
析取学习：我们所描述的算法使用排名靠前的程序选择最终程序中的析取词（在我们的实验中，我们发现前 10 个析取词的临界值在实践中实现了性能和鲁棒性的有效平衡）。
对于文本 DSL ，我们对子字符串运算符执行了析取合成，我们发现基础 Flash Fill 系统（Gulwani 2011）使用的排名产生了有效的析取。但是，在进行 web 提取的情况下，现有的合成系统（Polozov 和 Gulwani 2015；Le 和 Gulwani 2014）无法为过滤器操作提供足够的析取，因为这些系统倾向于支持最具体的条件或其他启发式技术来选择过滤条件，在实践中效果不佳。