(武漢大學(xué) 計(jì)算機(jī)學(xué)院， 湖北 武漢 430072)

1 類型推理介紹

類型推理是一種輕量級的形式化方法，是編程語言中的自動(dòng)推理部分或全部表達(dá)式類型的能力，通常在編譯時(shí)完成.編譯器能夠推理變量的類型或函數(shù)的類型名，而不需要給出顯式的類型注釋.它包括分析一個(gè)程序，然后推理該程序中某些或所有表達(dá)式的不同類型，這樣程序員就不需要每次在程序中使用變量時(shí)都顯式地輸入和定義數(shù)據(jù)類型.類型推理通常是函數(shù)式編程語言的編譯器特性，而不是面向?qū)ο缶幊陶Z言的編譯器特性.編譯器或解釋器只需要最少的信息和上下文，就可以確定變量或表達(dá)式的數(shù)據(jù)類型.推理算法嘗試確定參數(shù)類型和返回值類型，然后嘗試找到與所有參數(shù)一起工作的最特定的數(shù)據(jù)類型.類型推理的輸入可以是源代碼、字節(jié)碼或二進(jìn)制代碼，它是在編譯時(shí)自動(dòng)推理表達(dá)式的類型，使編譯器能夠在沒有給出明確的類型注釋的情況下推理出數(shù)據(jù)和函數(shù)的類型.在許多情況下，如果類型推理系統(tǒng)足夠健壯，或者程序或語言足夠簡單，則可以完全省略程序中的類型注釋.在程序編寫和編譯執(zhí)行過程中，類型推理是一項(xiàng)很重要的功能.

傳統(tǒng)的類型推理方法都是基于規(guī)則和語法結(jié)構(gòu)[1]，傳統(tǒng)的類型推理解決方案在方法上存在很大的差異.它們可以使用靜態(tài)分析、動(dòng)態(tài)分析以及它們的組合.如Troshina等[2]采用了靜態(tài)分析的方法，Guo等[3]使用了動(dòng)態(tài)分析的方法，Lee等[4]則采用了靜態(tài)分析和動(dòng)態(tài)分析的組合.另一方面，它們可以選擇從不同的類型信息來源出發(fā)，如Raman等[5]和Srinivasan等[6]使用基于值的類型推理方法，而Chandra等[7]選擇了基于流的類型推理方法.不同的類型推理方法還可以采用不同的數(shù)據(jù)結(jié)構(gòu)，如抽象語法樹、路徑圖、函數(shù)調(diào)用圖等. 其中，函數(shù)調(diào)用圖是利用程序中函數(shù)之間的調(diào)用關(guān)系建立起的模型，抽象語法樹是利用程序語義建立起的模型.同時(shí)，對于所推理的類型也有很大的差異，包括基本類(如整數(shù)、浮點(diǎn)和指針等)、聚合數(shù)據(jù)類型(如數(shù)組)，以及面向?qū)ο蟪绦蛑械念?它們也可以有不同的輸入形式，如源碼、二進(jìn)制代碼和字節(jié)碼等.但是，由于傳統(tǒng)的類型推理方法基于上下文與語法規(guī)則，所以其在許多實(shí)際應(yīng)用的情況下會(huì)具有局限性.在傳統(tǒng)的類型推理中，因?yàn)樾枰Z法規(guī)則和類型推演規(guī)則，所以要求被推理的程序片段首先都是合法的表達(dá)式，即要通過完整的語法檢查.然而隨著軟件技術(shù)的發(fā)展，在很多情況下獲取所需要的類型信息時(shí)，并不要求程序在語法上是合法的，而且在很多實(shí)際應(yīng)用的過程中，也無法保證所輸入的推理程序一定能夠通過語法檢查，這種情況下，就無法繼續(xù)進(jìn)行類型推理.

對于動(dòng)態(tài)類型語言，在缺乏上下文信息和語法規(guī)則的前提下，編譯器都很難正常理解這些代碼片段，所以采用傳統(tǒng)的類型推理方式則很難解決這些問題.例如python語言，它的程序嚴(yán)重依賴外部APIs和動(dòng)態(tài)語言的特性，而且python變量類型都是路徑敏感的，對于不同的程序路徑，變量可能會(huì)有不同的類型，對象的類型和屬性集可以動(dòng)態(tài)更改，大大增加了類型推斷的難度，使得傳統(tǒng)的方法并不適用.另一方面，現(xiàn)有的傳統(tǒng)特性往往無法區(qū)分不同語義的代碼區(qū)域，具有不同語義的程序文件可能具有相同值的傳統(tǒng)特性，要能夠區(qū)分這種語義差異的特性就需要能夠建立更加精確的預(yù)測模型.所以在這些情況下，能夠采用基于機(jī)器學(xué)習(xí)的方法對程序片段進(jìn)行類型推理就顯得尤為重要了.

