程序合成研究進展

張銀珠 董威 劉斌斌

摘 ?要： 在軟件工程領域中，程序自動合成是一個非常核心的研究方向，并且在軟件開發活動如此普及的社會中有望成為未來軟件工程變革的核心技術。隨著多年該領域的研究發展，已經衍生出了很多種不同的流派與技術路線。本文針對程序合成領域的發展現狀與技術研究進展做了綜合敘述，并探究目前程序合成領域所面臨的挑著與未來一段時間內需要解決的問題。

關鍵詞： 程序合成;搜索排序;程序結構

中圖分類號： TP311.51 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.005

本文著錄格式：張銀珠，董威，劉斌斌. 程序合成研究進展[J]. 軟件，2019，40（4）：2530

【Abstract】： Automatic program synthesis has become a core research direction in the field of software engineering. And it is expected to become the core technology of future software engineering with software development becoming more and more popular in current society. There exists different schools and technical routes in the research of program synthesis. In this paper， a comprehensive description of the development status and technology progress of program synthesis is given and we also explores the challenges facing the current field of program synthesis and the problems that need to be solved in the future.

【Key words】： Program synthesis; Search and rank; Program structure

0 ?引言

隨著軟件工程的發展，軟件開發愈加成為互聯網以及其他軟件相關企業的主要活動。因此軟件開發技能成為軟件從事企業人員的必備技能，即使在非必需的情況下，掌握基本的軟件開發知識，也能夠幫助工作人員更好的適應信息化場景的工作及要求。軟件開發人員的工作通常是復雜多樣并需要重復勞動，他們需要時常搜索并學習不同領域的開發方法，這對開發人員的要求大大提高，并極大增加開發人員的負擔，拖累開發工作的進程。為了將軟件開發人員從復雜繁重的開發工作中解放出來，程序合成成為未來軟件工程的重點研究與投入方向之一。

1 ?程序合成的概念

程序自動合成又稱程序綜合技術，旨在圍繞用戶意圖，合成出符合用戶需求的軟件代碼的活動。程序合成的目的是讓機器合成出代碼，能夠減輕程序員的負擔，并有望將編程人員將關注點放到軟件的高層設計上，而不用花費過多時間在細節實現上。研究人員Sumit Gulwani[1]指出，代碼自動生成過程一般分為三個階段，用戶需求的描述，程序搜索空間的表述，設計合適的搜索排序技術。這里每個階段都涉及到不同的方法，適用于不同的場景，例如用戶需求可以利用規約形式描述，也可以用自然語言描述。需求的描述越抽象，進行程序合成越困難。也就是說利用自然語言描述的需求來生成代碼面臨更多的挑戰，包括需要克服自然語言與程序需求之間的差距和程序需求與實際程序代碼之間的鴻溝。

2 ?程序合成的關鍵要素

程序合成有三個關鍵要素[1]，用戶意圖表述，搜索空間描述以及設計合適的搜索技術。用戶意圖表述有多種方式，邏輯規約，輸入輸出數據對，程序路徑以及自然語言等。該如何選擇不同的需求描述取決于具體的任務背景。邏輯規約用來描述程序輸入輸出間的邏輯關系，可以精確又簡明的描述程序所遵循的規范，但是對于用戶來說很難寫出完整的程序邏輯規約。終端用戶通常不如專家的編碼水平，因此更傾向于提供自然性的需求描述如自然語言等。搜索空間通常需要在需求符合性和程序合成效率間做一個平衡。一方面程序搜索空間需要足夠大到能夠囊括用戶需求所有可能的程序，另一方面為了提升程序合成的效率，需要采取更有效的搜索方法將搜索空間限定在小的范圍內。例如搜索空間可以被限定為所有操作組成空間的一個子集，或者在一個領域特定語言的范圍內。搜索技術與排序技術類似，目的是如何更有效的搜索出與需求接近的結果程序等。常見的搜索技術有枚舉搜索、基于約束求解的搜索或者兩者的結合等等。枚舉搜索將所有可能的程序按照某個順序一一列舉，通常效率較低，因此更常見的發方法是在傳統的枚舉搜索的基礎上加上啟發式的剪枝方法來提升搜索效率。基于約束求解的搜索通常分為兩個過程，約束生成過程和具體求解過程。約束生成過程是將需求解程序搜索空間用邏輯描述其規范并轉換成約束的過程，生成約束通常需要對程序可能的控制流以及控制流下行為進行編碼。求解約束的過程是在約束創建完成后，在約束所描述的搜索空間內按照某種方式列舉可行解的過程，例如可以單純使用枚舉的方法，也可以添加其他的約束來改變枚舉的順序。

