%0 Conference Proceedings
%F henglein97f
%A Henglein, Fritz
%T Breaking through the $n^3$ barrier: Faster object type inference
%B Proc.\ 4th Int'l Workshop on Foundations of Object-Oriented Languages (FOOL), Paris, France
%E Pierce, Benjamin
%X Abadi and Cardelli have presented and investigated object calculi that model most object-oriented features found in actual object-oriented programming languages. The calculi are innate object calculi in that they are \emph{not} based on $\lambda$-calculus. They present a series of type systems for their 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)$, where $n$ is the size of an untyped object expression, using an algorithm based on dynamic transitive closure. He also shows that each of the type inference problems is hard for polynomial time under log-space reductions. In this paper we show how we can break through the \emph{(dynamic) transitive closure bottleneck} and improve each one of the four type inference problems from $O(n^3)$ to the following time complexities: \begin{center} \begin{tabular}{|l|c|c|} \hline & no subtyping & subtyping \\ \hline w/o rec. types & $O(n)$ & $O(n^2)$ \\ with rec. types & $O(n \log^2 n)$ & $O(n^2)$ \\ \hline \end{tabular} \end{center} % Furthermore, for each of the four calculi we present a principal % typing characterization for typable object expression which can be % computed in the given times. The key ingredient that lets us ``beat'' the worst-case time complexity induced by using general dynamic transitive closure or similar algorithmic methods is that object subtyping is \emph{invariant}: an object type is a subtype of a ``shorter'' type with a subset of the field names if and only if the common fields have \emph{equal} types
%U http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein1997.pdf
%8 January
%D 1997
%K parametricity
%K  dyntyp