介紹：

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

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

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

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

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

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

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

我們的模型：

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

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

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

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

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

NL 編碼器：

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

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

輸入文字表示：

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

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

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

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

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

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

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

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

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

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

AST 編碼器

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

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

AST 表示

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

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

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

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

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

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

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

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

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

解碼器：

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

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

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

總結(jié)

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

致謝

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