可微分抽象機混合編程系統?

周 鵬,武延軍,趙 琛

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

2(中國科學院大學,北京 100049)

自計算機誕生以來,實現幫助計算機自動編寫程序的系統一直是人工智能研究者所追求的重要目標之一,相關研究最早可追溯到1971年[1].機器編程的研究總體分為類自然語言代碼挖掘和代碼生成兩大類,代碼生成的研究又可劃分為程序空間搜索和連續可微分優化法.近年來,隨著深度學習的興起,結合神經網絡以連續可微分優化理論為基礎構建編程模型的研究也成為一個研究熱點[2-4].總體而言,從輸入素材角度,可將這些神經網絡類編程模型分為基于程序執行軌跡樣例的方法[2]和基于程序輸入輸出數據樣例的方法[3,4].

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

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

本文的主要貢獻:1) 提出了在抽象層研究程序自動生成問題的一種思路,并給出該思路的一個完整驗證系統dAMP;2) dAMP給出了一種支持經驗輸入、編程語言與神經網絡組件元素相結合的混合編程模型,并給出其設計實現的關鍵技術;3) 給出了豐富的實驗驗證,對dAMP程序自動生成的學習機制做了深入的實驗分析.

本文第1節對dAMP框架做一個整體介紹.第2節介紹編程語言模型,包括理解本文需要預備的編程語言概念、語言運行模型知識.第3節介紹連續可微分抽象機實現方法.第4節詳細展開實現dAMP的關鍵技術.第5節實驗驗證并對模型的學習機制做深入的實驗分析.第6節介紹相關性工作.第7節是結束語.

1 整體架構

可微分抽象機混合編程系統總體可分為源程序、編譯與處理、連續可微分抽象機和計算圖這4個主要組成部分,如圖1所示.

Fig.1 dAMP architecture圖1 dAMP整體架構

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

(1) 源程序

使用Forth高級編程語言和神經網絡組件元素(簡稱nc)混合編寫的程序,與常規編程需要編寫程序的完整細節不同,dAMP編程程序員可以基于編程經驗只描述程序的框架,而把一些細節用待學習的神經網絡組件(nc)占位,通過框架和nc結構提供經驗信息.

(2) 編譯與處理

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

(3) 連續可微分抽象機

連續可微分抽象機dAM以代碼矩陣和訓練樣本的輸入部分?x為輸入,將程序以逐步的連續狀態轉換方式解釋執行,其執行結果是生成對應的程序計算圖表示.dAM 是使用矩陣代數對 Forth語言執行抽象機模型的連續可微分表示,主要包括狀態操作和指令集的連續可微分實現.因為和神經網絡一樣都使用矩陣代數實現形式,因此在dAM上,高級編程語言元素與神經網絡單元元素能夠無縫結合.

(4) 計算圖

計算圖是程序生成模型的最終表示,在dAM執行代碼矩陣期間構建生成,主要包括程序遞歸執行、學習目標loss損失函數、訓練函數train這3個部分,其中,程序遞歸執行邏輯表達為遞歸訪問抽象機狀態空間的RNN網絡,訓練期間訓練樣本的標記部分?y為輸入.

2 編程語言模型介紹

本節介紹文中用到的預備知識編程語言模型,主要包括Forth語言元素、語言運行模型.其中,語言元素只介紹與文中樣例代碼相關的內容,如果想詳細了解語言細節,請參考文獻[7].

2.1 語言執行模型

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

Fig.2 Forth VM圖2 Forth虛擬機模型

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

Fig.3 Example of expression evaluation圖3 表達式求值示例

2.2 部分語言元素

Forth將指令或函數稱為 word,它是一種可擴展語言,支持函數定義(subroutine)和函數調用,新定義的函數又稱新word,可以像內置word一樣被使用,因此,定義新函數的同時也擴展了Forth語言.表1是相關word功能說明,詳細可參考文獻[7].

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

3 可微分抽象機實現方法

由第2.1節Forth語言執行模型可知,其程序執行,既可看成指令執行序列,又可從公理語義的角度忽略指令的實現細節,只評估指令執行后對 Forth狀態單元的改變.這種完全以狀態的遷移來描述程序執行的方式,我們稱之為抽象機模型AM.Forth程序在AM上的指令執行可以表示為狀態的遷移:

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

