Hole Refinements for Polymorphic Type-and-Example Driven Synthesis
Many synthesizers implicitly benefit from using polymorphic types, since parametric polymorphism reduces the search space. Additional synthesis constraints may interfere with \emph{parametricity}. In particular, a polymorphic type may cause otherwise feasible input-output examples to contradict each other. We present \textsc{Taxi} (\textbf{t}ype-\textbf{a}nd-e\textbf{x}ample based \textbf{i}nferencer), a tool for efficiently reasoning about the feasibility of polymorphic programs specified by input-output examples, and \textsc{Driver}, a tactic language for top-down program synthesis that uses feasibility reasoning to prune the search space. \textsc{Taxi} guarantees that every search state corresponds to a correct (albeit possibly partial) implementation. In addition, it allows for shortcutting the synthesis when a subspecification covers all cases. We show that these techniques have the potential to speed up top-down enumerative type-and-example driven synthesizers.
Tue 13 JanDisplayed time zone: Brussels, Copenhagen, Madrid, Paris change
09:00 - 10:30 | |||
09:00 5mDay opening | Welcome PEPM | ||
09:05 30mResearch paper | Hole Refinements for Polymorphic Type-and-Example Driven Synthesis PEPM Niek Mulleners Utrecht University, Johan Jeuring Utrecht University, Wouter Swierstra Utrecht University, Netherlands DOI | ||
09:35 30mResearch paper | Inferring Typing Rules for Contextual Sugars PEPM Tailai Yu Peking University, Zhichao Guan Peking University, Di Wang Peking University, Zhenjiang Hu Peking University DOI | ||
10:05 15mShort-paper | S4 modal sequent calculus as intermediate logic and intermediate language (Short Paper) PEPM File Attached | ||
10:20 15mShort-paper | Epistemic Logic for Polyglots (Short Paper) PEPM File Attached | ||