編輯代碼文件的開發(fā)人員與函數(shù)名、參數(shù)和變量名等各種標(biāo)識符交互，這些標(biāo)識符都存在于一個(gè)類型系統(tǒng)中，類型系統(tǒng)限制只接受定義它們的操作數(shù).在編譯時(shí)進(jìn)行類型推理了解類型可以提高代碼的性能，并允許早期檢測錯(cuò)誤.較強(qiáng)的類型系統(tǒng)對于軟件開發(fā)工具也很有用，例如提高自動(dòng)完成的準(zhǔn)確性和調(diào)試信息.基于機(jī)器學(xué)習(xí)的類型推理可以被廣泛應(yīng)用于程序錯(cuò)誤檢測[8]、程序抽象、程序優(yōu)化、代碼補(bǔ)全、程序摘要、錯(cuò)誤定位[9]等多個(gè)軟件領(lǐng)域.

如今，已經(jīng)涌現(xiàn)出了很多基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理，對在缺乏上下文和語法規(guī)則的情況下預(yù)測所需程序片段的類型提供了新思路.本文對目前的基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理的幾個(gè)重要方面進(jìn)行了歸納總結(jié)，分析了實(shí)驗(yàn)所采用的不同方法，總結(jié)各自的特點(diǎn)、實(shí)驗(yàn)中能夠推理出的類型、具體的實(shí)現(xiàn)過程和實(shí)驗(yàn)結(jié)果的評估.同時(shí)，也對目前存在的問題和未來與之相關(guān)的研究方向進(jìn)行了討論.

2 基于機(jī)器學(xué)習(xí)的類型推理

在程序設(shè)計(jì)語言中，一個(gè)變量a的類型是它的所有可能的取值形成的集合Ta.傳統(tǒng)的類型推理依據(jù)程序設(shè)計(jì)語言的類型系統(tǒng)，設(shè)計(jì)類型推理的規(guī)則，為程序中的任意一個(gè)合法的短語α，指派一個(gè)類型Tα.

基于機(jī)器學(xué)習(xí)的類型推理則使用機(jī)器學(xué)習(xí)的方法，利用海量的已知類型的源程序作為語料訓(xùn)練，學(xué)習(xí)出一個(gè)類型推理函數(shù)Δ:Σ*×Σ*→T，其中Σ*為所有串的集合.在推理階段，給定程序P中的短語α，可以利用Δ(α,P)得到短語α的類型.

筆者對用機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理這一領(lǐng)域進(jìn)行了研究，研究表明，用機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理是一個(gè)多學(xué)科的領(lǐng)域，在編程語言、軟件工程和系統(tǒng)等多個(gè)領(lǐng)域都有相關(guān)的論文發(fā)表.本文系統(tǒng)地研究了基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理，選取研究的文獻(xiàn)來自于OOPSL、APOPI、PLDI、ICSE等多個(gè)計(jì)算機(jī)領(lǐng)域的頂級會(huì)議.表1總結(jié)了本文討論的基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理的幾篇文獻(xiàn)中所采用的方法，涉及到的編程語言.在本文的研究中，類型推理的輸入均為源代碼，因?yàn)閭鹘y(tǒng)的類型推理方法都是依賴于語法規(guī)則與類型推演規(guī)則，所以在缺乏上下文與語法規(guī)則的前提下進(jìn)行對程序片段的類型推理很具有挑戰(zhàn)性.源代碼的類型推理受編程語言、操作系統(tǒng)和目標(biāo)體系結(jié)構(gòu)等的影響.編程語言是程序員選擇的用于準(zhǔn)確定義計(jì)算機(jī)所需要使用的數(shù)據(jù)類型,而操作系統(tǒng)和目標(biāo)體系結(jié)構(gòu)可能影響代碼片段中數(shù)據(jù)的表示形式.雖然目前通常認(rèn)為所有提出的類型推理的方法可能是通用的，但是大多數(shù)方法都是在特定的編程語言和體系結(jié)構(gòu)組合上進(jìn)行評估的.在之后的章節(jié)將具體地討論基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理的幾篇文獻(xiàn)中實(shí)驗(yàn)的各個(gè)方面.

3 方 法

近年來，國內(nèi)外涌現(xiàn)出了很多基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理的研究，在本文中，將所有的基于機(jī)器學(xué)習(xí)類型推理的方法進(jìn)行了分類，分別為基于條件隨機(jī)場的類型推理方法、基于其他概率模型的類型推理方法和基于深度學(xué)習(xí)的類型推理方法，然后，具體討論實(shí)驗(yàn)研究過程中將如何運(yùn)用這些方法進(jìn)行類型推理.

表1 實(shí)驗(yàn)方法和程序語言的總結(jié)

3.1 基于條件隨機(jī)場的類型推理方法