3 ?程序合成的常見方法

程序自動生成分為幾種不同的技術路線，他們或利用不同的需求描述語言，或針對不同的適用場景設計不同的搜索算法。從不同的角度來看，程序合成方法可以被劃分為不同的類別，如圖1所示。

3.1 ?從規約選取角度進行分類

如圖1所示，從規約選取的角度來看，程序合成可以被分為基于示例（Programming by Examples）、基于框架（Sketch）、基于自然語言以及基于邏輯規約的程序合成方法。

（1）基于示例的程序合成（Programming by Examples）

基于示例的程序合成需要用戶提供輸入輸出示例作為需求描述，例如一個廣為人知的應用就是在Excel中的Flash Fill[4，18]功能。用戶在表格中填寫需求相關的多個輸入輸出對，在有解的情況下，工具能夠有限時間內找出合適的實現代碼，如圖2所示。

Mehdi Manshadi[9]等提出了使用<輸入-輸出>測試對和自然語言需求描述結合的方式來指導程序自動合成，該方法能夠提升僅在單一方法進行程序合成的效果。首先利用<輸出-輸出>測試對搜索得到一個滿足所有數據對的程序集合，據此指導程序合成的過程。此外他們還提出可以利用群體智能來指導基于自然語言的程序自動生成[14]，類似于“眾包”的思想，利用大量不同用戶為同一個自然語言描述的需求來提供不同的<輸入-輸出>測試對，然后進行程序合成，因此該方法能夠更好的捕捉到自然語言所描述的真實需求。

（2）基于Sketch（框架）的程序合成

基于框架（Sketch）的程序合成通常更加關注程序結構，例如while，if等循環語句，一個Sketch是不完整的部分程序，代表一個需要填充的程序框架。基于Sketch的程序合成允許用戶提供不完整的程序框架，合成工具通過語法指導或者其他方式進行程序合成。例如Rastislav Bodik等人[10]對基于Sketch的程序合成進行了總結并提出一些方法有助于程序合成在復雜Sketch上的合成過程，例如他們提出可以允許用戶提供部分程序框架的時候擴展描述語言，也可以通過增加反例的形式來對程序合成過程加速。基于Sketch的程序合成還可以與機器學習的方法學習起來，通過抽取大量Sketch與其實現代碼的數據對，利用機器學習模型學習其中的映射關系，例如Vijayaraghavan Murali等人[11]提出利用深度學習中的RNN時序模型通過訓練從大量Android代碼抽取出的<證據，Sketch>數據對，得到能夠根據用戶提供的證據預測程序Sketch的模型，然后通過語法指導的填充過程，得到填充后的程序。

（3）基于自然語言的程序合成

基于自然語言的程序合成需要用戶提供自然語言作為需求描述，程序合成利用自然語言或者將自然語言與別種形式的需求描述相結合生成出程序。由于自然語言通常與程序代碼之間有著較大的鴻溝，因此該方法的挑戰主要在于如何克服自然語言與機器語言之間的跨度上。相關工作如Aditya Desai等人[12]提出可以通過大量的<自然語言，領域特定語言>數據訓練出通過用戶給與的自然語言描述翻譯出領域特定語言，然后利用領域特定語言進行程序合成的方法。并通過在文本編輯，智能助手系統等領域的程序合成中驗證了其效果。Navid Yaghmazadeh等人[13]提出可以將自然語言處理，程序合成與自動程序修復領域結合起來，允許用戶給出一個自然語言描述，首先利用語義分析功能將其轉換為一個SQL查詢的Sketch，然后利用類型指導的程序合成方法合成出具體的SQL語句。由于用戶自然語言通常過于抽象，不能精確的反映出數據庫的機制，于是他們在方法中使用了錯誤修復技術，對得到的SQL Sketch進行合理性的修復知道得到高質量的SQL查詢語句為止。

