Research on "Formal Methods in Computing"

Rank 2 Intersection and Polymorphic Recursion

(Superseded by the paper [Damiani, 2007] )

ABSTRACT. Let |- be a rank-2 intersection type system. We say that a term is "|-simple" (or just "simple" when the system |- is clear from the context) if system |- can prove that it has a simple type. In this paper we propose new typing rules and algorithms that are able to type recursive definitions that are not simple. At the best of our knowledge, previous algorithms for typing recursive definitions in presence of intersection types allow only simple recursive definitions to be typed. The proposed rules are also able to type interesting examples of "polymorphic recursion" (i.e., recursive definitions "REC {x=e}" where different occurrences of "x" in "e" are used with different types). Moreover, the underlying techniques do not depend on particulars of rank-2 intersection, so they can be applied to other type systems.

An on-line demostration of a prototype implementation of the type system presented in the paper is available.

• pdf ( © Springer-Verlag )

BIBTEX.

@conference{Damiani:TLCA-05,
   author    = {F. Damiani},
   title     = {{Rank-2 Intersection and Polymorphic Recursion}},
   booktitle = {{TLCA'05}},
   year      = {2005},
   publisher = {Springer},
   pages     = {146-161},
   series    = {LNCS},
   volume = {3461}
}