Object-oriented type inference

Publisher Website
Google Scholar
Abstract
We present a new approach to inferring types in un- typed object-oriented programs with inheritance, assignments, and late binding. It guarantees that all messages are understood, annotates the pro- gram with type information, allows polymorphic methods, and can be used as the basis of an op- timizing 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. The algorithm guarantees that all messages are un- derstood, annotates the program with type infor- mation, allows polymorphic methods, and can be used as the basis of an optimizing compiler. Types are finite sets of classes and subtyping is set in- clusion. Given a concrete program, the algorithm constructs a finite graph of type constraints. The program is typuble if these constraints are solvable. The algorithm then computes the least solution in worst-case exponential time. The graph contains all type information that can be derived from the program without keeping track of nil values or flow analyzing the contents of instance variables. This makes the algorithm capable of checking most com- mon programs; in particular, it allows for polymor- phic methods. The algorithm is similar to previous

This publication has 15 references indexed in Scilit: