【论文笔记】Program synthesis using natural language

摘要

随着计算机走进千家万户的人类活动正变得极为普遍的现象。许多简单的或专业性任务往往只需要开发短小精悍的程序就能解决。为此开发这些一次性程序终端用户可能需要投入大量时间和精力来学习各种领域特定语言（DSL）这也给用户带来了一定程度上的不便

在本文中,作者开发了一个通用框架.该框架设计了一种程序合成器(Synthesizer),能够基于自然语言生成目标域特定语言(DSL)的代码.该合成器采用dsl定义与训练数据(Natural Language/DSL对)作为输入,经过训练形成一个分类器模型,该模型基于关键词编程翻译并利用自然语言处理提取关键特征,最终实现了目标程序的生成.通过这种方法,该框架适用于多个应用场景,包括重复文本编辑智能教学系统以及航班信息查询.实验结果表明,作者通过本文提出的方案构建了120余种英语描述分别对应不同领域的程序生成系统.预期生成的目标程序在综合评估中通常位于前1名及前3名的位置

关键词：自然语言；领域特定语言；程序合成

1 引言

程序合成(Program Synthesis)是一个基于给定规格(Specification)，利用某种基础领域特定语言(DSL)作为基础进行自动生成程序的过程。传统程序合成依赖于完全规格(Complete Specification)，然而由于编写完全规格本身就存在显著的挑战，并且对生成程序进行结果验证（Verification）也十分复杂困难，在实际应用中面临着极大的局限性。因此传统程序合成主要用于学术研究领域，在实际工程应用中则因诸多局限性而鲜有应用。

最近，相关研究尝试在程序合成过程中使用样例(Examples)作为指导合成的规格。该类研究已经得到了广泛应用，其原因在于：相比于完全规格，样例规格往往更容易获得。比较典型的例子有实例编程(Programing by Example，PBE)系统。由于样例需要与准确的程序意图相结合才能形成样例规格，因此，当样例的需求量过大时，规格的构建将变得十分困难。如 L 算法——一种用于描述常规语言的 PBE 系统——它的一大缺点就是系统构建需要依赖大量的样例；再如像航空旅行查询系统(Air Travel Information System，ATIS)这类的专业领域，要求终端用户(即普通乘客)构造成充斥着专业名词输出/输出样例是一件几乎不可能的事情。但与 L 算法所处的场景不同，ATIS 领域的合成问题存在改进的可能，因为“航线查询”这类领域任务通常可以利用自然语言描述。由此，作者认为自然语言的描述也许能够指导程序合成可靠地进行。

在本文的研究中，针对利用自然语言(NL)生成基础底层特定语言(DSL)程序的问题进行了研究与解决方案设计。由于自然语言（NL）本身的不精确性特点，在保证生成的程序能够满足准确性要求的前提下提出了新的处理方法。具体而言，在传统方法仅能产出单个结果的基础上进行改进，在这里我们将合成器输出定义为一系列经过排序的结果程序集合，并在此基础上提供多种验证途径供用户评估和选择合适的生成结果。通过实验分析发现，在测试基准数据集上该算法表现稳定：当处理任意给定序列时，在80%的情况下系统能够正确识别并返回Top-1级别的候选方案；而对于90%以上的样本则能够集中返回排名前三的最佳方案集合以供进一步筛选使用。此外，在算法实现细节部分我们还特别增加了对关键中间步骤进行动态监控的功能描述，并对核心数据结构进行了详细阐述以提高算法可解释性和可维护性

本文提出了一种新型程序合成系统，在应用开发框架时可为设计者提供多样化的输入支持：首先需提供DSL说明（包括从DSL操作到对应NL描述/概念的具体映射关系）；其次还需提供一组训练样例对（Example Pair），每对样例包含一组英语描述与一个相应的预期程序实例。在训练环节中：第一阶段将采用半自动化过程识别英语单词与DSL终止符之间的对应关系；第二阶段将利用通用综合算法实现英语单词最优权重/分类符（Optimal Weight/Classifier）的自动确定。总体而言，在完成上述步骤后本文方法所构建的NL-to-DSL程序合成系统可被视作一种通用架构

2 研究动机

作者在研究探索阶段识别了可应用于NL-to-DSL合成器的三种具体应用场景：涉及NL-to-DSL合成器的应用包括高阶文本编辑操作（第2章第1节）、涉及基于NL-to-DSL合成器的问题出现在智能教学系统中以及与NL-to-DSL合成器相关的航空旅游信息系统查询问题（第2章第3节）。

1 文本编辑(终端用户编程)

在浏览 Office 程序（如微软Excel及Word）的帮助论坛时,作者看到了许多关于"如何实现重复文本编辑操作"的问题.例如:在Word文档中,根据特定情况执行插入、删除、替换或提取等操作,如表1(b)所示.这些高级操作相比简单的文字搜索与字符串替换更为复杂,属于高级文字处理技术.高级处理技术具有以下两个显著特点:一是字符搜索采用正则表达式而非固定值;二是编辑结果与目标文字的位置密切相关.进行高级文字处理通常需要使用者掌握正则表达式、条件语句以及循环语句的基本原理与应用方法,而这对于绝大多数普通用户而言都显得过于专业.

