Ninth Annual IEEE Symposium on

Logic in Computer Science (LICS 1994)

Paper: Efficient inference of object types (at LICS 1994)

Authors: Jens Palsberg


Abadi and Cardelli (1994) have investigated a calculus of objects. 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”. In this paper we give an O(n3) algorithm for each of the four type inference problems and we prove that all the problems are P-complete


    author = 	 {Jens Palsberg},
    title = 	 {Efficient inference of object types},
    booktitle =  {Proceedings of the Ninth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1994},
    year =	 1994,
    editor =	 {Samson Abramsky},
    month =	 {July}, 
    pages =      {186--195},
    location =   {Paris, France}, 
    publisher =	 {IEEE Computer Society Press}