Synthesizing data structure manipulations from storyboards
Authors:
Open Access
- 9 September 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 289-299
Abstract
We present the Storyboard Programming framework, a new synthesis system designed to help programmers write imperative low-level data-structure manipulations. The goal of this system is to bridge the gap between the "boxes-and-arrows" diagrams that programmers often use to think about data-structure manipulation algorithms and the low-level imperative code that implements them. The system takes as input a set of partial input-output examples, as well as a description of the high-level structure of the desired solution. From this information, it is able to synthesize low-level imperative implementations in a matter of minutes. The framework is based on a new approach for combining constraint-based synthesis and abstract-interpretation-based shape analysis. The approach works by encoding both the synthesis and the abstract interpretation problem as a constraint satisfaction problem whose solution defines the desired low-level implementation. We have used the framework to synthesize several data-structure manipulations involving linked lists and binary search trees, as well as an insertion operation into an And Inverter Graph.National Science Foundation (U.S.). (Grant number CCF-1049406)Massachusetts Institute of Technology. Computer Science and Artificial Intelligence LaboratorKeywords
This publication has 22 references indexed in Scilit:
- ABC: An Academic Industrial-Strength Verification Tool2010
- Sketching concurrent data structures2008
- Program analysis as constraint solving2008
- Deriving linearizable fine-grained concurrent objectsACM SIGPLAN Notices, 2008
- Cyclic proofs of program termination in separation logic2008
- Constraint-Based Invariant Inference over Predicate AbstractionLecture Notes in Computer Science, 2008
- Binary Clause Reasoning in QBFLecture Notes in Computer Science, 2006
- Programming by sketching for bit-streaming programs2005
- Program Repair as a Game2005
- A Deductive Approach to Program SynthesisACM Transactions on Programming Languages and Systems, 1980