周 鵬,武延軍,趙 琛

1(中國(guó)科學(xué)院 軟件研究所,北京 100190)

2(中國(guó)科學(xué)院大學(xué),北京 100049)

自計(jì)算機(jī)誕生以來,實(shí)現(xiàn)幫助計(jì)算機(jī)自動(dòng)編寫程序的系統(tǒng)一直是人工智能研究者所追求的重要目標(biāo)之一,相關(guān)研究最早可追溯到1971年[1].機(jī)器編程的研究總體分為類自然語(yǔ)言代碼挖掘和代碼生成兩大類,代碼生成的研究又可劃分為程序空間搜索和連續(xù)可微分優(yōu)化法.近年來,隨著深度學(xué)習(xí)的興起,結(jié)合神經(jīng)網(wǎng)絡(luò)以連續(xù)可微分優(yōu)化理論為基礎(chǔ)構(gòu)建編程模型的研究也成為一個(gè)研究熱點(diǎn)[2-4].總體而言,從輸入素材角度,可將這些神經(jīng)網(wǎng)絡(luò)類編程模型分為基于程序執(zhí)行軌跡樣例的方法[2]和基于程序輸入輸出數(shù)據(jù)樣例的方法[3,4].

當(dāng)前,基于執(zhí)行軌跡的研究方法需要收集逐步的執(zhí)行軌跡有監(jiān)督數(shù)據(jù),數(shù)據(jù)成本高,并且該模型學(xué)習(xí)的本質(zhì)是通過對(duì)不同執(zhí)行路徑的監(jiān)督數(shù)據(jù)學(xué)習(xí)形成算法的神經(jīng)網(wǎng)絡(luò)編碼,而覆蓋不同路徑的收集本身意味著要求算法是明確的,因此嚴(yán)格意義上,該模型并沒有學(xué)習(xí)到新的代碼,基于輸入輸出數(shù)據(jù)樣例的方法直接提供輸入輸出數(shù)據(jù)訓(xùn)練集,讓神經(jīng)網(wǎng)絡(luò)嘗試從數(shù)據(jù)中學(xué)習(xí)從輸入轉(zhuǎn)換為輸出的規(guī)律,該方法面臨的問題是從輸入到輸出的轉(zhuǎn)換規(guī)則可能存在多種,即存在有歧義性,并且該方法會(huì)面臨編程語(yǔ)言過多的規(guī)則、實(shí)現(xiàn)細(xì)節(jié)帶來的學(xué)習(xí)復(fù)雜度,同時(shí)未能輸入源程序的背景知識(shí)(比如程序員預(yù)先學(xué)習(xí)的編程語(yǔ)言、計(jì)算機(jī)原理教程),導(dǎo)致模型處理信息不完備,也不能為訓(xùn)練學(xué)習(xí)過程提供珍貴的編程經(jīng)驗(yàn).額外的復(fù)雜度加上不完備的信息給模型訓(xùn)練學(xué)習(xí)帶來了巨大挑戰(zhàn),導(dǎo)致習(xí)得算法通常非常簡(jiǎn)單,比如很難處理分支、遞歸等復(fù)雜控制結(jié)構(gòu),并且泛化能力明顯不足.因此,當(dāng)前單純地以代碼或輸入輸出數(shù)據(jù)為輸入構(gòu)建的神經(jīng)網(wǎng)絡(luò)編程模型都存在局限性.我們認(rèn)為,在程序生成或程序語(yǔ)義處理問題上應(yīng)該跳出編程者視角,盡可能提升習(xí)模型建模的抽象層次,在更具抽象層面用公理語(yǔ)義的方式將程序描述為抽象機(jī)的狀態(tài)轉(zhuǎn)換,從而避免從操作語(yǔ)義角度去描述程序的執(zhí)行語(yǔ)義而陷入編程語(yǔ)言的復(fù)雜規(guī)范、底層實(shí)現(xiàn)細(xì)節(jié)等操作層面,提升程序處理的抽象層次是本文整個(gè)研究的基本動(dòng)機(jī).同時(shí),我們認(rèn)為,程序生成的研究不能單純地只從代碼或數(shù)據(jù)中學(xué)習(xí),進(jìn)一步的研究需要整合軟件工程中長(zhǎng)期積累的寶貴編程經(jīng)驗(yàn)為學(xué)習(xí)過程提供指導(dǎo),而本文的研究也說明:提升模型的抽象層次,是支持輸入并整合編程經(jīng)驗(yàn)的一個(gè)有效途徑.

本文研究了一種可將高級(jí)編程語(yǔ)言與神經(jīng)網(wǎng)絡(luò)組件無(wú)縫結(jié)合的混合式編程模型(簡(jiǎn)稱 dAMP).該模型的優(yōu)點(diǎn)是:可以同時(shí)使用過程化的高級(jí)編程語(yǔ)言元素和神經(jīng)網(wǎng)絡(luò)組件元素混合開發(fā)應(yīng)用程序,從而可以彌合兩種元素的隔閡,發(fā)揮并整合高級(jí)過程化編程和神經(jīng)網(wǎng)絡(luò)可訓(xùn)練學(xué)習(xí)編程各自的優(yōu)勢(shì),并為基于神經(jīng)網(wǎng)絡(luò)的程序自動(dòng)生成模型提供經(jīng)驗(yàn)知識(shí)的輸入途徑.dAMP研究的基本出發(fā)點(diǎn)是從抽象層次研究程序生成問題,其整體思路是:首先,從純機(jī)器演算角度構(gòu)造一個(gè)通用的抽象機(jī)(AM),用公理語(yǔ)義的方式將程序執(zhí)行描述為抽象機(jī)的狀態(tài)轉(zhuǎn)換,AM 有獨(dú)立的對(duì)外界無(wú)依賴的狀態(tài)存儲(chǔ)和指令集,支持傳統(tǒng)的高級(jí)編程語(yǔ)言過程化編程;然后,以某種方式將AM 實(shí)現(xiàn)為連續(xù)可微分抽象機(jī) dAM.該實(shí)現(xiàn)方式與典型的神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)是同質(zhì)的,因此可以無(wú)縫對(duì)接神經(jīng)網(wǎng)絡(luò)組件.借助 dAM,高級(jí)過程化程序可以在 dAM上以連續(xù)可微分的方式直接執(zhí)行.dAMP混合編程是研究如何編寫程序框架提供經(jīng)驗(yàn)信息、如何在程序中嵌入神經(jīng)網(wǎng)絡(luò)組件為 dAM 編寫程序框架以及如何使用訓(xùn)練數(shù)據(jù)學(xué)習(xí)生成完整的程序.抽象機(jī)的可選取原型目標(biāo)很多,這里選取 Forth[5,6]編程語(yǔ)言執(zhí)行模型作為構(gòu)造抽象機(jī)的目標(biāo).本文會(huì)對(duì) dAM 的實(shí)現(xiàn)方式做必要夠用的介紹,但重點(diǎn)是給出 dAMP混合編程的關(guān)鍵實(shí)現(xiàn)技術(shù),并對(duì) dAMP程序自動(dòng)生成的學(xué)習(xí)機(jī)制做詳細(xì)深入的實(shí)驗(yàn)分析.