表 1 文本编辑领域相关的语法和基准样本

上述需求启发作者设计一种用于实现高阶文本边界操作的命令语言,该语言的部分语法如表1(a)所示.语法中包含了用于文本编辑的关键命令,如插入(Insert)、删除(Remove)、打印(Print)和替换(Replace).这些命令均依赖一个明确其作用范围(比如一组行一组单词或整个Word文档)的IterScope表达式.选Str产生式(Production)内含一个允许有限通配符匹配的动作Token一个用于过滤匹配值的布尔条件BCond以及一个基于下标的选择记号——出现值Occurrence.例如我们可以使用AtomicOccurrence中的FirstFew(N)项来删除符合匹配条件前N的结果;特别地当Occurrence值为ALL时所有满足匹配条件的结果都将被删除.布尔条件BCond涵盖了诸如ContainsStartsWith等一些标准字符串匹配谓词由原子条件AtomicCond构成支持AndNot在内的条件组合.C共同Cond产生式指定了相对于某个字符组合的位置比如在某个字符组合之后After(Token)在某个组合之前Before(Token)和某两个组合之间等Between(TokenToken).样例1和样例2分别给出了针对表1(b)中所示的编辑任务1和2的命令语言描述.

此外，在表 1(c)中展示了该语言系统能够处理的各种变式情况。所有这些自然语言任务均可用表 1(a)中的DSL语法进行描述。研究者认为表1（a）所给出的DSL语法足以支持高级文本编辑功能：当用户熟练掌握并运用DSL语言执行基本条件性文本操作后，则可以通过将复杂的问题分解为若干简单问题来实现更为复杂的文本处理功能。

2 自动机理论(智能教学)

形式化方法的研究成果已在智能教学系统中得到广泛应用，在多个关键环节中发挥了重要作用, 包括问题生成（Problem Generation）、题解生成（Solution Generation）以及基于几何学与自动机理论等领域的反馈机制（Feedback Generation）等多个方面. 每个环节均涉及一个特定的编程语言框架, 用于创建习题, 输出解答过程, 并提供针对学生答案的意见.

作为示例讨论自动机构造问题：设想一位学生需要构建一个能够接受一段描述某种语言的英文段落（如表2所示）。基于Alur等人所提出的构造类似语言所需要素的标准，本研究设计了一种特定的编程语言（Domain-Specific Language, DSL）。为此，本研究设计了一种特定的编程语言（Domain-Specific Language, DSL）。该系统可提供两种主要功能：第一种功能是根据正确答案评估学生的解答；第二种功能是根据学生的回答自动生成变体问题。

表 2 有关自动机领域的基准样本

样例 3 和样例 4 分别展示了表 2 中规格 1 和规格 2 的 DSL 翻译结果。

3 航空旅游信息系统(ATIS)

ATIS 作为标准基准，在航空旅行信息查询方面发挥着重要作用；它不仅包含了英语查询功能，并且整合了航班信息数据库。自成立以来，在自然语言处理与语音处理领域内已经积累了一定的经验与技术成果；表 3 展示了一些来自 ATIS 的查询样本。

表 3 ATIS 领域的基准样本

该研究开发了一种基于SQL行列操作的专用语言（DSL），其主要功能包括执行谓词和表达式的运算。该DSL中的功能项与航空旅行查询领域的出发地/目的地、日期、价格等关键指标具有对应关系。表3中第一个DSL指令语句可转换为如样例5所示的具体形式。

样例 5 表 3 中第一个查询语句的 DSL 表示

3 问题定义

本文深入探讨如何基于给定的 DSL 和训练数据集构建目标 NL-to-DSL 合成器。现给出如下定义：

该领域特定语言L=(G,TC)由上下文无关文法G构成（其中GT代表终结符集合GR代表产生式规则集合）以及能够验证给定程序类型正确性的类型/语义验证系统TC组成构成一个系统

(2) 训练数据：训练数据构成由一组形如(S, P) 的对集合。其中，S 可被视为一个英语句子序列，并且 P 是由领域特定语言 L 编写的预期程序。

NL-to-DSL的功能目标：生成的 NL-to-DSL 生成器应当能够将一个英语句子转换为一系列经过排序的程序代码集合{P1, P2, …, Pk}。其中所有这些转换后的程序均由编程语言 L 编写。

4 语言转换算法

本文所提出的合成算法（算法1）由用户输入自然语言指令作为输入，并生成候选DSL优先级列表作为输出。该算法的第一阶段（位于第2行的循环）通过预先定义好的NL到终止符号映射字典结构NLDict将用户的输入句子中的每个词转化为一个或多个终止符号。该循环依次遍历输入句子中的每一个字符。对于每一个索引位置，在此过程中算法将调用NLDict提取出相关的词，并在目标语言库中检索与这些词相关的终止符号集合。其核心在于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, 其对应于算法中的第五步操作. 随后, 在最后一步操作中, 算法根据得分与权重对ResT中的所有候选程序进行排序

4.1 一致程序的综合

在DSL中定义程序P有两种可能性：一是作为基本值（即来自G中的terminals），另一种则是对参数列表施加函数或运算符的作用。通常情况下，在DSL中将函数应用表示为s-expressions（s-表达式）。具体来说，在这种表示法中，一个接受k个参数的函数F会被写成(F, P₁, ..., P_k)，其中P₁到P_k代表输入的各个参数。