條件隨機(jī)場(conditional random field)是一種判別式概率模型，是隨機(jī)場的一種，常用于標(biāo)注或分析序列資料，目前比較廣泛地應(yīng)用于自然語言處理中，進(jìn)行中文分詞和詞性標(biāo)注等詞法分析工作.條件隨機(jī)場的圖模型為無向圖模型，圖中所有的頂點(diǎn)分別代表隨機(jī)變量，而頂點(diǎn)間的連線則代表隨機(jī)變量間的依賴關(guān)系.在圖模型中，往往定義了兩種特征：狀態(tài)特征和轉(zhuǎn)移特征，其中狀態(tài)特征定義在結(jié)點(diǎn)上，表示這個(gè)結(jié)點(diǎn)是否擁有某個(gè)屬性；而轉(zhuǎn)移特征定義在邊上，表示兩個(gè)狀態(tài)是否會(huì)因?yàn)槟硞€(gè)特征而轉(zhuǎn)移.P(y|x)為線性鏈條件隨機(jī)場，則在X取x的條件下，Y取y的條件概率：

其中，Z(X)是歸一化因子，tk和sl是特征函數(shù)，λk和μl是對應(yīng)的權(quán)值，tk是定義在邊上的特征函數(shù)，即轉(zhuǎn)移特征，sl是定義在節(jié)點(diǎn)上的特征函數(shù)，即狀態(tài)特征.特征函數(shù)的取值當(dāng)滿足特征條件時(shí)取1，否則取0.原則上，條件隨機(jī)場的圖模型布局是可以任意給定的，一般常用的布局是鏈接式的架構(gòu)，鏈接式架構(gòu)不論在訓(xùn)練、推理，還是解碼上，都存在有效率的算法可供演算.條件隨機(jī)場是一個(gè)典型的判別式模型，其聯(lián)合概率可以寫成若干勢函數(shù)聯(lián)乘的形式，其中最常用的是線性鏈條件隨機(jī)場.

Raychev等[10]就是通過條件隨機(jī)場對JavaScript進(jìn)行程序?qū)傩缘念愋屯评?它是首先對 JavaScript 程序進(jìn)行語法分析后轉(zhuǎn)換為依賴網(wǎng)絡(luò)(Dependency Network)，然后利用已有的代碼進(jìn)行訓(xùn)練，從而能夠預(yù)測JavaScript 變量的名稱與簡單類型.該研究著重于推理程序?qū)傩缘囊话銌栴}，運(yùn)用新的統(tǒng)計(jì)方法，通過從已經(jīng)注釋了這些屬性的現(xiàn)有代碼庫中學(xué)習(xí)概率模型來預(yù)測給定程序的屬性.通過學(xué)習(xí)大量的代碼庫來預(yù)測程序?qū)傩缘暮诵乃枷胧?，將類型推理的問題表述為利用條件隨機(jī)場對程序?qū)傩赃M(jìn)行結(jié)構(gòu)化預(yù)測，實(shí)現(xiàn)對程序?qū)傩缘穆?lián)合預(yù)測.通過條件隨機(jī)場逐步預(yù)測程序?qū)傩缘倪^程，首先就是建立依賴網(wǎng)絡(luò)，然后基于該網(wǎng)絡(luò)構(gòu)建相應(yīng)的特征函數(shù)，通過特征函數(shù)的定義可以進(jìn)一步定義如何獲取預(yù)測值y的得分.在網(wǎng)絡(luò)中與所有其他節(jié)點(diǎn)斷開連接的節(jié)點(diǎn)的預(yù)測可以獨(dú)立于對其他節(jié)點(diǎn)的預(yù)測，而且因?yàn)闂l件隨機(jī)場具有條件獨(dú)立性的屬性，所以在網(wǎng)絡(luò)中被連接的兩個(gè)節(jié)點(diǎn)僅通過已知的節(jié)點(diǎn)進(jìn)行預(yù)測，兩個(gè)節(jié)點(diǎn)的屬性彼此獨(dú)立的分配，不會(huì)相互影響.但是兩個(gè)節(jié)點(diǎn)在不涉及已知節(jié)點(diǎn)的情況下，如果之間存在路徑則意味著兩個(gè)節(jié)點(diǎn)的預(yù)測可能相互依賴.該方法是已知的第一個(gè)展示如何在程序上下文中利用條件隨機(jī)場進(jìn)行研究的方法.

Uri等[11]也利用到了條件隨機(jī)場，提出了一種從程序中學(xué)習(xí)一般的基于路徑的表達(dá)，這種表示是純粹語法上的，并且是自動(dòng)提取.其主要思想是通過使用抽象語法樹中的路徑來表示程序.這種方法使學(xué)習(xí)模型能利用代碼的結(jié)構(gòu)化本質(zhì)，而不是將其視為一組扁平的令牌序列.改進(jìn)了條件隨機(jī)場，在條件隨機(jī)場中使用抽象語法樹路徑，而不是使用原始的因子.