本文的主要貢獻(xiàn):1) 提出了在抽象層研究程序自動(dòng)生成問題的一種思路,并給出該思路的一個(gè)完整驗(yàn)證系統(tǒng)dAMP;2) dAMP給出了一種支持經(jīng)驗(yàn)輸入、編程語(yǔ)言與神經(jīng)網(wǎng)絡(luò)組件元素相結(jié)合的混合編程模型,并給出其設(shè)計(jì)實(shí)現(xiàn)的關(guān)鍵技術(shù);3) 給出了豐富的實(shí)驗(yàn)驗(yàn)證,對(duì)dAMP程序自動(dòng)生成的學(xué)習(xí)機(jī)制做了深入的實(shí)驗(yàn)分析.

本文第1節(jié)對(duì)dAMP框架做一個(gè)整體介紹.第2節(jié)介紹編程語(yǔ)言模型,包括理解本文需要預(yù)備的編程語(yǔ)言概念、語(yǔ)言運(yùn)行模型知識(shí).第3節(jié)介紹連續(xù)可微分抽象機(jī)實(shí)現(xiàn)方法.第4節(jié)詳細(xì)展開實(shí)現(xiàn)dAMP的關(guān)鍵技術(shù).第5節(jié)實(shí)驗(yàn)驗(yàn)證并對(duì)模型的學(xué)習(xí)機(jī)制做深入的實(shí)驗(yàn)分析.第6節(jié)介紹相關(guān)性工作.第7節(jié)是結(jié)束語(yǔ).

1 整體架構(gòu)

可微分抽象機(jī)混合編程系統(tǒng)總體可分為源程序、編譯與處理、連續(xù)可微分抽象機(jī)和計(jì)算圖這4個(gè)主要組成部分,如圖1所示.

Fig.1 dAMP architecture圖1 dAMP整體架構(gòu)

總體而言,圖1的上半部分是對(duì)源程序處理,下半部分是程序的運(yùn)行時(shí)環(huán)境和訓(xùn)練學(xué)習(xí)環(huán)境.源程序首先經(jīng)過編譯形成中間代碼;然后對(duì)中間代碼做優(yōu)化處理和匯編處理,生成結(jié)構(gòu)化的適合連續(xù)可微分執(zhí)行的代碼矩陣表示;接著,連續(xù)可微分抽象機(jī)加載訓(xùn)練樣本的輸入部分?x到狀態(tài)緩存的數(shù)據(jù)棧并執(zhí)行代碼矩陣,而執(zhí)行的結(jié)果便是構(gòu)建生成程序執(zhí)行的計(jì)算圖表示,其中,計(jì)算圖的程序執(zhí)行部分總體是N步遞歸結(jié)構(gòu);最后,以 dAM的狀態(tài)為輸入執(zhí)行計(jì)算圖,并以訓(xùn)練樣本的標(biāo)記部分?y為輸入計(jì)算loss、以梯度下降可微分優(yōu)化的方式進(jìn)行訓(xùn)練學(xué)習(xí).圖中實(shí)箭頭連線是數(shù)據(jù)流,虛箭頭連線是控制依賴.下面對(duì)這4個(gè)主要組成部分分別做介紹.

(1) 源程序

使用Forth高級(jí)編程語(yǔ)言和神經(jīng)網(wǎng)絡(luò)組件元素(簡(jiǎn)稱nc)混合編寫的程序,與常規(guī)編程需要編寫程序的完整細(xì)節(jié)不同,dAMP編程程序員可以基于編程經(jīng)驗(yàn)只描述程序的框架,而把一些細(xì)節(jié)用待學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)組件(nc)占位,通過框架和nc結(jié)構(gòu)提供經(jīng)驗(yàn)信息.

(2) 編譯與處理

把源程序轉(zhuǎn)換為更適合dAM高效處理的形式,包括編譯、優(yōu)化和匯編這3個(gè)階段.編譯將源程序翻譯為中間代碼,包括詞法分析、語(yǔ)法樹生成以及生成中間代碼,在中間代碼生成期間,會(huì)額外做一些宏替換、控制語(yǔ)句處理等操作,比如將循環(huán)、條件分支、函數(shù)調(diào)用等都統(tǒng)一轉(zhuǎn)換為標(biāo)簽跳轉(zhuǎn)、統(tǒng)一分配標(biāo)簽等;優(yōu)化主要包括對(duì)分支的處理和代碼劃塊,分支的處理主要按照控制語(yǔ)句標(biāo)簽定義出現(xiàn)順序進(jìn)行序列化編碼,實(shí)現(xiàn)標(biāo)簽的表格化管理,代碼劃塊主要是將程序代碼劃分為若干粗粒度的順序代碼塊,便于后面將程序的狀態(tài)轉(zhuǎn)移由行粒度壓縮到塊粒度,從而顯著提升執(zhí)行效率和模型訓(xùn)練效果;匯編主要工作是將優(yōu)化后的中間轉(zhuǎn)換為可以在dAM上執(zhí)行的代碼矩陣,包括為神經(jīng)網(wǎng)絡(luò)占位符分配神經(jīng)網(wǎng)絡(luò)單元、代碼的表格結(jié)構(gòu)化管理、控制語(yǔ)句地址標(biāo)簽的表格結(jié)構(gòu)化管理以及在結(jié)構(gòu)化基礎(chǔ)上對(duì)代碼和地址的索引化引用,并將索引化引用以代碼原地(inplace)修改或替換方式反饋到代碼中,結(jié)構(gòu)化和索引化為在dAM上做連續(xù)可微分轉(zhuǎn)化和神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)模型構(gòu)建做準(zhǔn)備.

(3) 連續(xù)可微分抽象機(jī)

連續(xù)可微分抽象機(jī)dAM以代碼矩陣和訓(xùn)練樣本的輸入部分?x為輸入,將程序以逐步的連續(xù)狀態(tài)轉(zhuǎn)換方式解釋執(zhí)行,其執(zhí)行結(jié)果是生成對(duì)應(yīng)的程序計(jì)算圖表示.dAM 是使用矩陣代數(shù)對(duì) Forth語(yǔ)言執(zhí)行抽象機(jī)模型的連續(xù)可微分表示,主要包括狀態(tài)操作和指令集的連續(xù)可微分實(shí)現(xiàn).因?yàn)楹蜕窠?jīng)網(wǎng)絡(luò)一樣都使用矩陣代數(shù)實(shí)現(xiàn)形式,因此在dAM上,高級(jí)編程語(yǔ)言元素與神經(jīng)網(wǎng)絡(luò)單元元素能夠無(wú)縫結(jié)合.

(4) 計(jì)算圖

計(jì)算圖是程序生成模型的最終表示,在dAM執(zhí)行代碼矩陣期間構(gòu)建生成,主要包括程序遞歸執(zhí)行、學(xué)習(xí)目標(biāo)loss損失函數(shù)、訓(xùn)練函數(shù)train這3個(gè)部分,其中,程序遞歸執(zhí)行邏輯表達(dá)為遞歸訪問抽象機(jī)狀態(tài)空間的RNN網(wǎng)絡(luò),訓(xùn)練期間訓(xùn)練樣本的標(biāo)記部分?y為輸入.

2 編程語(yǔ)言模型介紹

本節(jié)介紹文中用到的預(yù)備知識(shí)編程語(yǔ)言模型,主要包括Forth語(yǔ)言元素、語(yǔ)言運(yùn)行模型.其中,語(yǔ)言元素只介紹與文中樣例代碼相關(guān)的內(nèi)容,如果想詳細(xì)了解語(yǔ)言細(xì)節(jié),請(qǐng)參考文獻(xiàn)[7].

2.1 語(yǔ)言執(zhí)行模型

