一種融合程序員和神經(jīng)網(wǎng)絡(luò)的自動化程序生成方法

周 鵬 武延軍 趙 琛

1(中國科學(xué)院軟件研究所 北京 100190) 2(中國科學(xué)院大學(xué) 北京 100049) 3(計算機(jī)科學(xué)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院軟件研究所) 北京 100190)

(zhoupengwork01@163.com)

教會機(jī)器理解代碼、編寫程序或構(gòu)造可自學(xué)習(xí)的智能軟件一直是人工智能的重要挑戰(zhàn)問題之一[1].當(dāng)前基于神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)在圖像處理、語音識別、自然語言處理等領(lǐng)域從研究到應(yīng)用取得了很大的成功，但是在程序生成上距離研究到實(shí)用仍有明顯差距.許多學(xué)者在程序處理領(lǐng)域也使用神經(jīng)網(wǎng)絡(luò)深度學(xué)習(xí)方法進(jìn)行了積極探索，提出了不少研究方法，取得了很好的效果，但是仍然未能有效解決泛化能力差、程序正確性、難以處理復(fù)雜程序結(jié)構(gòu)的問題.當(dāng)前基于神經(jīng)網(wǎng)絡(luò)的程序生成研究主要包括基于程序輸入-輸出數(shù)據(jù)樣例的方法[2-6]、基于標(biāo)注程序執(zhí)行軌跡樣例的方法[7-8]和基于標(biāo)注源碼的方法[9-13].

1) 基于程序輸入-輸出樣例的方法.該方法以神經(jīng)網(wǎng)絡(luò)為待學(xué)習(xí)控制器，從輸入-輸出樣例訓(xùn)練控制器學(xué)習(xí)預(yù)測對神經(jīng)網(wǎng)絡(luò)擴(kuò)展外部存儲的操作序列.該方法完全依賴輸入輸出數(shù)據(jù)對，存在從數(shù)據(jù)倒推操作序列的歧義性、泛化能力差、限定一個小的DSL(domain specific language)語言[14]空間、只能處理非常簡單的程序結(jié)構(gòu)等問題.比如著名的微軟DeepCoder[2]只能處理自定義的一個小型DSL語言，主要預(yù)測5行以內(nèi)、每行只有一個主標(biāo)識符、順序結(jié)構(gòu)的平鋪程序，不能處理分支、遞歸、跳轉(zhuǎn)等復(fù)雜控制結(jié)構(gòu)，因此習(xí)得的程序非常簡單.

2) 基于標(biāo)注程序執(zhí)行軌跡樣例的方法.該方法收集覆蓋算法所有執(zhí)行路徑的逐步執(zhí)行軌跡作為有監(jiān)督訓(xùn)練數(shù)據(jù)，其標(biāo)注方法是以下一步作為上一步的標(biāo)注.DeepMind NPI[7]是最有代表性的相關(guān)研究之一，其優(yōu)點(diǎn)是明顯提高了泛化能力.缺點(diǎn)是數(shù)據(jù)標(biāo)注成本高，同時考慮到每個執(zhí)行軌跡是算法的特定路徑，因此需要預(yù)先已知算法邏輯，所以本質(zhì)上未能從輸入-輸出樣例對中倒推學(xué)習(xí)到新代碼邏輯，而是從標(biāo)注執(zhí)行路徑中學(xué)習(xí)算法的神經(jīng)網(wǎng)絡(luò)表示；另外NPI是對標(biāo)測試的主要模型之一，其泛化能力雖然有很大提升但仍然是有限的，對此實(shí)驗(yàn)分析部分有具體對比.

3) 基于標(biāo)注源碼的方法.對源代碼做有監(jiān)督標(biāo)注.學(xué)習(xí)源碼跟標(biāo)注間的統(tǒng)計映射關(guān)系，然后通過輸入標(biāo)簽反過來推薦源程序.該方法會面臨由編程語言過多的規(guī)則、實(shí)現(xiàn)細(xì)節(jié)、源碼本身丟失語義信息所帶來的學(xué)習(xí)復(fù)雜度；同時未能輸入源程序的背景知識，比如程序員預(yù)先學(xué)習(xí)的編程語言規(guī)范、計算機(jī)原理教程等,導(dǎo)致模型處理信息不完備.額外的復(fù)雜度加上不完備的信息給模型訓(xùn)練學(xué)習(xí)帶來了巨大挑戰(zhàn).BAYOU[12]是最具代表性的相關(guān)研究之一，其優(yōu)點(diǎn)是可以從注釋標(biāo)簽生成大體正確的Java源代碼推薦，不足是不能保證和自我檢驗(yàn)生成的代碼語法是否正確，因此生成的程序代碼具有參考價值而不能直接解釋執(zhí)行.

