Refinement types and computational duality.

Abstract:

One lesson learned painfully over the past twenty years is the perilous interaction of Curry-style typing with evaluation order and side-effects. This led eventually to the value restriction on polymorphism in ML, as well as, more recently, to similar artifacts in prototype refinement type systems for ML with intersection and union types. For example, some of the traditional subtyping laws for unions and intersections are unsound in the presence of effects, while union-elimination requires an evaluation context restriction in addition to the value restriction on intersection-introduction.

Our aim is to show that rather than being ad hoc artifacts, phenomena such as the value and evaluation context restrictions arise naturally in type systems for effectful languages, out of principles of duality. Beginning with a review of recent work on the Curry-Howard interpretation of focusing proofs as pattern-matching programs, we explain how to interpret intersection and union refinements on these programs, and how to logically derive the subtyping relationship via an identity coercion interpretation. The value restriction, etc., emerge out of this analysis. However, this abstract account does not immediately yield an effective type system, essentially because the syntax is infinitary—both "infinitely wide" and "infinitely deep". We show how to mechanically construct a finitary syntax by applying two well-known PL techniques—pattern-compilation and defunctionalization—and conclude by giving this finitary syntax an algorithmic refinement type system. Parallel to the text, a formalization in the dependently-typed functional language Agda is described, both for the sake of clarifying these ideas, and also because it was an important guide in developing them. As one example, the Agda encoding split very naturally into an intrinsic ("Church") view of well-typed programs, and an extrinsic ("Curry") view of refinement typing for those programs.