1.引用

Cochran R A, D'Antoni L, Livshits B, et al. Program boosting: Program synthesis via crowd-sourcing[C].Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2015: 677-688.

2.摘要

在本文中，我們研究了一種基于眾包的程序合成方法。在眾包的幫助下，我們力求捕捉“眾人的智慧”，以找到解決固有棘手編程任務(wù)的好的（即使不是完美的）解決方案，這些任務(wù)缺乏易于形式化的規(guī)范，甚至連專家級開發(fā)人員都難以理解。

我們將這種方法稱為“程序增強(qiáng)”，它將為開發(fā)人員遇到的一個(gè)棘手編程問題眾包一些不夠完善的解決方法，然后將這些程序融合在一起以提高其正確性。

我們在 CROWDBOOST 系統(tǒng)中實(shí)現(xiàn)了這種方法，并在我們的實(shí)驗(yàn)中展示了一些有趣并且且有價(jià)值的任務(wù)(例如 URL 或電子郵件地址的正則表達(dá)式)可以有效地眾包。我們證明，將眾包結(jié)果混合在一起可以協(xié)調(diào)一致地對程序進(jìn)行增強(qiáng)，所產(chǎn)生的程序要好于任何初始的程序。我們對 465 個(gè)程序?qū)M(jìn)行實(shí)驗(yàn)，結(jié)果顯示出一致的準(zhǔn)確率提升，這證明了可以以相對低的成本來進(jìn)行程序增強(qiáng)。

3.技術(shù)介紹

3.1 眾包背景

在過去的幾年中，我們看到在一些非技術(shù)性任務(wù)（識別圖片中是否有貓，重新格式化文本數(shù)據(jù)，糾正句子中的語法）和技術(shù)性任務(wù)(根據(jù)要求提供插圖或圖形設(shè)計(jì)，撰寫產(chǎn)品的簡短說明)中使用眾包的情況有所增加。

Amazon 的 Mechanical Turk（通常縮寫為 asmturk）就是一個(gè)很好的非專業(yè)工作眾包網(wǎng)站例子；oDeskis 是另一個(gè)廣泛使用的平臺，該平臺主要用于技術(shù)性的任務(wù)。這兩個(gè)平臺均可用于眾包編程任務(wù)，盡管兩者都不是專門用于此目的。注意，可以將 StackOverflow 和其他類似的編程幫助站點(diǎn)視為一種非正式的眾包類型。確實(shí)，這些站點(diǎn)非常擅長提供解決棘手的編程問題的方法，以至于某些開發(fā)人員在編寫代碼時(shí)經(jīng)常瀏覽 StackOverflow。

Bountify（http://bountify.co）允許人們發(fā)布程序任務(wù)，其中一些涉及從頭開始編寫新代碼（編寫JavaScript函數(shù)以生成給定顏色的多種陰影），而其他則涉及修復(fù)現(xiàn)有代碼中的錯(cuò)誤（為什么 我的 HTML 表格看起來不符合我的期望，我應(yīng)該如何調(diào)整 CSS 使其看起來正確？）。這些編程任務(wù)通常不會(huì)太耗時(shí);一個(gè)典型的任務(wù)大約支付 5 美元?；貜?fù)是公開發(fā)表的，這使得其他開發(fā)者可以從中進(jìn)行學(xué)習(xí)。最后，發(fā)布者決定將獎(jiǎng)金授予哪個(gè)開發(fā)者。

請注意，交互式眾包并不是特定編程任務(wù)的唯一代碼源。確實(shí)，人們可以輕松地使用代碼搜索引擎來從開源項(xiàng)目中尋找。使用專用代碼引擎搜索諸如 urlregex 之類的術(shù)語將生成一些可能的正則表達(dá)式用來過濾 URL。

3.2 程序增強(qiáng)