實現連續可微分抽象機的方法原理.

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

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

4 可微分抽象機混合編程實現關鍵技術

本節詳細說明實現dAMP的關鍵技術,是本文的重點章節.

4.1 源程序到中間代碼編譯

· 詞法分析

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

· 語法分析(AST生成)

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

其中,〈nc〉條目用于產生內嵌神經網絡組件,以實現對用神經網絡組件與Forth元素混合編寫的源程序進行語法分析.為了簡單清晰,這里省略了一些簡單的term元素和與ifthenelse類似的結構(如while)的產生式.

· 中間代碼生成

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

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

輸入:ast-抽象語法樹;labelAllocator-分配管理不重名的跳轉標簽.

輸出:imCode-中間代碼.

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

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

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

神經網絡組件元素nc包括(encoder,transforms,decoder)這3個部分,其功能分別是狀態編碼、狀態轉換、狀態解碼產生狀態操作動作,這三者構成一個完整的帶有可學習參數的神經網絡組件,并可編程客制.

中間代碼指令功能單一、支持機械化微碼求值實現,算法1的中間代碼生成過程將函數定義、函數調用、ifthenelse等復雜結構轉換為基本中間指令序列,因此,將源程序轉換為中間代碼后非常適合轉換為逐步的連續可微分執行,即適合在dAM上運行,而混合編程語言語法特點是適合高效創作復雜源程序.

4.2 中間代碼優化

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

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

算法2.labRenumber(imCode).

輸入:imCode-跳轉標簽重編號前中間代碼.

輸出:labRenumberedIMCode-標簽重編號后中間代碼;labTable-標簽重編碼表.

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

算法3.conRenumber(imCode).

輸入:imCode-常量重編號前中間代碼.

輸出:conRenumberedIMCode-常量重編號后中間代碼;conTable-常量重編碼表.

算法4.blockPartion(imCode).

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

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

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

算法5將目標標簽轉換為目標地址,建立標簽到地址的映射表,并刪除標簽定義指令.

算法5.lab2addr(imBlocks).

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

輸出:addrIM-目的標簽轉換為目的地址后的中間代碼塊;tabLab2addr-標簽地址對照表.

算法6遍歷代碼塊,為沒有以控制轉移指令結尾的代碼塊追加插入step指令,從而確保每個代碼塊執行結束時都更新PC,即保證程序持續向前推進執行.

算法6.insertStepctl(addrIM).

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

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

算法7是中間代碼優化的整個流程,經過5次遍歷,生成最終在dAM上執行的優化代碼.代碼優化是一個復雜但關鍵的過程,代碼優化不僅能顯著提高訓練學習效率,也為實現結合神經網絡的深度學習模型提供了基礎.

算法7.optimiseIM(imCode).

輸入:imCode-優化前中間代碼.

輸出:optimisedIM-優化后中間代碼;tabLab2addr;conTable;labTable.

代碼優化對實現程序連續可微分執行、建模和訓練有重要意義.第3節介紹了程序在dAM上的執行被描述為在某個連續狀態空間中的連續狀態轉換,這顯然適合以RNN為基礎建模.RNN有一個問題是,如果步驟過多,會顯著降低訓練效果和效率.因此,把以指令字為單位轉換為以塊為單位的單步執行能顯著減少遷移步數,相當于通過壓縮狀態轉換序列長度顯著提升訓練效果和效率.中間代碼將地址空間轉換為線性平鋪的連續編號、常量和標簽跳轉編碼為連續的整數編號,這些優化處理為基于神經網絡的預測訓練建模提供了便利.

圖4是中間代碼優化結果示意圖,優化后的代碼以不同大小的基本塊組織,并以塊為單位編址構成線性平鋪代碼地址空間,每個塊都以顯式的控制轉移指令結尾,如果沒有,則在尾部插入step;程序以塊為單位逐步(塊)執行,如果碰到標簽跳轉指令,則按照標簽目標執行跳轉,標簽按照第1遍優化時分配的連續整數編碼命名,并按照第4遍優化時生成的標簽地址對照表tabLab2addr查找在代碼空間的實際地址.

Fig.4 Intermediate code optimization圖4 中間代碼優化

4.3 程序匯編

