基于深度學習的程序生成與補全技術研究進展?

胡 星,李 戈,劉 芳,金 芝

1(北京大學 信息科學技術學院,北京 100871)

2(高可信軟件技術教育部重點實驗室(北京大學),北京 100871)

如何有效地提高軟件開發的效率和質量,一直是軟件工程領域關心的問題.一直以來,許多研究者都通過改善軟件開發方法和運用技術手段來提高軟件開發的自動化水平.其中,程序自動生成技術被認為是提高軟件開發自動化程度和最終質量的重要方法,一直受到學術界和工業界的廣泛關注.程序自動生成技術指利用某些技術自動地為軟件生成源代碼,達到根據用戶的需求機器自動編程的目的.該技術極大程度地減輕了程序員的開發負擔,使得程序員可以更加關注于程序的設計工作.

目前,程序自動生成方法主要通過兩種方式實現:程序生成和代碼補全.程序生成和代碼補全是程序綜合問題的兩個分支,它們從不同程度上輔助甚至代替程序員的開發工作.代碼補全技術是最常見的程序自動生成技術,是現代集成開發環境(integrated development environment,簡稱 IDE)的重要組成部分.代碼補全技術有效地幫助程序員預測代碼的類名、方法名、關鍵字等,提高了程序開發的效率,并減少了編碼過程中的拼寫錯誤.目前,代碼補全工具通常對代碼進行靜態分析,用于補全的候選項通常按字母順序排列.程序生成要求根據用戶給定的需求自動構建程序,該技術在一定程度上讓機器代替程序員編寫代碼的工作.傳統的程序生成方法要求程序員設計邏輯規約,使得機器可以根據這些邏輯規約自動生成源代碼.然而這些方法不僅對程序員的要求較高,而且生成的代碼往往功能比較單一,無法完成復雜的任務.

近年來,人工智能技術取得了長足的發展與進步,這一進步對軟件工程領域的研究形成了重要的促進.人工智能的方法旨在使計算機理解程序中的語義信息和結構信息,這些信息可以用于軟件工程的多個領域,使得程序員從重復的任務中解放出來.深度學習技術在2006年被正式提出后,在近10年里得到了巨大的發展,使得人工智能產生了革命性的突破.在大量數據和計算資源的支持下,深度神經網絡已在圖像處理[1]、語音處理[2]、自然語言處理[3,4]等多個領域均有廣泛的應用,并已取得了令人矚目的效果.當前,深度神經網絡正在向更多的應用領域延伸擴展.以GitHub和Stack Overflow等網站為代表的開源代碼網站和開源社區的發展,給研究人員提供了大量、高質量的源代碼.這些代碼中隱含著許多知識,這些知識可被用于軟件開發中,這使得大規模代碼的學習成為可能.在軟件工程領域,程序生成和代碼補全技術是當前人工智能發展的最大的挑戰之一,也是在軟件工程-程序語言領域最熱門的方向之一.由于計算能力的增長和深度神經網絡的興起,程序生成和代碼補全研究中的許多局限已經慢慢被攻克,并且出現了復興的態勢,在很多領域得到了使用[5],例如代碼補全、基于功能描述的程序生成、基于輸出輸出的程序生成.

目前,基于深度學習的程序自動生成任務大多遵循圖1的架構.該架構主要包括4個部分:代碼資源庫、任務輸入、深度學習模型和輸出軟件代碼.如圖1所示,基于深度學習的程序自動生成框架的基礎是代碼資源庫的構建,這些代碼資源庫中的源代碼被挖掘處理后,利用深度神經網絡建立程序語言的模型,從而學習代碼資源中隱含的特征和知識.對于不同類型的程序自動生成任務,模型的輸入輸出不同,例如在代碼補全任務中,模型的輸入是部分代碼,輸出是當前位置需要補全的Token或者API調用.

Fig.1 Automatic program generation architecture based on deep learning圖1 基于深度學習的程序自動生成框架

目前,該方向的研究已經得到了學術界和工業界的廣泛關注.一些著名的 IT公司,如 Microsoft、Google、Facebook、百度等都在該方向展開研究,他們的研究成果在國際上引起轟動,例如 Google公司提出的 NPI、Microsoft公司提出的RobustFill、英特爾的AI Programmer等.程序自動生成已經成為當前軟件工程和人工智能領域最重要的前沿方向之一,在軟件工程和人工智能的國際頂級會議(如ICSE、FSE、ASE、IJCAI、ICML、ICLR等)都有該方向的論文發表以及研討,極大地促進了越來越多的學者投入到相關的研究中.

本文第1節主要介紹程序生成與代碼補全的背景知識以及研究問題和文獻的檢索方式.第2節闡述深度學習在程序生成上的應用.第3節闡述深度學習在代碼補全上的應用.第4節根據現有的相關工作的分析與研究,對目前主流的可以用于程序生成和代碼補全的深度學習模型進行詳細的描述.第 5節針對可以用于深度學習的代碼數據集進行總結.第6節對該方向的挑戰與未來方向進行總結.最后,在第7節對全文進行總結.

1 主要研究問題和文獻檢索方式

1.1 研究背景

代碼補全和程序生成是程序綜合(program synthesis)的重要分支,其目的在于輔助甚至代替程序員編寫程序.程序綜合是指根據用戶需求自動地構建計算機程序[5],程序綜合常見的用戶需求包括:基于邏輯的形式化規約、自然語言描述、輸入輸出樣例、程序執行的路徑[6].

