介紹：

代碼生成是一個(gè)重要的人工智能問(wèn)題，有可能顯著提高程序員的生產(chǎn)力。給定以自然語(yǔ)言編寫(xiě)的規(guī)范，代碼生成系統(tǒng)會(huì)將規(guī)范轉(zhuǎn)換為可執(zhí)行程序。例如，如果 python 程序員給出指令“初始化字典 Dict”，則代碼生成器應(yīng)自動(dòng)生成“Dict={}”。

隨著深度學(xué)習(xí)技術(shù)的發(fā)展，研究人員已針對(duì)此問(wèn)題應(yīng)用了各種神經(jīng)體系結(jié)構(gòu)，例如序列到序列(Seq2Seq)模型或序列到樹(shù)(Seq2Tree)模型。尤其是，最先進(jìn)的方法通過(guò)預(yù)測(cè)語(yǔ)法規(guī)則序列來(lái)生成代碼。也就是說(shuō)，系統(tǒng)保留已生成代碼的部分抽象語(yǔ)法樹(shù)(AST)，并預(yù)測(cè)將用于擴(kuò)展特定節(jié)點(diǎn)的語(yǔ)法規(guī)則。

語(yǔ)法規(guī)則的分類面臨兩個(gè)主要挑戰(zhàn)。第一個(gè)挑戰(zhàn)是長(zhǎng)時(shí)依賴問(wèn)題。代碼元素可能取決于另一個(gè)遙遠(yuǎn)的元素。例如，第 100 行的變量引用語(yǔ)句“if len(a)

在本文中，我們提出了一種新穎的神經(jīng)體系結(jié)構(gòu) TreeGen，用于代碼生成。為了解決第一個(gè)挑戰(zhàn)，TreeGen 采用了最近提出的 Transformer 架構(gòu)，該架構(gòu)能夠捕獲長(zhǎng)時(shí)依賴關(guān)系。但是，原始的 Transformer 體系結(jié)構(gòu)不是為程序設(shè)計(jì)的，并且不能利用樹(shù)結(jié)構(gòu)，即上述第二個(gè)挑戰(zhàn)。如在基于圖和樹(shù)的卷積神經(jīng)網(wǎng)絡(luò)中一樣，利用結(jié)構(gòu)信息的標(biāo)準(zhǔn)方法是將節(jié)點(diǎn)及其鄰接節(jié)點(diǎn)的向量表示形式組合為結(jié)構(gòu)化卷積子層的輸出。但是，標(biāo)準(zhǔn)的 Transformer 結(jié)構(gòu)沒(méi)有這樣的結(jié)構(gòu)化卷積子層，并且不清楚在何處添加它們。

試圖在所有 Transformer 塊中添加結(jié)構(gòu)化卷積子層是很誘人的。我們的核心推測(cè)是，在對(duì)一個(gè)節(jié)點(diǎn)及其鄰接點(diǎn)進(jìn)行卷積時(shí)，向量表示應(yīng)主要包含原始節(jié)點(diǎn)的信息。隨著節(jié)點(diǎn)的向量表示在 Transformer 的解碼器中由更多的塊進(jìn)行處理，它們逐漸混入來(lái)自其他節(jié)點(diǎn)的更多信息并丟失其原始信息。因此，我們僅將結(jié)構(gòu)卷積子層添加到前幾個(gè) Transformer 解碼器塊中，而不是全部添加。

一般而言，TreeGen 體系結(jié)構(gòu)包括三個(gè)部分：(1)自然語(yǔ)言(NL)編碼器：對(duì)文本描述進(jìn)行編碼;(2)AST 解碼器(前幾個(gè) Transformer 解碼器塊)使用結(jié)構(gòu)化卷積子層對(duì)先前生成的部分代碼進(jìn)行編碼;(3)解碼器(其余的 Transformer 解碼器塊)將 query(要在 AST 中擴(kuò)展的節(jié)點(diǎn))與前兩個(gè)編碼器組合在一起，以預(yù)測(cè)下一個(gè)語(yǔ)法規(guī)則。

