Program synthesis using abstraction refinement
Open accessThe DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Abstract
We present a new approach to example-guided program synthesis based on counterexample-guided abstraction refinement . Our method uses the abstract semantics of the underlying DSL to find a program P whose abstract behavior satisfies the examples. However, since program P may be spurious with respect to the concrete semantics, our approach iteratively refines the abstraction until we either find a program that satisfies the examples or prove that no such DSL program exists. Because many programs have the same input-output behavior in terms of their abstract semantics , this synthesis methodology significantly reduces the search space compared to existing techniques that use purely concrete semantics. While synthesis using abstraction refinement (SYNGAR) could be implemented in different settings, we propose a refinement-based synthesis algorithm that uses abstract finite tree automata (AFTA) . Our technique uses a coarse initial program abstraction to construct an initial AFTA, which is iteratively refined by constructing a proof of incorrectness of any spurious program. In addition to ruling out the spurious program accepted by the previous AFTA, proofs of incorrectness are also useful for ruling out many other spurious programs. We implement these ideas in a framework called Blaze, which can be instantiated in different domains by providing a suitable DSL and its corresponding concrete and abstract semantics. We have used the Blaze framework to build synthesizers for string and matrix transformations, and we compare Blaze with existing techniques. Our results for the string domain show that Blaze compares favorably with FlashFill, a domain-specific synthesizer that is now deployed in Microsoft PowerShell. In the context of matrix manipulations, we compare Blaze against Prose, a state-of-the-art general-purpose VSA-based synthesizer, and show that Blaze results in a 90x speed-up over Prose. In both application domains, Blaze also consistently improves upon the performance of two other existing techniques by at least an order of magnitude.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Cousot, P., & Cousot, R. (1977) · Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '77 · doi:10.1145/512950.512973 · Cited by 6,279 · cited 1×
“As standard in abstract interpretation [Cousot and Cousot 1977], we write γ (φ) to denote the set of concrete values represented by abstract value φ.”
BackgroundAlur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E., & Udupa, A. (2013) · 2013 Formal Methods in Computer-Aided Design · doi:10.1109/fmcad.2013.6679385 · Cited by 656
Self-citationAutomating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1925844.1926423 · Cited by 581
Smith, C., & Albarghouthi, A. (2016) · Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2908080.2908102 · Cited by 76 · cited 1×
“…[Feser et al. 2015; Yaghmazadeh et al. 2016], network policies [Yuan et al. 2014], data filtering [Wang et al. 2016], file manipulations [Gulwani et al. 2015], interactive parser synthesis [Leung et al. 2015], and synthesizing map-reduce distributed programs [Smith and Albarghouthi 2016].”
Method
Cited by
Program synthesis using conflict-driven learning
Feng, Y., Martins, R., Bastani, O., & Dillig, I. (2018) · Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3192366.3192382 · Cited by 111
“Other tools, such as λ 2 [9], Morpheus [7], and Blaze [37], similarly use logical reasoning to prune the search space but allow these specifications to be over-approximate.”
BackgroundSelf-citationAutoPandas: neural-backed generators for program synthesis
Bavishi, R., Lemieux, C., Fox, R., Sen, K., & Stoica, I. (2019) · Proceedings of the ACM on Programming Languages · doi:10.1145/3360594 · Cited by 73
“…2011; Parisotto et al. 2017], data wrangling [Feng et al. 2018, 2017; Le and Gulwani 2014], data processing [Smith and Albarghouthi 2016; Yaghmazadeh et al. 2018], syntax transformations [Rolim et al. 2017], database queries [Yaghmazadeh et al. 2017] and bit-vector manipulations [Jha et al. 2010].”
MethodMagicoder: Empowering Code Generation with OSS-Instruct
Wei, Y., Wang, Z., Liu, J., Ding, Y., & Zhang, L. (2023) · arXiv · doi:10.48550/arxiv.2312.02120 · Cited by 27
Wang, Y., Wang, X., & Dillig, I. (2018) · Proceedings of the ACM on Programming Languages · doi:10.1145/3276525 · Cited by 17
Self-citation
Metadata
- Authors
- Wang, X., Dillig, I., & Singh, R.
- Venue
- Proceedings of the ACM on Programming Languages
- Published
- 2017-12-27
- Volume
- 2
- Issue
- POPL
- Pages
- 1-30
- ISSN
- 2475-1421 (ISSN-L)
- OpenAlex
- W2765742677
- Cited by
- 73
- References
- 4
- FWCI
- 4.76
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.