Fritz Henglein. Breaking Through the $n^3$ Barrier: Faster Object Type Inference. Theory and Practice of Object Systems (TAPOS), Invited paper selected from 4th Int'l Workshop on Foundations of Object-Oriented Languages (FOOL), January 1997, Paris, France, 5(1):57-72, 1999.
Download paper:
Follow the link
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.
Abadi and Cardelli present a series of type systems for their object calculi, four of which are first-order. Palsberg has shown how typability in each one of these systems can be decided in time $O(n^3)$ and space $O(n^2)$, where $n$ is the size of an untyped object expression, using an algorithm based on dynamic transitive closure. In this paper we improve each one of the four type inference problems from $O(n^3)$ to the following time complexities: \begin{enumerate} \item no subtyping/no recursive types: $O(n)$; \item no subtyping/with recursive types: $O(n \log^2 n)$; \item with subtyping/no recursive types: $O(n^2)$; \item with subtyping/with recursive types: $O(n^2)$. \end{enumerate} Furthermore, our algorithms improve the space complexity from $O(n^2)$ to $O(n)$ in each case. The key ingredient that lets us ``beat'' the worst-case time and space complexity induced by general dynamic transitive closure or similar algorithmic methods is that object subtyping, in contrast to record subtyping, is \emph{invariant}: an object type is a subtype of a ``shorter'' type with a subset of the method names if and only if the common components have \emph{equal} types
[ Parametricity ] [ Dyntyp ]
@article{henglein99a,
Author = {Henglein, Fritz},
Title = {Breaking Through the $n^3$ Barrier: Faster Object Type Inference},
Journal = {Theory and Practice of Object Systems (TAPOS)},
Volume = {5},
Number = {1},
Pages = {57--72},
Year = {1999}
}
Get EndNote Reference (.ref)