Synthesis from Examples: Interaction Models and Algorithms
- 1 September 2012
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Examples are often a natural way to specify various computational artifacts such as programs, queries, and sequences. Synthesizing such artifacts from example based specifications has various applications in the domains of end-user programming and intelligent tutoring systems. Synthesis from examples involves addressing two key technical challenges: (i) design of a user interaction model to deal with the inherent ambiguity in the example based specification. (ii) design of an efficient search algorithm - these algorithms have been based on paradigms from various communities including use of SAT/SMT solvers (formal methods community), version space algebras (machine learning community), and A*-style goal-directed heuristics (AI community). This paper describes some effective user interaction models and algorithmic methodologies for synthesis from examples while discussing synthesizers for a variety of artifacts ranging from tricky bit vector algorithms, spreadsheet macros for automating repetitive data manipulation tasks, ruler/compass based geometry constructions, algebraic identities, and predictive intellisense for repetitive drawings and mathematical terms.Keywords
This publication has 22 references indexed in Scilit:
- From relational verification to SIMD loop synthesisPublished by Association for Computing Machinery (ACM) ,2013
- Spreadsheet data manipulation using examplesCommunications of the ACM, 2012
- QuickDrawPublished by Association for Computing Machinery (ACM) ,2012
- Synthesizing geometry constructionsPublished by Association for Computing Machinery (ACM) ,2011
- Automating string processing in spreadsheets using input-output examplesPublished by Association for Computing Machinery (ACM) ,2011
- Oracle-guided component-based program synthesisPublished by Association for Computing Machinery (ACM) ,2010
- Discovering affine equalities using random interpretationPublished by Association for Computing Machinery (ACM) ,2003
- Programming by Demonstration Using Version Space AlgebraMachine Learning, 2003
- Generalization as searchArtificial Intelligence, 1982
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980