Posts by Collection

portfolio

publications

Program Synthesis by Type-Guided Abstraction Refinement

Published in Principles of Programming Languages 2020, 2019

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 languages like Java do scale, but only apply to components over monomorphic data and functions: polymorphic data and functions 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.

Recommended citation: Guo, Z. (2019). "Program Synthesis by Type-Guided Abstraction Refinement." POPL 2020. 1(1). http://michaelbjames.com/files/hoogle-plus.pdf

talks

Component-based Type-driven Synthesis

Published:

I discussed Hoogle+, one of my research projects. It is a component-based type-driven synthesis technique for Haskell. Relying on a library of everyday functions and an input type query, the system finds an inhabitant of the, potentially polymorphic, type using those provided component set. The search tames an explosion of infinite types through a novel type-guided abstraction refinement (TYGAR) approach.

teaching

Undergraduate Teaching Assistant

COMP 105 - Programming Languages, Tufts University, 2015

Teaching Assistant for Kathleen Fisher’s programming languages course. I led a weekly recitation for students to better understand the semantic differences between imperative and functional programming languages. I helped to grade student homework assignments and tests.

Graduate Teaching Assistant

CSE130 - Programming Languages, University California, San Diego, 2019

Teaching Assistant for Nadia Polikarpova’s programming languages course. I ran a discussion section to reinforce knowledge on the Haskell programming language and run test-prep. As with any course, I held office hours, graded assignments/exams, and tended the garden of Piazza questions.