Annotations for intersection typechecking

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

Jana Dunfield


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 in EPTCS 121 (Proceedings of ITRS '12)

BibTeX entry

  author    =  {Jana Dunfield},
  title     =  {Annotations for Intersection Typechecking},
  booktitle =  {Proceedings of the Workshop on Intersection
                Types and Related Systems (ITRS '12)},
  series    =  {EPTCS},
  volume    =  {121},
  year      =  {2013},
  pages     =  {35--47},
  note      =  {\url{arXiv:1307.8204 [cs.PL]}}

J. Dunfield