3.2 基于其他概率模型的類型推理方法

機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)關(guān)鍵概念是不確定性，概率論為不確定性的量化和操作提供了框架，并形成了機(jī)器學(xué)習(xí)的核心基礎(chǔ)之一.它與決策論相結(jié)合，可以根據(jù)一些可獲得的信息做出最佳預(yù)測，即使這些信息可能并不完整.概率模型是用來描述不同隨機(jī)變量之間關(guān)系的數(shù)學(xué)模型，通常情況下刻畫了一個(gè)或多個(gè)隨機(jī)變量之間的相互非確定性的概率關(guān)系.從數(shù)學(xué)上講，該模型通常被表達(dá)為(Y，P)，其中Y是觀測集合用來描述可能的觀測結(jié)果，P是Y對應(yīng)的概率分布函數(shù)集合.若使用概率模型，一般而言需假設(shè)存在一個(gè)確定的分布P生成觀測數(shù)據(jù)Y.因此，通常使用統(tǒng)計(jì)推理的辦法確定集合P中誰是數(shù)據(jù)產(chǎn)生的原因.在機(jī)器學(xué)習(xí)中基于概率模型的方法有很多，例如貝葉斯模型、決策樹模型和線性回歸模型等.

南京大學(xué)Xu等[12]針對 Python 語言的動(dòng)態(tài)類型特點(diǎn)，利用機(jī)器學(xué)習(xí)得到從變量名稱到類型的概率模型，再根據(jù)數(shù)據(jù)流、屬性訪問等信息得到概率約束，最后設(shè)計(jì)概率推理模型，從而實(shí)現(xiàn)小語料情況下的變量類型推理.本文提出使用概率推理來允許傳播、聚合單個(gè)類型提示，并最終收斂于變量類型的概率.傳統(tǒng)的類型推理方法由于路徑敏感，所以對于python的類型推理并不適用.在python程序中有很多類型提示，然而這些類型提示中有很多是不確定不可靠的.所以此研究提出通過概率推理將所有不確定的類型提示關(guān)聯(lián)起來，通過程序構(gòu)件之間的關(guān)聯(lián)(例如變量之間的數(shù)據(jù)流)進(jìn)行傳播和聚合，最后計(jì)算收斂于變量類型的概率.這種新的思想能夠自然地對類型提示的不確定性建模，輕松處理動(dòng)態(tài)特性.實(shí)驗(yàn)的系統(tǒng)結(jié)構(gòu)由三個(gè)部分組成:變量名稱分類器、概率約束生成器和概率約束生成器類型推理引擎.首先，它通過對可以使用現(xiàn)有靜態(tài)類型推理技術(shù)進(jìn)行類型化的變量執(zhí)行機(jī)器學(xué)習(xí)來提取項(xiàng)目的命名約定；然后，從數(shù)據(jù)流、屬性訪問、類型檢查謂詞和變量名生成一組約束；接著，將這些生成的約束轉(zhuǎn)換為一個(gè)概率推理網(wǎng)絡(luò)因子圖，利用置信度傳播算法解析因子圖，得到每個(gè)變量的個(gè)體類型概率；最后，對計(jì)算出的類型概率(每個(gè)變量)進(jìn)行排序，并根據(jù)給定的閾值過濾出不太可能的類型.

Raychev等[13]提出了一種基于決策樹學(xué)習(xí)的精確通用概率模型學(xué)習(xí)方法，從大型代碼庫中學(xué)習(xí)代碼的概率模型來預(yù)測新程序，其關(guān)鍵思想是將學(xué)習(xí)代碼概率模型的問題描述為學(xué)習(xí)特定語言中的決策樹，而不是抽象語法樹，這樣可以在動(dòng)態(tài)計(jì)算的上下文中對程序元素的預(yù)測設(shè)置條件.此研究提出的是一種學(xué)習(xí)精確概率模型的新方法，該方法能在預(yù)測時(shí)自動(dòng)確定正確的上下文，關(guān)鍵的技術(shù)是遞歸地以類似于決策樹的方式分割訓(xùn)練數(shù)據(jù)，然后學(xué)習(xí)樹的每個(gè)分支更小的特定概率模型.此研究中擴(kuò)展和調(diào)整了經(jīng)典的ID3學(xué)習(xí)算法，使葉子不必對應(yīng)于無條件的最大似然估計(jì)，但可以使用基于復(fù)雜特征的概率模型來表示.這種新的基于決策樹的學(xué)習(xí)算法首先發(fā)現(xiàn)整個(gè)數(shù)據(jù)集的適當(dāng)分解，學(xué)習(xí)每個(gè)部分的最佳條件設(shè)置上下文，然后允許將概率模型用作獲得的決策樹的葉子.此方法被應(yīng)用到了Python和JavaScript構(gòu)建概率模型的任務(wù)之中.

