1. 引用
Desai A, Gulwani S, Hingorani V, et al. Program synthesis using natural language[C].Proceedings of the 38th International Conference on Software Engineering. 2016: 345-356.
2. 摘要
與計算機進行交互是數百萬人的普遍活動，重複的或特定的任務通常需要創建小的一次性的程序。終端用戶努力學習並使用無數領域特定語言（DSL）來有效地完成這些任務。
我們提出了一個通用框架，用於構造採用自然語言（NL）輸入並在目標 DSL 中生成表達式的程序合成器。該框架輸入為 DSL 定義以及由 NL / DSL 對組成的訓練數據。通過學習優化的權重和分類器（使用 NLP 特徵）來構建一個合成器，對基於翻譯的關鍵字編程的輸出進行排名。我們將框架應用於三個領域：重複文本編輯，智能輔導系統和航班信息查詢。在 1200 多個英語描述中，相應的合成器對於 80％和 90％的描述將所需的程序分別排為第 1 名和第 3 名。
3. 技術介紹
3.1 介紹
本文中，我們解決了從 NL 合成底層 DSL 程序的問題。NL 本質上是不精確的；因此，可能無法保證合成程序的正確性。相反，我們的目標是生成一組排序的程序，並讓用戶可以通過檢查程序的源代碼或在某些測試輸入上執行該程序得到的結果來選擇其中一個程序。這種用戶交互類似於 Flash Fill 等一些 PBE 技術中採用的交互。讀者也可以將此過程比作用戶如何在搜索引擎中搜索和選擇所需結果。此外，類似於搜索引擎，本文中的合成算法能夠一致地生成和排序期望的結果程序，在我們的基準測試中，超過 80％的時間排在第一位，或者超過 90％的時間排在前三位。為了使用戶對他們選擇的程序有信心，我們將代碼翻譯顯示為消除歧義的英語或運行它並將結果顯示為預覽。
與大多數現有的專門針對特定 DSL 的合成技術不同，我們的方法可以應用於各種 DSL。我們的方法需要來自合成程序設計者的兩個輸入：（i）DSL 定義，（ii）訓練數據，包含英語語句和相應預期 DSL 程序的實例對。訓練階段推斷英語單詞和 DSL 終結符（以半自動交互方式）成對的字典關係，以及最佳權重/分類器（以完全自動化的方式），以供通用合成算法使用。我們的方法可以看作是構建 NL-to-DSL 合成器的元合成框架。
通用合成算法（算法 1）將一個英語句子作為輸入，並生成可能的程序的排名集。首先，它使用一個 Bag 算法（算法 2）來高效地計算所有包含與句子中單詞相關的終結符的的 DSL 程序集。為此，它使用了將英文單詞和 DSL 終結符相關聯的字典(在訓練階段學習到的)。然後，它基於一組評分函數對這些程序進行排名。這些功能的靈感來自於程序的抽象語法樹（AST），它涉及兩個組成部分：程序中的終結符集，以及這些終結符之間的樹結構。我們使用 3 個評分的加權線性組合來確定每個程序的等級：(i)覆蓋評分：忽略用戶輸入中的許多單詞得到的結果是不可能正確的。(ii）映射評分：英語單詞可以具有多種含義和預期的關於 DSL 的行為，但我們傾向於可能性大的解釋（iii）結構評分：自然語言和編程語言都具有共性結構，我們傾向於更自然的結果。
在訓練階段使用現成的機器學習算法學習用來計算這些分數以及用來組合分數的權重的分類器。我們的方法的新穎之處在於產生的用於分類器學習的數據來自於高級數據，並且為了有效地學習權值，將離散的分數準則平滑為連續的、可微的損失函數。
3.2 激勵方案
我們描述了可以應用 NL-to-DSL 合成器的 3 個不同領域：文本編輯，面向智能輔導的問題自動構造和航空旅行信息系統的問答查詢。
通過針對 Office 套件應用程序（例如 Microsoft Excel 和 Word）的幫助論壇的研究，我們發現用戶經常請求有關重複文本編輯操作的幫助，例如在文本文件中進行插入，刪除，替換或提取。這些操作（表 1（b））比通過其他方法簡單地用一個字符串搜索和替換常量字符串更為複雜。 首先，要搜索的字符串通常不是常量，需要正則表達式匹配。其次，編輯通常取決於周圍的環境。 即使是這樣相對簡單的任務，也需要用戶瞭解正則表達式，條件和循環的語法和語義，這超出了大多數終端用戶的能力。
這啟發了我們設計一種用於文本編輯的命令語言（表 1（a）中顯示了語法的一個子集），其中包括關鍵命令 Insert，Remove，Print 和 Replace。這些命令中的每一個都依賴於 IterScope 表達式，該表達式指定文本編輯操作所處的區域（行集合，單詞集合或整個 Word 文檔）。 SelectStr 產品包括一個 Token，該 Token 允許有限的通配符匹配（例如，整個 WORDTOK，NUMBERTOK 或 PString 指定的模式），布爾條件 BCond 用作對匹配值的附加（局部）過濾。表 1（c）描述了我們的系統可以處理同一示例的不同變化版本。
我們的想法是，一旦用戶能夠完成這些條件性的和重複性的小任務，則可以通過將其他更復雜的任務縮減為一系列較小的任務來輕鬆完成。
面向智能輔導的問題自動構造
傳統方法研究的結果已應用於智能輔導系統的許多方面，包括問題生成，解決方案生成，尤其是反饋生成，涉及包括幾何和自動機理論在內的各種主題領域。這些領域每個都包含一個專用的 DSL，問題生成器工具使用它來創建新問題，解決方案生成工具使用它來生成解決方案，更重要的是，反饋生成工具用它來提供有關學生解決方案的反饋。
考慮自動機構造的領域，在該領域中，要求學生構造一個自動機，該自動機接受英語描述（有關示例參見表 2）。我們基於 Alur 等人提供的描述設計了一個 DSL。該 DSL 包含字符串謂詞、布爾連接詞、返回子字符串位置的函數以及字符串位置的通用/現有量化。這種語言通過兩種方式為學生的錯誤嘗試生成反饋：（i）解決方案生成工具使用它來生成正確的解決方案，以對學生的嘗試進行評分；（ii）還用於提供反饋並生成與學生的嘗試相符的問題變體。該反饋生成工具已部署在教室中，並且能夠以有意義的方式同時比人類更快，更一致地分配成績並生成反饋。我們的合成方法可用於從自然語言描述中自動生成該系統所需的規範。
航空旅行資訊系統（ATIS）
ATIS 是用於查詢航空旅行信息的標準基準，這些信息包括英語查詢和包含航班信息的相關數據庫。長期以來，它一直被用作自然語言處理和語音處理社區的標準基準。表 3 顯示了來自 ATIS 套件的一些示例查詢。對於 ATIS，我們設計了基於 SQL 樣式的行/列操作的 DSL，併為謂詞/表達式提供了支持，這些謂詞/表達式對應於航空查詢的重要概念，例如到達/出發位置，時間，日期，價格等。
3.3 算法
合成算法（算法 1）從用戶處接收自然的語言命令，並創建候選的 DSL 程序排名列表。第一步（第 2 行）是使用 NL 對終結符字典 DLDict 進行編程，將用戶輸入中的每個單詞轉換為一個或多個終結符（函數名稱或值）。該循環在輸入語句的長度範圍內，對於每個索引，查找與 NLDict 中該索引處的單詞相關聯的 DSL 中的終結符集。從根本上講，NLDict 對每個終結符進行編碼，表示哪些單詞很可能暗示該終結符在期望程序中出現。可以半自動方式構造此映射。一旦為終結符 t 建立了關聯，我們將一個終結符元組和一個單例映射（將單詞的索引與所產生的終結符相關聯）存儲到集合 R0（第 4 行）中。
對於每個自然語言單詞，字典 NLDict 為它關聯一組終結符集。終結符可以是常量值，也可以將帶有漏洞參數的函數應用程序。因此，算法（算法 1）（在第 3 行上使用 NLDict 時）可能會創建不完整的程序，其中缺少函數的某些參數。例如，考慮句子“打印不包含 834 的所有行”。由於語法包含 PrintCmd：= PRINT（SelectStr，IterScope），詞典將單詞“ print”與函數 PRINT 相關聯，因此將生成部分程序。以後，這些漏洞將被其他與參數類型 SelectStr 和 IterScope 匹配的程序替換。
一旦構建了基本的終結符集，算法便會使用 Bag 算法（算法 2）生成所有一致的程序集 ResT。 最後一步是使用分數和權重的組合，在第 7 行的循環中對這組程序進行排名。
4. 本文主要貢獻
本文提出了一種從自然語言描述中合成程序的新技術(從終結符集中生成程序並且排序，這些終結符與自然語言描述中的詞相對應)。並且，我們展示了這個框架如何通過簡單地提供轉化示例來創建支持不同 DSL 的程序合成器。
致謝
國家重點研發計劃課題：基於協同編程現場的智能實時質量提升方法與技術（2018YFB1003901）和國家自然科學基金項目：基於可理解信息融合的人機協同移動應用測試研究（61802171）
本文由南京大學軟件學院 2020 級碩士王一博轉述
閱讀更多 慕測科技 的文章