（4）基于邏輯規約的程序合成

基于邏輯規約的程序合成方法需要用戶針對程序功能提供完整的規約描述，規約可能用某種語法表示成公式。對于復雜需求，一般用戶來說寫出完整的程序規約比較困難，因此這種方法在應用中很少被用到，實用性不夠好。

3.2 ?從搜索策略角度進行分類

從采用的搜索策略的角度進行分類，程序合成方法又可以分為，基于語法指導的、基于代碼搜索的、基于深度學習以及基于API（組件）的程序合成。

（1）基于語法指導的程序合成

基于語法指導的程序合成一般需要用戶提供程序的輸入輸出規約或者語法框架，程序合成工具通過具體搜索策略或者符號搜索找到滿足用戶規約的程序，符號搜索需要從用戶規約中抽取出程序需要滿足的約束，然后利用約束求解器得到解。Kangjing Huang[17]等人提出可以將兩種搜索策略結合，利用決策樹的高度枚舉從短到長的程序代碼，在每個固定長度的枚舉過程中，通過舉反例的形式達到更精確的搜索。他們在一系列的benchmark上證明了該方法具有優秀的效果。Rajeev Alur[19]等人描述了幾種方法針對語法指導的程序合成，包括激活學習、增加反例以及隨即搜索等，并執行合理的benchmarks對比不同方法的效果。他們還對比了語法指導的程序合成比賽中驗證過1500個benchmark的6個新的工具[20]，并分析了其效果。

（2）基于代碼搜索的程序合成

基于搜索的程序合成方法結合了經典的代碼搜索過程，在程序合成初期，利用代碼搜索得到與需求最接近的代碼結果，在此基礎上再進行程序合成。基于搜索的程序合成方法能有效利用程序代碼搜索的結果縮小程序合成的時間復雜度和空間復雜度，該方法首先需要針對用戶需求進行代碼搜索，可針對自然語言或代碼片段、程序關鍵詞進行搜索，得到搜索出的代碼片段之后，再利用現有程序綜合技術得到符合需求的程序。相關工作例如Swim[2]，能夠針對用戶提供的需求規約，檢索出相關的API名稱，然后通過檢索API使用模式集合找到最可能用的API模式序列，并據此包裝生成代碼片段。相關工作還有Hunter[3]，能夠根據用戶提供的自然語言描述，檢索出相關代碼，并根據類型距離對檢索結果排序，最后通過整數線性規劃（Integer Linear Programing）將程序綜合問題轉化為基于API的代碼生成過程，并利用現有工具生成出符合需求的程序。基于搜索的程序自動生成的效果與前期代碼搜索結果息息相關，如何設計合理的搜索排序技術有效的找出與用戶需求最匹配的代碼成為該方法的關鍵點之一。基于搜索的程序合成技術利用代碼搜索的結果，能夠有效的縮小程序綜合的空間，提升程序合成的時間效率，成為很多程序合成技術的首要過程。

（3）基于深度學習的程序合成