Allamanis等[14]回顧了機(jī)器學(xué)習(xí)和統(tǒng)計(jì)自然語言處理方法應(yīng)用于源代碼的新興領(lǐng)域，關(guān)注于代碼的概率模型，并引入一個(gè)源代碼的分類概率模型.Seidel等[15]則實(shí)驗(yàn)了邏輯回歸、決策樹、隨機(jī)森林、神經(jīng)網(wǎng)絡(luò)等學(xué)習(xí)方法，定位與分析程序中的類型錯(cuò)誤.

3.3 基于深度學(xué)習(xí)的類型推理方法

在深度學(xué)習(xí)中[18]，深度置信網(wǎng)絡(luò)(Deep Belief Networks)是一種生成圖模型，通過訓(xùn)練其神經(jīng)元間的權(quán)重，可以使整個(gè)神經(jīng)網(wǎng)絡(luò)按照最大概率來生成訓(xùn)練數(shù)據(jù).不僅可以使用 DBN 識別特征、分類數(shù)據(jù)，還可以用它來生成數(shù)據(jù).它是由多層潛在變量組成的一類深度神經(jīng)網(wǎng)絡(luò)，在層之間具有連接但在每層內(nèi)的單元之間沒有連接.當(dāng)在沒有監(jiān)督的情況下對一組示例進(jìn)行訓(xùn)練時(shí)，深度置信網(wǎng)絡(luò)可以學(xué)習(xí)概率重建其輸入.然后這些層充當(dāng)特征檢測器.在該學(xué)習(xí)步驟之后，可以進(jìn)一步訓(xùn)練深度置信網(wǎng)絡(luò)以進(jìn)行分類.DBNs是由多個(gè)限制玻爾茲曼機(jī)層組成，一個(gè)典型的神經(jīng)網(wǎng)絡(luò)類型被“限制”為一個(gè)可視層和一個(gè)隱層，層間存在連接，但層內(nèi)的單元間不存在連接.隱層單元被訓(xùn)練去捕捉在可視層表現(xiàn)出來的高階數(shù)據(jù)的相關(guān)性.深度置信網(wǎng)絡(luò)通過采用逐層訓(xùn)練的方式，解決了深層次神經(jīng)網(wǎng)絡(luò)的優(yōu)化問題，通過逐層訓(xùn)練為整個(gè)網(wǎng)絡(luò)賦予了較好的初始權(quán)值，使得網(wǎng)絡(luò)只要經(jīng)過微調(diào)就可以達(dá)到最優(yōu)解.近年來，深度學(xué)習(xí)的研究越來越深入，在各個(gè)領(lǐng)域獲得了不少突破性的進(jìn)展.基于注意力機(jī)制的神經(jīng)網(wǎng)絡(luò)也逐漸成為了最近神經(jīng)網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)[19-20].

Wang等[16]提出了一種強(qiáng)大的表征學(xué)習(xí)算法，為了彌補(bǔ)程序語義信息與用于缺陷預(yù)測的特征之間的差距，通過深度學(xué)習(xí)的方法從源代碼中自動(dòng)學(xué)習(xí)程序的語義表示.具體來說，就是利用深度置信網(wǎng)絡(luò)從程序抽象語法樹中提取令牌向量，從而自動(dòng)學(xué)習(xí)語義特征，然后利用這些特征訓(xùn)練缺陷預(yù)測模型.此研究方法將訓(xùn)練集和測試集的源代碼中的標(biāo)記作為輸入，并從中生成語義特性，然后使用這些語義特性來構(gòu)建和評估用于預(yù)測缺陷的模型.實(shí)際過程中首先從訓(xùn)練集和測試集中的每個(gè)文件的源代碼中提取一個(gè)令牌向量.由于深度置信網(wǎng)絡(luò)需要整數(shù)向量形式的輸入數(shù)據(jù)，所以將在整數(shù)和令牌之間建立映射，并將令牌向量轉(zhuǎn)換為整數(shù)向量.為了生成語義特征，需要先使用訓(xùn)練集的整數(shù)向量來構(gòu)建深度置信網(wǎng)絡(luò).然后，利用深度置信網(wǎng)絡(luò)從訓(xùn)練集和測試集的整數(shù)向量中自動(dòng)生成語義特征.最后基于生成的語義特征，從訓(xùn)練集構(gòu)建缺陷預(yù)測模型，并在測試集上評估其性能.研究過程中的四個(gè)主要步驟：①將源代碼解析為令牌；②將令牌映射為整數(shù)標(biāo)識符，整數(shù)標(biāo)識符是深度置信網(wǎng)絡(luò)的期望輸入；③利用深度置信網(wǎng)絡(luò)自動(dòng)生成語義特征；④利用訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)的學(xué)習(xí)語義特征構(gòu)建缺陷預(yù)測模型并預(yù)測缺陷.實(shí)驗(yàn)顯示，與傳統(tǒng)方法相比，自動(dòng)學(xué)習(xí)的語義特性可以顯著提高項(xiàng)目內(nèi)部和跨項(xiàng)目缺陷預(yù)測.

