简介：代码生成是一个重要的AI问题，有可能显着提高程序员的生产力。给定以自然语言编写的规范，代码生成系统将规范转换为可执行程序。例如，如果python程序员给出指令“初始化字典Dict”，代码生成器应该自动生成“Dict={}”。随着深度学习技术的发展，研究人员已经将各种神经架构应用于该问题，例如序列到序列（Seq2Seq）模型或序列到树（Seq2Tree）模型。特别是，最先进的方法通过预测语法规则序列来生成代码。也就是说，系统保留生成代码的部分抽象语法树（AST），并预测将用于扩展特定节点的语法规则。语法规则的分类面临两个主要挑战。第一个挑战是长期依赖问题。一个代码元素可能依赖于另一个遥远的元素。例如，第100行的变量引用语句“iflen(a)”在本文中，我们提出了一种用于代码生成的新型神经架构TreeGen。为了应对第一个挑战，TreeGen采用了最近提出的Transformer架构，该架构能够捕获长期依赖关系。然而，最初的Transformer架构不是为编程而设计的，不能利用树结构，这是上面的第二个挑战。与基于图和树的卷积神经网络一样，利用结构信息的标准方法是将节点及其邻居的向量表示组合为结构化卷积子层的输出。然而，标准的Transformer结构没有这样的结构化卷积子层，并且不清楚在哪里尝试添加结构化卷积所有Transformer块中的子层。我们的核心猜想是，当对节点及其邻居进行卷积时，向量表示on应该主要包含原始节点的信息。随着节点的向量表示在Transformer的解码器中被更多的块处理，它们逐渐混合了更多来自其他节点的信息并丢失了它们的原始信息。因此，我们只在前几个Transformer-decoder块中添加结构卷积子层，而不是全部。一般来说，TreeGen架构由三部分组成：（1）自然语言（NL）编码器：对文本描述进行编码；(2)ASTDecoder（前几个Transformerdecoderblocks）使用结构化卷积子层对之前生成的部分代码进行编码；(3)解码器（Transformer解码器块的其余部分）将查询（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|NLinput,pi)，即给定自然语言描述和当前生成的部分AST，该模型将计算扩展该节点的规则的概率。NLCoder：输入的描述决定了代码的功能。它可以是Hearthstone数据集中的半结构化描述，也可以是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、门机制和词卷积）组成以提取特征，我们将在以下小节中详细描述。在两个子层之间，我们采用残差连接，然后进行层归一化。(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表示head的个数，Wh表示权重。注意层应用于每个头部head_t，由(6)计算。其中dk=d/H表示每个特征向量的长度。Q、K、V由式(7)计算。其中WQ、WK、WV是模型参数。xi是此Transformer块的输入。对于第一个block，它是lookuptableembedding和positionembedding的向量和，即ni+p1,i；对于其他block，就是下层Transformerblock的输出和block对应的positionembedding的向量和。(2)Gatingmechanism：通过Self-attention计算特征后，我们进一步合并字符嵌入信息。这是由基于softmax的门控机制给出的。对于第i个词，我们通过线性变换从y(self)i计算控制向量qi。字符嵌入的softmax权重k(c)i由等式2中n(c)i的线性变换给出。Transformer输出的softmax权重k(y)i由y(self)i的另一个线性变换给出.然后，门由（8）计算。它们用于变换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)Wordconvolution：最后在Gating机制y(gate)1,...,y(gate)L上应用两个卷积层，提取每个tokeny(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表示门控机制y(gate)i的输出。在这些层中，使用了可分离卷积。原因是可分离卷积的参数更少，更容易训练。对于第一个和最后一个单词，我们添加零填充。在这些层之间，我们使用GELU激活函数。总而言之，NLencoder有一些Transformer的self-attention，Gating机制和wordconvolution模块。自然语言描述被编码为特征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解码器将使用自注意力机制，因此我们需要使用语法规则来表示位置。我们首先在等式4中使用位置嵌入，表示何时使用序列r1,...,rP中的规则。位置嵌入由p1(r),...,pP(r)表示。然而，这种位置嵌入并没有捕捉到规则在AST中的位置。我们通过深度嵌入进一步编码这些信息。如果我们通过规则r扩展符号α：α→β1···βK，我们将用其父规则α表示规则的深度。这样，我们将查找表的深度嵌入的另一个序列d1,...,dP与使用的文法规则序列r1,...,rP关联起来。AST编码器的神经网络结构：AST编码器也由一堆块组成（总共N1个块）。每个块被分解为四个子层（即自注意力、门控机制、NL-注意力和树卷积）。除了树卷积层之外，我们在每个子层周围都使用了残差连接。在每个子层之后，我们应用层归一化。(1)Self-attention：为了捕捉AST的信息，我们构建了一个类似Transformer的self-attention层，输入是regularembedding、positionembedding和depthembedding之和，即ri+di+p(r）我。自注意力子层使用与等式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)NLAttention：在解码步骤中，我们应该被告知输入的自然语言描述。这是由Multi-headNL给出的。提取的特征用y(ast-nl)1,y(ast-nl)2,...,y(ast-nl)P表示。(4)Treeconvolution：如果我们只考虑上面的子层，读者很难将一个节点的信息与其祖先结合起来。在一个规则的序列中，一个节点可以远离它的祖先，但结构是紧密的。因此，传统的Transformer很难提取出这样的结构特征。我们将节点的特征与其祖先的特征结合起来。我们将AST视为图，并使用邻接矩阵M来表示有向图。如果节点αi是αj的父节点，则Mji=1。假设所有节点都用特征f1,...,fn表示，则可以通过与邻接矩阵相乘得到其父节点的特征。总之，AST解码器有这四个子层的N1个块，并产生特征y(ast)1,y(ast)2,...,y(ast)P。解码器：我们的最后一个组件是一个解码器，它将生成的代码信息与自然语言描述相结合，并预测下一个语法规则。与AST编码器类似，在解码器中使用如下堆叠的一叠块（总共N2个块），每个块有几个子层。每个子层周围也使用了残差连接，然后进行层归一化。解码器将待扩展的非终结符作为查询，查询节点表示为从根到待扩展节点的路径。例如，如果我们要扩展图1中的节点“Assign”，则路径将为root、Module、body、Assign。我们将此路径中的节点表示为数字向量。然后，将像等式2这样的全连接层应用于这些向量，路径的输出为qi。然后，我们应用两个注意力层来整合AST编码器和NL编码器的输出。最后，应用两个完全连接的层（其中第一层使用GELU激活函数）来提取预测特征。训练和推理：我们使用softmax根据解码器最后一层的特征在所有可能的候选词中预测下一个语法规则。我们还介绍了可以直接从自然语言描述中复制标记的指针网络（本质上是一种注意力）。在这种情况下，生成的文法规则是α→a，其中α是要扩展的非终结符，a是终止符。这种指针机制有助于用户定义的标识符，例如变量和函数名称。具体选择softmax还是pointernetwork是由另外一个Gating机制pg给出的，也是由decoder的最后一个feature计算出来的。推理从开始规则start:snode->root开始，将特殊符号snode展开为根符号。如果预测的AST中的每个叶节点都是终止符，则递归预测终止。在预测期间，我们使用大小为5的波束搜索。在波束搜索期间，排除了无效规则。总结在这项工作中，我们使用TreeGen来生成程序。TreeGen利用Transformer的attention机制缓解长期依赖问题，引入AST编码器将文法规则和AST结构结合起来。评估是在Python数据集Hearthstone和两个语义解析数据集ATIS和GEO上进行的。实验结果表明，我们的模型明显优于现有方法。我们还进行了深入的消融测试，表明模型中的每个组件都发挥着重要作用。致谢本文由南京大学软件学院iSE实验室2020级研究生曹振飞翻译转载。
