Breaking through the n3 barrier: Faster object type inference

Abadi and Cardelli [AC96] 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 not based on λ-calculus. They present a series of type systems for their calculi, four of which are first-order. Palsberg [Pal95] has shown how typability in each one of these systems can be decided in time O(n3), 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 (dynamic) transitive closure bottleneck and improve each one of the four type inference problems from O(n3) to the following time complexities: no subtyping subtyping w/o rec. types O(n) O(n2) with rec. types O(n log2 n) O(n2) The key ingredient that lets us “beat ” the worst-case time com-plexity induced by using general dynamic transitive closure or similar algorithmic methods is that object subtyping is 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 equal types.