Efficient Type Matching

Palsberg and Zhao~\cite{PalsbergZhao00} presented an $O(n^2)$ time algorithm for matching two recursive types. In this paper, we present an $O(n \log n)$ algorithm for the same problem. Our algorithm works by reducing the type matching problem to the well-understood problem of finding a size-stable partition of a graph. Our result may help improve systems, such as Polyspin and Mockingbird, that are designed to facilitate interoperability of software components. We also discuss possible applications of our algorithm to {\tt\small Java}. Issues related to subtyping of recursive types are also discussed.
Download:[PS,PDF]

Somesh Jha

Last modified: Fri Apr 11 16:17:02 CDT 2003