Interactive program synthesis aims to solve the ambiguity in specifications, and selecting the proper question to minimize the rounds of interactions is critical to the performance of interactive program synthesis. In this paper we address this question selection problem and propose two algorithms. \textit{SampleSy} approximates a state-of-the-art strategy proposed for optimal decision tree and has a short response time to enable interaction. \textit{EpsSy} further reduces the rounds of interactions by approximating \textit{SampleSy} with a bounded error rate. To implement the two algorithms, we further propose \textit{VSampler}, an approach to sampling programs from a probabilistic context-free grammar based on version space algebra. The evaluation shows the effectiveness of both algorithms.
Fri 19 JunDisplayed time zone: Pacific Time (US & Canada) change
08:00 - 09:00 | Synthesis III PLDI Research Papers at PLDI Research Papers live stream Chair(s): Santosh Nagarakatte Rutgers University, USA | ||
08:00 20mTalk | Exact and Approximate Methods for Proving Unrealizability of Syntax-Guided Synthesis Problems PLDI Research Papers Qinheping Hu University of Wisconsin-Madison, USA, John Cyphert University of Wisconsin-Madison, USA, Loris D'Antoni University of Wisconsin-Madison, USA, Thomas Reps University of Wisconsin-Madison, USA | ||
08:20 20mPaper | Question Selection for Interactive Program Synthesis PLDI Research Papers Ruyi Ji Peking University, China, Jingjing Liang Peking University, China, Yingfei Xiong Peking University, China, Lu Zhang Peking University, China, Zhenjiang Hu Peking University, China Pre-print | ||
08:40 20mTalk | Reconciling Enumerative and Deductive Program Synthesis PLDI Research Papers Kangjing Huang Purdue University, USA, Xiaokang Qiu Purdue University, USA, Peiyuan Shen Purdue University, USA, Yanjun Wang Purdue University, USA | ||