Forth是一種棧式語(yǔ)言,隨著時(shí)間推進(jìn),其執(zhí)行虛擬機(jī)模型有多個(gè)變體,本文采用一個(gè)比較經(jīng)典而簡(jiǎn)潔的雙棧模型,如圖2所示,執(zhí)行虛擬機(jī)模型[6]包括一個(gè)求值數(shù)據(jù)棧DataStack、一個(gè)子程序(函數(shù))返回棧Return Stack、一個(gè)算術(shù)邏輯運(yùn)算單元ALU和一個(gè)隨機(jī)內(nèi)存存儲(chǔ)Main Memory(其中包括以棧的方式管理幀,在本文不是必須的,忽略),另外包括5個(gè)內(nèi)存訪問寄存器:PC程序計(jì)數(shù)器、PSP參數(shù)棧指針(數(shù)據(jù)棧棧頂指針)、RSP返回棧指針、FP幀指針、FEP幀尾指針(FP和FEP可忽略).注意,雖然Return Stack返回棧從名字上看是保存子程序調(diào)用返回地址,實(shí)際上它還被用于臨時(shí)數(shù)據(jù)交換.

Fig.2 Forth VM圖2 Forth虛擬機(jī)模型

Forth表達(dá)式采用逆波蘭式(RPN)表示,因此,這種雙棧模型非常適合Forth程序的高效執(zhí)行.圖3以一個(gè)簡(jiǎn)單的例子2+4=6,說明Forth語(yǔ)言執(zhí)行模型.

Fig.3 Example of expression evaluation圖3 表達(dá)式求值示例

2.2 部分語(yǔ)言元素

Forth將指令或函數(shù)稱為 word,它是一種可擴(kuò)展語(yǔ)言,支持函數(shù)定義(subroutine)和函數(shù)調(diào)用,新定義的函數(shù)又稱新word,可以像內(nèi)置word一樣被使用,因此,定義新函數(shù)的同時(shí)也擴(kuò)展了Forth語(yǔ)言.表1是相關(guān)word功能說明,詳細(xì)可參考文獻(xiàn)[7].

Table 1 Part of Forth words表1 部分Forth指令

3 可微分抽象機(jī)實(shí)現(xiàn)方法

由第2.1節(jié)Forth語(yǔ)言執(zhí)行模型可知,其程序執(zhí)行,既可看成指令執(zhí)行序列,又可從公理語(yǔ)義的角度忽略指令的實(shí)現(xiàn)細(xì)節(jié),只評(píng)估指令執(zhí)行后對(duì) Forth狀態(tài)單元的改變.這種完全以狀態(tài)的遷移來描述程序執(zhí)行的方式,我們稱之為抽象機(jī)模型AM.Forth程序在AM上的指令執(zhí)行可以表示為狀態(tài)的遷移:

其中,D數(shù)據(jù)棧、R返回棧、Pc程序指針、Pd數(shù)據(jù)棧棧頂指針、Pr返回棧棧頂指針,它們構(gòu)成了 Forth抽象機(jī)AM 的狀態(tài)單元,左邊是指令執(zhí)行前狀態(tài),右邊是指令執(zhí)行后的狀態(tài).直接的,將 Forth抽象機(jī)的離散狀態(tài)空間映射到可微分抽象機(jī)dAM的連續(xù)狀態(tài)空間.dAM的狀態(tài)用sd=(Dd,Rd,Pcd,Pdd,Prd)表示,dAM執(zhí)行過程即狀態(tài)空間S中狀態(tài)到狀態(tài)的映射?dam:S→S,抽象機(jī)的word指令w∈?dam可被看作改變dAM狀態(tài)的函數(shù).

實(shí)現(xiàn)連續(xù)可微分抽象機(jī)的方法原理.

1)狀體操作連續(xù)可微分實(shí)現(xiàn):首先對(duì)Forth抽象機(jī)的狀態(tài)訪問的基本操作以矩陣代數(shù)的方式實(shí)現(xiàn)為連續(xù)可微分的,包括讀(READ)和寫(WRITE)操作,類似于 attention機(jī)制,通過把棧指針看成內(nèi)存單元權(quán)重的方式實(shí)現(xiàn)READ和WRITE操作,比如數(shù)據(jù)棧READ操作實(shí)現(xiàn)為數(shù)據(jù)棧指針Pd與數(shù)據(jù)棧D的矩陣乘法,其原理類似于NTM[3]內(nèi)存訪問實(shí)現(xiàn);然后,基于READ和WRITE線性組合實(shí)現(xiàn)PUSH、POP等內(nèi)存高級(jí)操作.

2)Word操作的連續(xù)可微分實(shí)現(xiàn):借助矩陣代數(shù)運(yùn)算來表示 word操作,從而實(shí)現(xiàn)為連續(xù)可微分的,比如word指令的基本功能可分為訪問抽象機(jī)狀態(tài)單元或算術(shù)邏輯運(yùn)算,其中,狀態(tài)訪問的實(shí)現(xiàn)原理與步驟1)類似,而算術(shù)邏輯運(yùn)算則可借助one-hot矩陣對(duì)數(shù)據(jù)進(jìn)行編碼,然后通過矩陣算術(shù)運(yùn)算計(jì)算結(jié)果.

4 可微分抽象機(jī)混合編程實(shí)現(xiàn)關(guān)鍵技術(shù)

本節(jié)詳細(xì)說明實(shí)現(xiàn)dAMP的關(guān)鍵技術(shù),是本文的重點(diǎn)章節(jié).

4.1 源程序到中間代碼編譯

· 詞法分析

這里給出本文詞法分析正規(guī)式定義,即生成token的規(guī)則,源程序經(jīng)過詞法分析,轉(zhuǎn)換為token序列,如正規(guī)式公式(2)所示.

· 語(yǔ)法分析(AST生成)

語(yǔ)法分析以源程序的 token序列為輸入生成抽象語(yǔ)法樹(AST),Forth通過棧和利用后綴表達(dá)式(RPN)的特點(diǎn)進(jìn)行解析,解析簡(jiǎn)單同時(shí)極其靈活,不需要復(fù)雜的語(yǔ)法制導(dǎo)解析過程,因此,當(dāng)前Forth語(yǔ)言沒有類似于C語(yǔ)言的靜態(tài)BNF產(chǎn)生式來限定語(yǔ)法[8].本文是經(jīng)過裁剪定制的Forth驗(yàn)證語(yǔ)言,為了描述清晰規(guī)范,這里給出實(shí)現(xiàn)本文驗(yàn)證用Forth語(yǔ)法分析的BNF主要產(chǎn)生式項(xiàng),如產(chǎn)生式公式(3)所示.

其中,〈nc〉條目用于產(chǎn)生內(nèi)嵌神經(jīng)網(wǎng)絡(luò)組件,以實(shí)現(xiàn)對(duì)用神經(jīng)網(wǎng)絡(luò)組件與Forth元素混合編寫的源程序進(jìn)行語(yǔ)法分析.為了簡(jiǎn)單清晰,這里省略了一些簡(jiǎn)單的term元素和與ifthenelse類似的結(jié)構(gòu)(如while)的產(chǎn)生式.

· 中間代碼生成

算法1描述從AST生成中間代碼,命名2同to,中間代碼指令集的部分指令與Forth指令同名且功能相同,但也有一些專門指令(控制指令為主).

算法1.ast2im(ast,labelAllocator). //ast2im取其讀音代表astToim

輸入:ast-抽象語(yǔ)法樹;labelAllocator-分配管理不重名的跳轉(zhuǎn)標(biāo)簽.

輸出:imCode-中間代碼.

算法1借助注釋描述了相關(guān)中間代碼指令含義,易混淆語(yǔ)義的指令由表2給出專門解釋.

