Efficient Inference of Object Types

Jens Palsberg


Abadi and Cardelli have recently investigated a calculus of objects
[2]. The calculus supports a key feature of object-oriented languages:
an object can be emulated by another object that has more refined
methods. Abadi and Cardelli presented four first-order type systems
for the calculus. The simplest one is based on finite types and no
subtyping, and the most powerful one has both recursive types and
subtyping. Open until now is the question of type inference, and
in the presence of subtyping the absence of minimum typings poses
practical problems for type inference [2].
In this paper we give an O(n^3) algorithm for each of the four type
inference problems and we prove that all the problems are P-complete.
We also indicate how to modify the algorithms to handle functions and

Full Text:


DOI: http://dx.doi.org/10.7146/brics.v2i32.19935
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.

ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library