我們?cè)诮⒌幕鶞?zhǔn)數(shù)據(jù)集上評(píng)估了我們的模型，這是紙牌游戲爐石傳說(shuō)的 Python 實(shí)現(xiàn)。結(jié)果表明，我們的模型明顯優(yōu)于以前的模型 4.5 個(gè)百分點(diǎn)。我們進(jìn)一步在兩個(gè)語(yǔ)義分析數(shù)據(jù)集(ATIS 和 GEO)上評(píng)估了我們的模型，這兩個(gè)數(shù)據(jù)集將自然語(yǔ)言句子轉(zhuǎn)換為 lambda 微積分邏輯形式。結(jié)果表明，我們的模型在以前的神經(jīng)模型中具有最高的準(zhǔn)確性，分別為 89.1%和 89.6%。我們的評(píng)估還表明，將結(jié)構(gòu)化卷積子層添加到前幾個(gè) Transformer 塊中，其性能明顯優(yōu)于所有塊中具有結(jié)構(gòu)化卷積的 Transformer。

我們的模型：

我們通過(guò)預(yù)測(cè)編程語(yǔ)言的語(yǔ)法規(guī)則來(lái)生成代碼。圖 2 顯示了我們模型的整體圖，它包括三個(gè)部分：NL 編碼器，AST 編碼器和解碼器。我們將在以下小節(jié)中詳細(xì)介紹它們。

語(yǔ)法規(guī)則預(yù)測(cè)：

在本節(jié)中，我們介紹如何將代碼生成建模為一系列語(yǔ)法規(guī)則的分類問(wèn)題。程序可以被分解為幾個(gè)與上下文無(wú)關(guān)的語(yǔ)法規(guī)則，并解析為 AST。例如，圖 1 顯示了代碼“length=10”的 PythonAST，其中虛線框是終止符，而實(shí)心框是非終止符。

可以將基于 AST 的代碼生成視為通過(guò)語(yǔ)法規(guī)則擴(kuò)展非終止符。重復(fù)此過(guò)程，直到所有葉節(jié)點(diǎn)都處于末尾。在圖 1 中，“1:root->Module”是語(yǔ)法規(guī)則的示例，其中前面的數(shù)字是規(guī)則的 ID。遵循預(yù)定遍歷，我們可以獲得在右上角顯示的生成 AST 的規(guī)則序列。

形式上，概率可以分解為遵循以下順序生成代碼的規(guī)則的概率。其中 ri 是規(guī)則序列中的第 i 條規(guī)則。通過(guò)這種方式，我們的任務(wù)是訓(xùn)練一個(gè)模型以計(jì)算 p(ri|NL 輸入，pi)，即給定自然語(yǔ)言描述和當(dāng)前生成的部分 AST，該模型將計(jì)算擴(kuò)展該節(jié)點(diǎn)的規(guī)則的概率。

NL 編碼器：

輸入的描述決定了代碼的功能。它可以是爐石傳說(shuō)數(shù)據(jù)集中的半結(jié)構(gòu)化描述，也可以是 ATIS 和 GEO 語(yǔ)義解析數(shù)據(jù)集中的自然語(yǔ)言。

對(duì)于輸入的描述，我們首先將其標(biāo)記為 n1，n2，...，nL，其中 L 表示輸入的長(zhǎng)度。然后將每個(gè) ni 拆分為字符 c1(ni)，c2(ni)，...，cS(ni)，其中 S 是 ni 中的字符數(shù)。通過(guò)嵌入，將所有標(biāo)記和字符表示為數(shù)值向量 n1，n2，...，nL 和 c1(ni)，c2(ni)，...，cS(ni)。

輸入文字表示：

字符嵌入。相似詞經(jīng)常具有相似的字符(例如“program”和“programs”)。為了利用此屬性，我們通過(guò)具有完全連接層的字符嵌入來(lái)表示標(biāo)記。其中 W(c)是權(quán)重，字符序列被填充為預(yù)定義的最大長(zhǎng)度 M。在全連接層之后，我們還應(yīng)用層歸一化。然后將這些向量反饋到 NL 編碼器，并通過(guò)子層將其與詞嵌入集成在一起。

NL 編碼器的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)：

NL 編碼器由一堆塊(總共 Nd 個(gè)塊)組成。每個(gè)塊包含三個(gè)不同的子層(即，self_attention，gating 機(jī)制和單詞卷積)以提取特征，我們將在以下小節(jié)中詳細(xì)介紹。在兩個(gè)子層之間，我們采用殘差連接，然后進(jìn)行層歸一化。

(1) Self-attention：self-attention 子層遵循 Transformer 的架構(gòu))，并使用 multi-headattention 來(lái)捕獲長(zhǎng)依賴信息。

