代码生成是一个重要的人工智能问题，有可能显着提高程序员的生产力。给定以自然语言编写的规范，代码生成系统会将规范转换为可执行程序。例如，如果 python 程序员给出指令“初始化字典 Dict”，则代码生成器应自动生成“Dict={}”。
随着深度学习技术的发展，研究人员已针对此问题应用了各种神经体系结构，例如序列到序列(Seq2Seq)模型或序列到树(Seq2Tree)模型。尤其是，最先进的方法通过预测语法规则序列来生成代码。也就是说，系统保留已生成代码的部分抽象语法树(AST)，并预测将用于扩展特定节点的语法规则。
语法规则的分类面临两个主要挑战。第一个挑战是长时依赖问题。代码元素可能取决于另一个遥远的元素。例如，第 100 行的变量引用语句“if len(a)
在本文中，我们提出了一种新颖的神经体系结构 TreeGen，用于代码生成。为了解决第一个挑战，TreeGen 采用了最近提出的 Transformer 架构，该架构能够捕获长时依赖关系。但是，原始的 Transformer 体系结构不是为程序设计的，并且不能利用树结构，即上述第二个挑战。如在基于图和树的卷积神经网络中一样，利用结构信息的标准方法是将节点及其邻接节点的向量表示形式组合为结构化卷积子层的输出。但是，标准的 Transformer 结构没有这样的结构化卷积子层，并且不清楚在何处添加它们。
试图在所有 Transformer 块中添加结构化卷积子层是很诱人的。我们的核心推测是，在对一个节点及其邻接点进行卷积时，向量表示应主要包含原始节点的信息。随着节点的向量表示在 Transformer 的解码器中由更多的块进行处理，它们逐渐混入来自其他节点的更多信息并丢失其原始信息。因此，我们仅将结构卷积子层添加到前几个 Transformer 解码器块中，而不是全部添加。
一般而言，TreeGen 体系结构包括三个部分：(1)自然语言(NL)编码器：对文本描述进行编码;(2)AST 解码器(前几个 Transformer 解码器块)使用结构化卷积子层对先前生成的部分代码进行编码;(3)解码器(其余的 Transformer 解码器块)将 query(要在 AST 中扩展的节点)与前两个编码器组合在一起，以预测下一个语法规则。
我们在建立的基准数据集上评估了我们的模型，这是纸牌游戏炉石传说的 Python 实现。结果表明，我们的模型明显优于以前的模型 4.5 个百分点。我们进一步在两个语义分析数据集(ATIS 和 GEO)上评估了我们的模型，这两个数据集将自然语言句子转换为 lambda 微积分逻辑形式。结果表明，我们的模型在以前的神经模型中具有最高的准确性，分别为 89.1%和 89.6%。我们的评估还表明，将结构化卷积子层添加到前几个 Transformer 块中，其性能明显优于所有块中具有结构化卷积的 Transformer。
我们的模型：
我们通过预测编程语言的语法规则来生成代码。图 2 显示了我们模型的整体图，它包括三个部分：NL 编码器，AST 编码器和解码器。我们将在以下小节中详细介绍它们。
语法规则预测：
在本节中，我们介绍如何将代码生成建模为一系列语法规则的分类问题。程序可以被分解为几个与上下文无关的语法规则，并解析为 AST。例如，图 1 显示了代码“length=10”的 PythonAST，其中虚线框是终止符，而实心框是非终止符。
可以将基于 AST 的代码生成视为通过语法规则扩展非终止符。重复此过程，直到所有叶节点都处于末尾。在图 1 中，“1:root->Module”是语法规则的示例，其中前面的数字是规则的 ID。遵循预定遍历，我们可以获得在右上角显示的生成 AST 的规则序列。
形式上，概率可以分解为遵循以下顺序生成代码的规则的概率。其中 ri 是规则序列中的第 i 条规则。通过这种方式，我们的任务是训练一个模型以计算 p(ri|NL 输入，pi)，即给定自然语言描述和当前生成的部分 AST，该模型将计算扩展该节点的规则的概率。
NL 编码器：
输入的描述决定了代码的功能。它可以是炉石传说数据集中的半结构化描述，也可以是 ATIS 和 GEO 语义解析数据集中的自然语言。
对于输入的描述，我们首先将其标记为 n1，n2，...，nL，其中 L 表示输入的长度。然后将每个 ni 拆分为字符 c1(ni)，c2(ni)，...，cS(ni)，其中 S 是 ni 中的字符数。通过嵌入，将所有标记和字符表示为数值向量 n1，n2，...，nL 和 c1(ni)，c2(ni)，...，cS(ni)。
输入文字表示：
字符嵌入。相似词经常具有相似的字符(例如“program”和“programs”)。为了利用此属性，我们通过具有完全连接层的字符嵌入来表示标记。其中 W(c)是权重，字符序列被填充为预定义的最大长度 M。在全连接层之后，我们还应用层归一化。然后将这些向量反馈到 NL 编码器，并通过子层将其与词嵌入集成在一起。
NL 编码器的神经网络结构：
NL 编码器由一堆块(总共 Nd 个块)组成。每个块包含三个不同的子层(即，self_attention，gating 机制和单词卷积)以提取特征，我们将在以下小节中详细介绍。在两个子层之间，我们采用残差连接，然后进行层归一化。
(1) Self-attention：self-attention 子层遵循 Transformer 的架构)，并使用 multi-headattention 来捕获长依赖信息。
对于输入标记 n1，n2，···，nL 的序列，我们通过查找表将它们表示为嵌入 n1，n2，···，nL。我们还使用位置嵌入对单词位置的信息进行编码，并计算第 b 个 Transformer 块中第 i 个单词的位置嵌入。其中 pi，b[·]是向量 pi，b 的维度的索引，而 d 是维数数量。
Transformer 块通过 Multi-head 学习非线性特征，从而产生矩阵 Y。Multi-head 层的计算公式如(5)，其中 H 表示头数，Wh 表示权重。注意层应用于每个头部 head_t，通过(6)计算。其中 dk=d/H 表示每个特征向量的长度。Q，K，V 通过(7)计算。其中 WQ，WK，WV 是模型参数。xi 是此 Transformer 模块的输入。对于第一个块，它是查找表嵌入和位置嵌入的向量和，即 ni+p1，i;对于其他块，则是更底层的 Transformer 块的输出和与该块相对应的位置嵌入的矢量和。
(2) Gating 机制：在通过 Self-attention 算出特征之后，我们将字符嵌入的信息进一步合并。这是由基于 softmax 的 Gating 机制给出的。对于第 i 个单词，我们通过线性变换从 y(self)i 计算控制向量 qi。用于字符嵌入的 softmax 权重 k(c)i 由公式 2 中的 n(c)i 进行线性变换给出。用于 Transformer 输出的 softmax 权重 k(y)i 由 y(self)i 进行的另一个线性变换给出。然后，通过(8)计算出 gate。它们用于对 Transformer 层 v(y)i 的特征和字符嵌入 v(c)i 的特征嵌入，分别由 y(self)i 和 n(c)i 线性转换。
与公式 5 相似，我们的机制的输出为 Y(gate)=(hi，t)i，t，其中(·)i，t 表示一个块矩阵，元素为 hi，t。
(3) 单词卷积：最后，将两个卷积层应用于 Gating 机制 y(gate)1，...，y(gate)L，并提取每个标记 y(conv，l)1，...，附近的局部特征。y(conv，l)L，其中 l 表示卷积层。y(conv，l)i 由(10)计算。其中 W(conv，l)是卷积权重，w=(k-1)/2，k 表示窗口大小。特别地，y(conv，0)i 表示 Gating 机制 y(gate)i 的输出。在这些层中，使用了可分离的卷积。原因是可分离的卷积参数较少，易于训练。对于第一个和最后一个词，我们添加零填充。在这些层之间，我们使用了 GELU 激活函数。
总而言之，NL 编码器具有一些 Transformer 的 self-attention，Gating 机制和单词卷积模块。自然语言描述被编码为特征 y(NL)1，y(NL)2，...，y(NL)L。
AST 编码器
我们设计了一个 AST 编码器，以对已生成的部分 AST 的结构进行建模。尽管我们的程序是通过预测语法规则的顺序生成的，但是仅这些规则就缺少程序的具体认识，不足以预测下一个规则。因此，我们的 AST 编码器会考虑异构信息，包括预测规则和树结构。
为了合并此类特定于程序的信息，我们首先将代码表示为规则序列，然后使用注意机制对规则进行编码，最后使用树卷积层将每个节点及其祖先的编码表示形式组合在一起。
AST 表示
(1)规则序列嵌入：为了编码规则信息，我们使用规则的 ID。假设我们有一个规则序列 r1，r2，...，rP，这些规则用于在解码步骤中生成部分 AST，其中 P 表示序列的长度。我们通过查找表嵌入将这些规则表示为数值向量 r1，r2，...，rP。
(2)规则定义编码：上面的表格查找嵌入将语法规则视为原子标记，并且会丢失该规则内容的信息。为了缓解此问题，我们使用规则定义的编码来增强规则的表示形式。对于语法规则 i：α→β1·βK，其中 α 是父节点，β1·βK 是子节点。它们可以是终止符或非终止符。索引 i 是规则的 ID。与等式 2 相似，我们通过全连接层将规则内容编码为向量 r(c)，输入是各个符号的查表嵌入 α，β1，...，βK。注意，该序列也被填充到最大长度。
(3)位置和深度编码：由于我们的 AST 解码器将使用 self-attention 机制，因此我们需要表示使用语法规则的位置。我们首先采用等式 4 中的位置嵌入，表示何时在序列 r1，...，rP 中使用规则。位置嵌入用 p1(r)，...，pP(r)表示。但是，这种位置嵌入不能捕获 AST 中规则的位置。我们通过深度嵌入进一步对此类信息进行编码。如果我们通过规则 r 扩展符号 α：α→β1···βK，我们将通过其父节点即 α 表示规则的深度。通过这种方式，我们将查找表深度嵌入的另一序列 d1，...，dP 与使用的语法规则 r1，...，rP 的序列相关联。
AST 编码器的神经网络结构：
AST 编码器还由一堆块(总共 N1 个块)组成。每个块被分解为四个子层(即，self-attention，Gating 机制，NL-attention 和树卷积)。除了树卷积层之外，我们在每个子层周围都采用了残差连接。在每个子层之后，我们应用层归一化。
(1) Self-attention：为了捕获 AST 的信息，我们构建了一个类似 Transformer 的 self-attention 层，其中输入是规则嵌入，位置嵌入和深度嵌入的总和，即 ri+di+p(r)i。self-attention 子层使用与公式 4、5、6 相同的机制来提取 AST 输入的特征即 y(ast-self)1，y(ast-self)2，...，y(ast-self)P 不同的权重，但在 p(r)i 中增加了嵌入深度。
(2) Gating 机制：我们希望将内容编码规则 y(rule)i 合并到 Transformer 的提取特征的部分中。我们采用方程式 8、9 中的 Gating 机制，在该子层之后，融合特征变为 y(ast-g)1，y(ast-g)2，...，y(ast-g)P。
(3) NL 注意力：在解码步骤中，应将输入的自然语言描述告知我们。这是由 Multi-headNL 给出的。所提取的特征由 y(ast-nl)1，y(ast-nl)2，…，y(ast-nl)P 表示。
(4) 树卷积：如果我们仅考虑上述子层，那么读者将很难将节点的信息与其祖先结合起来。在规则序列中，节点可以远离其祖先，但结构紧密。因此，传统的 Transformer 很难提取这种结构特征。我们将节点的特征与其祖先的特征进行组合。我们将 AST 视为图形，并使用邻接矩阵 M 表示有向图。如果一个节点 αi 是 αj 的父节点，则 Mji=1。假设所有节点都由特征 f1，...，fn 表示，则它们的父节点的特征可以通过与邻接矩阵相乘得出。总之，AST 解码器具有这四个子层的 N1 个块，并产生特征 y(ast)1，y(ast)2，...，y(ast)P。
解码器：
我们的最后一个组件是一个解码器，它将生成的代码信息与自然语言描述集成在一起，并预测下一个语法规则。与 AST 编码器类似，在解码器中使用如下堆栈的块堆栈(总共 N2 个块)，每个块都有几个子层。在每个子层周围还采用残余连接，然后进行层归一化。解码器将要扩展的非终止符作为 query，查询节点表示为从根到要扩展的节点的路径。例如，如果我们要扩展图 1 中的节点“Assign”，则路径应为 root，Module，body，Assign。我们将此路径中的节点表示为数值向量。然后，将等式 2 之类的全连接层应用于这些向量，并且路径的输出为 qi。然后，我们应用两个注意层来集成 AST 编码器和 NL 编码器的输出。最后，应用两个全连接层(其中第一层使用 GELU 激活函数)来提取特征以进行预测。
训练以及推论：
我们根据解码器的最后一层特征，通过 softmax 预测所有可能的候选词中的下一个语法规则。我们还介绍了可以直接从自然语言描述中复制标记 a 的指针网络(本质上是一种注意)。在这种情况下，生成的语法规则为 α→a，其中 α 是要扩展的非终止符，而 a 是终止符。这种指针机制对于用户定义的标识符(例如，变量和函数名称)很有帮助。具体选择 softmax 或是指针网络由另一个 Gating 机制 pg 给出，该值同样由解码器的最后一个特征计算得出。推理从起始规则 start：snode->root 开始，将特殊符号 snode 扩展到根符号。如果预测的 AST 中的每个叶节点都是终止符，则递归预测终止。在预测期间，我们使用大小为 5 的束搜索。在束搜索期间，将排除无效规则。
总结
在这项工作中，我们使用 TreeGen 生成程序。TreeGen 使用 Transformer 的注意力机制来缓解长期依赖问题，并引入 AST 编码器以将语法规则和 AST 结构相结合。评估是在 Python 数据集炉石传说和两个语义解析数据集 ATIS 和 GEO 上进行的。实验结果表明，我们的模型明显优于现有方法。我们还进行了深入的消融测试，表明模型中的每个组件都发挥着重要作用。
致谢
本文由南京大学软件学院 iSE 实验室 2020 级硕士研究生曹振飞翻译转述。
