Breaking through the n³ barrier: Faster object type inference

Abadi and Cardelli [AC96] have presented and investigated object calculi that model most object-oriented features found in actual objectoriented 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(n³), 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(n³) to the following time complexities: no subtyping subtyping w/o rec. types O(n) O(n²) with rec. types O(n log² n) O(n²) The key ingredient that lets us "beat" the wors..