  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.
