Thu 21 Oct 2021 22:05 - 22:20 at Zurich B - Program Synthesis - mirror Chair(s): Hakjoo Oh
While input-output examples are a natural form of specification for program synthesis engines, they can be imprecise for domains such as table transformations. In this paper, we investigate how extracting readily-available information about the user intent behind these input-output examples helps speed up synthesis and reduce overfitting. We present Gauss, a synthesis algorithm for table transformations that accepts partial input-output examples, along with user intent graphs. Gauss includes a novel conflict-resolution reasoning algorithm over graphs that enables it to learn from mistakes made during the search and use that knowledge to explore the space of programs even faster. It also ensures the final program is consistent with the user intent specification, reducing overfitting. We implement Gauss for the domain of table transformations (supporting Pandas and R), and compare it to three state-of-the-art synthesizers accepting only input-output examples. We find that it is able to reduce the search space by 56$\times$, 73$\times$ and 664$\times$ on average, resulting in 7$\times$, 26$\times$ and 7$\times$ speedups in synthesis times on average, respectively.
Thu 21 OctDisplayed time zone: Central Time (US & Canada) change
13:50 - 15:10 | |||
13:50 15mTalk | Generalizable Synthesis through UnificationVirtual OOPSLA Ruyi Ji Peking University, Jingtao Xia Peking University, Yingfei Xiong Peking University, Zhenjiang Hu Peking University DOI | ||
14:05 15mTalk | Gauss: Program Synthesis by Reasoning over GraphsVirtual OOPSLA Rohan Bavishi University of California at Berkeley, Caroline Lemieux Microsoft Research, Koushik Sen University of California at Berkeley, Ion Stoica University of California at Berkeley DOI | ||
14:20 15mTalk | APIfix: Output-Oriented Program Synthesis for Combating Breaking Changes in LibrariesVirtual OOPSLA Xiang Gao National University of Singapore, Arjun Radhakrishna Microsoft, Gustavo Soares Microsoft, Ridwan Salihin Shariffdeen National University of Singapore, Sumit Gulwani Microsoft, Abhik Roychoudhury National University of Singapore DOI | ||
14:35 15mTalk | LooPy: Interactive Program Synthesis with Control StructuresVirtual OOPSLA Kasra Ferdowsi University of California at San Diego, Shraddha Barke University of California at San Diego, Hila Peleg Technion, Sorin Lerner University of California at San Diego, Nadia Polikarpova University of California at San Diego DOI | ||
14:50 20mLive Q&A | Discussion, Questions and Answers OOPSLA |
21:50 - 23:10 | |||
21:50 15mTalk | Generalizable Synthesis through UnificationVirtual OOPSLA Ruyi Ji Peking University, Jingtao Xia Peking University, Yingfei Xiong Peking University, Zhenjiang Hu Peking University DOI | ||
22:05 15mTalk | Gauss: Program Synthesis by Reasoning over GraphsVirtual OOPSLA Rohan Bavishi University of California at Berkeley, Caroline Lemieux Microsoft Research, Koushik Sen University of California at Berkeley, Ion Stoica University of California at Berkeley DOI | ||
22:20 15mTalk | APIfix: Output-Oriented Program Synthesis for Combating Breaking Changes in LibrariesVirtual OOPSLA Xiang Gao National University of Singapore, Arjun Radhakrishna Microsoft, Gustavo Soares Microsoft, Ridwan Salihin Shariffdeen National University of Singapore, Sumit Gulwani Microsoft, Abhik Roychoudhury National University of Singapore DOI | ||
22:35 15mTalk | LooPy: Interactive Program Synthesis with Control StructuresVirtual OOPSLA Kasra Ferdowsi University of California at San Diego, Shraddha Barke University of California at San Diego, Hila Peleg Technion, Sorin Lerner University of California at San Diego, Nadia Polikarpova University of California at San Diego DOI | ||
22:50 20mLive Q&A | Discussion, Questions and Answers OOPSLA |