圖 2 顯示了我們系統(tǒng)的體系結(jié)構(gòu)。我們從一個(gè)文本測試任務(wù)規(guī)范和（正負(fù)）示例的初始訓(xùn)練集（也稱為“黃金集”）開始。為了將指定任務(wù)的解決方案眾包，我們利用了兩個(gè)人群：由開發(fā)人員組成的熟練人群和由常規(guī)計(jì)算機(jī)用戶組成的未經(jīng)訓(xùn)練的人群。前者包含通過諸如 Bountify 之類的服務(wù)進(jìn)行雇傭的開發(fā)人員，他們通常精通一種或多種語言（如 Java 和 C ），而后者則由在 Mechanical Turk 上找到的常規(guī)計(jì)算機(jī)用戶組成。

方法：為簡單起見，本文將重點(diǎn)放在二分類任務(wù)上，即（1）使用單一輸入的程序；（2）產(chǎn)生布爾值（是/否）輸出；（3）對于任何輸入，非專業(yè)的計(jì)算機(jī)用戶都可以決定其答案應(yīng)該是是或否。 此類任務(wù)的示例包括確定輸入是否為格式正確的電話號碼的程序，或確定輸入圖像是否包含長頸鹿的程序。

? 最后一個(gè)要求是改善程序的必要條件，即在未經(jīng)訓(xùn)練的人群的幫助下確定棘手案例的正確結(jié)果。我們的觀察是，盡管未經(jīng)培訓(xùn)的人群不會(huì)幫助我們程序，但他們將能夠識別正確或不正確的程序行為。通過類推的方式，雖然外行人可能無法編寫識別圖像中是否存在長頸鹿的計(jì)算機(jī)視覺程序，但人類非常擅長識別給定圖片中是否包含長頸鹿。這種兩人群的方法有助于我們詢問未經(jīng)培訓(xùn)人群來消歧，從而既可以收集候選程序，又可以系統(tǒng)地?cái)U(kuò)展輸入空間。

雖然存在其他合適的標(biāo)準(zhǔn)，但在這篇論文中，我們關(guān)注的是提高合成程序在正反面例子上的準(zhǔn)確性。

3.3 通過遺傳編程進(jìn)行程序增強(qiáng)

為了實(shí)現(xiàn)以上示例中所提出的方法，一種常見的技術(shù)是遺傳編程，它是遺傳算法的一種特殊形式。遺傳編程是程序領(lǐng)域中的一種搜索技術(shù)，其目的是在一系列迭代中提高程序的適用性。成功的遺傳編程方法取決于實(shí)現(xiàn)兩種操作：交叉和突變。

給定一組初始的眾包程序，該程序增強(qiáng)算法需要進(jìn)行多次迭代。在我們的電話號碼示例的上下文中，這些初始程序可以是兩個(gè)初始正則表達(dá)式。在每一代，它都將交叉和變異操作結(jié)合在一起。（在我們的示例中，這可能會(huì)將正則表達(dá)式的各個(gè)部分調(diào)整為像-和.這樣的電話號碼分隔符）作為一種改進(jìn)形式，之后我們將新示例添加到訓(xùn)練集中。例如，在我們的正則表達(dá)式實(shí)現(xiàn)中，優(yōu)化的目標(biāo)是通過將非顯而易見的情況例如 212.555?1212or1?)212)555?1212 作為有效或無效電話號碼添加到不斷發(fā)展的進(jìn)化訓(xùn)練集中來達(dá)到 100％的狀態(tài)覆蓋率。最后，選擇適應(yīng)性最高的候選者繼續(xù)下一代。

3.4 程序增強(qiáng)算法

圖 3 用偽代碼顯示了我們的程序增強(qiáng)算法。Σ 為所有程序集，Φ 為所有輸入集。在每次迭代中，我們更新當(dāng)前考慮的程序和當(dāng)前的示例.

請注意，該算法本質(zhì)上是迭代的：增強(qiáng)收益的過程類似于通常執(zhí)行遺傳編程的方式?？傮w目標(biāo)是在 Σ 中找到最適合的程序。每代產(chǎn)生一個(gè)新的 Φ 樣本并發(fā)送給人群以取得共識。

