張銀珠 董威 劉斌斌

摘 ?要： 在軟件工程領(lǐng)域中，程序自動(dòng)合成是一個(gè)非常核心的研究方向，并且在軟件開(kāi)發(fā)活動(dòng)如此普及的社會(huì)中有望成為未來(lái)軟件工程變革的核心技術(shù)。隨著多年該領(lǐng)域的研究發(fā)展，已經(jīng)衍生出了很多種不同的流派與技術(shù)路線(xiàn)。本文針對(duì)程序合成領(lǐng)域的發(fā)展現(xiàn)狀與技術(shù)研究進(jìn)展做了綜合敘述，并探究目前程序合成領(lǐng)域所面臨的挑著與未來(lái)一段時(shí)間內(nèi)需要解決的問(wèn)題。

關(guān)鍵詞： 程序合成;搜索排序;程序結(jié)構(gòu)

中圖分類(lèi)號(hào)： TP311.51 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.005

本文著錄格式：張銀珠，董威，劉斌斌. 程序合成研究進(jìn)展[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 ?引言

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

1 ?程序合成的概念

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

2 ?程序合成的關(guān)鍵要素

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

3 ?程序合成的常見(jiàn)方法

程序自動(dòng)生成分為幾種不同的技術(shù)路線(xiàn)，他們或利用不同的需求描述語(yǔ)言，或針對(duì)不同的適用場(chǎng)景設(shè)計(jì)不同的搜索算法。從不同的角度來(lái)看，程序合成方法可以被劃分為不同的類(lèi)別，如圖1所示。

3.1 ?從規(guī)約選取角度進(jìn)行分類(lèi)

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

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

基于示例的程序合成需要用戶(hù)提供輸入輸出示例作為需求描述，例如一個(gè)廣為人知的應(yīng)用就是在Excel中的Flash Fill[4，18]功能。用戶(hù)在表格中填寫(xiě)需求相關(guān)的多個(gè)輸入輸出對(duì)，在有解的情況下，工具能夠有限時(shí)間內(nèi)找出合適的實(shí)現(xiàn)代碼，如圖2所示。

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

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

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

（3）基于自然語(yǔ)言的程序合成

基于自然語(yǔ)言的程序合成需要用戶(hù)提供自然語(yǔ)言作為需求描述，程序合成利用自然語(yǔ)言或者將自然語(yǔ)言與別種形式的需求描述相結(jié)合生成出程序。由于自然語(yǔ)言通常與程序代碼之間有著較大的鴻溝，因此該方法的挑戰(zhàn)主要在于如何克服自然語(yǔ)言與機(jī)器語(yǔ)言之間的跨度上。相關(guān)工作如Aditya Desai等人[12]提出可以通過(guò)大量的<自然語(yǔ)言，領(lǐng)域特定語(yǔ)言>數(shù)據(jù)訓(xùn)練出通過(guò)用戶(hù)給與的自然語(yǔ)言描述翻譯出領(lǐng)域特定語(yǔ)言，然后利用領(lǐng)域特定語(yǔ)言進(jìn)行程序合成的方法。并通過(guò)在文本編輯，智能助手系統(tǒng)等領(lǐng)域的程序合成中驗(yàn)證了其效果。Navid Yaghmazadeh等人[13]提出可以將自然語(yǔ)言處理，程序合成與自動(dòng)程序修復(fù)領(lǐng)域結(jié)合起來(lái)，允許用戶(hù)給出一個(gè)自然語(yǔ)言描述，首先利用語(yǔ)義分析功能將其轉(zhuǎn)換為一個(gè)SQL查詢(xún)的Sketch，然后利用類(lèi)型指導(dǎo)的程序合成方法合成出具體的SQL語(yǔ)句。由于用戶(hù)自然語(yǔ)言通常過(guò)于抽象，不能精確的反映出數(shù)據(jù)庫(kù)的機(jī)制，于是他們?cè)诜椒ㄖ惺褂昧隋e(cuò)誤修復(fù)技術(shù)，對(duì)得到的SQL Sketch進(jìn)行合理性的修復(fù)知道得到高質(zhì)量的SQL查詢(xún)語(yǔ)句為止。

（4）基于邏輯規(guī)約的程序合成

基于邏輯規(guī)約的程序合成方法需要用戶(hù)針對(duì)程序功能提供完整的規(guī)約描述，規(guī)約可能用某種語(yǔ)法表示成公式。對(duì)于復(fù)雜需求，一般用戶(hù)來(lái)說(shuō)寫(xiě)出完整的程序規(guī)約比較困難，因此這種方法在應(yīng)用中很少被用到，實(shí)用性不夠好。

3.2 ?從搜索策略角度進(jìn)行分類(lèi)

從采用的搜索策略的角度進(jìn)行分類(lèi)，程序合成方法又可以分為，基于語(yǔ)法指導(dǎo)的、基于代碼搜索的、基于深度學(xué)習(xí)以及基于API（組件）的程序合成。