近幾年，人工智能行業迅猛發展，研究人員開始研究如何使用更加智能化的方法實現程序自動生成。機器學習等相關方法一般需要大量數據集來訓練，而隨著互聯網的繁榮發展，Github等代碼托管平臺上存儲了大量的項目代碼使得利用機器學習來學習如何寫代碼成為了可能。根據方法的風格不同，基于深度學習的程序合成方法一般分為兩種類別，一種是模型原理不可解釋的“黑盒”方法，另一種是能夠直接生成可解釋代碼的“代碼生成派”方法。黑盒的方法類似于一個黑箱子，直接利用大量數據集訓練得到代碼生成的規則，規則被表示為模型的參數，因此具有不可解釋性。“黑盒派”方法對用戶來說不易于使用和修改，因為用戶并不能理解模型到底學習出了什么樣的編程規則。而“代碼生成派”則能夠直接根據需求生成出顯示的程序代碼，更加符合人類所想象的機器自動編程的狀態。在模型的使用階段，用戶只需提供一至多個輸入輸出數據對，模型能夠根據輸入輸出數據對，提取高層特征，預測出需求所需要的各種操作原語的概率，結果概率越高的操作原語，越有可能在任務的實現代碼中用到。相關工作如DeepCoder[5]，一種使用輸入輸出樣本的深度學習解決編程競賽風格的方法。該方法屬于典型的代碼生成派工作，能夠通過訓練神經網絡來預測有輸入到輸出的程序屬性。Facebook在該領域也有所研究，例如其選擇層級生成CNN網絡結構[6]（Hierarchical Generative Convolutional Neural Network，又稱為HGCNN），利用隨機生成的程序，給定一些輸入，運行程序得到輸出來構造數據集，因此屬于無監督學習的過程。

（4）基于API（組件）的程序合成

基于API的程序合成旨在根據用戶意圖生成出純API的程序代碼。其特點是結果程序中只包含API以及控制結構，不包含常量的聲明、運算等語句。由于軟件模塊化程度是軟件開發過程中衡量項目質量的一個重要標準，因此在軟件開發過程中，提倡將不同功能封裝起來，降低軟件代碼的耦合性，以減少模塊之間的依賴，因此基于API的程序合成方法無疑是順應軟件開發的趨勢并且更方便用戶來復用代碼。典型的基于API的程序自動合成工作如Ye Feng[7]等題出利用PetriNet來對API中方法間的關系進行建模，用戶需要提供函數聲明和測試用例作為需求描述，該方法能夠遍歷PetriNet的可達性圖來找到符合用戶聲明的API序列，并執行測試用例直到找到滿足需求的解為止。此外他們也提出可以由示例驅動的基于API的程序合成方法[15]，可以處理特定領域任務例如表格等文檔的處理與轉換，該方法將基于SMT的約束求解方法和基于API的程序合成相結合，并采取局部評估的方法，能夠針對小規模的java程序取得一定的效果。Sumit Gulwani等人[16]提出利用用戶提供的規約描述，在組件庫中生成出loop-free的研究，通過將用戶的規約抽取成約束，然后利用約束求解的過程生成程序。該研究能夠做到探索超過2010的大小的程序搜索空間，例如能夠合成出長達20行的loop-free的位運算程序代碼。

4 ?程序合成面臨的挑戰

現有研究工作[1]指出，程序合成主要面臨來自于兩個維度的挑戰，一個是難掌控的程序搜索空間，一個是用戶意圖的多樣性。

任何程序合成方法都包含著在搜索空間搜索的過程，而程序對應的搜索空間都隨著其程序規模的增加呈指數增加趨勢，大量有可能的候選結果，如何有效排序，提升程序合成的效率，也是研究人員不停在鉆研的問題。隨著過去二十年里一些技術和算法上的突破，摩爾定理和約束求解的發展使得在合理時間內可以搜索更大的搜索空間。但盡管現在的程序合成能夠產生一些符合需求的代碼片段，程序合成依然不能產生大規模的現實世界的代碼，并且在工業界應用也非常受限。例如右Phothilimthana等人[8]提出的能夠合成出更短的程序的超優化技術可以探索1079大小的程序空間。而一個能夠實現MD5哈希函數的合成器就需要探索多達一萬五千多個程序，遠遠超過現在程序合成方法所能探索的空間。因此在程序合成領域，新的搜索算法以及領域特定研究仍然面臨著艱巨的挑戰并有待于進一步探索。

