Write a Blog >>
Wed 22 Jan 2020 11:45 - 12:07 at Ile de France III (IDF III) - Synthesis Chair(s): Mohsen Lesani

We consider the problem of type-directed component-based synthesis where, given a set of (typed) components and a query type, the goal is to synthesize a term that inhabits the query. Classical approaches based on proof search in intuitionistic logics do not scale up to the standard libraries of modern languages, which span hundreds or thousands of components. Recent graph reachability based methods proposed for Java do scale, but only apply to monomorphic data and components: polymorphic data and components infinitely explode the size of the graph that must be searched, rendering synthesis intractable. We introduce type-guided abstraction refinement (TYGAR), a new approach for scalable type-directed synthesis over polymorphic datatypes and components. Our key insight is that we can overcome the explosion by building a graph over abstract types which represent a potentially unbounded set of concrete types. We show how to use graph reachability to search for candidate terms over abstract types, and introduce a new algorithm that uses proofs of untypeability of ill-typed candidates to iteratively refine the abstraction until a well-typed result is found.

We have implemented TYGAR in H+, a tool that takes as input a set of Haskell libraries and a query type, and returns a Haskell term that uses functions from the provided libraries to implement the query type. Our support for polymorphism allows H+ to work with higher-order functions and type classes, and enables more precise queries due to parametricity. We have evaluated H+ on 44 queries using a set of popular Haskell libraries with a total of 291 components. H+ returns an interesting solution within the first five results for 32 out of 44 queries. Our results show that TYGAR allows H+ to rapidly return well-typed terms, with the median time to first solution of just 1.4 seconds. Moreover, we observe that gains from iterative refinement over exhaustive enumeration are more pronounced on harder queries.

tygar (tygar_v4.pdf)854KiB

Wed 22 Jan
Times are displayed in time zone: Saskatchewan, Central America change

11:45 - 12:30: SynthesisResearch Papers at Ile de France III (IDF III)
Chair(s): Mohsen LesaniUniversity of California, Riverside
11:45 - 12:07
Program Synthesis by Type-Guided Abstraction Refinement
Research Papers
Zheng GuoUniversity of California, San Diego, Michael B. JamesUniversity of California, San Diego, David JustoUniversity of California, San Diego, Jiaxiao ZhouUniversity of California, San Diego, Ziteng WangUniversity of California, San Diego, Ranjit JhalaUniversity of California, San Diego, Nadia PolikarpovaUniversity of California, San Diego
Link to publication DOI Media Attached File Attached
12:07 - 12:30
Synthesizing Replacement Classes
Research Papers
Malavika SamakCSAIL, MIT, Deokhwan KimCSAIL, MIT, Martin RinardMIT
Link to publication DOI Media Attached File Attached