因此，完全依賴神經(jīng)網(wǎng)絡(luò)，單一地以源代碼標(biāo)注、輸入-輸出對、程序執(zhí)行軌跡做為訓(xùn)練數(shù)據(jù)輸入構(gòu)建程序生成模型存在局限性.比如程序生成模型在實(shí)際應(yīng)用中一般需要關(guān)心模型的泛化能力、生成程序正確性、處理復(fù)雜程序結(jié)構(gòu)3個指標(biāo)，可以分別定性地解釋為模型生成的程序表示需要具備一定程度的變通能力(舉一反三是理想情況)、執(zhí)行的準(zhǔn)確率、可以處理有一定結(jié)構(gòu)的程序從而能描述更大范圍或有一定復(fù)雜度的任務(wù)，但是這些模型在應(yīng)對3個指標(biāo)時面臨挑戰(zhàn).我們分析認(rèn)為這主要是因?yàn)榫幊倘蝿?wù)往往非常復(fù)雜、程序相對于自然語言有其特殊性，完全依靠神經(jīng)網(wǎng)絡(luò)構(gòu)建的程序生成模型未能結(jié)合程序員的價值、未能獲得豐富的輸入信息(如背景知識).有意思的是觀察人類學(xué)習(xí)編程的過程，程序員會預(yù)先學(xué)習(xí)編程語言的語法規(guī)則、計算機(jī)原理等背景知識；對比神經(jīng)網(wǎng)絡(luò)和人類，神經(jīng)網(wǎng)絡(luò)善于從大量數(shù)據(jù)進(jìn)行自動化統(tǒng)計學(xué)習(xí)，人類善于問題分解、直覺感知、經(jīng)驗(yàn)復(fù)用.受此啟發(fā)，應(yīng)對程序生成的復(fù)雜性和挑戰(zhàn)性,我們探討如何發(fā)揮神經(jīng)網(wǎng)絡(luò)和人類程序員的整合優(yōu)勢，實(shí)現(xiàn)優(yōu)勢互補(bǔ).

因此本文提出一種融合程序員和神經(jīng)網(wǎng)絡(luò)各自優(yōu)勢的協(xié)作式編程范式HNCP.HNCP是一種高級可微分(“可微分”是使用反向傳播算法求解神經(jīng)網(wǎng)絡(luò)權(quán)重參數(shù)的基礎(chǔ))編程語言，執(zhí)行在一種提供端到端可微分運(yùn)行環(huán)境的編程語言級抽象虛擬機(jī)(diff-erentiable virtual machine, dVM)上.在HNCP編程范式下，程序員用類C高級編程語言提供程序框架，由神經(jīng)網(wǎng)絡(luò)組件根據(jù)訓(xùn)練數(shù)據(jù)學(xué)習(xí)(可微分優(yōu)化)生成程序的局部細(xì)節(jié)，因此最終完整確定的程序是由人類程序員和神經(jīng)網(wǎng)絡(luò)共同創(chuàng)作完成.如圖1所示，圖1(a)是一個程序框架，其功能是不完整的，其中空缺部分如圖1(b)所示，無縫嵌入一個神經(jīng)網(wǎng)絡(luò)組件，程序的完整行為將由程序員提供的程序框架和通過訓(xùn)練數(shù)據(jù)(輸入-輸出對)參數(shù)化的神經(jīng)網(wǎng)絡(luò)組件共同確定.

Fig. 1 Illustration of HNCP for automatic program generation圖1 HNCP程序自動生成示例

本文主要貢獻(xiàn)有3個方面：

1) 提出了神經(jīng)網(wǎng)絡(luò)與人工程序員協(xié)作的高級編程范式HNCP，它可以結(jié)合神經(jīng)網(wǎng)絡(luò)和程序員各自的優(yōu)點(diǎn)，使程序生成適用于復(fù)雜的程序結(jié)構(gòu)(如循環(huán)、遞歸、分支、函數(shù)調(diào)用等)；

2) 給出了一種高級過程化編程語言可微分運(yùn)行環(huán)境(dVM)的實(shí)現(xiàn)方法.dVM是實(shí)現(xiàn)傳統(tǒng)過程化程序結(jié)構(gòu)跟神經(jīng)網(wǎng)絡(luò)組件無縫融合的基礎(chǔ)，也是將離散的程序處理問題轉(zhuǎn)換為能用可微分優(yōu)化直接處理的問題的關(guān)鍵；

3) 實(shí)驗(yàn)表明，跟代表性同類程序生成模型相比，HNCP在程序生成任務(wù)上表現(xiàn)出更好的學(xué)習(xí)性能(泛化能力、樣本復(fù)雜度、準(zhǔn)確率、復(fù)雜程序結(jié)構(gòu)).這表明整合人工程序員和神經(jīng)網(wǎng)絡(luò)的協(xié)作式編程是一種有潛力的研究方法，可以促進(jìn)程序自動生成的實(shí)際應(yīng)用能力.

1 相關(guān)工作