程序綜合問題最早可以追溯到1932年,Kolmogoroff[7]提出在構造性數學中(constructive mathematics)可以通過編寫小的子程序,然后將其組合起來構造成一個算法.但是在當時,這種想法大多用于數學上,直到 20世紀60年代末,研究者開始逐漸關注基于邏輯推導的程序綜合(deductive program synthesis)問題[8-10].之后,越來越多的研究者投入到該方向的研究[11,12].基于邏輯推導的程序綜合方法依賴于邏輯學的理論推導過程,擁有嚴格的理論依據,能夠保證生成的程序的正確性.因此,該方法在程序驗證領域被廣泛地使用.然而,基于邏輯推導的程序綜合通常需要用戶提供完整的邏輯規約,許多情況下,用戶寫的邏輯規約幾乎和程序的復雜度相同,并沒有達到減輕人類編程負擔的目的.因此,有研究者開始了針對歸納程序綜合(inductive program synthesis)的研究.相對于基于邏輯推導的程序綜合技術,基于歸納的程序綜合技術是一個從一般到抽象的程序綜合過程.基于歸納的程序綜合最初由Summer[13]在1977年提出,他提出,在特定的約束限制下,一個循環的LISP程序是能夠從輸入輸出樣例中計算出來的,而不用在程序空間中進行搜索.他的這個觀點影響了許多后續的基于歸納的程序綜合問題[14-19].2009年,Kitzelmann[20]對幾種典型的基于歸納的程序綜合方法做了簡單的綜述.到了2010年左右,微軟的Gulwani團隊開始將程序綜合的方法用到實際的應用中去.Gulwani團隊研發的應用于Microsoft Excel的FlashFill[21,22]是目前用戶最熟悉的程序綜合應用.Gulwani[6]定義了程序綜合的3個維度,即用戶需求、搜索空間和搜索技術,并且對程序綜合的發展現狀做了綜述.隨著機器學習和深度學習的快速發展,我們正在進入智能化時代.越來越多的研究者將深度學習技術用于程序生成和代碼補全中.

程序生成指根據用戶需求自動地生成代碼片段,其用戶需求通常是高層次的描述,例如功能描述、輸入輸出樣例.程序生成一定程度上實現了機器代替程序員完成開發的工作,即機器編程.代碼補全是程序綜合中最直接也是最成功的應用.大多數現代代碼編輯器和集成開發環境都具有根據前面編寫的部分程序自動補全下一個Token的功能.該應用極大地減輕了程序員的開發負擔,加快了開發速度.

1.2 主要研究問題

本文的研究聚焦在基于深度學習的程序生成和代碼補全.與傳統程序綜合和代碼自動生成方法的不同在于,該問題旨在將深度學習技術與程序分析技術相結合,從大量高質量代碼庫中學習其中的知識,并利用這些知識進行程序自動化開發.

本文的主要目的是總結基于深度學習的程序生成和代碼補全的相關工作,并給出未來的研究方向.根據圖1所示的程序自動生成框架,本文將框架中涉及到的技術總結成程序自動生成的 4個維度,并對其展開研究,如圖2所示.

1)代碼語料庫.利用深度學習模型的前提是有高質量的數據集,即代碼語料庫,數據集的質量直接影響深度神經網絡學習到的代碼知識.

2)程序表示.其次,研究者需要確定程序的表示粒度.通常,研究者用Token序列、抽象語法樹、數據流圖、API調用圖來表示程序.程序的不同表示從不同的角度反映了程序的特征,例如,程序的Token序列反映了程序的語法和詞法特征,程序的抽象語法樹反映了代碼的抽象語法特征而忽略語法實現細節.

3)模型.不同粒度的程序表示往往使用不同的深度學習模型,也就是第 3個維度,即深度學習模型的選擇.研究者往往利用語言模型來對Token序列建模,因為語言模型可以學習到Token之間的序列關系;在使用抽象語法樹來表示程序時,研究者往往會設計基于樹的網絡來學習.

4)應用.訓練好的模型將被用于實際的任務場景中,即第 4個維度,程序生成和代碼補全的實際應用場景.不同的應用場景通常輸入和輸出都不一樣,例如,代碼補全應用以部分代碼作為輸入,輸出往往為基于當前位置預測的Token;基于功能描述的程序生成通常輸入為自然語言查詢,輸出為代碼片段.

Fig.2 Four dimensions of program generation and code completion process based on deep learning圖2 基于深度學習的程序生成和代碼補全過程的4個維度

具體而言,本文采用自頂向下的方式對當前的相關工作進行綜述.主要集中在程序生成和代碼補全的應用、相關的深度學習模型以及相關數據集的介紹.因為程序表示形式通常與應用和深度學習模型息息相關.在對這兩方面綜述時會對其加以描述,因此,本文不再對程序的表示形式單獨綜述.程序生成應用的介紹主要包括兩個方面:基于輸入輸出樣例的程序生成和基于功能描述的程序生成.對相關深度神經網絡介紹時,分為兩個大類:語言模型和結構模型.最后,本文對研究者工作中提供的高質量數據集進行了相關的綜述.

1.3 文獻檢索方式

本文在檢索文獻時,主要通過谷歌學術搜索、ACM Digital Library、IEEE Xplore Digital Library及Springer Link Online Library等.利用深度神經網絡的程序生成和代碼補全的研究,屬于軟件工程與機器學習的交叉領域,而其本質上是基于機器學習的代碼分析方法的延伸.因此,發表的論文主要分布在軟件工程和人工智能領域.檢索的論文主要是發表在軟件工程-系統軟件-程序設計語言領域和人工智能領域的國際頂級會議 ESEC/FSE、ICSE、ASE、PLDI、NIPS、IJCAI、AAAI、ICML、ACL、ICLR.

本文通過對人工智能領域和軟件工程領域頂級會議自2014年至今錄用的文章進行統計,從中篩選出與深度學習與程序生成和代碼補全相關的論文,統計結果見表1(由于一些會議還未召開,例如FSE、ASE等,所以未完全統計在內).