Table 2 Part of intermediate commands表2 部分中間代碼指令

源程序以中間代碼的形式在可微分抽象機(jī)上執(zhí)行.算法1中,函數(shù)調(diào)用通過call指令實(shí)現(xiàn),該指令在控制轉(zhuǎn)移前執(zhí)行保存現(xiàn)場(chǎng)操作,call保存現(xiàn)場(chǎng)只保存返回地址,不處理函數(shù)局部變量或函數(shù)參數(shù)傳遞.出于簡(jiǎn)化,本文沒實(shí)現(xiàn)Frame Stack,典型的Forth實(shí)現(xiàn)也沒有Frame Stack,但這不影響實(shí)現(xiàn)函數(shù)的嵌套及遞歸調(diào)用,函數(shù)體以exit指令結(jié)束,消耗返回地址、恢復(fù)控制現(xiàn)場(chǎng).函數(shù)定義的代碼生成在生成函數(shù)體代碼前,先插入一個(gè)跳轉(zhuǎn)標(biāo)簽,指向函數(shù)結(jié)尾,從而保證正確的執(zhí)行轉(zhuǎn)移.標(biāo)簽地址是符號(hào)地址,隨后的中間代碼優(yōu)化處理階段替換為實(shí)際地址,參照函數(shù)調(diào)用的實(shí)現(xiàn)技巧可以很容易理解條件分支、循環(huán)等控制指令實(shí)現(xiàn)方式.

神經(jīng)網(wǎng)絡(luò)組件元素nc包括(encoder,transforms,decoder)這3個(gè)部分,其功能分別是狀態(tài)編碼、狀態(tài)轉(zhuǎn)換、狀態(tài)解碼產(chǎn)生狀態(tài)操作動(dòng)作,這三者構(gòu)成一個(gè)完整的帶有可學(xué)習(xí)參數(shù)的神經(jīng)網(wǎng)絡(luò)組件,并可編程客制.

中間代碼指令功能單一、支持機(jī)械化微碼求值實(shí)現(xiàn),算法1的中間代碼生成過程將函數(shù)定義、函數(shù)調(diào)用、ifthenelse等復(fù)雜結(jié)構(gòu)轉(zhuǎn)換為基本中間指令序列,因此,將源程序轉(zhuǎn)換為中間代碼后非常適合轉(zhuǎn)換為逐步的連續(xù)可微分執(zhí)行,即適合在dAM上運(yùn)行,而混合編程語(yǔ)言語(yǔ)法特點(diǎn)是適合高效創(chuàng)作復(fù)雜源程序.

4.2 中間代碼優(yōu)化

為了提高中間代碼在dAM上執(zhí)行效率和dAM執(zhí)行輸出計(jì)算圖的訓(xùn)練學(xué)習(xí)效率,需要對(duì)中間代碼進(jìn)行優(yōu)化處理.本節(jié)介紹中間代碼優(yōu)化處理的算法.中間代碼優(yōu)化比較復(fù)雜也非常關(guān)鍵,需經(jīng)多遍處理才能完成,每一遍的優(yōu)化目標(biāo)不同,因此根據(jù)不同目標(biāo),我們首先分步驟把算法拆分成若干子算法分別做詳細(xì)說明,然后整合起來形成中間代碼優(yōu)化總算法.

算法2對(duì)中間代碼做兩次遍歷:第1遍按照先后順序給標(biāo)簽定義,分配從0開始的連續(xù)整數(shù)編號(hào),生成標(biāo)簽編碼表labTable;第2遍根據(jù)labTable對(duì)所有指令類型為標(biāo)簽跳轉(zhuǎn)或標(biāo)簽定義的指令,用編號(hào)重命名其標(biāo)簽屬性.

算法2.labRenumber(imCode).

輸入:imCode-跳轉(zhuǎn)標(biāo)簽重編號(hào)前中間代碼.

輸出:labRenumberedIMCode-標(biāo)簽重編號(hào)后中間代碼;labTable-標(biāo)簽重編碼表.

算法3與算法2類似,但因?yàn)槌Ａ坎环侄x和使用,只需對(duì)中間代碼做1次遍歷:按照遍歷時(shí)首次訪問順序給常量分配從0開始的連續(xù)整數(shù)編號(hào),并生成常量編碼表conTable(字典類型,鍵是常量的value屬性,值是分配的整數(shù)編號(hào)),對(duì)所有指令類型為常量(constant)的指令,用編號(hào)重命名其常量值屬性,遇到重復(fù)的常量,復(fù)用conTable已分配編號(hào).算法3主體代碼與labReplace類似,故不詳細(xì)展開其偽代碼.

算法3.conRenumber(imCode).

輸入:imCode-常量重編號(hào)前中間代碼.

輸出:conRenumberedIMCode-常量重編號(hào)后中間代碼;conTable-常量重編碼表.

算法4.blockPartion(imCode).

輸入:imCode分塊前中間代碼.

輸出:imBlocks分塊后中間代碼.

把中間代碼劃分為塊,通常,一個(gè)塊主要由不做控制轉(zhuǎn)移的普通word組成一個(gè)元組,塊結(jié)尾才可能有控制轉(zhuǎn)移word,塊的類型包括block塊、label塊、nc塊,分塊處理后的中間代碼,其每個(gè)塊可看作一個(gè)大word.

算法5將目標(biāo)標(biāo)簽轉(zhuǎn)換為目標(biāo)地址,建立標(biāo)簽到地址的映射表,并刪除標(biāo)簽定義指令.

算法5.lab2addr(imBlocks).

輸入:imBlocks-分塊后的中間代碼.

輸出:addrIM-目的標(biāo)簽轉(zhuǎn)換為目的地址后的中間代碼塊;tabLab2addr-標(biāo)簽地址對(duì)照表.

算法6遍歷代碼塊,為沒有以控制轉(zhuǎn)移指令結(jié)尾的代碼塊追加插入step指令,從而確保每個(gè)代碼塊執(zhí)行結(jié)束時(shí)都更新PC,即保證程序持續(xù)向前推進(jìn)執(zhí)行.

算法6.insertStepctl(addrIM).

輸入:addrIM-清除目標(biāo)標(biāo)簽并建立標(biāo)簽到地址映射后的中間代碼.

輸出:blockStepIM-補(bǔ)全step控制指令后的中間代碼塊.

算法7是中間代碼優(yōu)化的整個(gè)流程,經(jīng)過5次遍歷,生成最終在dAM上執(zhí)行的優(yōu)化代碼.代碼優(yōu)化是一個(gè)復(fù)雜但關(guān)鍵的過程,代碼優(yōu)化不僅能顯著提高訓(xùn)練學(xué)習(xí)效率,也為實(shí)現(xiàn)結(jié)合神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)模型提供了基礎(chǔ).

算法7.optimiseIM(imCode).

輸入:imCode-優(yōu)化前中間代碼.

輸出:optimisedIM-優(yōu)化后中間代碼;tabLab2addr;conTable;labTable.

