Storyboard programming of data structure manipulations : a picture is worth 20 lines of code
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/60187 |
| _version_ | 1826217757665918976 |
|---|---|
| author | Singh, Rishabh |
| author2 | Armando Solar-Lezama. |
| author_facet | Armando Solar-Lezama. Singh, Rishabh |
| author_sort | Singh, Rishabh |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. |
| first_indexed | 2024-09-23T17:08:40Z |
| format | Thesis |
| id | mit-1721.1/60187 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T17:08:40Z |
| publishDate | 2010 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/601872019-04-11T02:46:42Z Storyboard programming of data structure manipulations : a picture is worth 20 lines of code Singh, Rishabh Armando Solar-Lezama. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. Includes bibliographical references (p. 67-69). We introduce Storyboard Programming, a new programming model that harnesses the programmer's visual intuition about a problem to synthesize a correct implementation. The motivation for our technique comes from the domain of data-structure manipulations. In this domain, programmers often think in terms of abstract graphical visualizations but have a hard time translating that intuition into low-level pointer manipulating code. We aim to bridge this gap and show that it is possible to derive the low-level implementation automatically from the graphical specifications with little additional input from the programmer. The storyboard in our programming model consists of a series of scenarios which show how the data-structure evolves under different conditions. We present two novel algorithms to synthesize the code from the storyboards. The algorithms derive an abstract domain and a set of correctness conditions automatically from the storyboards. The synthesizer uses the abstract domain to perform abstraction guided combinatorial synthesis. The resulting program is guaranteed to satisfy the correctness conditions derived from the storyboard, and to conform to the high-level structure specified by the programmer. We have implemented our framework successfully on top of the SKETCH system. Our implementation is capable of synthesizing several interesting data-structure manipulations such as insertion, deletion, rotation, reversal over linked list and binary search tree data structures. by Rishabh Singh. S.M. 2010-12-06T17:35:24Z 2010-12-06T17:35:24Z 2010 2010 Thesis http://hdl.handle.net/1721.1/60187 681919301 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 69 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Singh, Rishabh Storyboard programming of data structure manipulations : a picture is worth 20 lines of code |
| title | Storyboard programming of data structure manipulations : a picture is worth 20 lines of code |
| title_full | Storyboard programming of data structure manipulations : a picture is worth 20 lines of code |
| title_fullStr | Storyboard programming of data structure manipulations : a picture is worth 20 lines of code |
| title_full_unstemmed | Storyboard programming of data structure manipulations : a picture is worth 20 lines of code |
| title_short | Storyboard programming of data structure manipulations : a picture is worth 20 lines of code |
| title_sort | storyboard programming of data structure manipulations a picture is worth 20 lines of code |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/60187 |
| work_keys_str_mv | AT singhrishabh storyboardprogrammingofdatastructuremanipulationsapictureisworth20linesofcode |