從數量上看,目前這個研究方向的論文還不算多,各個領域對程序生成和代碼補全任務的錄取情況有很大的差別.與軟件工程領域相比,人工智能領域在該方面的成果較多,占了總發表論文的88.5%,其中,ICLR和ACL在該方面的成果占了大部分.

Table 1 Statistics of accepted articles each year表1 歷年錄用論文統計結果

如圖3所示(圖3的統計包含了一些在arXiv上預發表的論文),該方向的研究在2016年迅速引起研究者的重視,2016年的論文數量是2015年論文數量的11倍.

Fig.3 Illustration of literature distribution by year圖3 文獻年代分布情況

此外,不同的應用發表的論文數量也不盡相同,如圖4所示,從論文數量上來看,基于輸入輸出的程序生成的研究成果最多,而代碼補全的相關工作較少.通過分析可以發現:基于輸入輸出的程序生成的研究成果中,ICLR會議發表的論文占了 50%;也能看得出,ICLR會議對此類程序生成問題更為感興趣.ACL會議主要的方向是計算語言,因此,基于自然語言功能描述的程序生成的成果中,ACL會議發表的論文占了66.7%.其主要研究目標是建立自然語言與程序語言的關系,從而達到從自然語言的功能描述到程序語言的轉化過程.從兩個領域的論文數量上來看,軟件工程領域對深度學習應用于程序生成和代碼補全的研究相對滯后,還有很大的發展潛力.然而軟件工程領域研究成果更加廣泛,深度學習被用于各種軟件工程任務中,包括代碼搜索、代碼注釋生成、缺陷檢測等.

Fig.4 Analysis of the research content of articles圖4 相關論文研究內容分析

本文在后面的第2節、第3節分別對基于深度學習的程序生成和代碼補全方面的最新研究進展進行綜述,第 4節對經常用于程序生成和代碼補全的深度神經網絡進行綜述,最后,對該方向已有的數據集進行簡要總結.表2是對現有相關工作的總結,后文會展開介紹.

Table 2 Summary of existing studies of code generation and completion based on deep learning表2 基于深度學習的程序生成與補全現有工作的方法總結

1.4 程序性質

直觀上,程序語言與自然語言有很多相似之處,比如都是由符號(token)組成、都可以表達為語法樹(parse tree)、在一定程度上都具有重復性和可預測性等.這些相似的地方也是我們利用深度學習技術來解決程序自動生成問題的基礎.但是相對于在自然語言領域的應用,深度學習在自動編程領域并沒有展現出它獨特的優勢,這與程序語言和自然語言的區別分不開.在自然語言中具有大量的不確定性和歧義性,所以基于規則的方法很難處理大量的特殊情況.而程序語言則是人為的根據規則嚴格定義和設計的語言.在語法層面或者低端的語義方面,機器(比如編譯器)都可以準確地解析和理解.因此在這個層面上,基于規則的方法具有天然的優勢.研究者利用深度學習實現程序自動生成任務時,考慮程序自身獨特的性質是十分重要的.程序語言相對于自然語言有如下性質.

1)強結構性.雖然自然語言的句子可以被解析為依存語法樹或成分樹,但由于使用的語法規則是由語言學家在語料中歸納得到,往往不能包含全部情況,且自然語言先天具有歧義性,其結構性較弱.而程序語言具有強結構性.通常,一段代碼可以按定義的語法規則解析為唯一對應的抽象語法樹.

2)無限制的字典.字典是訓練語言模型所必需的,程序語言和自然語言都有無限的字典.對于自然語言來說,一種語言常用的詞是有限的,人們很少會遇到罕見的詞匯.而程序語言則不同,程序員會定義不同的變量和方法名,這使得同樣規模的語料庫中,程序語言包含的字典大小往往會大于自然語言.

3)演化速度快.自然語言發展至今,雖然也存在種種演化,但其速度較慢.而程序語言的語料庫大多選自一些開源的代碼庫,對于一個軟件系統來說,版本演化是很常見的現象,演化過程通常伴隨著對系統缺陷的修復和添加新的功能特征.這一演化速度,使得研究者們需要不斷地更新自己使用的語料庫.

4)局部性特征.與自然語言相比,程序語言在一定范圍內會重復出現.例如,我們在定義一個變量后,該變量往往會在后文代碼出現;當我們引入一個庫后,通常在后文中會調用該庫中的API.如何更好地利用局部性特征來輔助程序生成,是許多研究者所關注的問題.

2 程序生成

基于深度學習的程序生成主要分為兩種:基于輸入輸出樣例的程序生成和基于功能描述的程序生成.現有的研究工作在實現上有不同的技術特點.表3總結了基于深度學習的程序生成現有工作的技術特點.

Table 3 Techniques summary of exsiting studies for program generation based on deep learning表3 基于深度學習的程序生成現有工作的技術總結

2.1 基于輸入輸出樣例的程序生成

基于輸入輸出樣例的程序生成又被稱為歸納程序綜合(inductive program synthesis,簡稱 IPS)或實例編程(programming by examples,簡稱PBE),是程序綜合的一類,IPS通過給定的輸入-輸出樣例來學習生成程序.建立一個IPS系統需要解決兩個問題.

(1) 搜索問題:通過在合適的程序集合中找到與輸入-輸出一致的程序.

(2) 排序問題:如何對多個與輸入-輸出一致的程序進行排序,然后返回最佳程序[29].

目前,歸納程序綜合任務主要在兩種數據上實現:一種是不局限于某一種程序語言,而是使用定義好的領域建模語言(domain-specific language,簡稱DSL);另一種是在實際的Microsoft Excel數據.由于可能程序的假設空間很大,在如此大的搜索空間中找到符合相應輸入輸出的程序是很具有挑戰性的.目前,利用學習的方法來進行DSL語言的歸納程序綜合任務大多遵循圖5的框架.