本節主要介紹對優化后的中間代碼塊做進一步匯編處理,匯編處理就是為每個代碼塊轉換為一個可直接操作可微分狀態機狀態的函數,這個函數就是中間代碼塊對應的匯編代碼,因此,塊經過匯編處理后可以在運行階段直接操作dAM運行并生成計算圖.

每個block塊或nc匯編代碼包括兩個部分用于執行時的兩個階段.

· 第1階段是在符號狀態機上以符號執行的方式對中間代碼代碼塊做化簡,形成用符號變量、符號棧表示的塊代碼執行結果.因為符號執行時基于符號變量做計算,因此不依賴棧和變量的具體值,只需為每個塊提供一個初始態的符號狀態機做操作參數,不需要考慮塊序列狀態依賴、狀態傳遞等問題.符號執行取得的符號化簡結果與狀態無關,一次執行永遠有效,所以只在中間代碼塊首次被訪問時執行一次并可復用;

· 第 2階段在連續可微分抽象機上求值:首先需要創建分配一個可微分抽象機,該抽象機除了提供基本操作、指令集等連續可微分實現,還需要分配、初始化和管理各狀態組件,包括數據棧、返回棧、棧指針、Pc指針、代碼詞匯表、代碼矩陣、標簽地址映射表、常量編碼表等,其中,詞匯表和代碼矩陣是中間代碼優化并經過匯編處理后的代碼字,代碼矩陣是代碼編號one-hot表示;可微分抽象機創建并初始化后,便構成狀態機的初始狀態,中間代碼在這個初始狀態基礎上逐步執行,逐步執行并不意味著一直順序執行,比如碰到分支跳轉指令會改變控制流.

神經網絡組件(nc)的匯編處理相對要復雜一些,nc塊包括nc.type和nc.value兩個部分,vaule包括dec,enc,transforms和label這4個部分,前3個需要專門處理.生成dec的匯編處理結果,需要把dec按照項目循環展開處理,算法8是生成dec的匯編代碼指令字算法流程概要結構,算法9是為相應enc編碼部分生成匯編代碼的算法概要結構.

算法8.dec2decAsse(dec).

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

輸出:decAsse-匯編處理后的指令字結構.

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

輸入:enc-網絡組件(nc)值的enc狀態編碼部分;transforms-狀態轉換函數列表;outputDim-編碼輸出維度.

輸出:encAsse-匯編處理后的指令字結構.

4.4 程序可微分執行模型

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

程序的可微分執行模型:創建Sdam_init,然后在Sdam_init上繼續執行n步,n是針對程序特點和輸入規模計算的執行步數,所以程序的執行模型是一個RNN模型,該RNN模型在時間序列上展開后由n步組成,而每一步執行包括兩個動作.

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

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

· 第2個動作是基于Csel_w選擇指令執行,該動作有兩種實現方式:

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

其中,Scurrent是當前狀態;RUN(Code,Scurrent)表示在Scurrent狀態下分別執行代碼Code的每個匯編后指令,一共codesize次,每個執行結果得到一個新狀態,所有新狀態構成結果狀態向量,然后以Csel_w取結果向量權重和就是本次單步執行的結果;

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

其中,sharpen函數對Csel_w做銳化處理,得到一個one-hot向量,該one-hot向量與Code矩陣乘法取出唯一的指令編號;然后,該指令在當前狀態Scurrent下執行的結果就是本次單步執行的結果.

理論上,兩種方法都是可行的,但銳化處理因為不需要每次執行所有指令字,所以效率更高.

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

4.5 訓練目標函數

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

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

其中,H是交叉熵函數.一般的,在具體算法場景,其損失函數不需要所有5個分量,本文的實驗只用到Pd和D兩個分量,給定算法場景用不到的分量的交叉熵為 0,因此可在公式中去掉相應交叉熵分量的計算.因為系統是連續可微分的,所以可以使用反向傳播算法訓練優化損失函數.

5 實驗分析

本節對dAMP系統做實驗分析,首先給出同一個多位數加法算法的3種代碼實現實例,結合具體例子對比分析了 dAMP的代碼生成特性、實例選取的原因動機;然后以該算法的程序為例,對模型的訓練效果、訓練過程中運行時狀態對技術設計目標正確性的反饋驗證和模型復雜度進行實驗分析;最后對系統的性能進行評估.

5.1 多位數初等加法算法

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

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