代碼優(yōu)化對(duì)實(shí)現(xiàn)程序連續(xù)可微分執(zhí)行、建模和訓(xùn)練有重要意義.第3節(jié)介紹了程序在dAM上的執(zhí)行被描述為在某個(gè)連續(xù)狀態(tài)空間中的連續(xù)狀態(tài)轉(zhuǎn)換,這顯然適合以RNN為基礎(chǔ)建模.RNN有一個(gè)問題是,如果步驟過多,會(huì)顯著降低訓(xùn)練效果和效率.因此,把以指令字為單位轉(zhuǎn)換為以塊為單位的單步執(zhí)行能顯著減少遷移步數(shù),相當(dāng)于通過壓縮狀態(tài)轉(zhuǎn)換序列長(zhǎng)度顯著提升訓(xùn)練效果和效率.中間代碼將地址空間轉(zhuǎn)換為線性平鋪的連續(xù)編號(hào)、常量和標(biāo)簽跳轉(zhuǎn)編碼為連續(xù)的整數(shù)編號(hào),這些優(yōu)化處理為基于神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)訓(xùn)練建模提供了便利.

圖4是中間代碼優(yōu)化結(jié)果示意圖,優(yōu)化后的代碼以不同大小的基本塊組織,并以塊為單位編址構(gòu)成線性平鋪代碼地址空間,每個(gè)塊都以顯式的控制轉(zhuǎn)移指令結(jié)尾,如果沒有,則在尾部插入step;程序以塊為單位逐步(塊)執(zhí)行,如果碰到標(biāo)簽跳轉(zhuǎn)指令,則按照標(biāo)簽?zāi)繕?biāo)執(zhí)行跳轉(zhuǎn),標(biāo)簽按照第1遍優(yōu)化時(shí)分配的連續(xù)整數(shù)編碼命名,并按照第4遍優(yōu)化時(shí)生成的標(biāo)簽地址對(duì)照表tabLab2addr查找在代碼空間的實(shí)際地址.

Fig.4 Intermediate code optimization圖4 中間代碼優(yōu)化

4.3 程序匯編

本節(jié)主要介紹對(duì)優(yōu)化后的中間代碼塊做進(jìn)一步匯編處理,匯編處理就是為每個(gè)代碼塊轉(zhuǎn)換為一個(gè)可直接操作可微分狀態(tài)機(jī)狀態(tài)的函數(shù),這個(gè)函數(shù)就是中間代碼塊對(duì)應(yīng)的匯編代碼,因此,塊經(jīng)過匯編處理后可以在運(yùn)行階段直接操作dAM運(yùn)行并生成計(jì)算圖.

每個(gè)block塊或nc匯編代碼包括兩個(gè)部分用于執(zhí)行時(shí)的兩個(gè)階段.

· 第1階段是在符號(hào)狀態(tài)機(jī)上以符號(hào)執(zhí)行的方式對(duì)中間代碼代碼塊做化簡(jiǎn),形成用符號(hào)變量、符號(hào)棧表示的塊代碼執(zhí)行結(jié)果.因?yàn)榉?hào)執(zhí)行時(shí)基于符號(hào)變量做計(jì)算,因此不依賴棧和變量的具體值,只需為每個(gè)塊提供一個(gè)初始態(tài)的符號(hào)狀態(tài)機(jī)做操作參數(shù),不需要考慮塊序列狀態(tài)依賴、狀態(tài)傳遞等問題.符號(hào)執(zhí)行取得的符號(hào)化簡(jiǎn)結(jié)果與狀態(tài)無(wú)關(guān),一次執(zhí)行永遠(yuǎn)有效,所以只在中間代碼塊首次被訪問時(shí)執(zhí)行一次并可復(fù)用;

· 第 2階段在連續(xù)可微分抽象機(jī)上求值:首先需要?jiǎng)?chuàng)建分配一個(gè)可微分抽象機(jī),該抽象機(jī)除了提供基本操作、指令集等連續(xù)可微分實(shí)現(xiàn),還需要分配、初始化和管理各狀態(tài)組件,包括數(shù)據(jù)棧、返回棧、棧指針、Pc指針、代碼詞匯表、代碼矩陣、標(biāo)簽地址映射表、常量編碼表等,其中,詞匯表和代碼矩陣是中間代碼優(yōu)化并經(jīng)過匯編處理后的代碼字,代碼矩陣是代碼編號(hào)one-hot表示;可微分抽象機(jī)創(chuàng)建并初始化后,便構(gòu)成狀態(tài)機(jī)的初始狀態(tài),中間代碼在這個(gè)初始狀態(tài)基礎(chǔ)上逐步執(zhí)行,逐步執(zhí)行并不意味著一直順序執(zhí)行,比如碰到分支跳轉(zhuǎn)指令會(huì)改變控制流.

神經(jīng)網(wǎng)絡(luò)組件(nc)的匯編處理相對(duì)要復(fù)雜一些,nc塊包括nc.type和nc.value兩個(gè)部分,vaule包括dec,enc,transforms和label這4個(gè)部分,前3個(gè)需要專門處理.生成dec的匯編處理結(jié)果,需要把dec按照項(xiàng)目循環(huán)展開處理,算法8是生成dec的匯編代碼指令字算法流程概要結(jié)構(gòu),算法9是為相應(yīng)enc編碼部分生成匯編代碼的算法概要結(jié)構(gòu).

算法8.dec2decAsse(dec).

輸入:dec-神經(jīng)網(wǎng)絡(luò)組件(nc)的值的dec解碼部分,即中間代碼塊條目列表.

輸出:decAsse-匯編處理后的指令字結(jié)構(gòu).

算法9.enc2encAsse(enc,transforms,outputDim).

輸入:enc-網(wǎng)絡(luò)組件(nc)值的enc狀態(tài)編碼部分;transforms-狀態(tài)轉(zhuǎn)換函數(shù)列表;outputDim-編碼輸出維度.

輸出:encAsse-匯編處理后的指令字結(jié)構(gòu).

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

第1步創(chuàng)建連續(xù)可微分抽象機(jī)dAM,并初始化,包括匯編后的詞匯表vocab、代碼矩陣、常量編碼表、標(biāo)簽地址映射表、PC指針初始指向代碼地址0、新建返回棧并初始化為干凈狀態(tài)、數(shù)據(jù)棧和數(shù)據(jù)棧指針則由占位符變量初始化,用來接收訓(xùn)練樣例輸入.dAM對(duì)象包含了指令集實(shí)現(xiàn)函數(shù)和抽象機(jī)當(dāng)前完整狀態(tài),初始dAM即初始狀態(tài)(用Sdam_init表示).程序在dAM上一次執(zhí)行軌跡就是由從初始狀態(tài)出發(fā)的狀態(tài)列表exeTrace=[Sdam_init,Sdam_1,Sdam_2,...,Sdam_n],初始值[Sdam_init],每個(gè)狀態(tài)Sdam_i都是在前一個(gè)狀態(tài)上執(zhí)行某個(gè)代碼塊匯編函數(shù)結(jié)果.顯然,不同的初始狀態(tài)可能會(huì)產(chǎn)生不同的執(zhí)行軌跡,包括導(dǎo)致PC序列可能存在差異.

程序的可微分執(zhí)行模型:創(chuàng)建Sdam_init,然后在Sdam_init上繼續(xù)執(zhí)行n步,n是針對(duì)程序特點(diǎn)和輸入規(guī)模計(jì)算的執(zhí)行步數(shù),所以程序的執(zhí)行模型是一個(gè)RNN模型,該RNN模型在時(shí)間序列上展開后由n步組成,而每一步執(zhí)行包括兩個(gè)動(dòng)作.

· 第1個(gè)動(dòng)作是根據(jù)Pc向量從代碼矩陣中做指令尋址,其連續(xù)可微分矩陣計(jì)算可描述為公式(4).