Consistent Programs and Witness Maps.

给定一种编程语言规范（DSL）：L = (G,TC)，如果存在一个转换函数M能够将句子S中的某些词汇转换为GT中的终止符，并且其覆盖范围与程序P所包含的所有终止符一致，则我们称这种转换函数为目击者转换，并记作WitnessMaps(P,S)表示所有这类转换函数的集合。（需要注意的是，在自然语言中同一个英文词在不同位置可能会导致不同的语义解释；因此，在这种情况下该方法要求任何这样的转换函数都需要考虑上下文的位置信息。）然而该论文未对此进行说明

Usable and Used Words.

Let S be an English sentence, and P be a program consistent with the English sentence S . The usable words in S , denoted by UsableWords(S), are the words that are mapped to some syntactic terminal symbols; therefore, it may be useful for translation. The set of used words in S , denoted by UsedWords(S, M), consists of the words that are available for mapping; it is used as part of the mapping process for M .

Partial Programs.

一个部分程序扩展了概念域，并允许将一个hole用作参数输入。即表示一个占位符符号（即在一个完整的小规模程序中填充它）。为了简化描述起见，在这种情况下我们可将其简称为‘程序’。给定一个部分程序 P = (F,...,✷,...) 有一个hole ✷位置，在这里我们可以用一个完整的子系统 P' 来填补这个占位符符号位置：

有效性验证 TC 确保所有合成程序均在 DSL 语法和类型系统方面精确规范地进行了定义（否则我们将返回无效程序 ⊥）

Combination.

该运算符用于生成所有有效程序的集合；这些集合中的每一个元素都是通过将完整程序P' 替换到部分程序P中的某个特定hole位置而实现的；具体来说，则是通过遍历P的所有参数并在存在hole的位置生成相应的替换操作而完成这一过程；对于给定的部分程序P=(F,P1,...,Pk) 和完整的程序P'而言：

Bag Algorithm.

算法 2 Bag 子合成算法

Bag 算法（ Alg. 2）由遍历程序集中所有适当类型的组合来计算程序集的闭包。 其主循环部分（位于第 2 行）执行的是对已构建程序结果集的不动点迭代运算。 当我们在应用 SubAll 函数时，默认假设 P2 是一个完整的程序（第 5 行），这一假设确保了最终生成的结果程序中唯一的 hole 来自于初始输入中的 hole。 在这种情况下，默认将 B0 的初始化仅限于包含完整程序以及仅在其顶层含有 hole 的部分程序。 这种限制允许我们通过归纳推理得出结论：在每一步操作中，默认所有部分程序都只会在顶层含有 hole。 因此我们可以按照自底向上的方式高效地计算出所有可能的部分程序及其对应的不动点集合。 只有当两个函数 UsedWords(S,M1) 和 UsedWords(S,M2) 的交集为空时（第 6 行），才能保证两个生成器不会共享来自用户输入词表中的相同词汇集合；这种特性也保证了最终生成的所有可能组合数量是有限制的，并且与输入中的单词数量相关联。 第 8 行描述了如何构造出所有潜在替换到 P1 中 hole 的可能性集合（但排除掉那些会导致无效结果的情况）。 对于每一个潜在的可能性进行评估后，在第 9 行将其映射结果与当前映射集合取并集以更新新生成器库；由于这些映射操作域互不重叠因此联合操作具有明确定义性

4.2 一致程序的排序

我们坚信合成系统中抽象语法树由两个关键要素构成：一个是系统中的token集合另一个是该集合中token间的层次关系结构。通过对这些基本元素的数据特征进行分析我们可以计算出以下三个指标用于评估一致系统的性能表现：其一是覆盖度评分衡量英语文本中被系统映射到操作或值的数量其二是intent mapping评分衡量了token到token间映射关系对用户意图传达的效果其三是架构评分反映了语法树结构特征及其与文本部分间的关联程度

4.2.1 覆盖率分数

对于给定的句子 S、候选翻译 P 和见证映射 M，覆盖率分数定义为，

CoverageScore(P,S,M) 是衡量S中实际用于生成P的信息量占总可用信息的比例。该指标旨在尽可能多地利用输入信息。

第一个程序 P1 基于用户输入的全部内容，并包含最低票价的信息；相比之下，第二个程序 P2 完全忽略了这一关键信息。Coverage 分数表明，在综合评估后,P1 的排名位于P2之上。

4.2.1 映射分数

对于任何一个词 w，在其对应的 NLDict(w) 中可能存在多个终止符（即函数或值），每个终止符对应着对 w 的不同解释。我们利用机器学习技术从斯坦福 NLP 引擎 [26] 提供的词性标注数据中训练出一个分类器 Cmap。Cmap 的预测函数用于评估将每个词正确映射到其对应的终结符的概率。基于 Cmap 的预测结果计算 MappingScore 值，则该值表示 P 集合中的所有终止符能够正确解释 S 集合中相应单词的可能性。

MappingScore分数的一个限制是什么呢？它仅考虑单个词之间的映射关系，而忽略了词语之间的相互关联及其翻译映射方式。因此，在正确翻译中交换一对终结符可能会导致相同的错误评分。