Fig.5 Elementary multidigit addition圖5 多位數初等加法

5.2 模型訓練效果分析

· 模型可收斂性實驗驗證

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

Fig.6 Convergence of model training圖6 模型訓練收斂情況

· 軌跡步數設置對訓練的影響

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

Fig.7 Effect of number of trace step on training圖7 軌跡步數對訓練的影響

5.3 運行時執行過程驗證

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

Fig.8 Runtime PC-trace correctness verification圖8 運行時PC軌跡正確性驗證

5.4 模型復雜度分析

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

5.5 性能評估

dAMP開發環境為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內存,測試環境同開發環境.性能評估選用有代表性的算術操作和關系操作,實驗方法為隨機生成50組形狀為(1,10)的操作數,統計每個操作執行50次運算的總時間,單位為s.Performance數值越小,表示性能越好.為了對dAMP性能有一個橫向的評估,實驗同時選取了TensorFlow(TF)功能相近的操作,使用相同的數據做測試對照.圖9(a)是算術操作性能測評結果,對照 TF.add、TF.subtract、TF.multiply、TF.div,圖9(b)是關系操作測評結果,對照 TF.equal、TF.greater、TF.less、TF.greater_equal、TF.less_equal、TF.not_equal.測試數據表明,dAMP表現出很好的性能.這里,性能測試未做任何專門優化,如果使用 GPU加速,則理論上性能還會有明顯提升.

Fig.9 Performance of fundmental operations圖9 基礎操作性能

6 相關工作

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

· 類自然語言研究方法

該方法將自然語言處理的研究方法遷移到編程語言領域[12-14].相關工作集中在代碼注釋、論壇等自然語言語料到代碼關鍵字、標識符等的對照關系處理上,對代碼自身信息的直接處理上表現不足.

· 歸納式程序合成方法

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

· 基于連接的神經網絡方法

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

7 結束語

本文提出在抽象層研究程序自動生成問題的一種思路,給出其驗證系統 dAMP,實現了一種可無縫結合高級過程化編程語言與神經網絡組件的混合編程模型,給出了包含順序塊、條件分支、函數調用、遞歸等常規復雜程序結構元素和神經網絡組件結構的程序樣例實驗分析.顯然,這些結構具備表達其他更廣泛復雜程序的能力,完整嚴謹的技術設計和實驗分析表明,通過抽象層次提升,這種基于可微分抽象、支持表達復雜問題程序結構的混合編程模型在理論和技術上是可行的.與已有的程序生成方法相比,本文所提方法具有更靈活的可微分編程控制能力、良好的程序自動生成與泛化能力、優秀的性能.

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

1)通過擴展C語言子集,設計支持神經網絡混合編程的類C語法作前端,基于本文的技術作為后端支持,從而更便于程序員編程思想表達,發揮其編程創造性.

2)在前一個工作基礎上,設計豐富的神經網絡混合編程語言原語,以C語言、Java等語言為例,豐富的編程原語對編程模型走向實際應用有重要意義,dAMP全可微分特性支持嵌入包括神經網絡在內任何可微組件,因此理論上可把典型的神經網絡模型(如 seq2seq,encoder-decoder,CNN,GAN 等)甚至非神經網絡但可微分模型設計為該編程模型原語級支持,以增強其編程表達能力.

3)全面探討或反向總結該可微分混合編程模型的應用場景適應性或編程潛力,參照Java等大多數編程模型發展經驗,這不是一個完全可正向評估的純技術問題,往往依賴于Java用戶生態的編程創造性的反向反饋,即具有開放性和創造性.

在正向上,因為支持豐富復雜的程序結構以及可微分混合編程特性,因此從技術上顯然有能力表達廣泛復雜的程序,并因新語言結構的融合而引入新編程表達能力.如傳統C程序是確定性的,因此主要用于編寫完整的程序,求解完全明確的問題之類場景,而該模型特性則支持以傳統過程化編程方式在確定性框架下引入非確定性編程支持,而非確定性局部又可借助數據驅動自學習生成,因此適合但不限于“不完全明確但有數據可依賴的問題編程”或者出于降低編程難度或提高編程效率的“非完整編程”.但在編程便利性應用上,還有賴于下一步諸如類C語法前端和原語豐富性設計等工作,從而更好地激發程序員利用模型特性的編程創造性發揮.