文獻(xiàn)[12]提出了一種基于Java源程序語法相似性的組合搜索生成源代碼示例的方法.我們都用高級編程語言處理復(fù)雜的程序，但是文獻(xiàn)[15]中的方法是以語法而不是語義為條件的，既不考慮生成程序的準(zhǔn)確性，也不考慮生成程序的完整性，生成的代碼示例具有參考價值而不能直接解釋執(zhí)行.因此，我們在研究目標(biāo)和方法上都與之不同.文獻(xiàn)[16]提出了基于C語言的程序骨架編程，它是基于SAT(Boolean satisfiability problem)的歸納綜合過程，即使用搜索和符號推理來尋找滿足人工定義規(guī)則的程序.但在本文中，我們采用的是神經(jīng)網(wǎng)絡(luò)可微分優(yōu)化法，也不需要額外的人工定義規(guī)則，因此是明顯不同的；文獻(xiàn)[15-18]擴(kuò)展了神經(jīng)網(wǎng)絡(luò)使之具有較大外部記憶存儲，這為可微分存儲器緩存的設(shè)計提供了有益的啟發(fā).但它們都缺乏高級編程接口，而在本文中，我們提供了一個具有外部存儲器和高級C語言接口的可微分編程系統(tǒng)，這對于整合程序員的編程框架或者經(jīng)驗(yàn)、無縫融合神經(jīng)網(wǎng)絡(luò)組件到過程化程序結(jié)構(gòu)中是非常重要的.

2 方法設(shè)計與實(shí)現(xiàn)

HNCP是基于類C語法的擴(kuò)展，增加了神經(jīng)網(wǎng)絡(luò)組件嵌入的語言構(gòu)造.HNCP源程序首先需要編譯成中間代碼表示(intermediate representation, IR)，從而便于以可微分的矩陣計算方式進(jìn)行程序解釋執(zhí)行和求解.IR的指令集設(shè)計參考了Forth[19]和SECD[20].表1對IR指令集的主要指令進(jìn)行了說明.該指令集是一個棧式求值語言，我們基于該棧式求值模式構(gòu)造了一個可微分的運(yùn)行時環(huán)境，命名為dVM，它是一個語言級虛擬機(jī)，滿足直接對IR程序的可微分解釋執(zhí)行，從而滿足對HNCP的類C源程序的解釋執(zhí)行.程序在dVM上以端到端可微分的方式執(zhí)行生成程序的計算圖表示，包括神經(jīng)網(wǎng)絡(luò)組件構(gòu)成計算圖的組成部分.進(jìn)一步，通過輸入-輸出樣例訓(xùn)練計算圖來確定嵌入的神經(jīng)網(wǎng)絡(luò)組件參數(shù)，從而學(xué)習(xí)生成一個完整、確定的程序表示.

Table 1 Instruction Set表1 指令集

Fig. 2 Overall processing flow of HNCP program圖2 HNCP程序處理的整體流程

2.1 HNCP方法概述

圖2所示是用HNCP協(xié)作式編程創(chuàng)作的源程序框架自動生成完整、確定的程序的整體處理流程.

首先通過編譯技術(shù)將C語法的HNCP源程序翻譯為更底層的(直接面向dVM)指令集表示的中間語言表示；然后根據(jù)分支、控制結(jié)構(gòu)對程序進(jìn)行分塊，包括普通的中間語言代碼塊和神經(jīng)網(wǎng)絡(luò)塊(統(tǒng)稱代碼塊).

每個神經(jīng)網(wǎng)絡(luò)塊都攜帶著可以通過訓(xùn)練數(shù)據(jù)來確定其行為的可學(xué)習(xí)參數(shù)(所以完整的程序行為是由程序框架和數(shù)據(jù)訓(xùn)練學(xué)習(xí)共同確定).每個代碼塊是用代碼片段構(gòu)成的函數(shù)來實(shí)現(xiàn)，而代碼片段描述為矩陣代數(shù)運(yùn)算(即指令集的可微分實(shí)現(xiàn))，dVM的狀態(tài)緩存部件以及對狀態(tài)的訪問、處理也用矩陣和矩陣代數(shù)表示，因此程序執(zhí)行的每個基礎(chǔ)步驟是尋址下一個代碼塊，在dVM的狀態(tài)部件上做矩陣代數(shù)計算，程序的整體執(zhí)行是由這些基礎(chǔ)步驟一步一步推進(jìn)構(gòu)成的遞歸過程.dVM的狀態(tài)由R(返回棧)、S(求值數(shù)據(jù)棧)、H(隨機(jī)變量堆)這些狀態(tài)緩存和PR(返回棧棧頂指針)、PS(數(shù)據(jù)棧棧頂指針)、PC(程序計數(shù)器指針)組成.

2.2 dVM可微分虛擬機(jī)

從公理語義[21]的角度將指令的執(zhí)行和求值表示為虛擬機(jī)的狀態(tài)轉(zhuǎn)換.我們給出了一個全可微分計算系統(tǒng)(dVM)的實(shí)現(xiàn)方法，dVM支持高級類C編程語言，具有IR指令集和擴(kuò)展內(nèi)存.

2.2.1 可微分虛擬機(jī)整體結(jié)構(gòu)

圖3所示，可微分虛擬機(jī)dVM包括3個狀態(tài)區(qū)(即相對于神經(jīng)網(wǎng)絡(luò)內(nèi)部記憶空間的擴(kuò)展內(nèi)存)、1個控制器(對應(yīng)于處理器)和狀態(tài)轉(zhuǎn)移指令集.擴(kuò)展內(nèi)存區(qū)包括2個棧結(jié)構(gòu)(S，R)和一個隨機(jī)內(nèi)存結(jié)構(gòu)(H)；控制器包括PS，PR，PC這3個寄存器，PS，PR分別是S，R棧頂指針，PC是程序計數(shù)器指針.支持編程控制，即支持輸入用指令集寫好的程序(程序框架)在虛擬機(jī)上執(zhí)行.