? 稍后我們將展示如何使用 SFA 實(shí)現(xiàn)與正則表達(dá)式的函數(shù) β，μ，δ 和 η 相對應(yīng)的運(yùn)算。請注意，在實(shí)踐中，為了更快地完成代碼，我們通常將迭代次數(shù)限制在一個(gè)設(shè)置的限制（例如 10）中。

我們的實(shí)現(xiàn)受益于并行運(yùn)算。在特殊情況下，我們使算法的第 6 行和第 12 行的兩個(gè)循環(huán)并行進(jìn)行。盡管我們在執(zhí)行過程中需要小心謹(jǐn)慎，以避免出現(xiàn)共享狀態(tài)，但這種相對簡單的更改最終會(huì)能夠幾乎完全利用具有 8 或 16 個(gè)內(nèi)核的計(jì)算機(jī)。

1 有限符號自動(dòng)機(jī)：盡管正則表達(dá)式簡潔明了，相對容易理解，但對代數(shù)來說卻不容易操縱。特別是，沒有直接的算法可以互補(bǔ)或相交。因此，我們選擇了有限自動(dòng)機(jī)。經(jīng)典確定性有限自動(dòng)機(jī)（DFA）具有許多閉包性質(zhì)和友好的復(fù)雜性，但是每個(gè) DFA 轉(zhuǎn)換只能攜帶一個(gè)字符，從而導(dǎo)致 DFA 中的轉(zhuǎn)換數(shù)量與字母的大小成比例。當(dāng)字母表很大（UTF16 具有 2 的 16 次方個(gè)元素）時(shí)，這種表示不切實(shí)際。

符號有限自動(dòng)機(jī)（SFA）擴(kuò)展了帶有符號字母的經(jīng)典自動(dòng)機(jī)。在 SFA 中，每個(gè)邊都標(biāo)記有謂詞，而不是單個(gè)輸入字符，這使自動(dòng)機(jī)可以簡潔地表示多個(gè)具體轉(zhuǎn)換。例如，在圖 7 的 SFA 中，從狀態(tài) 10 到狀態(tài) 11 的轉(zhuǎn)換用謂詞[^＃- /？ s]標(biāo)記。由于 UTF16 集的大小，經(jīng)典自動(dòng)機(jī)中的這個(gè)轉(zhuǎn)換將由數(shù)千個(gè)具體轉(zhuǎn)換來表示。

2 適應(yīng)度計(jì)算 ：作為用于程序增強(qiáng)的遺傳程序設(shè)計(jì)方法的一部分，我們需要能夠評估特定程序的適用性。對于正則表達(dá)式，這相當(dāng)于在訓(xùn)練集上計(jì)算精度。適應(yīng)度計(jì)算過程本身可能會(huì)非常耗時(shí)。原因是當(dāng)我們考慮成千上萬的 SFA 和數(shù)百個(gè)例子時(shí)，運(yùn)行一些大的例子，并計(jì)算有多少被 SFA 正確接受是一個(gè)擴(kuò)展性很差的過程。相反，我們構(gòu)造 SFA P 和 N，分別表示所有肯定組和所有否定組的語言。對于任何 SFA A，我們計(jì)算交集的基數(shù)（參見圖 4 中的虛線區(qū)域），兩者都可以使用 SFA 操作來快速計(jì)算。然后可以將精確度計(jì)算限制在范圍為 0 到 1。我們的改進(jìn)技術(shù)固有的挑戰(zhàn)是我們進(jìn)化的示例集可能會(huì)與最初的黃金集大相徑庭。盡管不完美，但我們?nèi)匀幌Ｍ麑ⅫS金集視為更可靠的真理來源，為此，我們使用加權(quán)為整體適應(yīng)度計(jì)算中的黃金集賦予更高的權(quán)重。在我們的實(shí)驗(yàn)評估中，如果將黃金：進(jìn)化示例權(quán)重設(shè)置為 9：1，我們將獲得可靠的良好結(jié)果。

