Learning abstractions for program synthesis

DOI10.1007/978-3-319-96145-3_22MaRDI QIDQ6045015zbMATH OpenFDO

Authors

Publication date 26 May 2023

Published in Computer Aided Verification (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1804.04152

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Many example-guided program synthesis techniques use abstractions to prune the search space. While abstraction-based synthesis has proven to be very powerful, a domain expert needs to provide a suitable abstract domain, together with the abstract transformers of each DSL construct. However, coming up with useful abstractions can be non-trivial, as it requires both domain expertise and knowledge about the synthesizer. In this paper, we propose a new technique for learning abstractions that are useful for instantiating a general synthesis framework in a new domain. Given a DSL and a small set of training problems, our method uses tree interpolation to infer reusable predicate templates that speed up synthesis in a given domain. Our method also learns suitable abstract transformers by solving a certain kind of second-order constraint solving problem in a data-driven way. We have implemented the proposed method in a tool called ATLAS and evaluate it in the context of the BLAZE meta-synthesizer. Our evaluation shows that (a) ATLAS can learn useful abstract domains and transformers from few training problems, and (b) the abstractions learned by ATLAS allow BLAZE to achieve significantly better results compared to manually-crafted abstractions.

Recommendations

• Synthesis with abstract examples
• Abstraction-based interaction model for synthesis
• From program verification to program synthesis
• Programmable program synthesis
• Programming by predicates: a formal model for interactive synthesis

Cited in

(11)

• AUTOMAT[\texttt{R}]IX: learning simple matrix pipelines
• Toward neural-network-guided program synthesis and verification
• Synthesis with abstract examples
• Program synthesis using deduction-guided reinforcement learning
• D^3: data-driven disjunctive abstraction
• Learning programs from noisy data
• Automated discovery of simulation between programs
• Computer Aided Verification
• Learning programs with magic values
• Bootstrapping library-based synthesis
• Neural network-guided synthesis of recursive list functions

This page was built for publication: Learning abstractions for program synthesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6045015)