Fig.5 Architecture of inductive program synthesis system圖5 歸納程序綜合系統框架

2015年,Reed等人[37]開發了一個名為NPI(neural programmer-interpreter)的框架,利用該框架可以解釋執行程序.在他們的方法中,程序被視為一組詞向量,利用神經網絡來生成程序執行所需要的語句以及參數.Cai等人[38]、Xiao等人[39]、Chen等人[40]在Reed等人工作的基礎上對NPI進行改進,從而提高程序生成的準確率.2016年出現了大量的基于深度學習的程序生成工作[29,32,51].Balog等人[29]提出利用神經網絡來輔助搜索與一組輸入-輸出樣例一致的代碼,而不是直接預測整個代碼片段.Gong等人[51]提出了一種層級的卷積神經網絡HGCNN.HGCNN根據輸入-輸出樣例自動的給出程序的每行指令.Parisotto等人[32]提出用兩個神經網絡模塊來完成 IPS任務:一個模塊用于生成輸入輸出對的向量表示,另一個模塊利用一個基于樹的網絡結構來根據輸入輸出的向量表示來逐步擴展程序.2017年,Shu等人[30]提出一種基于深度神經網絡的模型,用該模型來生成一些解決字符串處理的程序.其生成的程序由一系列的原子操作組成,每個原子操作可能會使用前一個原子操作的執行結果,因此,該模型在只用幾個定義好的原子操作情況下可以合成復雜的程序.

Microsoft Excel的字符轉換功能是 PBE任務中較為成功的應用.作為 Microsoft Excel的一個重要特性,FlashFill[21,22]根據用戶提供的輸入輸出的字符串樣例,可以自動將其余輸入數據轉化為輸出數據格式.例如,利用FlashFill從地址中抽取郵編或轉換時間戳格式等.Shu等人[30]提出了NPBE(neural programming by example)完成45種字符串操作.NPBE的意圖是讓模型從輸入輸出字符串中學習相關的特征,并用學到的特征來歸納正確的程序.其核心模塊 Program Generator分別生成方法和參數的詞向量,最后融合兩部分向量,模塊 Symbol Selector利用融合的向量從方法和相應的參數列表中選擇合適的方法和參數.Parisotto等人[32]提出的R3NN模型通過在FlashFill數據上驗證發現:雖然其模型對多數Excel字符串操作都有效,但是當需要4個及以上Concat操作時,該方法會失效.Devlin等人[33]提出一種變長注意力機制循環神經網絡結構,該網絡可以有效地對變長無序的輸入輸出樣例集合進行編碼.不僅如此,為了驗證其魯棒性,對FlashFill數據人工注入各種噪聲數據后,驗證不同方法的準確率.實驗結果顯示,該方法在有大量噪聲的情況下依然保持較高的準確率,而基于人工的方法在有少部分噪聲的情況下其準確率就會大幅度降低.

2.2 基于功能描述的程序生成

人們通常利用自然語言來描述程序功能,從自然語言描述到程序的自動翻譯是極具挑戰性的問題.自然語言文本和程序的多樣性、文本的二義性以及代碼的復雜結構,使得建立文本和代碼的聯系成為一個難題.利用深度學習可以有效地解決代碼和文本中二義性的問題.

許多研究者利用深度學習的方法從自然語言生成 If-This-Then-That(IFTTT)代碼[41,43-45].IFTTT程序相對于常用的編程語言來說,其結構更加簡單,也更容易學習其結構規則.IFTTT程序通過創建一個流程(recipe)來完成特定的功能需求.This表示所要進行的操作被稱為觸發器(trigger),也就是在某個網絡服務的操作行為;而That則意味著連鎖反應所帶來的另外一個網絡服務行為動作(action).Dong等人[45]提出了一種基于注意力機制的編碼器-解碼器模型.該模型利用循環神經網絡對自然語言進行編碼,利用樹形的循環神經網絡生成程序.2016年,Liu等人[43]提出了一種隱注意力機制,該機制可以有效地學習自然語言中哪些詞對觸發器的預測更重要,哪些詞對動作的預測更加重要.同年,Beltagy等人[44]將IFTTT程序生成問題當做語義分析問題,其目標是根據自然語言描述生成衍生樹.

與生成IFTTT程序相比,根據功能描述生成常用程序語言(例如Java、Python等)的難度大得多.在2016年,Gu等人[46]提出了一個利用深度學習根據自然語言問題生成 API序列的工具 DEEPAPI.該工具利用編碼器-解碼器模型將自然語言問題的語義與API序列的語義建立關聯.DEEPAPI在一定程度上實現了程序生成功能,在API序列的生成上取得了較高的準確率.2017年,Yin等人[42]提出了一個語法模型,實現了從功能描述生成Python程序.該語法模型分為兩個部分:APPLYRULE和GENTOKEN.APPLYRULE在當前節點上應用生成規則來按照深度優先和從左至右的順序來生成程序結構;GENTOKEN既可以從預定義的詞表中生成終結節點,也可以直接從自然語言描述中復制一些詞來作為終結節點.

查詢關系型數據庫要求用戶理解查詢語言,例如 SQL,這對于非專業人員來說是相當困難的.因此,許多研究者考慮根據自然語言生成 SQL語句.2017年,Zhong等人[49]提出了 Seq2SQL模型,將自然語言描述翻譯為SQL查詢語句.在SQL查詢語句中,查詢條件是無序的,這導致了SQL生成查詢條件時不適合利用傳統的交叉熵來優化,因此,他們采用基于策略的強化學習來生成查詢條件.2018年,Cai等人[50]提出將深度學習方法與傳統的查詢解析技術相結合來提高生成 SQL的準確率.在生成 SQL語句時,他們通過加入 SQL的巴克斯范式(Backus-Naur form,簡稱BNF)來約束SQL的生成.

