Breaking through then3 barrier: Faster object type inference
✍ Scribed by Henglein, Fritz
- Book ID
- 101223358
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 217 KB
- Volume
- 5
- Category
- Article
- ISSN
- 1074-3227
No coin nor oath required. For personal study only.
✦ Synopsis
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:
no subtyping subtyping w/o rec. types
with rec. types
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 worstcase time and space complexity induced by general dynamic transitive closure or similar algorithmic methods is that object subtyping, in contrast to record subtyping, is 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 equal types.