PriMagic: Component-Based Synthesis of Loopy and Non-Loopy Programs
Abstract/Contents
- Abstract
- Previous works in component-based synthesis have struggled to synthesize loops and other control structures. We present PriMagic, a new approach to component-based synthesis that can synthesize loopy programs from input-output examples. Our approach first mines primitives: by generating random straight-line programs and remembering those that are consistent with many input-output examples, we can obtain a set of code fragments that are likely to be useful for synthesis. Then, we randomly generate programs where we leave control structure conditions blank. We evaluate these partial programs using the idea of magic conditions, where we analyze the different code flows to determine if it is possible for the partial program to pass all test cases. In the last step, we resolve the magic conditions by filling them with random Boolean expressions. We demonstrate that PriMagic can synthesize short but interesting loopy programs within several minutes, and that it can be a useful tool for API translation.
Description
Type of resource | text |
---|---|
Date created | May 9, 2017 |
Creators/Contributors
Author | Shi, Kensen |
---|---|
Degree granting institution | Stanford University, Department of Computer Science |
Primary advisor | Liang, Percy |
Subjects
Subject | PriMagic |
---|---|
Subject | program synthesis |
Subject | component-based synthesis |
Subject | loops |
Subject | Department of Computer Science |
Subject | honors thesis |
Genre | Thesis |
Bibliographic information
Access conditions
- Use and reproduction
- User agrees that, where applicable, content will not be used to identify or to otherwise infringe the privacy or confidentiality rights of individuals. Content distributed via the Stanford Digital Repository may be subject to additional license and use restrictions applied by the depositor.
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Preferred citation
- Preferred Citation
- Shi, Kensen. (2017). PriMagic: Component-Based Synthesis of Loopy and Non-Loopy Programs. Stanford Digital Repository. Available at: http://purl.stanford.edu/ym983tb1954
Collection
Undergraduate Theses, School of Engineering
View other items in this collection in SearchWorksContact information
- Contact
- kensens@stanford.edu
Also listed in
Loading usage metrics...