3 代碼補全

代碼補全技術是最常見的程序自動化技術,也是現代集成開發環境的重要組成部分.代碼補全極大地提高了程序開發的效率,并且減少了編碼過程中的拼寫錯誤.代碼補全技術通常幫助程序員預測代碼的類名、方法名、關鍵字等.下一個Token的預測是代碼補全最常見的形式,也是目前主流IDE所采用的補全方式.在常用的IDE中,推薦的Token往往按字母排序,增加了程序員對候選Token的選擇時間.

傳統的代碼補全主要分為兩種:一種是利用靜態類型信息結合各種啟發式規則來決定要預測的 Token,例如方法名、參數等,這種方法通常很少考慮代碼的前文語義信息,例如主流的代碼補全系統Eclipse,Eclipse利用靜態的類別信息給用戶推薦 Java方法,推薦的方法名通常按照字母序排列;另一種方法利用代碼樣例和前文語義來補全Token.2009年,Bruch等人[52]利用k-Nearest Neighbor(kNN)算法對當前的補全語義與之前的代碼樣例做匹配,從而提高代碼補全的準確率.利用前文語義幫助代碼補全的技術通常利用特殊類別的上下文信息,例如前文中調用的API集合,來輔助代碼補全.2010年,Huo等人[53]提出了名為BCC的代碼補全技術,該方法對API進行排序和篩選來提高 Eclipse基于類型的代碼補全系統.這些方法通常需要人工定義很多啟發式規則來規范上下文的語義集合,如果當前補全位置的上下文語義與定義的語義集合不匹配,這種方法就會失效.

深度學習方法從大規模代碼中學習代碼Token之間的概率分布,來提高Token推薦的準確率.對代碼Token序列進行概率建模,由Hindle等人[54]在2012年首次提出,他們指出:程序語言從理論上說是由人類寫的,具有重復性的語言,因此具有一些可以被預測的統計特征,這些統計特征可以被語言模型所捕捉.這一假說成為利用概率模型乃至深度學習對程序語言進行學習的基石.對下一個Token預測最直接的方法就是利用程序的Token序列對當前補全位置進行預測.目前,利用深度學習來完成代碼補全問題的主要流程如圖6所示.該流程主要包括兩部分:訓練階段和代碼補全階段.研究者首先從開源代碼庫或者開源社區獲得大量的數據作為深度學習的語料庫.為了更好地學習語料庫中的代碼,研究者通常利用代碼解析器對源代碼進行處理,例如將源代碼轉化為Token序列或者轉化為抽象語法樹.之后,研究者選擇或者設計一個合適自己任務的深度神經網絡,并對語料庫中的數據進行訓練.

Fig.6 Architecture of deep learning on code completion圖6 基于深度學習的代碼補全框架

目前,在代碼補全任務中經常用到的深度神經網絡是語言模型,例如循環神經網絡.語言模型可以有效地學習程序的序列特征,并且將該特征用于代碼補全任務.在代碼補全階段輸入部分代碼片段,在當前補全位置調用訓練好的深度學習模型,該模型根據輸入代碼片段的語義或結構特征來預測需要補全的Token或者API等.表4是對基于深度學習的代碼補全工作技術特點的總結.

Table 4 Technique summary of existing studies of code completion based on deep learning表4 基于深度學習的代碼補全現有工作技術總結

2014年,Tu等人[55]在Hindle等人[54]的基礎上提出代碼的Token在局部范圍內具有一定的重復性.語言模型可以學習代碼全局的規律,然而卻忽略了程序的局部性特征.因此,Tu等人[55]在語言模型的基礎上加入了“緩存”機制來維護.實驗結果顯示,該方法比之前的方法提升了16%～45%.Hellendoorn等人[24]通過對比循環神經網絡與帶有“緩存”機制的N-gram,發現代碼的局部性特征對于Token的預測有極大的幫助.

如何有效地利用程序的結構信息來提高代碼補全的準確率,一直是許多研究人員的關注熱點.在利用代碼結構進行代碼補全時,研究者通常從兩個方向展開研究:將樹結構轉化為序列和直接對樹結構進行建模.Li等人[27]和Liu等人[23]通過AST序列對程序的終結節點和非終結節點進行預測.這種基于AST序列對Token進行預測不僅可以預測下一個終結節點即實際代碼 Token的預測,而且可以預測代碼的結構信息即非終結節點.在對AST序列進行建模時,要求AST序列既能保證程序的語義信息,又能保證程序的結構信息.因此,研究者在將AST轉化為序列時,需要保證AST序列唯一表示一個代碼片段.2018年,Li等人[27]在對AST節點進行編碼時額外加了兩位,用來表示該節點是否有子節點和右兄弟節點.直接對代碼結構進行建模需要設計相應結構的網絡結構對其進行建模.2016年,Raychev等人[56]利用決策樹來對程序的樹結構直接建模來預測代碼的Token.

除了對下一個Token進行補全以外,應用程序接口(application programming interface,簡稱API)的補全也受到了極大的關注.API的使用,極大地提高了程序員的開發效率.如何利用深度學習方法來補全多個API并且保持較高的準確率,是API補全的難點.API級別的補全通常學習API的使用模式,利用API的使用模式來完成大規模的API補全.Raychev等人[25]在2014年提出利用語言模型根據上下文信息來補全API調用.他們提出的工具SLANG可以有效地補全API的調用和API的參數.2016年,Gu等人[46]利用序列到序列模型訓練了大規模的自然語言描述和API序列對,從而建立了自然語言和API序列的映射關系,其模型DEEPAPI有效地根據自然語言查詢返回API的調用序列.2018年,Gu等人[57]利用API序列遷移的方法生成相似程序語言的API序列,其利用API序列及其自然語言功能描述來學習API序列的向量表示.功能相似的API序列在向量空間中的的距離也相近,因此可以利用向量的相似度來生成相同功能、不同程序語言的API序列.

