Annotations for Intersection Typechecking

ITRS '12 (Dubrovnik, June 2012); post-proceedings to appear in EPTCS

Joshua Dunfield

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.

Reader’s guide

This paper takes a new look at annotations in systems with intersection types, in the light of a mechanism from the elaboration-based approach to intersection typing. It is also a retrospective deconstruction of the contextual typing annotations from "Tridirectional Typechecking".

Workshop slides

Version to appear in EPTCS (Proceedings of ITRS '12)

Version of June 2012 (pre-proceedings)

BibTeX entry

@Unpublished{Dunfield12:annotation-preliminary,
  author    =  {Joshua Dunfield},
  title     =  {Annotations for Intersection Typechecking},
  month     =  jun,
  year      =  {2012},
  note      =  {\url{http://www.cs.cmu.edu/~joshuad/papers/sectanno}}
}
  

Joshua Dunfield