對(duì)于輸入標(biāo)記 n1，n2，···，nL 的序列，我們通過(guò)查找表將它們表示為嵌入 n1，n2，···，nL。我們還使用位置嵌入對(duì)單詞位置的信息進(jìn)行編碼，并計(jì)算第 b 個(gè) Transformer 塊中第 i 個(gè)單詞的位置嵌入。其中 pi，b[·]是向量 pi，b 的維度的索引，而 d 是維數(shù)數(shù)量。

Transformer 塊通過(guò) Multi-head 學(xué)習(xí)非線性特征，從而產(chǎn)生矩陣 Y。Multi-head 層的計(jì)算公式如(5)，其中 H 表示頭數(shù)，Wh 表示權(quán)重。注意層應(yīng)用于每個(gè)頭部 head_t，通過(guò)(6)計(jì)算。其中 dk=d/H 表示每個(gè)特征向量的長(zhǎng)度。Q，K，V 通過(guò)(7)計(jì)算。其中 WQ，WK，WV 是模型參數(shù)。xi 是此 Transformer 模塊的輸入。對(duì)于第一個(gè)塊，它是查找表嵌入和位置嵌入的向量和，即 ni+p1，i;對(duì)于其他塊，則是更底層的 Transformer 塊的輸出和與該塊相對(duì)應(yīng)的位置嵌入的矢量和。

(2) Gating 機(jī)制：在通過(guò) Self-attention 算出特征之后，我們將字符嵌入的信息進(jìn)一步合并。這是由基于 softmax 的 Gating 機(jī)制給出的。對(duì)于第 i 個(gè)單詞，我們通過(guò)線性變換從 y(self)i 計(jì)算控制向量 qi。用于字符嵌入的 softmax 權(quán)重 k(c)i 由公式 2 中的 n(c)i 進(jìn)行線性變換給出。用于 Transformer 輸出的 softmax 權(quán)重 k(y)i 由 y(self)i 進(jìn)行的另一個(gè)線性變換給出。然后，通過(guò)(8)計(jì)算出 gate。它們用于對(duì) Transformer 層 v(y)i 的特征和字符嵌入 v(c)i 的特征嵌入，分別由 y(self)i 和 n(c)i 線性轉(zhuǎn)換。

與公式 5 相似，我們的機(jī)制的輸出為 Y(gate)=(hi，t)i，t，其中(·)i，t 表示一個(gè)塊矩陣，元素為 hi，t。

(3) 單詞卷積：最后，將兩個(gè)卷積層應(yīng)用于 Gating 機(jī)制 y(gate)1，...，y(gate)L，并提取每個(gè)標(biāo)記 y(conv，l)1，...，附近的局部特征。y(conv，l)L，其中 l 表示卷積層。y(conv，l)i 由(10)計(jì)算。其中 W(conv，l)是卷積權(quán)重，w=(k-1)/2，k 表示窗口大小。特別地，y(conv，0)i 表示 Gating 機(jī)制 y(gate)i 的輸出。在這些層中，使用了可分離的卷積。原因是可分離的卷積參數(shù)較少，易于訓(xùn)練。對(duì)于第一個(gè)和最后一個(gè)詞，我們添加零填充。在這些層之間，我們使用了 GELU 激活函數(shù)。

總而言之，NL 編碼器具有一些 Transformer 的 self-attention，Gating 機(jī)制和單詞卷積模塊。自然語(yǔ)言描述被編碼為特征 y(NL)1，y(NL)2，...，y(NL)L。

AST 編碼器

我們?cè)O(shè)計(jì)了一個(gè) AST 編碼器，以對(duì)已生成的部分 AST 的結(jié)構(gòu)進(jìn)行建模。盡管我們的程序是通過(guò)預(yù)測(cè)語(yǔ)法規(guī)則的順序生成的，但是僅這些規(guī)則就缺少程序的具體認(rèn)識(shí)，不足以預(yù)測(cè)下一個(gè)規(guī)則。因此，我們的 AST 編碼器會(huì)考慮異構(gòu)信息，包括預(yù)測(cè)規(guī)則和樹(shù)結(jié)構(gòu)。

為了合并此類特定于程序的信息，我們首先將代碼表示為規(guī)則序列，然后使用注意機(jī)制對(duì)規(guī)則進(jìn)行編碼，最后使用樹(shù)卷積層將每個(gè)節(jié)點(diǎn)及其祖先的編碼表示形式組合在一起。