從目前的工作來看,深度學習方法的出現極大地促進了程序生成任務和代碼補全任務的發展,但是目前的工作還局限于生成規模較小、功能單一的程序.依據給定輸入輸出樣例生成的程序往往通用性較差,目前主要應用在DSL語言和Excel處理上,而不能普遍地適用于通用編程語言,例如Java,Python等.如何利用深度學習生成可以實際運行的程序,仍然是目前亟待解決的問題.

4 程序自動生成深度學習模型

4.1 基于語言模型的程序生成技術

語言模型廣泛地應用于各種自然語言處理問題,例如機器翻譯、語音識別、問答系統等等.語言模型定義了自然語言中 Token序列的概率分布.基于程序語言的自然性,語言模型也被應用于程序的建模.語言模型通常將解析過的代碼片段(通常在詞或字符級別)當做文本直接作為輸入,該模型的目標是對程序語言的文本的概率分布進行建模,也就是說,概率模型用于估計一個代碼片段s的概率分布P(s).對于一個代碼片段s={w1,…,wm}來說,許多語言模型通過計算每一個詞基于已經生成的詞的條件概率來計算整個代碼片段的概率分布,即

在程序語言處理中,常用到的語言模型有N-gram和循環神經網絡(recurrent neural network,簡稱RNN),其中,循環神經網絡是基于深度神經網絡的語言模型.

N-gram是最早用于程序學習的語言模型,在N-gram模型中,下一個單詞wi的概率依賴于前n-1個詞,即

因此,N-gram模型可以在一定程度上捕捉句子的局部信息.在Hindle等人[54]將N-gram模型應用于代碼建模后,有許多利用N-gram的工作隨后出現.N-gram雖然可以有效地學習代碼片段的局部上下文,但是不能理解代碼片段的語義信息.為了解決這些問題,許多研究者結合軟件工程任務的特點對N-gram 模型進行了改進.Nguyen等人[58]提出的SLAMC模型將全局信息加入N-gram模型,SLAMC結合了語義信息,并對語義標注的規則進行建模,該方法在代碼推薦的準確率上較普通的N-gram有顯著的提升.Raychev等人[25]將N-gram模型與循環神經網絡結合,在Java在API調用級別進行代碼補全.為了解決代碼具有局部性特征的挑戰,Tu等人[55]和Hellendoorn[24]等人提出了將緩存機制加入到N-gram 模型中,利用標識符會在較近的范圍內重復出現的特性,從而在代碼預測上取得了顯著的效果.

與N-gram相比,RNN不僅可以捕獲句子中詞之間的規律性,而且可以捕捉距離較遠的詞之間的關系.為了更進一步解決長距離依賴問題,許多基于RNN的變體,例如長短記憶模型(long short-term memory,簡稱LSTM)、門限循環單元(gated recurrent unit,簡稱GRU)被提出并得到廣泛應用(如圖7所示).利用RNN模型可以有效地對源代碼進行建模,并且學習源代碼的向量表示.Nguyen等人[59]、Nguyen等人[60]和Gu等人[57]利用RNN學習分別Java語言和C#的API向量表示,將學到的向量表示應用于這兩種語言的API遷移任務中,從而在API級別生成代碼.許多學者將RNN模型用于代碼Token預測補全,并且取得了顯著的效果[26].大多數研究工作都是利用RNN在詞的級別對代碼進行建模學習,但是由于代碼大量的變量導致學習難度很大,有一些工作開始在字符級別對代碼進行學習[61].

Fig.7 An illustration of basic RNN and LSTM structures圖7 基礎循環神經網絡和長短記憶網絡結構

程序語言在本地(localness)上具有一定的重復性,例如,一個定義過的變量往往會在后邊重復使用.然而,這些變量在很大程度上往往會被當成詞典外的詞(out-of-vocabulary,簡稱OoV),通常被記為UNK.給程序員預測一個 UNK對于他們的編程是毫無幫助的,因此,研究者考慮將指針網絡機制加入到語言模型,來準確預測本地重復出現的詞.利用指針網絡可以有效地從輸入的代碼片段中復制需要重復使用的詞.指針網絡(pointer networks)由 Vinyals等人[62]在 2015年提出,最初被用于解決組合優化問題,是神經機器翻譯模型(即序列到序列模型,Seq2Seq模型)的一個變種.在指針網絡中,注意力更簡單,它不考慮輸入元素,而是在概率上指向它們.

2016年,Bhoopchand等人[26]提出了一種精簡指針網絡(sparse pointer network),該網絡主要解決了自定義標識符預測的問題(例如類名、方法名、變量名等).論文中定義了“內存(memory,簡稱M)”的概念,該“內存”用于存儲前K個標識符.此外,該方法維護了一個向量m=[id1,…,idK]用于記錄標識符在全局詞表中的位置,即指向全局詞表的指針.在每個時刻進行預測時,該網絡結合全局的語言模型概率分布,自定義標識符的指針概率分布以及當前的代碼輸入來決定輸出的詞.與傳統循環神經網絡(不帶有注意力機制)相比,該方法在 Python自定義標識符預測準確率上提高了25%左右.