这两个程序共享同一个词汇表，并因此拥有相同的覆盖度评分。 主要区别在于单词'beginning'在P1中对应于带有动词性质的StartsWith，在P2中则对应于介词性质的Before。 通过覆盖分数的比较可以看出P1是更为合适的选项。

4.2.3 结构分数

结构得分反映了子程序放置中的自然性概念。我们利用句子 S 中的连接特征、结合其自然语言解析树 NLParse(S) 和程序 P 来定义整体结构得分。这些特征被用来构建分类器 Cstr，并用于评估每个组合的成功几率。

说明 1（联结）。 对于形如 N → N₁ …Nᵢ …Nⱼ …N_k 的产生式 R ∈ GR 中的元组 (R, i, j)，其中 1 ≤ i, j ≤ k 并且i≠j，则被称为这种联结的一个实例。

定义 2（组合）。 采用产生式 R :N → N1N2 ...Nk 的方式构成一个程序 P = (P1,P2, ..., Pk)，其中每个 Ni（当1 ≤ i ≤ k）都会生成相应的 Pi。这些子程序之间的组合关系通过 Conn(Pi ,Pj) 来表示。

整体结构得分是基于程序 P 的各种连接概率计算这些概率的几何平均而获得的整体评分——这一过程用于将分数规范化处理以便于解释不同连接数对系统性能的影响。

我们为每个连接 Conn 分配了一个独立分类器 Cstr[Conn]。该函数 Cstr[Conn].Predict 负责计算输入向量 f-vec 出现在正确翻译中的概率值（标记为1），其余情况则标记为0。
给定一个程序 P 和输入句子 S，则称它们之间存在基于见证映射 M 和解析树 NLParse(S) 的关联关系。以下函数描述了一系列重要关系：

在本节剩下的部分中, 我们考虑到 P_1 和 P_2 代表了程序 P 的两个子组件. 这些特性影响了程序 P 及其子组件 (P_1 和 P_2) 与系统 S 之间的天然连接程度.

其词性特征是由 NL Parser 分配为分别与 P1 和 P2 相关联的子树根节点所具有的词性标签。

特征 fpos1 和 fpos2 有助于学习通常使用特定连接组合的短语。

定义 4（LCA 距离）。 定义 LCA 为 Root(P1,S,M) 和 Root(P2,S,M) 的最低公共祖先（lowest common ancestor）。 其属性表现为：从 LCA 到分别与 P1 和 P2 相关联的子树根节点之间的路径长度即为其距离（distance）：

序号规定为5的项（即"顺序"）定义如下：该属性的值取决于与P1及P2相关联的子树根节点在NLParse(S)生成的中序遍历序列中的位置。

相关参数flca1、flca2和forder被用来建立解析树结构与程序语义之间的映射关系。通过这些相关参数，我们使得生成的翻译框架与解析树的架构保持高度一致。

说明 6（重叠）。 重叠特征捕获了这两个程序由 NL 解析树中的两个子树的混合构造的可能性：

考虑两个系统 P1 和 P2，在分析它们所使用的单词跨度差异的基础上... 作为一个衡量系统之间相似性的重要指标。

fover 和 fdist 特征能够提取单词之间的邻近关系，并且具有显著价值；这是因为相关词汇在输入句子中通常会同时出现。

在解析树NLParse(S)中，“output”函数接受两个参数：“输出类型（line）”以及其执行条件“仅在不包含834的情况下”。通过分析候选程序的功能模块设计我们可以发现

(a) 单词 "positions" 更接近 "print area" ，而单词 "834" 在 NLParse(S) 中更远。 对于 P1 来说我们能够观察到相同的结构模式 ，然而对于 P2 来说他们无法观察到同样的模式。 这归因于 LCA distance 捕捉到了这种差异性。

NLParse(S)中的单词顺序与P1中的顺序匹配，在P1中遵循这种顺序比在P2中更为理想。这是因为这种方法能够有效捕捉到序列特性。

(c) 在P1中，“not contain 834”这一短语得以保留完整，在P2中则被拆分为两个部分。重叠与距离特征将会捕获这种分解及其重组的方式。
这两个程序采用了相同的词汇库，并建立了相同词汇到终止符的映射关系因而获得了完全一致的覆盖分数与映射分数值尽管如此 程序P1是正确的我们所选择的特徵使得它在这类任务中表现更为优异

4.3 综合分数示例

为了深入探讨各种分数的互补优势及其局限性时

Add a “*” at the beginning of the line in which the string “P.O. BOX” occurs.

表格 4 列举了 Bag 算法产出的一致系统列表。其中第一个系统（P1）被视为预期翻译基准；我们可以观察到每个组件得分的表现情况

覆盖率分数： P1 和 P4 都使用句子中的最大单词数，并列在最高分上。 P4 是错误的，因为它添加了“P. O. BOX”在包含“*”的行的开头。
映射分数： 我们系统学习的分类器将单词“beginning”映射到终结符 StartsWith 的概率很高，但映射到终结符 START 的概率较低。 此外，它以更低的概率将“发生”映射到终结符包含。 P2 不使用“occur”这个词，否则它与 P1 具有相同的映射。 因此，它比 P1 具有更高的映射分数，但在覆盖率方面受到影响。 P3 将“beginning”映射到 StartsWith，并且不使用“occurs”这个词。 因此，它的映射分数低于 P2 但高于 P1。 如果我们单独使用映射分数，我们将无法将所需程序 P1 排在错误程序 P3 和 P4 之上。

