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-andarrows" 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-interpretationbased 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.
Another related technique is Storyboard Programming REF for learning data structure manipulation programs from examples by combining abstract interpretation and shape analysis.
Synthesizing data structure manipulations from storyboards
ESEC/FSE '11
Computer Science