遞歸神經(jīng)網(wǎng)絡(luò)(Recursive Neural Network)是具有樹狀階層結(jié)構(gòu)且網(wǎng)絡(luò)節(jié)點(diǎn)按其連接順序，對輸入信息進(jìn)行遞歸的人工神經(jīng)網(wǎng)絡(luò)，是深度學(xué)習(xí)算法之一 .它被視為循環(huán)神經(jīng)網(wǎng)絡(luò)的推廣 .當(dāng)遞歸神經(jīng)網(wǎng)絡(luò)的每個(gè)父節(jié)點(diǎn)都僅與一個(gè)子節(jié)點(diǎn)連接時(shí)，其結(jié)構(gòu)等價(jià)于全連接的循環(huán)神經(jīng)網(wǎng)絡(luò) .遞歸神經(jīng)網(wǎng)絡(luò)具有靈活的拓?fù)浣Y(jié)構(gòu)且權(quán)重共享，適用于包含結(jié)構(gòu)關(guān)系的機(jī)器學(xué)習(xí)任務(wù)，在自然語言處理領(lǐng)域有重要應(yīng)用.由于標(biāo)準(zhǔn)的RNN隨著遞歸往往會(huì)出現(xiàn)權(quán)重指數(shù)級爆炸和梯度消失的問題，會(huì)喪失學(xué)習(xí)到連接遠(yuǎn)距離信息的能力，于是出現(xiàn)了兩種新的遞歸神經(jīng)網(wǎng)絡(luò)的變體，分別是長短期記憶網(wǎng)絡(luò)(Long Short-Term Memory)和門控循環(huán)單元(Gated Recurrent Unit).其中，GRU是LSTM網(wǎng)絡(luò)的一種效果很好的變體，它較LSTM網(wǎng)絡(luò)的結(jié)構(gòu)更加簡單，而且效果也很好.

目前Hellendoorn等[17]提出了一種深度學(xué)習(xí)模型，它能夠理解哪些類型在特定的上下文和關(guān)系中是自然發(fā)生的，并能夠提供類型建議，即使它不能在一開始就推理出類型，但是這些建議往往都可以由類型檢查器進(jìn)行驗(yàn)證.此研究受到了現(xiàn)有的自然語言處理任務(wù)的啟發(fā)，比如詞性標(biāo)注和命名實(shí)體識別等.利用序列到序列(sequence-to-sequence)的模型，將一個(gè)令牌序列轉(zhuǎn)換為一個(gè)類型序列.為了很好地結(jié)合單詞左右兩邊的相關(guān)上下文，提出了一種雙向的遞歸神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，因?yàn)榇嬖谟性S多不同的遞歸神經(jīng)網(wǎng)絡(luò)模型，此研究中選用的是門控循環(huán)單元模型.雙向的遞歸神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)結(jié)合了兩個(gè)反向運(yùn)行的遞歸神經(jīng)網(wǎng)絡(luò)，一個(gè)向前遍歷序列，另一個(gè)反向遍歷序列.于是單個(gè)令牌的上下文表示形式稱為將正向和反向的狀態(tài)連接起來.此時(shí)，所形成的網(wǎng)絡(luò)體系結(jié)構(gòu)結(jié)社為每個(gè)令牌生成的注釋彼此獨(dú)立，這在自然語言中往往正確，但是在源碼中卻不一樣，因?yàn)樽兞靠梢栽谡麄€(gè)代碼中多次使用，但是它真正的類型與聲明時(shí)的類型相同，所以還不能夠忽略多個(gè)令牌之間的相互依賴關(guān)系.為了解決這個(gè)問題，文章還提出了一個(gè)一致性層作為標(biāo)準(zhǔn)雙向遞歸神經(jīng)網(wǎng)絡(luò)的拓展，提高了文件中類型注釋的一致性和準(zhǔn)確性.

4 具體實(shí)現(xiàn)

本章節(jié)將系統(tǒng)總結(jié)在基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理的實(shí)驗(yàn)實(shí)現(xiàn)中，所選取的代碼片段、主要的推理類型、采用的平臺、指令集體系結(jié)構(gòu)、操作系統(tǒng)和實(shí)現(xiàn)等情況.

4.1 代碼片段的選取

本文研究的所有基于機(jī)器學(xué)習(xí)進(jìn)行類型推理的方法都選擇以源代碼作為輸入.然而，源代碼的編程語言選擇有很多種，本文研究的文章中選擇的編程語言分別有Java，Python，JavaScript，Typescript等.Uri等[11]提出的用基于抽象語法樹路徑的表示方式學(xué)習(xí)條件隨機(jī)場中還使用到了C#.大部分研究中選擇的編程語言都是Python和JavaScript，Wang等[16]提到希望未來能將它們的方法擴(kuò)展到C/C++的項(xiàng)目之中.很少有研究選擇C/C+的原因可能是這兩個(gè)程序語言的結(jié)構(gòu)更加復(fù)雜，依賴信息更多.

