Sian Jha, Jens Palsberg, Tian Zhao, Fritz Henglein. Efficient Type Matching. TOPPS Report D-474 Department of Computer Science, University of Copenhagen (DIKU), 2002.
Download paper:
Adobe portable document (pdf)
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Palsberg and Zhao presented an $O(n^2)$ time algorithm for matching two recursive types; that is, deciding type isomorphism under associative-commutative type constructors. In this paper, we present an $O(n \log n)$ algorithm for matching recursive types and an $O(n)$ algorithm for matching nonrecursive types. The linear-time algorithm for nonrecursive types works without hashing or pointer arithmetic, by employing multiset discrimination due to Paige {\it et al.}. The $O(n \log n)$ algorithm for recursive types works by reducing the type matching problem to the problem of finding a size-stable partition of a graph, which has $O(n \log n)$ algorithms due to Cardon/Crochemore and Paige/Tarjan. The key to these algorithms is the use of a ``modify-the-smaller-half'' approach pioneered by Hopcroft and Ullman for DFA minimization. Our results 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
[ Rectype ] [ Parametricity ]
S. Jha
J. Palsberg
Tian Zhao
Fritz Henglein
@TechReport{jpzh2002,
Author = {Jha, Sian and Palsberg, Jens and Zhao, Tian and Henglein, Fritz},
Title = {Efficient Type Matching},
Institution = {Department of Computer Science, University of Copenhagen (DIKU)},
Year = {2002}
}
Get EndNote Reference (.ref)