Efficient Type Matching

Somesh Jha Jens Palsberg Tian Zhao

To appear at Foundations of Software Science and Computation Structures (FOSSACS02), Grenoble, France, 6-14 April, 2002


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.

Server START Conference Manager
Update Time 14 Dec 2001 at 14:02:37
Maintainer fossacs02@brics.dk.
Start Conference Manager
Conference Systems