结构评分： 仅关注单个词的映射关系而忽视其与其他映射之间的关联及其在原始句子中的位置的评分标准存在不足。通过分析句子的结构信息（如语法树、词序以及词间距离），结构评分得以解决这一问题。
P4 的评分很低，原因在于它颠倒了字符串‘*’ 和 ‘P.O. BOX’在句子中的顺序。当 P3 将‘beginning’（对应于StartsWith）从‘Add’（对应于Insert）中移除时，在这种情况下也会受到影响。
P1 获得了极高的评分标准，在此评分体系下表现最佳因为它成功地保持了输入文本原有的语法框架。值得注意的是 P2 和 P5 的评分同样很高这是因为该评分标准未考虑所使用单词数量以及单词到终结符之间的映射关系。因此即便使用少量单词却准确地将其映射至恰当终结符并正确放置它们也有可能获得较高的评分值。
所需的程序 P1 在单一评分维度上表现最优但由于其在其他方面同样出色因此最终综合排名仍然位于榜首即使这种情况下其排名也会与另一个不正确方案并列第一！
但是当将各单项评分类别与其相应的权重进行综合考量时 P1 将毫无疑问地成为最优秀的方案！

5 训练阶段

本节阐述了第4节所述合成方法所采用的分类模型、权重设定以及词到终止符映射的学习流程。其中最为关键的是：(1) 选择采用何种机器学习方法；(2) 基于DS/OL开发者提供的高级训练数据集为该机器学习模型生成相应的基础训练样本

5.1映射分数分类器Cmap

Cmap分类器的主要目标是基于单词w及其POS标签来计算映射到终结符t ∈ GT的概率值。该分类器的学习过程基于朴素贝叶斯算法[6]进行设计与实现。具体而言,其训练数据集如算法3所示

核心概念是先生成所有可以从自然语言输入 S 中产生程序 P 的见证映射集合 M 。随后通过利用相似性得分元组（likeability score tuples）所定义的字典偏序（partial lexicographic order），从候选集合 M 中筛选出最优的见证映射。文中给出以下推导：

相似性元组主要基于两个目标服务：第一，在借助UsedWords机制下，系统会更加关注那些能够充分利用输入语句各组成部分的映射；第二，在Disjointness约束下，则会优先减少单一输入部分对多个子程序构建的影响。

5.2 结构分数分类器Cstr

本段将详细阐述旨在服务于结构得分服务的分类器Cstr及其训练流程。针对每个连接对象Conns系统都会自动分配一个相应的Cstr[Conns]进行识别。每个Conns对象都配备了一个相应的Cstr[Conns]用于评估其属性匹配程度。本文采用了现有的朴素贝叶斯实现技术来构建训练数据集，并按照算法4的具体步骤进行了操作。

算法4的核心思路在于未记录单个步骤得分而构建合成算法（SynthNoScore）。其目标是通过生成一个英文句子S来产生包含所有可能程序结果的集合AllOpts。其中P'属于AllOpts中的一个程序实例。所有包含在P'中但未出现在原始程序P中的实例会被标记为负样本（Negative Example）；而那些同时存在于P'和P中的实例则会被标记为正样本（Positive Example）。

5.3 字典构建

本文提出了一种基于 DSL 终结符命名的半自动化方法来构建字典 NLDict。其中，在处理表示函数与参数的终结符名称时，默认采用与该功能相关联的标准词汇表进行查询与补充以确保语义一致性；对于那些由特定命名策略生成而非直接映射到标准术语系统的术语（如 StartsWith），系统会先对操作名称进行分层解析，并提取每个层次的关键组成部分后再分别查证相应的同义词集合以实现精准匹配

需要注意的是：WordNet提供的同义词集合可能包含一些在目标特定领域无意义的英文词汇。该问题由第5.1节所述算法3解决：基于映射得分为训练依据。此外，在完成分数分配后会剔除所有分数低于设定阈值的所有映射；此外，在某些情况下WordNet可能无法提供某个特定领域内极为重要的英文词汇，并且在某些情况下DSL中的终止符名称也无法有效对应到英文词汇。鉴于此，在这种情况下算法4将无法生成见证者映射，并且系统能够自动识别这种情况并告知用户其输入中有哪些词汇无法与终止符有效对应。这些不能正确对应到终止符中的会被用作种子词（Seed Word）输入到 WordNet以便进一步生成更加全面的同义词集

5.4 学习组合权重

在之前的内容部分中, 我们对翻译过程进行了详细划分,将其划分为三个主要方面: 输入语言、输出语言以及翻译规则. 该方法通过加权计算得到各组成部分对应的评价指标值, 最终形成一个综合得分. 在这一章节, 我们将介绍一种新的学习方法, 旨在优化权重参数以使目标函数达到最大值.

优化函数：训练集中的基准数量，正确翻译的等级为 1。