Li等人[27]在2018年提出一種結合注意力機制的語言模型和指針網絡的模型進行代碼補全,其模型對抽象語法樹序列進行建模.該模型不僅可以預測語法樹的節點類型,而且可以預測節點的值,即要預測的代碼.直覺上,在預測代碼時,父親節點對于孩子節點的預測幫助更大,因此,其注意力機制在傳統的注意力機制上結合了語法樹“父親-孩子”節點關系.論文利用指針網絡從輸入的代碼片段中復制單詞來預測詞表外的詞,即OoV.論文中通過定義一個選擇器(switcher)來決定是根據語言模型在全局詞表上的分布來預測下一個詞,還是利用指針網絡從輸入的代碼片段中復制一個詞.該方法在兩個數據集上進行了驗證,分別是 Python和 JavaScript.結果表明,其方法在預測OoV詞上有顯著的提高.

4.2 結構化代碼生成網絡

代碼的強結構性問題對于深度學習模型來說既是一個挑戰,也是一個機遇.由于程序語言是一種強結構性語言,每個代碼片段都對應一個唯一的抽象語法樹.不同于自然語言的語言模型,許多研究者致力于對代碼結構進行建模并實現代碼的生成.與基于序列的建模方式不同,結構化的建模通常描述結構(如抽象語法樹)生成過程的概率分布.因此,許多工作都從結構是如何生成的來對程序結構進行建模.利用深度學習對程序結構建模從而生成程序主要分為兩種:基于抽象語法樹的網絡和基于圖的網絡.

4.2.1 基于抽象語法樹的網絡

基于抽象語法樹的網絡是對程序結構進行建模時最常見的網絡結構.研究者主要從兩個方向上運用抽象語法樹,將語法樹的節點遍歷成序列形式結合序列化模型和直接設計樹形的網絡對語法樹建模.

1) 將抽象語法樹遍歷成序列,并利用基于序列的模型對其建模.

該方法相對于設計樹形網絡要簡單許多,其難點在于如何保證一個序列唯一對應一個程序,即保證序列無二義性.在 Liu等人[23]的工作中,將代碼補全問題看做是在給定部分抽象語法樹的情況下預測樹的下一個節點.他們在遍歷抽象語法樹時,利用中序深度優先遍歷得到序列.Li等人[27]在其工作中將抽象語法樹也是按照中序深度優先的方法進行遍歷得到序列,通過帶有指針網絡的語言模型對該序列進行學習.與 Liu等人[23]的工作不同,為了保證該序列唯一對應一個代碼片段,他們在對節點進行編碼時額外加了兩位,用來表示該節點是否有孩子節點和是否有右兄弟節點.其結果與Liu等人[23]等結果相比,在預測節點的Type和Value的準確率上均提高了4%左右.

2) 樹形網絡.

利用樹形網絡生成代碼時,通常按照從上到下從左至右的順序生成樹的子節點.一般來說,生成樹結構的深度學習模型很難學習:首先,這種模型計算成本很高;其次,對樹生成過程的上下文建模需要更加復雜的數據結構(與序列模型相比).一些研究者利用機器學習的方法對抽象語法樹建模,Bielik等人[63]和Raychev等人[56]分別利用上下文無關文法和決策樹對抽象語法樹建模并預測代碼.深度學習方法比機器學習網絡結構更為復雜,需要根據抽象語法樹的結構定制新的網絡.Rabinovich等人[64]提出一種抽象語法網絡(abstract syntax network,簡稱ASN),該網絡是標準編碼器-解碼器框架的擴展形式.與序列模型不同,其解碼器是由許多子模塊組成,每個子模塊都與抽象語法樹的一個語法結構對應.在解碼過程中,循環神經網絡的狀態從一個模塊傳遞到另一個模塊,從而實現模塊之間信息的傳遞.在樹的生成過程中,根據當前的狀態選擇不同的模塊執行不同的網絡,從而實現樹結構的預測.與 Rabinovich等人[64]根據樹的語法結構設計不同的模塊不同,Dong等人[45]提出一種層級的樹解碼器 SEQ2TREE.解碼器根據編碼器得到的結果之后,利用循環神經網絡生成樹深度為1的Token,當預測為非終結節點時,將非終結節點的狀態作為輸入預測樹的下一層,直到沒有非終結節點.

4.2.2 基于圖的網絡

Nguyen等人[65]提出對Java程序的API調用的圖表示方法.與Gu等人[46,57]將Java方法中的API按序列表示其關系不同,Nguyen等人[65]在對API的調用關系建圖時,圖中的節點包括動作(即API調用、重載操作和域的訪問)和控制點(即控制結構的分支if,while,for等).圖的邊表達了這些節點的依賴關系.Allamanis等人[28]提出利用基于圖的網絡來表示代碼結構的句法和語義特征,其模型利用不同的邊來表達不同Token之間的句法和語義關系.如圖8所示,其圖的模型在抽象語法樹的基礎上對節點的關系進一步刻畫,圖中的邊包括兩類:Child和NextToken,其中,Child邊連接抽象語法樹的節點.為了進一步表示非終結節點的孩子節點中葉子節點的順序,該模型用NextToken邊將其連接起來.

Fig.8 Graph representation model of AST in Allamanis,etal.[28]圖8 Allamanis等人提出的基于抽象語法樹的圖表示模型[28]

5 用于深度學習的代碼語料庫

代碼數據集是利用深度學習實現程序生成和代碼補全的前提,規范、高質量的代碼語料庫更有利于深度神經網絡的學習.在圖像識別和自然語言處理中,有許多公開的數據集供研究者展開研究.然而在程序語言中,很少有公開的數據集供研究者使用,許多研究者需要自己去構造數據集.目前,一些研究者在論文中公開了自己的數據集,這些數據集可以被其他研究者使用.本文對文獻中的相關數據集進行了總結,見表5.

Table 5 Code corpora proposed by existing studies表5 現有工作提出的代碼語料庫