4.2 推理類型

本節(jié)討論在不同的類型推理方法中所捕獲的不同類型.研究發(fā)現(xiàn)，類型推理可以針對許多不同的類型，包括初始類型、類、數(shù)組、字符串、抽象類和函數(shù)類型等.但是沒有一項(xiàng)工作是試圖恢復(fù)所有類型，如聯(lián)合體幾乎沒有工作支持，而抽象類則受到比較少的關(guān)注.對于類型推理的最終輸出，大多數(shù)方法都是生成標(biāo)識變量的單個(gè)類型.基本類型是最小的類型單元，由編程語言作為內(nèi)置類型提供，如Integer、char、float、pointer等.目前基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理的主要推理類型，都是圍繞基本類型來討論的.類是一種面向?qū)ο笥?jì)算機(jī)編程語言的構(gòu)造，由某種特定的元數(shù)據(jù)所組成的內(nèi)聚的包，它描述了所創(chuàng)建的對象共同的屬性和方法.面向?qū)ο蟪绦蛑械念愐彩穷愋屯评淼囊粋€(gè)流行目標(biāo)，但是目前方法提及到的對于類的推理都是一些可以單一標(biāo)記的類型，對于一些復(fù)雜的構(gòu)造類型則無法推理了，更不用說遞歸類型了.遞歸類型是存儲遞歸指針的聚合類型，這種復(fù)雜類型涉及到更多更加復(fù)雜的程序操作，需要將每一步的復(fù)雜類型分析清楚十分困難.數(shù)組是同一類型元素序列的常見內(nèi)置類型，在數(shù)組中，所有元素都具有相同的類型，一旦推理出元素的類型，就知道數(shù)組的類型了.字符串是具有特定編碼的字符序列，字符串很難從底層表示(如字符數(shù)組)中區(qū)分出來，所以對于區(qū)分?jǐn)?shù)組和字符串的方法，以及標(biāo)識它們的類型形式，目前的相關(guān)研究并不多.函數(shù)類型能夠捕獲函數(shù)的原型，即參數(shù)和返回值的數(shù)量、位置和類型，恢復(fù)函數(shù)的類型，獲取函數(shù)參數(shù)類型和返回值類型，也是目前對于恢復(fù)函數(shù)類型的一項(xiàng)挑戰(zhàn).

4.3 體系結(jié)構(gòu)和操作系統(tǒng)

Wang等[16]進(jìn)行了幾個(gè)實(shí)驗(yàn)來研究提出的語義特征的性能，并與現(xiàn)有的傳統(tǒng)特征進(jìn)行了比較.他們選擇在一臺2.5 GHz i5-3210M、4GB RAM的機(jī)器上進(jìn)行實(shí)驗(yàn).Raychev等[10]則是在一臺32核機(jī)器上執(zhí)行了性能評估，該機(jī)器有4個(gè)2.13 GHz Xeon處理器，運(yùn)行Ubuntu 12.04和64位OpenJDK Java 1.7.0_51.其他的實(shí)驗(yàn)研究論文中并未詳細(xì)說明實(shí)驗(yàn)方案中具體選用實(shí)施的體系結(jié)構(gòu)和操作系統(tǒng).

5 評估測試方法

本節(jié)將討論不同的實(shí)驗(yàn)研究過程中都是如何評估基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理的效果的，將從評估基準(zhǔn)和評估方法兩個(gè)方面進(jìn)行討論.

5.1 評估基準(zhǔn)

在基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理的研究中，為了考量實(shí)際的實(shí)驗(yàn)效果，研究中往往會(huì)采用一些度量值來量化分析推理結(jié)果.評估基準(zhǔn)基本上都是對實(shí)驗(yàn)結(jié)果的準(zhǔn)確性和一致性進(jìn)行預(yù)測評估，部分實(shí)驗(yàn)同時(shí)還會(huì)綜合評估時(shí)間效率的問題.常用到的四個(gè)度量值：精確率、召回率、F1參數(shù)和準(zhǔn)確率，這四個(gè)指標(biāo)被廣泛用于評估類型推理技術(shù).準(zhǔn)確率反映了對于給定的測試數(shù)據(jù)集進(jìn)行類型推理，正確推理的樣本數(shù)與總樣本數(shù)之比.準(zhǔn)確率表示了預(yù)測為真的樣本中有多少是真正的樣本，它是針對實(shí)際類型推理的預(yù)測結(jié)果而言的.召回率則說明了樣本中的正例有多少被預(yù)測正確了，它是針對原來的樣本而言的.F1參數(shù)則同時(shí)考慮到了精確率和召回率.