Fig. 3 The dVM architecture圖3 可微分虛擬機(jī)整體結(jié)構(gòu)

為了保證整個計算環(huán)境是連續(xù)可微分地執(zhí)行程序，指令集(包括擴(kuò)展內(nèi)存訪問指令)用算術(shù)矩陣操作實(shí)現(xiàn)為可微分函數(shù)(fun_foo)，擴(kuò)展內(nèi)存區(qū)用矩陣表示，寄存器用one-hot向量表示.控制器負(fù)責(zé)取指令、執(zhí)行指令、更新抽象機(jī)狀態(tài)，控制器還包括一個指示指令尋址的向量PC，用于實(shí)現(xiàn)執(zhí)行控制轉(zhuǎn)移.這些基本行為都以連續(xù)的可微分函數(shù)實(shí)現(xiàn).

2.2.2 指令集與指令集的可微分實(shí)現(xiàn)

表1給出了dVM的主要指令集的說明.為了不影響閱讀連貫性，我們在附錄中給出了指令集可微分實(shí)現(xiàn)的詳細(xì)數(shù)學(xué)表示，參見附錄A.

內(nèi)存讀寫的實(shí)現(xiàn)原理為，將棧指針看做分布在內(nèi)存空間上的訪問權(quán)重，基于此將內(nèi)存訪問(如READ，WRITE)表示為位置權(quán)重跟內(nèi)存單元的矩陣計算，然后基于READ，WRITE的線性組合可以實(shí)現(xiàn)PUSH，POP等復(fù)雜的棧操作；指令集的可微分實(shí)現(xiàn)原理為，對dVM狀態(tài)(擴(kuò)展內(nèi)存)的訪問與改變實(shí)現(xiàn)為READ，WRITE，PUSH，POP的線性組合；對于算術(shù)邏輯操作、控制操作通過矩陣代數(shù)運(yùn)算和運(yùn)算的組合來實(shí)現(xiàn)，矩陣算術(shù)操作理論指導(dǎo)可參看雙線性映射[22].因此所有的指令集都是用矩陣代數(shù)運(yùn)算表示的連續(xù)可微分實(shí)現(xiàn)，可以跟神經(jīng)網(wǎng)絡(luò)(神經(jīng)網(wǎng)絡(luò)也是矩陣代數(shù)運(yùn)算)無縫整合，因此可以用反向傳播算法的可微分優(yōu)化技術(shù)對程序生成、程序處理進(jìn)行直接建模.

2.2.3 程序的可微分執(zhí)行模型

算法1描述了過程化程序結(jié)構(gòu)在dVM上可微分解釋執(zhí)行流程.從狀態(tài)轉(zhuǎn)換的角度，其執(zhí)行過程被描述為從初始狀態(tài)S0出發(fā)的steps步狀態(tài)遷移.算法1中diffInstsLib是指令集的可微分實(shí)現(xiàn)函數(shù)庫，通過字典結(jié)構(gòu)索引.用到的FetchInst，step操作.dVM的初始狀態(tài)設(shè)置，訓(xùn)練開始時先將dVM擴(kuò)展內(nèi)存(即S，R，H構(gòu)成的狀態(tài)區(qū))清0，然后用標(biāo)注數(shù)據(jù)“輸入-輸出”樣例對的“輸入”初始化填充dVM擴(kuò)展內(nèi)存，并將對應(yīng)的棧指針初始化指向下一個空白位置，經(jīng)過初始設(shè)置內(nèi)存區(qū)構(gòu)成初始狀態(tài)S0.附錄B是一段程序在dVM上運(yùn)行過程例子.

算法1.可微分虛擬機(jī)程序執(zhí)行流程.

輸入:S0是dVM初始狀態(tài)、Code是待執(zhí)行程序框架、steps是執(zhí)行總步數(shù)；

輸出:狀態(tài)轉(zhuǎn)換列表LTRACE=[S0,S1,…,Ssteps].

① function:run(S0,Code,steps)

②S←S0,PC←S.pc,LTRACE[];

③LTRACE.append(S);

④ for (i=1;i≤steps;i++)

⑤Weightstate←FetchInst(PC,Code);

⑥ for (j=1;j≤Code.size;j++)

⑦Stmp←diffInstsLib[Code[j].key](S);

⑧StatesVector.append(Stmp);

⑨ end for

⑩Snext←step(Weightstate,StatesVector),

S←Snext;

算法1的執(zhí)行過程是從初始狀態(tài)開始的steps步連續(xù)狀態(tài)遷移，每一步是通過尋址從代碼空間選擇指令在當(dāng)前狀態(tài)上執(zhí)行并推進(jìn)dVM遷移到下一個狀態(tài).因此整個執(zhí)行過程構(gòu)成一個steps步的RNN模型，程序的一遍執(zhí)行可以描述為

exeTrace=(S1,S2,…,Si,…,Ssteps),

(1)

其中Si=step(Weightcode,Si-1)，S1是初始狀態(tài).

