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ā)人員都難以理解。

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

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

3.技術(shù)介紹

3.1 眾包背景

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

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

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

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

3.2 程序增強

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

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

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

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

3.3 通過遺傳編程進行程序增強

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

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

3.4 程序增強算法

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

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

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

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

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

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

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

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

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

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

4.本文主要貢獻

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

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

致謝

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

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