援用
Desai A, Gulwani S, Hingorani V, et al. Program synthesis using natural language[C]//Proceedings of the 38th International Conference on Software Engineering. 2016: 345-356.
摘要
随着计算机进入千家万户，人机交互变成了一项极其普遍的活动。一些反复性或专业性义务通常需求创建小型的、一次性的程序。为了完成这些一次性程序，终端用户（End-User）能够需求花费大量工夫和精神去学习各种范畴特定言语（Domain Specific Language，DSL），这为用户带来了极大的不便。
在本文中，作者提出了一个通用框架。该框架可以构建一种可以应用自然言语（Nature Language，NL）合成目的 DSL 的程序合成器（Synthesizer）。该框架以 DSL 定义和训练数据（NL/DSL 对）为输入，经过训练运用最优权重和自然言语处理（Nature Language Processing，NLP）的若干特征的、基于关键词编程翻译的分类器，完成了目的程序合成器的构建。该框架可以运用于反复文本编辑、智能教学系统和航班信息查询三个范畴。经过本文提供的框架，作者应用 1200 余个英语描画分别构建出三个针对不同范畴的程序合成器。预期程序（Desired Program）在程序合成器输入的合成程序列表中排在 Top-1 和 Top-3 的概率分别为 80%和 90%。
关键词：自然言语；范畴特定言语；程序合成
1 引言
程序合成（Program Synthesis）是一个根据给定的规格（Specification）、以某种基础范畴特定言语（DSL）为原料自动合成程序的过程。传统的程序合成依赖完全规格（Complete Specification）。由于编写完全规格存在困难，同时结果验证（即验证合成得出的程序能否满足规格）也非常不易，因此传统程序合成并没有得到广泛的运用。
最近，相关研讨尝试在程序合成过程中运用样例（Examples）作为指点合成的规格。该类研讨曾经得到了广泛运用，其缘由在于：相比于完全规格，样例规格往往更容易获得。比较典型的例子有实例编程（Programing by Example，PBE）系统。由于样例需求与准确的程序意图相结合才能构成样例规格，因此，当样例的需求量过大时，规格的构建将变得非常困难。如 L算法——一种用于描画常规言语的 PBE 系统——它的一大缺陷就是系统构建需求依赖大量的样例；再如像航空游览查询系统（Air Travel Information System，ATIS）这类的专业范畴，要求终端用户（即普通乘客）构形成充斥着专业名词输入/输入样例是一件几乎不能够的事情。但与 L算法所处的场景不同，ATIS 范畴的合成成绩存在改进的能够，由于“航线查询”这类范畴义务通常可以应用自然言语描画。由此，作者以为自然言语的描画也许可以指点程序合成牢靠地停止。
在本文中，作者处理了应用自然言语（NL）合成基础底层特定言语（DSL）的程序的成绩。从本质下去说，NL 是不准确的，因此能够无法保证合成程序的正确性。为了保证结果程序的准确性，作者将程序合成器的输入定义为一组排序后的结果程序（而不是单个结果程序），并允许用户经过检查源代码和观察程序输入的方式来检查程序、挑选程序。本文提出的合成算法可以在基准数据上提供波动的合成结果：在 80%的序列结果序列中，预期程序排在 Top-1 的地位；在 90%的结果中，预期程序排在前三。此外，为了协助用户更好地选择程序，作者还将代码翻译成无歧义的英语表达，以供用户预览。
本文提出的方法可以运用于多种 DSL。在运用框架时，程序合成器的设计人员需求提供两个输入：① DSL 定义，一组从 DSL 操作到对应 NL 描画/概念的映射；② 训练数据，一组样例对（Example Pair），每个样例对包含一组英语描画和一个符合这组描画的预期程序。在训练阶段，本文的方法会：① 以半自动方式推断英语单词和 DSL 终结符之间的字典关系；② 经过一个通用合成算法，以完全自动化的方式推断英语单词的最优权重/分类符（Optimal Weight/Classifier）。综上，本文提出的方法可以看作一个可以构建 NL-to-DSL 程序合成器的通用框架。
2 研讨动机
作者在研讨过程中发现了三种可以运用 NL-to-DSL 合成器的场景，分别是：高阶文本编辑操作（2.1 节）、智能教学系统中的自动机构造成绩（2.2 节）以及航空旅游信息系统的查讯成绩（2.3 节）。
2.1 文本编辑（终端用户编程）
在阅读 Office 程序（如 Microsoft Excel 和 Word）的协助论坛时，作者发现了许多关于“如何停止反复文本编辑操作”的求助。例如：在 Word 文档中执行特定条件下的插入、删除、交换或提取操作，如表 1（b）所示。这些操作比单纯的文本搜索或字符串交换要复杂的多，属于高阶文本编辑操作。高阶操作通常具有两类特征：① 字符串的搜索条件不是常量，而是正则表达式；② 文本的编辑和目的文本的上下文有关。高阶文本编辑往往需求用户了解正则表达式、条件语句和循环语句的语法和语义，而这大大超出了绝大部分终端用户的才能。
表 1 文本编辑范畴相关的语法和基准样本
上述需求启示作者设计一种用于完成高阶文本边界操作的命令言语，该言语的部分语法如表 1（a）所示。语法中包含了一些文本编辑的关键命令，如插入 Insert、删除 Remove、打印 Print 和交换 Replace，这些命令都依赖于一个指明了编辑操作作用范围（比如一组行、一组单词或整个 Word 文档）的 IterScope 表达式。SelectStr 产生式（Production）内含一个允许有限通配符婚配的令牌 Token、一个用于过滤婚配值的布尔条件 BCond 以及一个基于下标的结果选择记号——出现值 Occurrence。例如：我们可以运用 AtomicOccurrence 中的 FirstFew(N)项来删除符合婚配条件的前 N 的结果；特别地，当 Occurrence 的值为 ALL 时，一切满足婚配条件的结果都将被删除。布尔条件 BCond 囊括了一些标准的字符串婚配谓词（如 Contains、StartsWith 等），由原子条件 AtomicCond 组成，支持 And、Not 在内的条件组合。CommonCond 产生式标定了相对于某个字符组合的地位，如在某个字符组合之后 After(Token)、在某个组合之前 Before(Token)和某两个组合之间等 Between(Token, Token)。样例 1 和样例 2 分别给出了针对表 1（b）中所示的编辑义务 1 和 2 的命令言语描画。
样例 1 表 1（b）中文本编辑义务 1 的 DSL 描画
样例 2 表 1（b）中文本编辑义务 2 的 DSL 描画
此外，表 1（c）描画了该言语系统可以处理的其他变式。这些自然言语义务都可以用表 1（a）所示 DSL 语法来描画。作者以为表 1（a）给出的语法足够支持高阶文本编辑操作：一旦用户习气运用 DSL 言语完成简单的条件性文本操作，那么经过将复杂成绩分解为简单成绩，愈加复杂的文本操作也不成成绩。
2.2 自动机实际（智能教学）
方式化方法的研讨成果曾经在智能教学系统的多个部分中得到了运用，包括成绩生成（Problem Generation）、题解生成（Solution Generation）和一些关于几何、自动机实际在内的各种学科范畴的反馈生成（Feedback Generation）等多个范畴。这些范畴中的每一个都触及一种公用的 DSL，用于生成标题、产生题解以及生成针对先生提交题解的反馈意见。
以自动机的构造为例：假设先生需求构造这样一个自动机，该自动机需求可以接受一段描画了某种言语的英文段落（有关示例见表 2）。根据 Alur 等人提供的、关于构造此类言语的一些要素，作者设计了一种 DSL，可以经过两种方式为先生提供指点：① 作为题解生成工具的输入以生成一个正确的题解，并以这个正确题解为基准为先生提交的题解打分；② 用于提供反馈并根据先生的提交生成成绩变式。该反馈生成工具曾经部署在部分教室中。实际证明，该工具可以以比人类更快、更合理方式分配成绩和生成反馈。
表 2 有关自动机范畴的基准样本
样例 3 和样例 4 分别展现了表 2 中规格 1 和规格 2 的 DSL 翻译结果。
样例 3 表 2 中规格 1 的 DSL 翻译结果
样例 4 表 2 中规格 2 的 DSL 翻译结果
2.3 航空旅游信息系统（ATIS）
ATIS 是用于查询航空游览信息的标准基准，包括英语查询和包含航班信息的数据库。长期以来，ATIS 不断被自然言语处理和语音处理社区广泛用作通用基准。表 3 展现了一些来自 ATIS 的查询样本。
表 3 ATIS 范畴的基准样本
针对 ATIS，作者设计了一种基于 SQL 行列操作的 DSL，能支持谓词和表达式运算。这些谓词和表达式与航空游览查询范畴的出发地/目的地、日期、价格等重要概念相对应。表 3 中的第一个查询语句可以翻译成如样例 5 所示的方式。
样例 5 表 3 中第一个查询语句的 DSL 表示
3 成绩定义
本文次要研讨如何运用给定的 DSL 定义和训练数据合成目的 NL-to-DSL 合成器。现给出如下定义：
（1）范畴特定言语：一个范畴特定言语 L = (G, TC)由一组上下文有关文法 G（其中 G\T 表示终结符集、GR 表示产生式规则集）和一个可以检查给定程序类型正确性的类型/语义检查器 TC 构成；
（2）训练数据：训练数据由一组形如(S, P)的对组成，其中：S 是一个英语句子，P 是用范畴特定言语 L 写成的预期程序。一个英语句子 S 可以简单表示为一个单词序列[w1, w2, … , wn]；
（3）NL-to-\DSL\的功能目的\：生成的 NL-to-DSL 生成器应该可以将一个英语句子翻译成一个由排序后程序组成集合[P\1, P2, …, P\k]。其中一切的程序都由 L 编写。
4 言语转换算法
本文提出的合成算法（算法 1）从用户处获取自然言语命令作为输入，并创建候选 DSL 排名列表作为输入。算法的第一步（第 2 行的循环）是应用定义了 NL 到终结符映射的字典结构 NLDict 将用户输入中的而每个单词转换为一个或多个终结符。该循环遍历输入语句的每个字符。针对每一个索引，算法将应用 NLDict 挑选出相关单词，并查找 DSL 中与这些单词相关终结符集。从本质下去说，NLDict 为每个终结符停止了编码，并根据输入的英语单词决议在最终生成的预期程序中选用哪些终结符。
字典 NLDict 会分别将每个自然言语单词与一组终结符关联起来。终结符能够是常量值，也有能够是参数空缺的的函数（留白参数用“□”表示）。因此，当在算法 1 的第三行上运用 NLDict 时，生成程序中某些函数的参数能够会发生缺失，进而输入不残缺的程序。以语句“Print all lines that do not contain 834（打印除 834 以外的一切行）”为例：由于语法中包含产生式规则 PrintCmd := Print(SelectStr，IterScope)，且字典将单词“print”与函数 Print 关联在了一同，那么这样就会生成不残缺的程序 Print(□, □)。这些空缺将在后续被一些可以婚配参数 SelectStr 和 IterScope 的程序所交换。
算法 1 NL-to-DSL 合成算法
在完成了基本终结符集合的构建之后，算法 1 将采用 Bag 算法（算法 2）来生成一个包含一切候选程序的集合 ResT，对应算法 1 的第 5 行。算法 1 的最后一步是结合得分和权重，对集合中一切的候选程序停止排序，对应算法 1 第 8 行。
算法 2 Bag 子合成算法
5 训练阶段
本节次要引见分类器、权重和单词到终结符映射的学习过程。训练阶段的关键在于 ① 确定运用哪种机器学习算法；② 应用 DSL 设计者提供的高阶训练数据生成为机器悬系算法服务的低阶训练数据。
5.1 映射得分分类器（Cmap）
Cmap 的功能是应用单词 w 的 POS 标签预测 w 映射到某个终结符 t ∈ G\T 的能够性。本文运用了一种朴素贝叶斯分类器的现有完成来训练分类器 Cmap，用于训练 C\map 的算法如算法 3 所示。
算法 3 训练映射得分分类器 Cmap
相似性元组次要为两个目的服务：第一，经过 UsedWords，引导系统侧重那些“运用了输入语句中一切部分”的映射；第二，经过 D\isjointness，引导系统侧重那些惩罚了“运用输入语句中单个部分来构建多个不同子程序”的映射。
5.2 结构得分分类器（Cstr）
本部分将引见为结构得分服务的分类器 Cstr 的训练过程。对于每一个衔接 Conn，都有一个分类器 C\str [Conn]与之对应。分类器 Cstr [Conn]的次要功能是预测一个组合 c 是衔接 Conn 的一个实例的概率。本文运用了朴素贝叶斯分类器的现有完成来生成训练数据，训练过程如算法 4 所示。
算法 4 训练结构得分分类器 Cstr
算法 4 的关键思绪是在不记录单个步骤得分的状况下（SynthNoScore）运转合成算法，目的是应用一个英语句子 S 构造包含一切能够程序结果的集合 A\llOpts。P’是 AllOpts 中的一个程序。任何出如今 P\’但没有出如今 P 中的组合都将被用作负样例（Negative Example）；相反的，假如该组合同时出如今 P’和 P 中，那么它将被用作正样例（Positive Example）。
5.3 字典构建
应用 DSL 中终结符的名字（表示函数和参数），本文提出的方法将经过一种半自动化的方式构建字典 NLDict。对于名字恰恰对应英文单词（例如 Insert）的操作，作者直接应用 WordNet 同义词列表来搜集一切和该操作（插入操作）相关的一切常用同义词；对于终结符的名字不是一个英文单词、而是采用某种命名方式产生的单词的链接（例如 StartsWith）的操作，作者首先应用命名规则分解操作称号，紧接着再解析出每个子称号对应的同义词。
值得留意的是：WordNet 提供的同义词集合中能够会包含一些对目的特定范畴没有意义的英文单词。这个成绩由 5.1 节引见的算法 3 处理：根据映射得分训练算法，这类单词的得分将会比较低。并且，本文的方法还会在得分分配完成后，舍弃掉得分低于某个阈值的一切映射；同理，WordNet 也有能够无法提供对于某个特定范畴极其重要的英语单词、或者 DSL 中终结符的称号不能有效地婚配到英语单词。由于在这种状况下，算法 4 将无法生成见证者映射，因此系统将可以自动检测到这种状况，并告知用户他/她的输入中有哪些无法和终结符正确对应的单词。这些不能正确对应到终结符的单词将被用作种子单词（Seed Word）输入到 WordNet，以进一步生成愈加片面的同义词集。
致谢
本文由南京软件学院 2020 级硕士钱瑞祥翻译转述。 |