代碼空間尋址是根據(jù)PC和代碼矩陣Code計算在代碼行的權(quán)重分布:

FetchInst(PC,Code)←(PC⊙Code)1T.

(2)

計算取指令，其中Code是需要執(zhí)行程序的矩陣結(jié)構(gòu)化表示，PC是程序計數(shù)器的向量表示，1是行向量(1,1,…,1)，⊙是哈達(dá)瑪積.

(3)

Fig. 4 Step forward to get the next state圖4 單步執(zhí)行計算下一個狀態(tài)

單步執(zhí)行，其中Statecurrent是當(dāng)前狀態(tài)向量，Statenext是執(zhí)行后遷移的下一個狀態(tài)，Weightcode是取指令計算得到的指令執(zhí)行權(quán)重分布(用softmax計算)，functionCBi是匯編后的代碼塊(即用函數(shù)代碼片段給出的指令集可微分實(shí)現(xiàn))，StatesVector是狀態(tài)行向量.該求值邏輯如圖4所示，SP是執(zhí)行前當(dāng)前狀態(tài)，SN是單步執(zhí)行后遷入的狀態(tài)，Sn_i是dVM在SP狀態(tài)下執(zhí)行地址空間某個指令塊得到的狀態(tài).

2.2.4 訓(xùn)練目標(biāo)

(4)

(5)

我們在求值中發(fā)現(xiàn)通過PC，PS，PR指針計算狀態(tài)分量的掩碼(即只計算執(zhí)行結(jié)束時擴(kuò)展內(nèi)存的有效區(qū)域)，可以免去PC，PS，PR分量的距離計算.

Fig. 5 dVM state buffer components圖5 dVM狀態(tài)分量

2.3 從C語法到中間代碼表示的編譯生成

HNCP原型實(shí)現(xiàn)是在C語法基礎(chǔ)上擴(kuò)展支持嵌入神經(jīng)網(wǎng)絡(luò)作為基本語言構(gòu)造，稱作NCP(neural network component placeholder).圖6所示為HNCP前端語法產(chǎn)生式(grammar productions)的BNF描述；其中NCP的語法構(gòu)造由ncp產(chǎn)生式衍生.作為原型驗(yàn)證ncp只給出了encoder-transform-decoder神經(jīng)網(wǎng)絡(luò)模型結(jié)構(gòu),其中encoder對程序上下文輸入?yún)?shù)條件編碼，transform對條件進(jìn)行特征轉(zhuǎn)換，decoder解碼條件并基于此預(yù)測生成執(zhí)行動作.得益于dVM可微分運(yùn)行時環(huán)境，采用類似思路可增加其他可微分模型，如CNN(convolutional neural networks),seq2seq(sequence to sequence)等作為HNCP語法構(gòu)造的編程原語.

HNCP使用棧式求值語言作為中間表示(IR)，通過BNF產(chǎn)生式語義規(guī)則可以定義將HNCP源程序編譯為IR表示的語義動作；其基本思路是將C語法構(gòu)造翻譯為IR指令、語言構(gòu)造表示，如while用do-loop-endloop，if-else用GOTOF，函數(shù)調(diào)用用CALL，函數(shù)返回用RET，變量定義用H堆內(nèi)存分配，不同作用域的同名變量用可區(qū)分的命名前綴表示等.附錄C給出了BNF產(chǎn)生式語義規(guī)則的實(shí)現(xiàn)樣例.

Fig. 6 HNCP BNF grammar productions圖6 HNCP的BNF語法產(chǎn)生式

1) 在該神經(jīng)原語中，encoder以上下文參數(shù)作為條件進(jìn)行特征編碼，transform做進(jìn)一步特征轉(zhuǎn)換，同時也是對ncp網(wǎng)絡(luò)參數(shù)和層數(shù)做適當(dāng)?shù)恼{(diào)節(jié)，decoder解碼并做出執(zhí)行動作決策.

2)linear(out)增加輸出寬度為out的線性變換層.

3)observe將dVM狀態(tài)緩存的元素進(jìn)行聯(lián)合.元素取自求值數(shù)據(jù)棧(S)、控制返回棧(R)或隨機(jī)訪問內(nèi)存堆(H)中的單元項(xiàng).

圖7所示為encoder-transform-decoder的典型神經(jīng)網(wǎng)絡(luò)拓?fù)洌⒁鈭D中每個隱藏層可包含多層神經(jīng)網(wǎng)絡(luò).

Fig. 7 A typical topology of encoder-transform-decoder圖7 encoder-transform-decoder網(wǎng)絡(luò)拓?fù)?/p>

3 實(shí)驗(yàn)評估

本節(jié)對模型的程序生成學(xué)習(xí)性能、處理復(fù)雜程序結(jié)構(gòu)的能力進(jìn)行分析評估，包括泛化能力、樣本復(fù)雜度(訓(xùn)練樣本消耗)、準(zhǔn)確率的評估，以及代表性程序生成模型的主要指標(biāo)對比性分析.DeepMind NPI[7]是生成直接可運(yùn)行程序表示一類模型中表現(xiàn)最好的，seq2seq[23]是程序生成研究中普遍用來做參照的基準(zhǔn)模型，因此HNCP主要跟這2個模型做對比.要比較的學(xué)習(xí)任務(wù)采用NPI中使用的冒泡排序(SORT)和多位數(shù)初等加法(ADD)，除了可以跟NPI,seq2seq做直接對比，還考慮到它們包含多層次的復(fù)雜程序結(jié)構(gòu)，如函數(shù)調(diào)用、循環(huán)、分支、遞歸，這些結(jié)構(gòu)是廣泛的復(fù)雜任務(wù)編程關(guān)鍵，因此具有代表性.附錄D給出了任務(wù)的程序框架詳情.

