Test-driven synthesis
Authors:
Open Access
- 5 June 2014
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 49 (6) , 408-418
Abstract
Programming-by-example technologies empower end-users to create simple programs merely by providing input/output examples. Existing systems are designed around solvers specialized for a specific set of data types or domain-specific language (DSL). We present a program synthesizer which can be parameterized by an arbitrary DSL that may contain conditionals and loops and therefore is able to synthesize programs in any domain. In order to use our synthesizer, the user provides a sequence of increasingly sophisticated input/output examples along with an expert-written DSL definition. These two inputs correspond to the two key ideas that allow our synthesizer to work in arbitrary domains. First, we developed a novel iterative synthesis technique inspired by test-driven development---which also gives our technique the name of test-driven synthesis ---where the input/output examples are consumed one at a time as the program is refined. Second, the DSL allows our system to take an efficient component-based approach to enumerating possible programs. We present applications of our synthesis methodology to end-user programming for transformations over strings, XML, and table layouts. We compare our synthesizer on these applications to state-of-the-art DSL-specific synthesizers as well to the general purpose synthesizer Sketch.Keywords
Funding Information
- Microsoft Research
This publication has 24 references indexed in Scilit:
- Spreadsheet data manipulation using examplesCommunications of the ACM, 2012
- Learning semantic string transformations from examplesProceedings of the VLDB Endowment, 2012
- Synthesizing Number Transformations from Input-Output ExamplesLecture Notes in Computer Science, 2012
- Spreadsheet table transformations from examples2011
- Automating string processing in spreadsheets using input-output examples2011
- Grammar-based Genetic Programming: a surveyGenetic Programming and Evolvable Machines, 2010
- Automatic program repair with evolutionary computationCommunications of the ACM, 2010
- Efficient Exhaustive Generation of Functional Programs Using Monte-Carlo Search with Iterative DeepeningLecture Notes in Computer Science, 2008
- Inductive functional programming using incremental program transformationArtificial Intelligence, 1995
- Eliminating branches using a superoptimizer and the GNU C compiler1992