（1）基于語(yǔ)法指導(dǎo)的程序合成

基于語(yǔ)法指導(dǎo)的程序合成一般需要用戶(hù)提供程序的輸入輸出規(guī)約或者語(yǔ)法框架，程序合成工具通過(guò)具體搜索策略或者符號(hào)搜索找到滿(mǎn)足用戶(hù)規(guī)約的程序，符號(hào)搜索需要從用戶(hù)規(guī)約中抽取出程序需要滿(mǎn)足的約束，然后利用約束求解器得到解。Kangjing Huang[17]等人提出可以將兩種搜索策略結(jié)合，利用決策樹(shù)的高度枚舉從短到長(zhǎng)的程序代碼，在每個(gè)固定長(zhǎng)度的枚舉過(guò)程中，通過(guò)舉反例的形式達(dá)到更精確的搜索。他們?cè)谝幌盗械腷enchmark上證明了該方法具有優(yōu)秀的效果。Rajeev Alur[19]等人描述了幾種方法針對(duì)語(yǔ)法指導(dǎo)的程序合成，包括激活學(xué)習(xí)、增加反例以及隨即搜索等，并執(zhí)行合理的benchmarks對(duì)比不同方法的效果。他們還對(duì)比了語(yǔ)法指導(dǎo)的程序合成比賽中驗(yàn)證過(guò)1500個(gè)benchmark的6個(gè)新的工具[20]，并分析了其效果。

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

基于搜索的程序合成方法結(jié)合了經(jīng)典的代碼搜索過(guò)程，在程序合成初期，利用代碼搜索得到與需求最接近的代碼結(jié)果，在此基礎(chǔ)上再進(jìn)行程序合成。基于搜索的程序合成方法能有效利用程序代碼搜索的結(jié)果縮小程序合成的時(shí)間復(fù)雜度和空間復(fù)雜度，該方法首先需要針對(duì)用戶(hù)需求進(jìn)行代碼搜索，可針對(duì)自然語(yǔ)言或代碼片段、程序關(guān)鍵詞進(jìn)行搜索，得到搜索出的代碼片段之后，再利用現(xiàn)有程序綜合技術(shù)得到符合需求的程序。相關(guān)工作例如Swim[2]，能夠針對(duì)用戶(hù)提供的需求規(guī)約，檢索出相關(guān)的API名稱(chēng)，然后通過(guò)檢索API使用模式集合找到最可能用的API模式序列，并據(jù)此包裝生成代碼片段。相關(guān)工作還有Hunter[3]，能夠根據(jù)用戶(hù)提供的自然語(yǔ)言描述，檢索出相關(guān)代碼，并根據(jù)類(lèi)型距離對(duì)檢索結(jié)果排序，最后通過(guò)整數(shù)線(xiàn)性規(guī)劃（Integer Linear Programing）將程序綜合問(wèn)題轉(zhuǎn)化為基于API的代碼生成過(guò)程，并利用現(xiàn)有工具生成出符合需求的程序?；谒阉鞯某绦蜃詣?dòng)生成的效果與前期代碼搜索結(jié)果息息相關(guān)，如何設(shè)計(jì)合理的搜索排序技術(shù)有效的找出與用戶(hù)需求最匹配的代碼成為該方法的關(guān)鍵點(diǎn)之一?；谒阉鞯某绦蚝铣杉夹g(shù)利用代碼搜索的結(jié)果，能夠有效的縮小程序綜合的空間，提升程序合成的時(shí)間效率，成為很多程序合成技術(shù)的首要過(guò)程。

（3）基于深度學(xué)習(xí)的程序合成

