Annotations for intersection typechecking

Abstract

In functional programming languages, the classic form of annotation is a single type constraint on a term. Intersection types add complications: a single term may have to be checked several times against different types, in different contexts, requiring annotation with several types. Moreover, it is useful (in some systems, necessary) to indicate the context in which each such type is to be used.

This paper explores the technical design space of annotations in systems with intersection types. Earlier work (Dunfield and Pfenning, 2004) introduced contextual typing annotations, which we now tease apart into more elementary mechanisms: a “right hand” annotation (the standard form), a “left hand” annotation (the context in which a right-hand annotation is to be used), a merge that allows for multiple annotations, and an existential binder for index variables. The most novel element is the left-hand annotation, which guards terms (and right-hand annotations) with a judgment that must follow from the current context.