3.1 生成程序泛化能力

泛化能力是評估程序生成模型實(shí)用性最重要的指標(biāo)之一，定義為Gen=Lengthtest_maxLengthtrain_max，Gen值越大越好，其中Lengthtrain_max是訓(xùn)練期間見過的最大任務(wù)規(guī)模(如排序任務(wù)的序列長度)，Lengthtest_max是測試期間可正確預(yù)測的最大任務(wù)規(guī)模.圖8中，SORT任務(wù)：seq2seq模型泛化能力為1，即泛化能力差只能對訓(xùn)練期間見過的序列長度正確排序，當(dāng)測試樣本略長于訓(xùn)練樣本時準(zhǔn)確率立即迅速下降)；NPI泛化能力為3，即可正確完成3倍于訓(xùn)練樣本長度的序列排序；HNCP表現(xiàn)了最佳泛化能力(實(shí)驗(yàn)最多測試了32倍規(guī)模).ADD任務(wù)：HNCP表現(xiàn)最好，seq2seq仍表現(xiàn)差，對于這個簡單些的任務(wù)NPI泛化表現(xiàn)也很好.

Fig. 8 Strong vs. weak generalization圖8 泛化能力比較

實(shí)驗(yàn)表明，整合人工編程和神經(jīng)網(wǎng)絡(luò)自動生成構(gòu)建程序生成模型有助于提升程序生成的泛化能力.

3.2 樣本復(fù)雜度

模型達(dá)到最佳泛化能力所消耗的訓(xùn)練樣本數(shù)量，該指標(biāo)值越小表示模型學(xué)習(xí)性能越好.圖9所示，對于SORT任務(wù)，本文HNCP模型消耗約272個樣本，比NPI和seq2seq明顯少；對于ADD任務(wù)，本文模型消耗約320個樣本，比NPI和seq2seq模型需求明顯少.該實(shí)驗(yàn)表明通過整合人工程序員和神經(jīng)網(wǎng)絡(luò)優(yōu)勢構(gòu)建程序生成模型可有效提高學(xué)習(xí)效率.

Fig. 9 Consumption of training samples圖9 訓(xùn)練樣本消耗量

注意，NPI模型標(biāo)注樣本量是統(tǒng)計任務(wù)執(zhí)行軌跡的步驟數(shù)，而不是直接計算輸入-輸出對.比如，SORT任務(wù)樣本數(shù)是[m(m-1)2]n,ADD任務(wù)樣本數(shù)是(10m)n,其中m是問題規(guī)模(如排序序列長度)，n是任務(wù)個數(shù).

3.3 生成程序準(zhǔn)確率

生成程序準(zhǔn)確率：模型生成的程序執(zhí)行結(jié)果完全正確的任務(wù)樣本占總測試樣本的比例.

如圖10、圖11所示，對于ADD和SORT任務(wù)，使用長度為2的樣本訓(xùn)練的HNCP模型在比訓(xùn)練樣本長很多的測試樣本上可以獲得100%的準(zhǔn)確率，明顯優(yōu)于基線(NPI和seq2seq).測試發(fā)現(xiàn)seq2seq(LSTM實(shí)現(xiàn))學(xué)習(xí)排序任務(wù)是很困難的，表現(xiàn)在當(dāng)測試序列稍微比訓(xùn)練樣本長時，準(zhǔn)確率會立即快速下降.HNCP只需用長度為2的序列訓(xùn)練程序框架，便成功地學(xué)到了排序行為，并很好地泛化到很長的任務(wù)序列.

Fig. 10 Test accuracy of task ADD圖10 加法任務(wù)生成程序測試準(zhǔn)確率

Fig. 11 Test accuracy of task BubbleSort圖11 排序任務(wù)生成程序測試準(zhǔn)確率

跟對標(biāo)基準(zhǔn)方法一樣，這里使用測試準(zhǔn)確率來評估生成程序的精確性，可以很好地跟同類研究做性能指標(biāo)對比.當(dāng)前神經(jīng)網(wǎng)絡(luò)可解釋性是一個難題，因此使用神經(jīng)網(wǎng)絡(luò)構(gòu)建程序生成模型的相關(guān)研究主要采用測試樣例準(zhǔn)確率來評估生成程序的精確性.所以不同于一般意義上的程序正確性證明，對于這類程序生成模型，做到類似“形式語義”等方式實(shí)現(xiàn)嚴(yán)格的程序正確性證明是困難的.

3.4 代表性程序生成模型指標(biāo)對比

本節(jié)對主要的代表性程序生成模型，結(jié)合主要指標(biāo)進(jìn)行對比性匯總分析.如表2所示：