如何精準的表達并解釋用戶意圖是程序合成面臨的第二大挑戰，最初的用戶意圖通常用程序邏輯規約來表示，這通常是針對一些演繹合成方法。最簡單的功能例如字符串操作，針對一些輸入輸出規約通常會有數百萬的程序與之一致，需要用戶提供簡單的邏輯規約即可。但一旦問題變得稍微復雜，用戶很難想象需求會有怎樣完整的規約，編寫完整的規約對用戶來說就像編寫程序一樣復雜，非常不友好。近些年程序需求描述更加偏向自然語言化的趨勢，用戶可以很輕松的用自然語言描述其所需要的功能，但這也帶來了需求描述和實現代碼之間的距離更加遠，需要研究更有效的算法來將自然語言程序翻譯成符合需求的代碼。如何在減輕用戶負擔的基礎上探索更好的用戶意圖表述方式成為程序自動合成研究所面臨的另一挑戰。

5 ?討論與展望

近年來，程序合成技術取得了多方面的進步，從搜索算法到程序和成框架上都在隨著計算機研究熱點而有所改變。就目前整體取得的進展和面臨的挑戰來說，我們認為從以下幾個方面是未來一段時間內程序合成技術有待于解決的階段性難題。

（1）人機交互

程序合成技術通常面臨的用戶水平參差不齊，對于一些剛剛使用程序合成工具的用戶來說很難一次性提供完整的需求描述，因此良好的人機交互和階段性反饋能夠給程序合成工具帶來更好的用戶體驗和使用效果。并且經過用戶反復修改規約描述得到的合成代碼，往往能夠更加接近用戶需求的解。現有的程序合成方法鮮有可方便用戶反饋調式的工作出現，而程序合成技術要想更好的落地實施，在其研究中占主要的不應該僅僅是內部算法，更不能缺少的是良好的用戶體驗和易用性。

（2）多元化需求描述

過去的程序合成算法中探索了多種用戶意圖描述的方法，從最初的程序規約到后來更加易用的自然語言。然而只使用一種輸入作為需求描述往往不具有普適性，比如初級用戶難以寫出完美的程序規約來約束程序合成過程，而僅使用自然語言雖然減輕了用戶負擔卻又給程序合成過程帶來了較為不確定的空間描述，導致用戶意圖過于抽象，合成不出理想的代碼結果。正如如今的軟件開發過程講究的是協同合作而不是單一決策一樣，未來一段時間內程序合成有必要探索如何結合多種形式的輸入，達到一種資源匯聚的效果。將自然語言、規約描述、關鍵詞描述等多種輸入結合能夠更好的減輕用戶負擔，避免用戶難以針對一種需求描述方法寫出完善的規約。

（3）智能化程序合成

隨著人工智能的火熱發展，研究學者們更希望能夠用智能化的方法來合成程序。雖然已經產生了“黑盒派”以及“代碼生成派”等相關研究工作，但這些方法都處于研究的初期階段，無法很好的在現有需求上產生應用，因此機器自動編碼領域仍有很長一段路要走。類似于Github等互聯網代碼托管平臺已經存儲了大量的項目代碼，這給以深度學習訓練為核心來實現程序合成的方法提供了良好的契機。因此未來很長一段時間內將會有大量的研究工作將重心放在基于深度學習的程序自動合成上，如何更好的挖掘出先驗知識中的編碼規范來指導程序自動合成，成為軟件工程領域當前一個熱點研究領域。

6 ?結束語

信息化發達的互聯網時代已經持續了很多年，使得軟件開發活動在社會發展中一直占有重要地位并不斷演化前進。現如今軟件開發規模的復雜性使得人們更加追求良好的編程規范和高效的編碼效率，因此程序自動合成領域在近年重新成為軟件工程領域的研究熱點。但程序自動合成距離能夠產生工業應用的那天還很遙遠，無論在搜索空間效率上，還是在用戶交互的可用性上都沒有達到一個良好的效果。而人工智能的發展給程序自動合成帶來了新的方法流派，未來程序合成技術還有更多方向需要繼續探索前進。

參考文獻

[1] S. Gulwani， O. Polozov and R. Singh. Program Synthesis. Foundations and Trends? in Programming Languages， vol. 4， no. 1-2， pp. 1–119， 2017.