3 交叉 交叉操作是將兩個(gè) SFA 通過混合他們的行為，交叉成單個(gè) SFA。這個(gè)操作的說明示例如圖 6 所示。給定兩個(gè) SFA A 和 B，交叉算法通過重定向兩個(gè)轉(zhuǎn)換（一個(gè)從 A 到 B，一個(gè)從 B 到 A）來創(chuàng)建新的 SFA。此類操作的目標(biāo)是使用包含 A 的 B 的組件。

4 變異 在其經(jīng)典定義中，變異算子會(huì)更改輸入程序的一個(gè)或多個(gè)值，并產(chǎn)生一個(gè)變異的值。SFA 的值要更改的太多（每個(gè)轉(zhuǎn)換都可以攜帶 2 的 16 次方個(gè)元素），“盲目”方法會(huì)產(chǎn)生太多變異。相反，我們考慮使用引導(dǎo)方法，其中將變異作為 SFA A 的輸入和反例 s（s 是一個(gè)正例子但它不屬于 L(A)或者 s 是一個(gè)反例但它屬于 L(A)）。使用這些額外的信息，我們僅以會(huì)導(dǎo)致正確分類的方式進(jìn)行變異。這種操作背后的直覺是執(zhí)行最小的語法改變以正確分類反例。

5 示例生成 生成一個(gè)字符串通常不足以描述 SFA 的語言。在生成示例中，我們遵循下列不變式：為了生成 SFA 的全覆蓋，我們需要進(jìn)行下一個(gè)迭代。迭代算法示例如圖 8 所示；給定包含 k 個(gè)狀態(tài)的 SFA，它最多迭代 k 輪終止。該算法只是在每次迭代中生成一個(gè)新的字符串，強(qiáng)制覆蓋至少一個(gè)尚未覆蓋的狀態(tài)。

4.本文主要貢獻(xiàn)

本文提出了一種新穎的眾包方法來進(jìn)行程序合成，稱為程序增強(qiáng)。我們主要關(guān)注即使是最熟練的開發(fā)人員存在困難的編程任務(wù)。我們的見解是，可以將群眾的智慧集中到這些艱巨的任務(wù)上。在本文中，我們展示了如何使用兩個(gè)人群：一群熟練的開發(fā)人員和一群未經(jīng)培訓(xùn)的計(jì)算機(jī)工作者來成功地為涉及擬定正則表達(dá)式的復(fù)雜任務(wù)生成解決方案。

我們已經(jīng)在名為 CROWDBOOST 的工具中實(shí)現(xiàn)了程序增強(qiáng)，并進(jìn)行了測試。在四個(gè)復(fù)雜的任務(wù)上，我們從 Bountify 和其他幾個(gè)來源眾包了 33 個(gè)正則表達(dá)式，并對其進(jìn)行成對增強(qiáng)。我們發(fā)現(xiàn)我們的程序增強(qiáng)技術(shù)是穩(wěn)定的：當(dāng)在 465 對眾包程序上進(jìn)行測試時(shí)，它產(chǎn)生了一致性的精確性增強(qiáng)。即使是從合格的開發(fā)人員眾包而來的高質(zhì)量初始程序開始合成，我們也始終如一地能夠提高準(zhǔn)確率，平均達(dá)到 16.25％。

致謝

國家重點(diǎn)研發(fā)計(jì)劃課題：基于協(xié)同編程現(xiàn)場的智能實(shí)時(shí)質(zhì)量提升方法與技術(shù)（2018YFB1003901）和國家自然科學(xué)基金項(xiàng)目：基于可理解信息融合的人機(jī)協(xié)同移動(dòng)應(yīng)用測試研究（61802171）

本文由南京大學(xué)軟件學(xué)院 2020 級碩士王一博轉(zhuǎn)述