Object-Oriented Type Inference

We present a new approach to inferring types in untyped object-oriented programs with inheritance, assignments, and late binding. It guarantees that all messages are understood, annotates the program with type information, allows polymorphic methods, and can be used as the basis of an optimizing compiler. Types are finite sets of classes and subtyping is set inclusion. Using a trace graph, our algorithm constructs a set of conditional type constraints and computes the least solution by least fixed-point derivation. 1 Introduction Untyped object-oriented languages with assignments and late binding allow rapid prototyping because classes inherit implementation and not specification. Late binding, however, can cause programs to be unreliable, unreadable, and inefficient [27]. Type inference may help solve these problems, but so far no proposed inference algorithm has been capable of checking most common, completely untyped programs [9]. We present a new type inference algorithm for a ba..