在数值优化问题中,实现目标函数的最大化是一个经典的范式,通常可借助随机梯度下降方法[5]加以解决. 作为一种必要的数学工具,我们需构建一个连续可导的损失函数F_{loss}来指导迭代过程. 这一损失函数将被用于寻觅一组参数,其能在这些参数作用下使目标函数达到全局最大值.

其中∇表示梯度符号, γ 是一个正数. 每次迭代, 参数 w 沿着损失函数下降方向移动, 当连续迭代过程中损失函数的变化量小于预先设定的阈值 ε 时, 算法终止.

常见的损失函数形式包括sigmoid。为了使我们的不良优化函数能够更好地适应梯度下降的需求，我们可以将其转换为更接近所需的形式。具体而言，我们可以通过构造基于最佳错误结果比率分数和期望速率分数的sigmoid模型来实现这一目标

尽管上述转换使得大部分损失函数表现出良好效果（good performance），然而它被适当饱和，并且在分段上是连续且可微的（continuous and differentiable in segments）。尽管如此，在某些点上仍存在函数不连续的情况（points of discontinuity）。特别地，在 Vwrong 的定义中使用 max 函数会导致在 Floss 中出现不可导的情况（不可导）。然而这些见解表明我们可以用一个处处可导的方式替代当前的最大值操作：）

从而使得我们能够用该函数替代max运算符，并在此基础上自然地将这种扩展应用至k个参数的情形下。在Vwrong计算中生成了一个全局连续且可微的整体损失函数，并且这种扩展方式能够自然地容纳多个输入参数而不引入额外复杂性或计算开销。为了减少出现错误结果的数量并使各个分数之间呈现出高度相似性的情况发生概率最低的同时还可以调节不同结果之间的相对重要程度为此我们建议将c设置为较大值这样可以更加显著地降低错误情况的发生几率进而提升整体模型性能此外在两个分数极其接近的情况下（即最坏情况下）近似的影响会引导梯度下降过程朝向提高Vwrong与Score(Pdesired)之间比率的方向发展这一设计既不会影响梯度下降算法的有效性也不会引入任何额外的技术难题

除了能够实现梯度下降的基本需求之外，在λ取较大值时我们的损失函数Floss会趋于饱和。这意味着对于任意给定的输入S（V_{wrong}/Score(P_{desired}) \gg 1），它将不会主导损失函数Floss的变化，并且会导致在提升单一基准性能的同时不得不牺牲其他基准整体性能。其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态。其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态。其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态. 其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态. 其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态. 其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态. 其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态. 其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态. 其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态. 其收敛性体现在即使在没有优化空间的情况下也能稳定地达到最优解状态. 其收敛性体现在即使在没有优化空间的情况下也能稳定地到达

6 实验评估

基于 Bag 算法与特征提取技术（主要用于排名评估）构建的一种在线集成方法主要由 C# 语言实现，并借助斯坦福 NLP 引擎（版本 2.0.2）完成词性标注及其他自然语言处理功能

本研究的主要目标之一在于开发一个通用框架...为此, 我们选择了三个不同领域的任务类别, 分别包括问答任务(atis), 基于约束的模型构建任务(自动机理论辅导),以及非结构化数据处理中的命令执行任务(重复文本编辑). 这些领域(在第2章中进行了详细阐述)涵盖了底层dsl中的各种组成要素, 包括所采用的语言习语以及常见英语句子的表现形式. 在基准测试中, 自动机描述是通过教科书及在线作业中的原文直接提取; 文本编辑描述也是逐字来源于帮助论坛及用户的调研报告; atis描述则取自标准套件. 表1(b)、1(c)及表格2与3共同构成了一个基准样本集合. 关于该基准集合的具体细节及其获取途径, 可参考配套网站: https://sites.google.com/site/nl2pgm/[9].

航空旅行信息系统 (ATIS)

我们随机选取了完整版的ATIS集合（包含数千个问题），并利用我们的DSL开发了一种专门针对这些查询的程序以完成其操作。ATIS领域中的每一个任务都涉及与飞行相关的信息查询。

自动机理论辅导

研究人员从相关自动机理论教材及网络课程资源库中整理出约两百四十五台有限状态自动机的自然语言规范（即其接受条件）。

重复文本编辑

我们汇编了来自Excel书籍及辅助论坛中的共21项文本编辑任务说明。在用户研究的基础上,我们整理出这21项任务共包含有来自不同来源的英文描述,其中本研究招募了包括本科一、二年级学生的在内的共25名参与者

6.1 准确率、召回率和计算成本

本研究采用了标准的十折交叉验证方法测定译员在各个领域的准确率与召回率指标。随后从数据集中选取90%的数据作为训练集以建立分类器/确定权重参数；剩余的10%数据则用于系统性能评估（非训练阶段）。关于排序结果的具体计算方式，在论文[46]所提出的1334排序方案下进行处理：当多个对象具有相同的排序分值时，在这些对象构成的组别内统一赋予一个对应的最低排序位置值。

准确率