目前,這些數據集被用于許多軟件工程任務中.例如,Mou等人[68]提出的104類的C程序被用于程序分類任務和代碼克隆檢測任務;源代碼以及對應注釋的數據集被用于代碼摘要生成任務中.已有工作的數據集大多來源于 GitHub,為了保證數據集的質量,大多研究工作都選擇星級(star)或復刻(fork)較高的項目,然后從這些項目中抽取相應的代碼片段作為代碼語料庫.然而,這些語料庫中仍有一些噪聲,對源碼的學習帶來影響,這些噪聲主要來源于以下幾個方面.

· 代碼編寫不規范.許多項目開發人員在編寫代碼時,沒有按照統一的規范來開發,尤其在注釋書寫上有很大的差異性,主要體現在:各國語言同時使用:注釋并不是解釋代碼片段的功能需求:缺少規范的注釋,例如Javadoc注釋.

· 存在大量相似甚至重復的代碼片段.在項目開發過程中,由于重載或重寫機制,許多代碼片段十分相似,這就導致在模型的訓練過程中容易出現過擬合現象.對于Online Judge這類提交解決方案代碼的數據集,這種現象更加明顯.對于同一個方案的不同提交,它們之間的差異性很小.

因此,我們在使用這些數據集時,應該根據自己的需求對于數據集一定程度上的清洗,通過定義一些規則過濾掉可能產生噪聲的數據,從而達到生成符合編程規范的程序的目的.

6 挑戰與未來方向

總體來看,當前利用深度學習技術的程序生成和代碼補全還處于起步階段.從介紹的相關工作中可以看出,利用深度學習代碼補全與傳統方法相比有了較大的提升,而程序生成技術還無法用于工業化.目前的研究工作還難以滿足實際軟件自動化開發的需求,主要面臨著以下的挑戰.

1)實驗缺乏統一的自動化評估標準.現有的文獻中,用來評測模型能力的指標包括預測下一個 token的準確率、信息檢索領域使用的指標MRR和機器翻譯領域使用的指標BLEU等.這些指標之間無法直接轉化,也就難以將各種模型能力進行直接比較.此外,這些指標的高低與程序的正確性與否之間的關系還難以清晰表述.因此,如何找到一種能夠自動評估生成程序正確性的指標,是將現有研究工作投入到實際開發中的一項重要挑戰.

2)訓練語料的質量參差不齊.現有的工作中,用來訓練深度學習模型的語料大致可以分為兩類:一類是基于DSL人為構造出的程序;另一類是從開源社區,如GitHub等網站上爬取的項目.基于DSL的程序往往語法較為簡單,程序長度較短,易于訓練和測試,但同時,針對 DSL設計的模型也難以推廣到其他語言上使用;而開源社區上爬取的項目雖然更接近于實際軟件開發,但是也難以保證代碼的質量——低質量、不規范的代碼會給神經網絡帶來額外的噪聲,而使用不同編程規范的代碼則會使神經網絡模型在訓練和預測時產生混淆.如何獲取統一規范的高質量程序語料庫也是一項挑戰.

結合當前程序生成和代碼補全的研究現狀,以下幾個方面可能成為進一步的研究方向:

1)結合編譯技術提高程序生成質量.現有的模型自動生成代碼時,由于沒有考慮到是否符合語法,會產生大量無法編譯通過的部分代碼片段.而實際上,這些錯誤可以由程序員或IDE的語法檢查功能查出并修復.因此,將程序語言的語法和規范引入到程序自動生成模型中,作為模型的一部分或在生成token時作為約束和限制,有可能提高程序自動生成技術的可靠性,更好地輔助程序員快速開發.

2)使模型具有更強的用戶可自定義性.神經網絡模型往往基于大規模語料庫訓練并測試,但在項目開發過程中,程序員可能會依照實際需求使用新的自定義標識符編寫未在此前語料庫中出現過的代碼片段.因此,為了提升用戶體驗,我們需要使得模型具有更強的用戶可自定義性,即可以根據用戶自己編寫的代碼來更新模型.

7 結束語

為了減輕程序員的開發負擔,提高軟件開發的自動化程度,提高軟件開發的效率和質量,學界和工業界都不斷嘗試研究程序自動生成技術.盡管常用的集成開發環境中往往整合了代碼補全工具,但現有的代碼補全工具通常只簡單地基于靜態詞頻統計,候選結果則按照字典順序排列,低準確率的代碼補全工具在實際場景中可能反而會增加程序員的開發成本.此外,更進一步地,研究者們也致力于直接生成執行某一特定功能的代碼片段或完整程序,即程序生成.人工智能的發展極大地促進了程序自動生成技術的進步,但是由計算機直接生成代碼仍然十分困難,目前的程序生成技術還局限于生成規模較小、功能單一、領域特定的程序,對于復雜的程序,其技術還是十分受限.

隨著深度學習技術的再次火熱,越來越多的研究者開始將深度神經網絡模型應用于提升程序自動生成技術的性能.由于程序語言也屬于人類創造的語言,整體來看,研究者們傾向于將原本用于對自然語言建模的模型應用于程序語言上,如許多工作中將語言模型用于對程序語言建模.但與自然語言相比,程序語言具有結構性強、擁有無限制大的詞表以及演化速度快等特點,這給研究者們帶來了更多的挑戰,同時也提供了新的可能性.例如,代碼可以轉換成與其對應的抽象語法樹,最近已經有越來越多的工作致力于對抽象語法樹建模,并取得了比只對詞序列建模的方法更好的效果.此外,如何更好地處理程序語言中過大的詞匯表.也是進行基于深度學習的程序自動生成技術研究的一條可選道路.隨著深度學習技術的快速發展,相信在將來,越來越多的重復性的程序開發將由機器代替,程序員將更關注于上層的開發與設計工作.