5.2 評估方法

實(shí)驗(yàn)過程中的評估方法基本上都是首先選擇從大量的訓(xùn)練語料庫中進(jìn)行機(jī)器學(xué)習(xí)，然后根據(jù)文章中提出的基于機(jī)器學(xué)習(xí)進(jìn)行類型推理的方法獲取實(shí)驗(yàn)結(jié)果，再計(jì)算相應(yīng)的精確率、召回率、F1參數(shù)等進(jìn)行有效的評估，并與之前有相似實(shí)驗(yàn)方法的文章進(jìn)行對比討論，總結(jié)評估文章的改進(jìn)和優(yōu)勢.Xu等[12]將概率圖模型與Raychev等[10]的實(shí)驗(yàn)?zāi)Ｐ瓦M(jìn)行了對比，認(rèn)為他們的方法實(shí)現(xiàn)了局部最優(yōu)性，對單個(gè)變量具有更好的精確度和召回率.Raychev等[13]將計(jì)算出的新的決策樹模型的準(zhǔn)確率與之前的PCFG、3-garm和DeepSyn進(jìn)行了對比，顯示準(zhǔn)確率有了明顯提升.

6 討 論

本節(jié)將根據(jù)現(xiàn)有的用機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理，討論目前實(shí)驗(yàn)方案中的局限性、存在的問題以及未來需要迎接的挑戰(zhàn).

與傳統(tǒng)的基于規(guī)則的類型推理方法相比，基于統(tǒng)計(jì)與機(jī)器學(xué)習(xí)的類型推理方法具有較好的魯棒性，能夠在不完整上下文的情況下進(jìn)行推理，解決更多的實(shí)際問題，并為更多的應(yīng)用場景提供服務(wù).但是目前這些工作還存在很多不足.首先仍然比較依賴于分析的程序符合語法要求，否則無法正確有效地提取出所需要的特征進(jìn)行學(xué)習(xí)和推理.其次，目前的方法所能支持推理的類型比較有限，大多數(shù)為簡單的類型，如int、float、char等這些比較單一的類型，對于一些復(fù)雜的構(gòu)造類，尤其是遞歸類型和抽象類等并沒有相應(yīng)的具體方法進(jìn)行推理，而對于復(fù)雜類型的推理在程序分析中顯得更加重要，能夠幫助我們更好地了解參數(shù)信息，尋找更深層次的錯(cuò)誤信息.最后，雖然通常認(rèn)為所有提出的類型推理的方法可能是通用的，但是大多數(shù)方法都是在特定的編程語言和體系結(jié)構(gòu)組合上進(jìn)行評估的，而且這些方法大多數(shù)選擇python和JavaScript這些相對來說結(jié)構(gòu)更加簡單的程序語言，然后對于C/C++等約束條件更多更復(fù)雜的程序語言來說，比較少涉及.

對于未來的工作，可以基于目前所存在的問題進(jìn)行改進(jìn).一方面是希望基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理能夠更少的依賴于程序本身的語法分析，使得對于類似于帶有未解析的宏的程序片段等情況下，也能夠采用機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理.另一方面是擴(kuò)展類型推理的程序語言和推理類型.將基于機(jī)器學(xué)習(xí)進(jìn)行類型推理的方法應(yīng)用于更多的程序語言，而不僅僅局限于python和JavaScript這些結(jié)構(gòu)相對來說比較簡單的語言.對于推理的類型應(yīng)該擴(kuò)展到一些復(fù)雜的類型，比如數(shù)組、字符串、遞歸類型、聯(lián)合體、抽象類，還有函數(shù)類型，包括函數(shù)中的參數(shù)類型和返回值類型等.

7 總 結(jié)

傳統(tǒng)的類型推理方法都是基于規(guī)則和語法結(jié)構(gòu)的，然而隨著軟件技術(shù)的發(fā)展，在新的軟件應(yīng)用場景中，需要研究新的在缺乏上下文與語法規(guī)則的前提下對程序片段進(jìn)行類型推理的方法.基于機(jī)器學(xué)習(xí)的方法進(jìn)行類型推理是一個(gè)比較具有挑戰(zhàn)性的問題，基于它對程序錯(cuò)誤檢測、程序優(yōu)化、代碼補(bǔ)全、錯(cuò)誤定位等方面都有很大的幫助，人們在這一方面進(jìn)行了大量的研究，涌現(xiàn)出了許多基于機(jī)器學(xué)習(xí)進(jìn)行類型推理的方法.本文研究了已存在的基于機(jī)器學(xué)習(xí)進(jìn)行類型推理的方法，并從幾個(gè)重要方面進(jìn)行了系統(tǒng)化的總結(jié)，包括實(shí)驗(yàn)方法、具體的實(shí)現(xiàn)和評測方法等，還討論了目前已有的類型推理方法的局限性、存在的問題和未來需要解決的問題.