Table 2 Summaries of Indexes of Program Generation Models表2 程序生成模型主要指標(biāo)對比匯總

泛化能力(Gel)：BAYOU和DeepCoder預(yù)測生成的代碼樣例不能保證正確、可運(yùn)行，也沒有正確性自動檢測方法，所以生成程序的泛化能力無法評估.其中HNCP是表現(xiàn)最好的，NPI次之；復(fù)雜程序結(jié)構(gòu)(Ctl)：HNCP和BAYOU表現(xiàn)最好，都支持循環(huán)、分支、函數(shù)等復(fù)雜控制結(jié)構(gòu)，NPI在自定義的DSL專用小語言上支持函數(shù)嵌套、分支、跳轉(zhuǎn)控制結(jié)構(gòu)；編程語言支持(Lan)：HNCP和BAYOU都支持通用編程語言，NPI和DeepCoder支持自定義DSL專用語言，seq2seq和NTM不支持編程語言；樣本復(fù)雜度(Sam)：該指標(biāo)越低越好，HNCP樣本消耗最低，其他都消耗偏多,NPI僅次于HNCP，但其樣本標(biāo)注需要預(yù)先知道程序所有執(zhí)行路徑，所以標(biāo)注代價偏高；可執(zhí)行(Exe)：BAYOU和DeepCoder生成的程序不能直接執(zhí)行；是否學(xué)習(xí)到新的程序行為(Lrn)：根據(jù)是否需要提供完整的程序來區(qū)分，NPI是對給出的程序路徑的神經(jīng)網(wǎng)絡(luò)編碼，BAYOU需要收集大量功能相似的源碼樣例，剩下其他模型都可以從輸入-輸出樣例對中學(xué)習(xí)到程序行為；學(xué)習(xí)生成的程序表示(Rep)：Code表示代碼形式，Net表示用神經(jīng)網(wǎng)絡(luò)編碼形式.

綜合來看HNCP表現(xiàn)出更好的程序生成學(xué)習(xí)優(yōu)勢，這表明結(jié)合程序框架(人工程序員創(chuàng)作)和輸入-輸出數(shù)據(jù)對學(xué)習(xí)(神經(jīng)網(wǎng)絡(luò)自動生成)探索構(gòu)建程序生成模型的研究是有價值的.

3.5 討 論

實(shí)驗(yàn)表明，本文方法跟同類代表性研究方法相比表現(xiàn)出更好的學(xué)習(xí)性能.結(jié)合模型與實(shí)驗(yàn)設(shè)計，我們有理由相信這種性能提升是因?yàn)槿诤狭巳斯こ绦騿T和神經(jīng)網(wǎng)絡(luò)的協(xié)作，即模型將人工程序員的貢獻(xiàn)整合進(jìn)來發(fā)揮了作用；但因?yàn)楫?dāng)前神經(jīng)網(wǎng)絡(luò)模型的可解釋性瓶頸，我們很難給出一個嚴(yán)格的證明.實(shí)驗(yàn)表明其性能提升明顯、并能表達(dá)復(fù)雜程序結(jié)構(gòu)，驗(yàn)證了這種整合模型的優(yōu)勢；而同時從某種意義上可能認(rèn)為這種整合帶來的性能優(yōu)勢是以犧牲全自動化程序生成為半自動化的便利性為代價(局限性)，但這需要結(jié)合技術(shù)發(fā)展階段綜合考慮：首先，我們在引言中結(jié)合相關(guān)工作和觀察分析探討過，當(dāng)前完全依賴神經(jīng)網(wǎng)絡(luò)的全自動或者全黑盒的程序生成模型在關(guān)鍵指標(biāo)上表現(xiàn)不足(因此全自動的便利性是尚不存在的)，在該背景下我們提出協(xié)作式模型并給出一種實(shí)現(xiàn)方法進(jìn)行驗(yàn)證，實(shí)驗(yàn)表明這種融合程序員和神經(jīng)網(wǎng)絡(luò)的協(xié)助式程序生成模型表現(xiàn)出優(yōu)勢，結(jié)合分析表明這是有潛力、富有價值的研究思路；其次，考慮到程序生成總需要以一定的方式將需求提供給模型，結(jié)合引言中對程序員和神經(jīng)網(wǎng)絡(luò)各自的優(yōu)勢、不足的討論，因此將程序員融合到自動化程序生成建模中是否是必要的，是一個開放性、多因素均衡問題，并且很可能會隨著AI技術(shù)的發(fā)展階段不同而需要做出不同選擇.

關(guān)于實(shí)驗(yàn)評估測試任務(wù)的選擇.主要選取對標(biāo)基準(zhǔn)模型(NPI,seq2seq)中用到的相同測試任務(wù)，這方便將我們的方法跟基準(zhǔn)模型直接進(jìn)行性能對比，其中NPI是這類模型中表現(xiàn)最好的，因此這種任務(wù)比較具有代表性；SORT，ADD任務(wù)包含循環(huán)、函數(shù)調(diào)用、遞歸、分支、順序執(zhí)行等復(fù)雜控制結(jié)構(gòu)，對于當(dāng)前的程序自動生成相關(guān)研究具有足夠復(fù)雜性和挑戰(zhàn)性，能夠?qū)⒋硇阅Ｐ?如基準(zhǔn)模型和本文模型)的性能指標(biāo)進(jìn)行有效區(qū)分，另外這些程序結(jié)構(gòu)足以表達(dá)其他比較復(fù)雜的任務(wù).

