使用自然语言进行程序合成引用DesaiA,GulwaniS,HingoraniV,etal

文章插图
引用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）所示。这些操作比单纯的文本搜索或字符串替换要复杂的多，属于高阶文本编辑操作。高阶操作通常具有两类特征：① 字符串的搜寻条件不是常量，而是正则表达式；② 文本的编辑和目标文本的上下文有关。高阶文本编辑往往需要用户了解正则表达式、条件语句和循环语句的语法和语义，而这大大超出了绝大部分终端用户的能力。