近幾年，人工智能行業(yè)迅猛發(fā)展，研究人員開(kāi)始研究如何使用更加智能化的方法實(shí)現(xiàn)程序自動(dòng)生成。機(jī)器學(xué)習(xí)等相關(guān)方法一般需要大量數(shù)據(jù)集來(lái)訓(xùn)練，而隨著互聯(lián)網(wǎng)的繁榮發(fā)展，Github等代碼托管平臺(tái)上存儲(chǔ)了大量的項(xiàng)目代碼使得利用機(jī)器學(xué)習(xí)來(lái)學(xué)習(xí)如何寫(xiě)代碼成為了可能。根據(jù)方法的風(fēng)格不同，基于深度學(xué)習(xí)的程序合成方法一般分為兩種類(lèi)別，一種是模型原理不可解釋的“黑盒”方法，另一種是能夠直接生成可解釋代碼的“代碼生成派”方法。黑盒的方法類(lèi)似于一個(gè)黑箱子，直接利用大量數(shù)據(jù)集訓(xùn)練得到代碼生成的規(guī)則，規(guī)則被表示為模型的參數(shù)，因此具有不可解釋性?！昂诤信伞狈椒▽?duì)用戶(hù)來(lái)說(shuō)不易于使用和修改，因?yàn)橛脩?hù)并不能理解模型到底學(xué)習(xí)出了什么樣的編程規(guī)則。而“代碼生成派”則能夠直接根據(jù)需求生成出顯示的程序代碼，更加符合人類(lèi)所想象的機(jī)器自動(dòng)編程的狀態(tài)。在模型的使用階段，用戶(hù)只需提供一至多個(gè)輸入輸出數(shù)據(jù)對(duì)，模型能夠根據(jù)輸入輸出數(shù)據(jù)對(duì)，提取高層特征，預(yù)測(cè)出需求所需要的各種操作原語(yǔ)的概率，結(jié)果概率越高的操作原語(yǔ)，越有可能在任務(wù)的實(shí)現(xiàn)代碼中用到。相關(guān)工作如DeepCoder[5]，一種使用輸入輸出樣本的深度學(xué)習(xí)解決編程競(jìng)賽風(fēng)格的方法。該方法屬于典型的代碼生成派工作，能夠通過(guò)訓(xùn)練神經(jīng)網(wǎng)絡(luò)來(lái)預(yù)測(cè)有輸入到輸出的程序?qū)傩?。Facebook在該領(lǐng)域也有所研究，例如其選擇層級(jí)生成CNN網(wǎng)絡(luò)結(jié)構(gòu)[6]（Hierarchical Generative Convolutional Neural Network，又稱(chēng)為HGCNN），利用隨機(jī)生成的程序，給定一些輸入，運(yùn)行程序得到輸出來(lái)構(gòu)造數(shù)據(jù)集，因此屬于無(wú)監(jiān)督學(xué)習(xí)的過(guò)程。

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

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

4 ?程序合成面臨的挑戰(zhàn)

現(xiàn)有研究工作[1]指出，程序合成主要面臨來(lái)自于兩個(gè)維度的挑戰(zhàn)，一個(gè)是難掌控的程序搜索空間，一個(gè)是用戶(hù)意圖的多樣性。

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

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

5 ?討論與展望

近年來(lái)，程序合成技術(shù)取得了多方面的進(jìn)步，從搜索算法到程序和成框架上都在隨著計(jì)算機(jī)研究熱點(diǎn)而有所改變。就目前整體取得的進(jìn)展和面臨的挑戰(zhàn)來(lái)說(shuō)，我們認(rèn)為從以下幾個(gè)方面是未來(lái)一段時(shí)間內(nèi)程序合成技術(shù)有待于解決的階段性難題。

（1）人機(jī)交互

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

（2）多元化需求描述

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

（3）智能化程序合成

隨著人工智能的火熱發(fā)展，研究學(xué)者們更希望能夠用智能化的方法來(lái)合成程序。雖然已經(jīng)產(chǎn)生了“黑盒派”以及“代碼生成派”等相關(guān)研究工作，但這些方法都處于研究的初期階段，無(wú)法很好的在現(xiàn)有需求上產(chǎn)生應(yīng)用，因此機(jī)器自動(dòng)編碼領(lǐng)域仍有很長(zhǎng)一段路要走。類(lèi)似于Github等互聯(lián)網(wǎng)代碼托管平臺(tái)已經(jīng)存儲(chǔ)了大量的項(xiàng)目代碼，這給以深度學(xué)習(xí)訓(xùn)練為核心來(lái)實(shí)現(xiàn)程序合成的方法提供了良好的契機(jī)。因此未來(lái)很長(zhǎng)一段時(shí)間內(nèi)將會(huì)有大量的研究工作將重心放在基于深度學(xué)習(xí)的程序自動(dòng)合成上，如何更好的挖掘出先驗(yàn)知識(shí)中的編碼規(guī)范來(lái)指導(dǎo)程序自動(dòng)合成，成為軟件工程領(lǐng)域當(dāng)前一個(gè)熱點(diǎn)研究領(lǐng)域。

6 ?結(jié)束語(yǔ)

信息化發(fā)達(dá)的互聯(lián)網(wǎng)時(shí)代已經(jīng)持續(xù)了很多年，使得軟件開(kāi)發(fā)活動(dòng)在社會(huì)發(fā)展中一直占有重要地位并不斷演化前進(jìn)?，F(xiàn)如今軟件開(kāi)發(fā)規(guī)模的復(fù)雜性使得人們更加追求良好的編程規(guī)范和高效的編碼效率，因此程序自動(dòng)合成領(lǐng)域在近年重新成為軟件工程領(lǐng)域的研究熱點(diǎn)。但程序自動(dòng)合成距離能夠產(chǎn)生工業(yè)應(yīng)用的那天還很遙遠(yuǎn)，無(wú)論在搜索空間效率上，還是在用戶(hù)交互的可用性上都沒(méi)有達(dá)到一個(gè)良好的效果。而人工智能的發(fā)展給程序自動(dòng)合成帶來(lái)了新的方法流派，未來(lái)程序合成技術(shù)還有更多方向需要繼續(xù)探索前進(jìn)。

參考文獻(xiàn)

[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.