4 總 結(jié)

經(jīng)過學(xué)者們長期的努力，自動化程序生成研究取得了明顯進(jìn)步，但與圖像、語音處理等相比，距實(shí)際應(yīng)用仍有很大的可提升空間.本文提出了一種結(jié)合“人工編程”與“神經(jīng)網(wǎng)絡(luò)自動化程序生成”構(gòu)建程序生成模型的研究方法.實(shí)驗(yàn)表明整合人工程序員和神經(jīng)網(wǎng)絡(luò)各自優(yōu)勢的協(xié)作式程序生成模型可以明顯提升程序生成的訓(xùn)練學(xué)習(xí)性能(泛化能力、準(zhǔn)確率、樣本復(fù)雜度)，并適應(yīng)復(fù)雜程序結(jié)構(gòu).因此，本文探討的思路是可行且高效的，值得未來做更廣泛的研究探索.

提出一種協(xié)作式程序生成建模方法并實(shí)驗(yàn)驗(yàn)證其技術(shù)上的可行性和有效性只是研究工作的一個方面，最終希望走向廣泛的實(shí)際應(yīng)用.而在工程應(yīng)用中不僅關(guān)心技術(shù)可行性，還需考慮比如豐富并總結(jié)程序員跟神經(jīng)網(wǎng)絡(luò)的編程任務(wù)分工的規(guī)則、設(shè)計豐富的編程原語、正確性驗(yàn)證等，因此我們認(rèn)為，下一步有必要對4項(xiàng)工作進(jìn)行探討:

1) 豐富分工協(xié)作規(guī)則并進(jìn)行總結(jié).比如可以從應(yīng)用場景、任務(wù)類型出發(fā)，全面探討和總結(jié)在程序員和神經(jīng)網(wǎng)絡(luò)間高效的編程任務(wù)分工規(guī)則.并將這些規(guī)則以程序模板、編程原語或用戶編程接口等方式封裝呈現(xiàn).參照J(rèn)ava,C++等編程模型發(fā)展經(jīng)驗(yàn),這不是一個完全可正向評估的純技術(shù)問題,往往依賴于Java,C++等用戶生態(tài)的編程創(chuàng)造性的反饋和迭代,即具有開放性和創(chuàng)造性.

2) 如何劃分協(xié)作分工是一個開放性問題.本文實(shí)驗(yàn)驗(yàn)證采用的是“程序員負(fù)責(zé)框架編制、神經(jīng)網(wǎng)絡(luò)負(fù)責(zé)局部細(xì)節(jié)生成”的分工方法，該方法在呈現(xiàn)協(xié)作式程序生成的概念形態(tài)、證明協(xié)作式模型的可行性、驗(yàn)證可取得程序生成學(xué)習(xí)性能的明顯改進(jìn)等方面具有優(yōu)勢,從而證明本文方法理念在意義上是足夠的；但未必是最合理的分工方式，并且肯定不能覆蓋全部的可能分工模式或規(guī)則.因此設(shè)計不同的分工協(xié)作方法，并為新分工方法構(gòu)建可實(shí)現(xiàn)、可驗(yàn)證的模型具有很大的探索空間，比如在本文思路基礎(chǔ)上，如果能夠適當(dāng)?shù)卦O(shè)計擴(kuò)展模型使得神經(jīng)網(wǎng)絡(luò)可在“程序框架的編制”任務(wù)中參與分工，將是對程序員與神經(jīng)網(wǎng)絡(luò)協(xié)作式編程模型很有意義的貢獻(xiàn).

3) 考慮到程序需求場景的復(fù)雜性.程序自動生成的應(yīng)用不僅僅是某個或某幾個技術(shù)點(diǎn)問題，而是涉及一系列技術(shù)集成，因此與大范圍應(yīng)用的圖像處理、語音識別等相比，距離工程應(yīng)用仍有差距.制約程序自動生成應(yīng)用的因素很多，其中對需求進(jìn)行建模并能恰當(dāng)?shù)馗窠?jīng)網(wǎng)絡(luò)銜接是關(guān)鍵因素之一;而本文探討的程序員和神經(jīng)網(wǎng)絡(luò)協(xié)作式模型中，程序員提供的程序框架其實(shí)也屬于一種需求描述規(guī)范的表達(dá)方式，如果沿著這個思路拓展并總結(jié)一套系統(tǒng)化需求描述規(guī)范，輸入給融合的神經(jīng)網(wǎng)絡(luò)組件處理，我們相信這是值得進(jìn)一步拓展探索的研究工作.

4) 生成程序的準(zhǔn)確性證明.當(dāng)前基于神經(jīng)網(wǎng)絡(luò)的程序生成相關(guān)研究主要通過測試準(zhǔn)確率評估生成程序的精確性，對生成程序進(jìn)行嚴(yán)格的準(zhǔn)確性證明是一個富有挑戰(zhàn)性的工作.