AST 表示

(1)規(guī)則序列嵌入：為了編碼規(guī)則信息，我們使用規(guī)則的 ID。假設(shè)我們有一個(gè)規(guī)則序列 r1，r2，...，rP，這些規(guī)則用于在解碼步驟中生成部分 AST，其中 P 表示序列的長(zhǎng)度。我們通過(guò)查找表嵌入將這些規(guī)則表示為數(shù)值向量 r1，r2，...，rP。

(2)規(guī)則定義編碼：上面的表格查找嵌入將語(yǔ)法規(guī)則視為原子標(biāo)記，并且會(huì)丟失該規(guī)則內(nèi)容的信息。為了緩解此問(wèn)題，我們使用規(guī)則定義的編碼來(lái)增強(qiáng)規(guī)則的表示形式。對(duì)于語(yǔ)法規(guī)則 i：α→β1·βK，其中 α 是父節(jié)點(diǎn)，β1·βK 是子節(jié)點(diǎn)。它們可以是終止符或非終止符。索引 i 是規(guī)則的 ID。與等式 2 相似，我們通過(guò)全連接層將規(guī)則內(nèi)容編碼為向量 r(c)，輸入是各個(gè)符號(hào)的查表嵌入 α，β1，...，βK。注意，該序列也被填充到最大長(zhǎng)度。

(3)位置和深度編碼：由于我們的 AST 解碼器將使用 self-attention 機(jī)制，因此我們需要表示使用語(yǔ)法規(guī)則的位置。我們首先采用等式 4 中的位置嵌入，表示何時(shí)在序列 r1，...，rP 中使用規(guī)則。位置嵌入用 p1(r)，...，pP(r)表示。但是，這種位置嵌入不能捕獲 AST 中規(guī)則的位置。我們通過(guò)深度嵌入進(jìn)一步對(duì)此類信息進(jìn)行編碼。如果我們通過(guò)規(guī)則 r 擴(kuò)展符號(hào) α：α→β1···βK，我們將通過(guò)其父節(jié)點(diǎn)即 α 表示規(guī)則的深度。通過(guò)這種方式，我們將查找表深度嵌入的另一序列 d1，...，dP 與使用的語(yǔ)法規(guī)則 r1，...，rP 的序列相關(guān)聯(lián)。

AST 編碼器的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)：

AST 編碼器還由一堆塊(總共 N1 個(gè)塊)組成。每個(gè)塊被分解為四個(gè)子層(即，self-attention，Gating 機(jī)制，NL-attention 和樹(shù)卷積)。除了樹(shù)卷積層之外，我們?cè)诿總€(gè)子層周圍都采用了殘差連接。在每個(gè)子層之后，我們應(yīng)用層歸一化。

(1) Self-attention：為了捕獲 AST 的信息，我們構(gòu)建了一個(gè)類似 Transformer 的 self-attention 層，其中輸入是規(guī)則嵌入，位置嵌入和深度嵌入的總和，即 ri+di+p(r)i。self-attention 子層使用與公式 4、5、6 相同的機(jī)制來(lái)提取 AST 輸入的特征即 y(ast-self)1，y(ast-self)2，...，y(ast-self)P 不同的權(quán)重，但在 p(r)i 中增加了嵌入深度。

(2) Gating 機(jī)制：我們希望將內(nèi)容編碼規(guī)則 y(rule)i 合并到 Transformer 的提取特征的部分中。我們采用方程式 8、9 中的 Gating 機(jī)制，在該子層之后，融合特征變?yōu)?y(ast-g)1，y(ast-g)2，...，y(ast-g)P。

(3) NL 注意力：在解碼步驟中，應(yīng)將輸入的自然語(yǔ)言描述告知我們。這是由 Multi-headNL 給出的。所提取的特征由 y(ast-nl)1，y(ast-nl)2，…，y(ast-nl)P 表示。

