SPLASH 2017
Sun 22 - Fri 27 October 2017 Vancouver, Canada
Wed 25 Oct 2017 15:52 - 16:14 at Regency A - Synthesis Chair(s): Jonathan Edwards

In application domains that store data in a tabular format, a common task is to fill the values of some cells using values stored in other cells. For instance, such data completion tasks arise in the context of \emph{missing value imputation} in data science and \emph{derived data} computation in spreadsheets and relational databases. Unfortunately, end-users and data scientists typically struggle with many data completion tasks that require non-trivial programming expertise.
This paper presents a synthesis technique for automating data completion tasks using \emph{programming-by-example (PBE)} and a very lightweight sketching approach. Given a \emph{formula sketch} (e.g., {\texttt{AVG}}($\texttt{?}_1$, $\texttt{?}_2$)) and a few input-output examples for each hole, our technique synthesizes a program to automate the desired data completion task. Towards this goal, we propose a domain-specific language (DSL) that combines spatial and relational reasoning over tabular data and a novel synthesis algorithm that can generate DSL programs that are consistent with the input-output examples. The key technical novelty of our approach is a new version space learning algorithm that is based on \emph{finite tree automata} (FTA). The use of FTAs in the learning algorithm leads to a more compact representation that allows more sharing between programs that are consistent with the examples. We have implemented the proposed approach in a tool called \textsc{DACE} and evaluate it on 84 benchmarks taken from online help forums. We also illustrate the advantages of our approach by comparing our technique against two existing synthesizers, namely Prose and Sketch.

#### Wed 25 OctDisplayed time zone: Tijuana, Baja California change

 15:30 - 17:22 SynthesisOOPSLA at Regency A Chair(s): Jonathan Edwards 15:3022mTalk Model-Assisted Machine-Code SynthesisOOPSLAVenkatesh Srinivasan University of Wisconsin - Madison, Ara Vartanian University of Wisconsin-Madison, USA, Thomas Reps University of Wisconsin - Madison and GrammaTech, Inc. DOI 15:5222mTalk Synthesis of Data Completion Scripts using Finite Tree AutomataOOPSLAXinyu Wang UT Austin, Isil Dillig UT Austin, Rishabh Singh Microsoft Research DOI 16:1422mTalk SQLizer: Query Synthesis from Natural LanguageOOPSLANavid Yaghmazadeh University of Texas, Austin, Yuepeng Wang University of Texas at Austin, Isil Dillig UT Austin, Thomas Dillig DOI 16:3722mTalk Synthesizing Configuration File Specifications with Association Rule LearningOOPSLAMark Santolucito Yale University, Ennan Zhai Yale University, USA, Rahul Dhodapkar MongoDB, USA, Aaron Shim Microsoft, USA, Ruzica Piskac Yale University DOI 16:5922mTalk Natural Synthesis of Provably-Correct Data-Structure ManipulationsOOPSLAXiaokang Qiu Purdue University, Armando Solar-Lezama MIT CSAIL DOI