(武漢大學 計算機學院， 湖北 武漢 430072)

1 類型推理介紹

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

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

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

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

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

2 基于機器學習的類型推理

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

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

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

3 方 法

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

表1 實驗方法和程序語言的總結

3.1 基于條件隨機場的類型推理方法

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

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

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

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

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

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

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

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

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

3.3 基于深度學習的類型推理方法

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

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

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

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

4 具體實現(xiàn)

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

4.1 代碼片段的選取

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

4.2 推理類型

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

4.3 體系結構和操作系統(tǒng)

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

5 評估測試方法

本節(jié)將討論不同的實驗研究過程中都是如何評估基于機器學習的方法進行類型推理的效果的，將從評估基準和評估方法兩個方面進行討論.

5.1 評估基準

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

5.2 評估方法

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

6 討 論

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

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

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

7 總 結

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