(4) 樹(shù)卷積：如果我們僅考慮上述子層，那么讀者將很難將節(jié)點(diǎn)的信息與其祖先結(jié)合起來(lái)。在規(guī)則序列中，節(jié)點(diǎn)可以遠(yuǎn)離其祖先，但結(jié)構(gòu)緊密。因此，傳統(tǒng)的 Transformer 很難提取這種結(jié)構(gòu)特征。我們將節(jié)點(diǎn)的特征與其祖先的特征進(jìn)行組合。我們將 AST 視為圖形，并使用鄰接矩陣 M 表示有向圖。如果一個(gè)節(jié)點(diǎn) αi 是 αj 的父節(jié)點(diǎn)，則 Mji=1。假設(shè)所有節(jié)點(diǎn)都由特征 f1，...，fn 表示，則它們的父節(jié)點(diǎn)的特征可以通過(guò)與鄰接矩陣相乘得出。總之，AST 解碼器具有這四個(gè)子層的 N1 個(gè)塊，并產(chǎn)生特征 y(ast)1，y(ast)2，...，y(ast)P。

解碼器：

我們的最后一個(gè)組件是一個(gè)解碼器，它將生成的代碼信息與自然語(yǔ)言描述集成在一起，并預(yù)測(cè)下一個(gè)語(yǔ)法規(guī)則。與 AST 編碼器類似，在解碼器中使用如下堆棧的塊堆棧(總共 N2 個(gè)塊)，每個(gè)塊都有幾個(gè)子層。在每個(gè)子層周圍還采用殘余連接，然后進(jìn)行層歸一化。解碼器將要擴(kuò)展的非終止符作為 query，查詢節(jié)點(diǎn)表示為從根到要擴(kuò)展的節(jié)點(diǎn)的路徑。例如，如果我們要擴(kuò)展圖 1 中的節(jié)點(diǎn)“Assign”，則路徑應(yīng)為 root，Module，body，Assign。我們將此路徑中的節(jié)點(diǎn)表示為數(shù)值向量。然后，將等式 2 之類的全連接層應(yīng)用于這些向量，并且路徑的輸出為 qi。然后，我們應(yīng)用兩個(gè)注意層來(lái)集成 AST 編碼器和 NL 編碼器的輸出。最后，應(yīng)用兩個(gè)全連接層(其中第一層使用 GELU 激活函數(shù))來(lái)提取特征以進(jìn)行預(yù)測(cè)。

訓(xùn)練以及推論：

我們根據(jù)解碼器的最后一層特征，通過(guò) softmax 預(yù)測(cè)所有可能的候選詞中的下一個(gè)語(yǔ)法規(guī)則。我們還介紹了可以直接從自然語(yǔ)言描述中復(fù)制標(biāo)記 a 的指針網(wǎng)絡(luò)(本質(zhì)上是一種注意)。在這種情況下，生成的語(yǔ)法規(guī)則為 α→a，其中 α 是要擴(kuò)展的非終止符，而 a 是終止符。這種指針機(jī)制對(duì)于用戶定義的標(biāo)識(shí)符(例如，變量和函數(shù)名稱)很有幫助。具體選擇 softmax 或是指針網(wǎng)絡(luò)由另一個(gè) Gating 機(jī)制 pg 給出，該值同樣由解碼器的最后一個(gè)特征計(jì)算得出。推理從起始規(guī)則 start：snode->root 開(kāi)始，將特殊符號(hào) snode 擴(kuò)展到根符號(hào)。如果預(yù)測(cè)的 AST 中的每個(gè)葉節(jié)點(diǎn)都是終止符，則遞歸預(yù)測(cè)終止。在預(yù)測(cè)期間，我們使用大小為 5 的束搜索。在束搜索期間，將排除無(wú)效規(guī)則。

總結(jié)

在這項(xiàng)工作中，我們使用 TreeGen 生成程序。TreeGen 使用 Transformer 的注意力機(jī)制來(lái)緩解長(zhǎng)期依賴問(wèn)題，并引入 AST 編碼器以將語(yǔ)法規(guī)則和 AST 結(jié)構(gòu)相結(jié)合。評(píng)估是在 Python 數(shù)據(jù)集爐石傳說(shuō)和兩個(gè)語(yǔ)義解析數(shù)據(jù)集 ATIS 和 GEO 上進(jìn)行的。實(shí)驗(yàn)結(jié)果表明，我們的模型明顯優(yōu)于現(xiàn)有方法。我們還進(jìn)行了深入的消融測(cè)試，表明模型中的每個(gè)組件都發(fā)揮著重要作用。

致謝

本文由南京大學(xué)軟件學(xué)院 iSE 實(shí)驗(yàn)室 2020 級(jí)碩士研究生曹振飛翻譯轉(zhuǎn)述。