其中,Code是匯編代碼塊編號(hào)的one-hot代碼矩陣;Pc是one-hot表示程序指針向量,訓(xùn)練期間,其分量是代碼分布權(quán)重;codesize是代碼包含的代碼塊個(gè)數(shù),或者匯編后詞匯表指令字個(gè)數(shù);Csel_w是指令尋址權(quán)重分布,在銳化處理或者訓(xùn)練穩(wěn)定后,Csel_w精確選取單個(gè)匯編指令.

· 第2個(gè)動(dòng)作是基于Csel_w選擇指令執(zhí)行,該動(dòng)作有兩種實(shí)現(xiàn)方式:

? 方法1是執(zhí)行所有代碼塊,然后按照Csel_w計(jì)算attention權(quán)重和,可描述為公式(5).

其中,Scurrent是當(dāng)前狀態(tài);RUN(Code,Scurrent)表示在Scurrent狀態(tài)下分別執(zhí)行代碼Code的每個(gè)匯編后指令,一共codesize次,每個(gè)執(zhí)行結(jié)果得到一個(gè)新狀態(tài),所有新狀態(tài)構(gòu)成結(jié)果狀態(tài)向量,然后以Csel_w取結(jié)果向量權(quán)重和就是本次單步執(zhí)行的結(jié)果;

? 方法2是對(duì)Csel_w做銳化處理,基于銳化結(jié)果選定一條指令執(zhí)行并改變可微分抽象機(jī)狀態(tài),可描述為公式(6).

其中,sharpen函數(shù)對(duì)Csel_w做銳化處理,得到一個(gè)one-hot向量,該one-hot向量與Code矩陣乘法取出唯一的指令編號(hào);然后,該指令在當(dāng)前狀態(tài)Scurrent下執(zhí)行的結(jié)果就是本次單步執(zhí)行的結(jié)果.

理論上,兩種方法都是可行的,但銳化處理因?yàn)椴恍枰看螆?zhí)行所有指令字,所以效率更高.

從初始狀態(tài)Sdam_init開始,每執(zhí)行一步產(chǎn)生下一個(gè)狀態(tài),這些狀態(tài)最終形成一個(gè)完整的狀態(tài)遷移軌跡.從公式(4)～公式(6)可知,執(zhí)行過程中,根據(jù)Scurrent.Pc以連續(xù)可微分方式做指令尋址,根據(jù)指令尋址選擇匯編指令函數(shù)做連續(xù)可微分執(zhí)行,并基于Scurrent和執(zhí)行結(jié)果更新生成下一個(gè)狀態(tài)Snext,其中包括Snext.Pc,Snext.DataStack,Snext.Pd等屬性,因此,逐步執(zhí)行生成n步執(zhí)行軌跡的過程,就是生成程序的連續(xù)可微分計(jì)算圖表示的過程.

4.5 訓(xùn)練目標(biāo)函數(shù)

模型使用程序執(zhí)行軌跡的結(jié)束狀態(tài)進(jìn)行訓(xùn)練,中間狀態(tài)在訓(xùn)練模型時(shí)不需考慮,因此不需要像 NPI[2]那樣對(duì)執(zhí)行軌跡的每一步做標(biāo)注,因而顯著降低了訓(xùn)練數(shù)據(jù)的生成和標(biāo)注成本.表示訓(xùn)練樣本是初始狀態(tài),標(biāo)注目標(biāo)是結(jié)束狀態(tài);表示對(duì)應(yīng)于初始狀態(tài),在參數(shù)為θ的dAM模型上執(zhí)行n步后得到的狀態(tài).模型的訓(xùn)練目標(biāo)是對(duì)于所有的訓(xùn)練樣本i,求解使得y與差距最小的參數(shù)θ*:

每個(gè)狀態(tài)最多包括DataStack(D),Pd,ReturnStack(R),Pr,Heap(H)這5個(gè)狀態(tài)分量,所以公式(8)可分解為5個(gè)分量的和:

其中,H是交叉熵函數(shù).一般的,在具體算法場(chǎng)景,其損失函數(shù)不需要所有5個(gè)分量,本文的實(shí)驗(yàn)只用到Pd和D兩個(gè)分量,給定算法場(chǎng)景用不到的分量的交叉熵為 0,因此可在公式中去掉相應(yīng)交叉熵分量的計(jì)算.因?yàn)橄到y(tǒng)是連續(xù)可微分的,所以可以使用反向傳播算法訓(xùn)練優(yōu)化損失函數(shù).

5 實(shí)驗(yàn)分析

本節(jié)對(duì)dAMP系統(tǒng)做實(shí)驗(yàn)分析,首先給出同一個(gè)多位數(shù)加法算法的3種代碼實(shí)現(xiàn)實(shí)例,結(jié)合具體例子對(duì)比分析了 dAMP的代碼生成特性、實(shí)例選取的原因動(dòng)機(jī);然后以該算法的程序?yàn)槔?對(duì)模型的訓(xùn)練效果、訓(xùn)練過程中運(yùn)行時(shí)狀態(tài)對(duì)技術(shù)設(shè)計(jì)目標(biāo)正確性的反饋驗(yàn)證和模型復(fù)雜度進(jìn)行實(shí)驗(yàn)分析;最后對(duì)系統(tǒng)的性能進(jìn)行評(píng)估.

5.1 多位數(shù)初等加法算法

多位數(shù)初等加法運(yùn)算是由低位往高位移動(dòng)做單位數(shù)加法,每步單位數(shù)加法基本操是基于低位進(jìn)位、本位被加數(shù)和本位加數(shù)計(jì)算向高位的進(jìn)位和本位和,多位數(shù)加法是遞歸執(zhí)行單位數(shù)加法.該樣例的好處是問題簡(jiǎn)單,但包含了順序語(yǔ)句、分支控制、函數(shù)調(diào)用、遞歸等復(fù)雜程序結(jié)構(gòu)元素(顯然這些結(jié)構(gòu)足以表達(dá)其他廣泛、復(fù)雜的編程問題),因此方便進(jìn)行簡(jiǎn)單明了的多方面系統(tǒng)分析,又不失對(duì)dAMP全可微分模型編程能力驗(yàn)證,分支、函數(shù)調(diào)用、遞歸等控制結(jié)構(gòu)處理能力也是程序生成研究關(guān)鍵之一[2-4].

圖5給出了該多位數(shù)初等加法的類C語(yǔ)言偽代碼、Forth代碼以及與Forth實(shí)現(xiàn)相對(duì)應(yīng)的dAMP神經(jīng)網(wǎng)絡(luò)組件混合代碼的實(shí)現(xiàn).圖中黑體加粗代碼是計(jì)算進(jìn)位和計(jì)算本位和的代碼的3種對(duì)照實(shí)現(xiàn),其中,Forth代碼實(shí)現(xiàn)是確定性的,需20個(gè)word實(shí)現(xiàn),每個(gè)word是Forth的一行代碼(把20個(gè)word放在5行以節(jié)省空間);而dAMP實(shí)現(xiàn)則是不確定的,不需編寫完整算法,其中最復(fù)雜的每步計(jì)算進(jìn)位和本位和操作用待訓(xùn)練學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)組件代替,通過編寫框架主要提供2個(gè)編程經(jīng)驗(yàn)輸入(這是一個(gè)遞歸算法結(jié)構(gòu),每步計(jì)算進(jìn)位和本位和的取值范圍分別是0～1和0～9).

Fig.5 Elementary multidigit addition圖5 多位數(shù)初等加法

5.2 模型訓(xùn)練效果分析

· 模型可收斂性實(shí)驗(yàn)驗(yàn)證