图 1 描述了在 DSL 方法中所需程序作为最高排名结果所占的输入比例；此外还提供了所需结果在前三个结果中的分布情况。在超过 80% 的输入样本中（其中每个领域均达到这一比例），所需程序均被明确标记为排名第一的结果。特别地，在 ATIS 领域这一比例进一步提高至 88.4%，并呈现出显著的稳定性（±4.2%）。基于来自完整 ATIS 套件的样本数据（如文献[57]、[42] 和 [27] 所示），我们可以得出结论：所需的程序将在自然语言处理任务中展现强大的竞争力——其准确率达到 88.4%，置信区间为 ±4.2%（95%置信水平）。这些研究数据表明我们提出的方法与当前最先进的自然语言处理系统具有可比性

召回率

在大多数输入中持续不断地生成所需程序。
然而, 排名算法将所需程序置于前三个结果中的概率仅为5%-12%.
因此, 在所有三个研究领域中,
这些需求的解决方案通常出现在前三名.
对于高于90%的自然语言查询,
它们会优先列出所需的结果.
然而, 在其他几个领域中,
仅有不到10%的查询会遇到这种情况;
特别是, 在文本编辑时只有5%
的问题能够得到解决,
因为合成器无法有效识别并将其列为前三位.

计算成本

图 2 展示出基于具有 8 GB RAM 和运行于 2.80 GHz Intel(R) Core(TM) i7 CPU 上的算法合成与执行排名的时间分布情况。完成文本编辑平均耗时为 0.68 秒 自动化系统完成 ATIS 输入平均耗时为 1.38 秒 而此过程的整体时间分布则明显偏向某一侧 在超过 85\% 的案例中仅需不到 1 秒即可完成任务 而仅有少数案例会超出 3 秒的时间限制 这些超出范围的情况往往是由用户采用了冗余的方式来描述具体的操作指令所导致

基于指数空间搜索的方法等同于所有综合技术。然而主要挑战在于实际案例中高效地实现这一点。我们的技术代价在最坏情况下是DSL规模呈指数增长。此外我们的合成能够快速处理一系列有用的DSL（通常不到1秒）。值得注意的是字典规模对翻译时间的影响最小

6.2 单个组件评估

在第四节中阐述了用于排序的各种组成部分并从直观上解释了这些组件的价值.为了考察这些组件分数对于获得良好结果的重要程度我们采用了不同组合的组件分数集合并通过优化不同权重值以及重新排列程序中的相关模块或步骤来进行评估

单个分数的表现

实验结果表明，在筛选出性能较高的程序时，单独采用CoverageScore指标可获得17.9%的有效率；而仅使用MappingScore指标则达到31.0%，StructureScore指标则表现最佳为51.4%。这些数值均低于采用组合评估策略时的最高结果84.9%（即将所需程序占输入总量的84.9%）。因此，我们得出结论：单一组件无法满足需求

得分的独立性

虽然这些结果表明单独的任何组件都无法单独进行程序排名，但有可能存在一种情况：其中一个组件实际上是另外两个组件的组合。表6详细列出了在移除某一个组件时对程序进行排序的影响结果。具体而言，在丢弃StructureScore时所导致的性能下降最为显著——最坏情况下可达81.86%，即使是最优的情况也仅有47.75%的性能保留。同样地，在降低CoverageScore时也会带来明显的性能退化（相比StructureScore略为温和），而丢弃MappingScore的影响相对较小（范围控制在2.04%至4.67%）。值得注意到的是MappingScore持续稳定的积极贡献使其在评分中仍发挥着重要的作用

字典构建

在实际应用场景中进行半自动构建时

分数组合权重

采用梯度下降算法训练计算程序中各分项在最终排序中的重要性程度。我们通过对比梯度下降得出各分项重要性程度与其所有分项均等分配的情况以及增强技术应用效果的结果来检验这些重要性的准确性。该技术通过将一组较弱的表现（如单个组件的具体分数）结合起来生成一个强大的综合排序。表7列出了采用三种不同方法所得出的各项排序结果。

与基于传统权重选择的方法相比，在使用梯度下降算法时显著地提升了排名靠前的基准的数量（达到15%）。然而，在排名靠前的几个位置上所获得的改进相对较小。同样地，在这些位置上所获得的结果显著优于RankBoost算法，在排名靠前的位置上两者的平均年龄差距仅为9%。因此，在综合考虑各种因素的情况下我们建议优先采用梯度下降算法来学习组合权重以获得更好的效果

选择合适的排名函数对于确保结果质量至关重要。如表6所示,移除任何组件函数都会显著影响精度。相比之下,采用梯度下降法与简单的方法（如等权重或提升[10]）相比,计算组合权重时会带来9%-15%的精度损失（见表7）。在我们的系统中,大多数解决方案未能进入前三个的主要原因在于英语描述中的隐含信息不足,例如“I want to fly to Chicago on August 15”。在这种情况下,默认出发城市应设为"CURRENT_CITY",时间设为"ANY"。类似的问题可以通过提供规模更大的训练数据或构建专门的支持来解决每个领域中的隐式上下文信息的问题。

在学习分量分数权重中, 我们采用了逻辑函数的一个移位变体来构建我们的损失函数（见第5节）。 图3展示了损失值随迭代索引及领先基准数量的变化情况. 可以看出, 损失值与领先基准数量呈负相关关系. 因此, 这些变量之间的负相关性是梯度下降算法最佳性能所需的关键因素, 即使我们使用了最大操作并对其取对数近似之后, 损失函数依然表现出良好的适应性.