[2] Raghothaman M， Wei Y， Hamadi Y. SWIM： synthesizing what I mean： code search and idiomatic snippet synthesis. In： Proc. of the 38th Intl Conf. on Software Engineering. ACM， 2016： 357-367.[doi： 10. 1145/2884781. 2884808]

[3] Wang Y， Feng Y， Martins R， et al. Hunter： next-generation code reuse for Java. In： Proc. of the 24th ACM SIGSOFT Intl Symp. on Foundations of Software Engineer. ACM， 2016： 1028-1032.[doi： 10. 1145/2950290. 2983934]

[4] Gulwani S， Esparza J， Grumberg O， et al. Programming by Examples （and its applications in Data Wrangling）. Verific-ation and Synthesis of Correct and Secure Systems. IOS Press， 2016.

[5] Balog M， Gaunt A L， Brockschmidt M， et al. DeepCoder： Learning to Write Programs. In： Proc. of the 5th Intl Conf. on Learning Representations. 2017.

[6] Gong Q， Tian Y， Zitnick C L. Unsupervised Program Induction with Hierarchical Generative Convolutional Neural Networks. In： Proc. Of the 5th Intl Conf. on Learning Representations.

[7] Feng Y， Martins R， Wang Y， et al. Component-based synthesis for complex APIs. In： Proc. of the 44th Annual ACM SIGPLANSIGACT Symp. on Principles of Progra-mming Languages. 2017： 599-612. [doi：10.1145/3093333. 3009851]

[8] Phitchaya Mangpo Phothilimthana， Aditya Thakur， Rastislav Bodík， and Dinakar Dhurjati. Scaling up superoptimization. In Proceedings of the 21st International Conference on Architectural Support for Programming Languages and Operating System （ASPLOS）， pages 297-310， 2016.

[9] Manshadi M H， Gildea D， Allen J F. Integrating Programming by Example and Natural Language Programming. In： Proc. of the 27th AAAI Conf. on Artificial Intelligence. 2013. AAAI Conf. on Artificial Intelligence. 2013.

[10] Bodik R， Solar-Lezama A. Program synthesis by sketching[J]. Dissertations & Theses - Gradworks， 2008.

[11] Murali V， Chaudhuri S， Jermaine C. Bayesian Sketch Learning for Program Synthesis[J]. 2017.

[12] Desai A， Gulwani S， Hingorani V， et al. Program Synthesis using Natural Language[J]. 2016.

[13] Yaghmazadeh N， Wang Y， Dillig I， et al. Type- and Content-Driven Synthesis of SQL Queries from Natural Language[J]. 2017.

[14] Manshadi M， Keenan C， Allen J. Using the crowd to do natural language programming. In： Proc. of the 26th AAAI Conf. on Artificial Intelligence， Workshop on Human-Com-puter Interaction. 2012.

[15] Feng Y， Martins R， Van Geffen J， et al. Component-based synthesis of table consolidation and transformation tasks from examples. In： Proc. of the 38th ACM SIGPLAN Conf. on Programming Language Design and Implementation. ACM， 2017： 422-436.[doi： 10. 1145/3062341. 3062351]

[16] Gulwani S， Jha S， Tiwari A， et al. Synthesis of loop-free programs[J]. ACM SIGPLAN Notices， 2011， 46（6）： 62.

[17] Huang K， Qiu X， Tian Q， et al. Reconciling Enumerative and Symbolic Search in Syntax-Guided Synthesis[J]. 2018.

[18] Gulwani， S.， Harris， W. R.， Singh， R.： Spreadsheet data manipulation using examples. Commun. ACM 55（8）， 97–105 （Aug 2012）， http：//doi.acm.org/10.1145/2240236.2240260

[19] Alur R， Bodik R， Juniwal G， et al. Syntax-guided synthesis[C]// Formal Methods in Computer-aided Design. IEEE， 2013.

[20] Alur R， Fisman D， Singh R， et al. SyGuS-Comp 2017： Results and Analysis[J]. 2017.