可通過反向傳播算法訓(xùn)練優(yōu)化是模型的關(guān)鍵,第3節(jié)、第4節(jié)介紹dAMP實(shí)現(xiàn)時(shí),從理論上說明了dAMP是連續(xù)可微分的.圖6所示實(shí)驗(yàn)數(shù)據(jù)對(duì)此進(jìn)行了驗(yàn)證,該實(shí)驗(yàn)以一位加數(shù)、一位被加數(shù)和進(jìn)位的輸入輸出數(shù)據(jù)為訓(xùn)練樣例,以2位～4位(加數(shù)加被加數(shù)長(zhǎng)度共8位)整數(shù)加法構(gòu)建測(cè)試樣例.由圖6(a)可知在Loss穩(wěn)定收斂,訓(xùn)練約400步時(shí),Loss收斂到非常接近0;由圖6(b)可知,在模型訓(xùn)練超過400步時(shí),2位～4位數(shù)加法的測(cè)試準(zhǔn)確率達(dá)100%.因此,模型具有很好的收斂性.另外,我們測(cè)試了用1位數(shù)加法訓(xùn)練得到的模型做2位～34位整數(shù)加法,得到了100%的準(zhǔn)確率,所以模型具有很好的泛化能力.

Fig.6 Convergence of model training圖6 模型訓(xùn)練收斂情況

· 軌跡步數(shù)設(shè)置對(duì)訓(xùn)練的影響

第4.4節(jié)介紹了dAMP程序執(zhí)行模型是由n步狀態(tài)遷移構(gòu)成的exeTrace,因此設(shè)置合適的n對(duì)模型訓(xùn)練很關(guān)鍵.n的設(shè)置需參照中間代碼優(yōu)化后代碼塊個(gè)數(shù)和程序的輸入規(guī)模,比如,如圖7(a)所示,當(dāng)訓(xùn)練加法算法輸入規(guī)模為2時(shí),n=14左右效果最佳;當(dāng)n≥16時(shí),明顯增加訓(xùn)練步數(shù);當(dāng)n≤12時(shí),準(zhǔn)確率波動(dòng)很大.同時(shí),圖7(b)顯示,其Loss收斂很好.這種情況很可能是因n偏小造成過擬所致.

Fig.7 Effect of number of trace step on training圖7 軌跡步數(shù)對(duì)訓(xùn)練的影響

5.3 運(yùn)行時(shí)執(zhí)行過程驗(yàn)證

驗(yàn)證方法是記錄加法程序在dAMP上訓(xùn)練運(yùn)行時(shí)PC的值,分析在一個(gè)執(zhí)行軌跡周期中其值的變化是否符合預(yù)期.圖8(a)是PC的實(shí)際執(zhí)行軌跡,該軌跡取自2位數(shù)加法訓(xùn)練過程;圖8(b)給出了多位數(shù)加法程序經(jīng)過中間代碼優(yōu)化和匯編后的代碼塊以及以塊為基本執(zhí)行單位的程序控制轉(zhuǎn)移邏輯作為參照.從圖中可以看出,運(yùn)行時(shí)PC移動(dòng)軌跡完全符合預(yù)期,其中,虛框部分證明模型正確執(zhí)行了函數(shù)調(diào)用與遞歸,右上角最后兩步停留在 Halt指令不再轉(zhuǎn)移,說明程序執(zhí)行正常結(jié)束.該實(shí)驗(yàn)現(xiàn)象也說明,exeTrace設(shè)置為20步即可滿足要求.

Fig.8 Runtime PC-trace correctness verification圖8 運(yùn)行時(shí)PC軌跡正確性驗(yàn)證

5.4 模型復(fù)雜度分析

第4.4節(jié)給出了程序在dAMP上執(zhí)行模型是n步exeTrace,因此程序在dAM上執(zhí)行復(fù)雜度主要由n決定.以多位數(shù)加法為例,設(shè)加數(shù)(或被加數(shù))位數(shù)為m,則n=2+5m+2+2m+2=7m+6=O(m),即問題輸入規(guī)模的線性復(fù)雜度,該計(jì)算過程可參照?qǐng)D8運(yùn)行時(shí)軌跡.類似地,對(duì)于冒泡排序,其模型復(fù)雜度是O(n2),所以dAMP運(yùn)行時(shí)軌跡復(fù)雜度取決于算法框架本身.第 4.2節(jié)的中間代碼優(yōu)化將程序按照控制結(jié)構(gòu)分塊,將程序從逐指令粒度優(yōu)化到塊粒度執(zhí)行,從而有效提升執(zhí)行性能,但因?yàn)闆]有改變程序結(jié)構(gòu),因此不會(huì)達(dá)到改變復(fù)雜度.另外,將梯度計(jì)算放在程序執(zhí)行結(jié)尾而不是執(zhí)行過程中的每個(gè)狀態(tài)遷移,也是性能優(yōu)化的一個(gè)方面.顯然,dAMP混合模型能夠利用nc組件消除條件分支等控制結(jié)構(gòu),但進(jìn)一步,對(duì)于給定問題如冒泡排序,是否能設(shè)計(jì)影響程序循環(huán)或遞歸結(jié)構(gòu)從而達(dá)到優(yōu)化算法復(fù)雜度,還有待未來做專門探討.

5.5 性能評(píng)估

dAMP開發(fā)環(huán)境為Python3.5.2,NumPy[10]1.14.5,TensorFlow[11]1.10.0 CPU版,Ubuntu 16.04 X86_64,8核心Intel Xeon E5-2407處理器,64G內(nèi)存,測(cè)試環(huán)境同開發(fā)環(huán)境.性能評(píng)估選用有代表性的算術(shù)操作和關(guān)系操作,實(shí)驗(yàn)方法為隨機(jī)生成50組形狀為(1,10)的操作數(shù),統(tǒng)計(jì)每個(gè)操作執(zhí)行50次運(yùn)算的總時(shí)間,單位為s.Performance數(shù)值越小,表示性能越好.為了對(duì)dAMP性能有一個(gè)橫向的評(píng)估,實(shí)驗(yàn)同時(shí)選取了TensorFlow(TF)功能相近的操作,使用相同的數(shù)據(jù)做測(cè)試對(duì)照.圖9(a)是算術(shù)操作性能測(cè)評(píng)結(jié)果,對(duì)照 TF.add、TF.subtract、TF.multiply、TF.div,圖9(b)是關(guān)系操作測(cè)評(píng)結(jié)果,對(duì)照 TF.equal、TF.greater、TF.less、TF.greater_equal、TF.less_equal、TF.not_equal.測(cè)試數(shù)據(jù)表明,dAMP表現(xiàn)出很好的性能.這里,性能測(cè)試未做任何專門優(yōu)化,如果使用 GPU加速,則理論上性能還會(huì)有明顯提升.

Fig.9 Performance of fundmental operations圖9 基礎(chǔ)操作性能

6 相關(guān)工作

機(jī)器編程相關(guān)研究始于20世紀(jì)70年代[1],經(jīng)過近50年的發(fā)展取得了長(zhǎng)足進(jìn)步,但是其通用能力、泛化能力、程序覆蓋能力仍明顯不足,因此限制了實(shí)際應(yīng)用.主要相關(guān)性研究.

· 類自然語(yǔ)言研究方法

該方法將自然語(yǔ)言處理的研究方法遷移到編程語(yǔ)言領(lǐng)域[12-14].相關(guān)工作集中在代碼注釋、論壇等自然語(yǔ)言語(yǔ)料到代碼關(guān)鍵字、標(biāo)識(shí)符等的對(duì)照關(guān)系處理上,對(duì)代碼自身信息的直接處理上表現(xiàn)不足.