基于 §4.2 的分析可知，在各个领域中所学得的学习权重具有通用性。实验数据表 8 显示，在将单个领域内的学习所得应用于另一个领域时，则能较好地排序节目列表。具体而言，在排序列表中的节目数量平均下降仅为1.9%，其中最大降幅达5%，因此我们未将其纳入考虑范围之内。这一结果充分证明了分量权重的学习机制具有高度跨域独立性以及良好的泛化性能——即可以通过直接重用这些 learned weights 来快速适应并开始新的研究领域工作

7 相关工作

该系统通过用户的任务执行进行跟踪记录，并采用基于一组输入输出示例的学习方法，在多个终端用户编程领域得到了广泛应用（参考文献[7]）。其应用涵盖文本操作（参考文献[28]）以及表格转换（参考文献[23}）等（参考文献[7}）。Gulwani团队近期的研究成果涵盖了字符串处理（参考文献[13,48}）、数字运算（参考文献[49}）以及表格处理（参考文献[21}）等多个方面。（如前所述），当处理需要条件判断的操作时… 相较而言… 基于自然语言的方法表现出色。

关键字编程是指将一组或一序列的关键字通过特定的 API 转换为函数调用的行为。这些 API 或者基于现有编程语言的操作 [34, 41, 54] ，或者是专为特定任务类别设计的Domain-Specific Language [32, 33]。这些技术利用底层 API 元素构建表达式树的方法多种多样，并采用启发式排名方法对生成的结果进行排序。尽管如此，在处理具有复杂意图的输入时准确率较低 [34] ，其中最高准确率达到88%（我们达到了这一水平），但仍然经常推荐不正确的程序。

语义解析[39]是一种基于专门的语言解析器从自然语言构建程序的繁琐方法。到目前为止,已经开发出多种相关技术,其中包括方向性语义[25], 基于NLP的解析树[11], 被支持向量机驱动[24], 组合分类语法[27,56,57], 以及基于依赖关系的语义分析[30,42].这些系统通常表现出极高的准确性,一般会给出正确的程序建议;然而在ATIS任务中其召回率却低于85%[57].相比之下,本文提出的技术不仅带来了超过92%的召回率,还在准确度上达到了或超过了现有方法.

许多自然语言编程系统都是基于语法、NLC [4] 或模板等方法构建的，并以特定方式约束用户的输入表达式。这些系统对于语法错误或无关术语表现出高度敏感性。针对开发数据库的自然语言接口 (NLIDB) [2, 40] ，研究人员进行了深入研究。尽管早期系统主要依赖于将用户输入与预设模式进行匹配的方式处理问题，但Precise [43, 44]通过将语义上较为容易处理的语言问题转化为相应的SQL查询实现了突破性进展。然而这些系统由于高度依赖于具有预定义模式的基础数据，在面对未预先定义的数据结构（例如本工作中所使用的文本编辑域等未知或不存在的情况）时就显得力不从心。

该系统[29]能够从自然语言（NL）自动生成智能手机脚本。 该系统的核心技术在底层智能手机领域具有高度的专业化，并采用简单的排名策略来生成程序。 类似地，在特定领域（如mula所涉及的电子表格）中设计了该系统[20]能够从自然语言（NL）合成电子表格公式，并采用相对简单的基于覆盖率、映射和重叠特征等价物的排名机制。 同样地，在特定领域（如mula所涉及的电子表格）中设计了该系统[20]能够从自然语言（NL）合成电子表格公式，并采用相对简单的基于覆盖率、映射和重叠特征等价物的排名机制。 相比之下，我们的方法与目标Domain-SpecificLanguage（DSL）的具体细节无关，并且会自动学习这些特征的最佳权重配置。 此外，请参考表6中的实验结果以了解使用现有排序方法会导致召回率/精度显著降低的情况。 因此，在本文中我们改进了针对NLyze/SmartSynth系统的排序方法，并通过整合这些改进进一步提升了其性能水平

[47] 中的研究工作基于自然语言来实现组合 PBE（以示例程序的方式进行编程）。 该方法未采用 PBNL 方法中所涉及的任何自然语言学习技术，而是仅依赖于将自然语言分解为短语的过程，并要求用户提供基于这些短语的示例解释。

8 结论

我们开发了一种新型元方法旨在从自然语言描述中生成程序。该方法能够支持一系列具有吸引力的Domain-Specific Language（DSL）实例具体包括文本处理方面的应用自动机构建方面的应用以及信息检索查询方面的应用。我们的元方法通过收集来自设计师的三个关键输入并基于这些输入构建了一个词汇至标记字典的映射关系进而生成高效精准的Domain-Specific Language解释器。该解释器能够实现一组基础训练数据集上的高精度与高召回率性能从而显著提升了代码理解和维护效率。

我们的主要目标是扩大该框架的应用范围，并为其提供更多支持以应对更广泛的领域需求。 另一个研究方向是在解析单个意图（如我们的）时引入上下文感知机制，并以此为基础构建交互式编程环境来处理更大规模的Domain-Specific Languages（DSL）中的复杂任务。