· 歸納式程序合成方法

該方法將程序生成定義為搜索問題.所有程序樣例的全集構(gòu)成一個(gè)離散程序空間,程序生成的過程就是通過觀察輸入輸出樣例數(shù)據(jù)特征,在程序空間歸納搜索與樣例數(shù)據(jù)行為一致的程序,受程序合成研究方法習(xí)慣于用規(guī)則和抽象提高問題處理效果啟發(fā)[15-17],本文提出在更具抽象層設(shè)計(jì)連續(xù)可微分抽象機(jī)的混合編程的程序處理思路.但是不同于歸納式程序合成把程序生成定義為在離散空間搜索,本文則是基于連續(xù)可微分優(yōu)化的更通用的一種方法.

· 基于連接的神經(jīng)網(wǎng)絡(luò)方法

該方法為程序處理尋找一個(gè)連續(xù)空間表示,將問題看成是在連續(xù)空間待學(xué)習(xí)參數(shù)和一套可微分規(guī)則組成的系統(tǒng),程序生成問題被轉(zhuǎn)換為在連續(xù)空間采用可微分優(yōu)化方法來逼近一個(gè)解,這是本文最相關(guān)的研究方法.典型的 NPI[2]使用神經(jīng)網(wǎng)絡(luò)從程序執(zhí)行軌跡中學(xué)習(xí)預(yù)測(cè)下一步調(diào)用的子指令,非完全可微分,依賴于收集高成本程序執(zhí)行軌跡,本質(zhì)上是算法編碼而不是生成.NTM[3]通過注意力機(jī)制將外部存儲(chǔ)與神經(jīng)網(wǎng)絡(luò)內(nèi)部存儲(chǔ)耦合,擴(kuò)展了神經(jīng)網(wǎng)絡(luò)的記憶容量,實(shí)現(xiàn)了全微分方式訪問外部緩存,為實(shí)現(xiàn) dAMP的連續(xù)可微分棧訪問操作提供了借鑒.但NTM無(wú)指令集,因此無(wú)法實(shí)現(xiàn)可微分編程控制.Forth[9]提出了一種forth編程語(yǔ)言可微分解釋器的初步實(shí)現(xiàn)方法但不完整,有很好的借鑒意義.與之相比,本文提出并驗(yàn)證了一種在更具抽象層解決程序生成問題的混合編程研究思路,給出了更完整、成熟、嚴(yán)謹(jǐn)?shù)膶?shí)現(xiàn)框架,對(duì)PC尋址銳化顯著提升效率,提出驗(yàn)證了多種訓(xùn)練目標(biāo)函數(shù)以適應(yīng)不同問題,提出并分析了如何合理設(shè)置執(zhí)行軌跡步數(shù)、對(duì)關(guān)鍵學(xué)習(xí)機(jī)理進(jìn)行了理論和實(shí)驗(yàn)分析.Deepcoder[4]提出了一種基于神經(jīng)網(wǎng)絡(luò)在給定的 DSL語(yǔ)言下計(jì)算指令頻度的方法,本質(zhì)上是結(jié)合神經(jīng)網(wǎng)絡(luò)的歸納式程序合成方法.

7 結(jié)束語(yǔ)

本文提出在抽象層研究程序自動(dòng)生成問題的一種思路,給出其驗(yàn)證系統(tǒng) dAMP,實(shí)現(xiàn)了一種可無(wú)縫結(jié)合高級(jí)過程化編程語(yǔ)言與神經(jīng)網(wǎng)絡(luò)組件的混合編程模型,給出了包含順序塊、條件分支、函數(shù)調(diào)用、遞歸等常規(guī)復(fù)雜程序結(jié)構(gòu)元素和神經(jīng)網(wǎng)絡(luò)組件結(jié)構(gòu)的程序樣例實(shí)驗(yàn)分析.顯然,這些結(jié)構(gòu)具備表達(dá)其他更廣泛復(fù)雜程序的能力,完整嚴(yán)謹(jǐn)?shù)募夹g(shù)設(shè)計(jì)和實(shí)驗(yàn)分析表明,通過抽象層次提升,這種基于可微分抽象、支持表達(dá)復(fù)雜問題程序結(jié)構(gòu)的混合編程模型在理論和技術(shù)上是可行的.與已有的程序生成方法相比,本文所提方法具有更靈活的可微分編程控制能力、良好的程序自動(dòng)生成與泛化能力、優(yōu)秀的性能.

原型驗(yàn)證在理論和技術(shù)上可行只是研究工作的一個(gè)方面,最終希望走向廣泛的應(yīng)用,而應(yīng)用不僅關(guān)心技術(shù)可行性,比如首先可能還關(guān)心用戶接口,因此我們認(rèn)為,下一步有必要對(duì)以下幾個(gè)工作進(jìn)行探討.

1)通過擴(kuò)展C語(yǔ)言子集,設(shè)計(jì)支持神經(jīng)網(wǎng)絡(luò)混合編程的類C語(yǔ)法作前端,基于本文的技術(shù)作為后端支持,從而更便于程序員編程思想表達(dá),發(fā)揮其編程創(chuàng)造性.

2)在前一個(gè)工作基礎(chǔ)上,設(shè)計(jì)豐富的神經(jīng)網(wǎng)絡(luò)混合編程語(yǔ)言原語(yǔ),以C語(yǔ)言、Java等語(yǔ)言為例,豐富的編程原語(yǔ)對(duì)編程模型走向?qū)嶋H應(yīng)用有重要意義,dAMP全可微分特性支持嵌入包括神經(jīng)網(wǎng)絡(luò)在內(nèi)任何可微組件,因此理論上可把典型的神經(jīng)網(wǎng)絡(luò)模型(如 seq2seq,encoder-decoder,CNN,GAN 等)甚至非神經(jīng)網(wǎng)絡(luò)但可微分模型設(shè)計(jì)為該編程模型原語(yǔ)級(jí)支持,以增強(qiáng)其編程表達(dá)能力.

3)全面探討或反向總結(jié)該可微分混合編程模型的應(yīng)用場(chǎng)景適應(yīng)性或編程潛力,參照J(rèn)ava等大多數(shù)編程模型發(fā)展經(jīng)驗(yàn),這不是一個(gè)完全可正向評(píng)估的純技術(shù)問題,往往依賴于Java用戶生態(tài)的編程創(chuàng)造性的反向反饋,即具有開放性和創(chuàng)造性.

在正向上,因?yàn)橹С重S富復(fù)雜的程序結(jié)構(gòu)以及可微分混合編程特性,因此從技術(shù)上顯然有能力表達(dá)廣泛復(fù)雜的程序,并因新語(yǔ)言結(jié)構(gòu)的融合而引入新編程表達(dá)能力.如傳統(tǒng)C程序是確定性的,因此主要用于編寫完整的程序,求解完全明確的問題之類場(chǎng)景,而該模型特性則支持以傳統(tǒng)過程化編程方式在確定性框架下引入非確定性編程支持,而非確定性局部又可借助數(shù)據(jù)驅(qū)動(dòng)自學(xué)習(xí)生成,因此適合但不限于“不完全明確但有數(shù)據(jù)可依賴的問題編程”或者出于降低編程難度或提高編程效率的“非完整編程”.但在編程便利性應(yīng)用上,還有賴于下一步諸如類C語(yǔ)法前端和原語(yǔ)豐富性設(shè)計(jì)等工作,從而更好地激發(fā)程序員利用模型特性的編程創(chuàng)造性發(fā)揮.