Nordic Journal of Computing Bibliography

Jens Palsberg and Trevor Jim. Type Inference with Simple Selftypes is NP-complete. Nordic Journal of Computing, 4(3):259-286, Fall 1997.
Abstract

The metavariable self is fundamental in object-oriented languages. Typing self in the presence of inheritance has been studied by Abadi and Cardelli, Bruce, and others. A key concept in these developments is the notion of selftype, which enables flexible type annotations that are impossible with recursive types and subtyping. Bruce et al. demonstrated that, for the language TOOPLE, type checking is decidable. Open until now is the problem of type inference with selftype. In this paper we present a simple type system with selftype, recursive types, and subtyping, and we prove that type inference is NP-complete. With recursive types and subtyping alone, type inference is known to be P-complete.Our example language is the object calculus of Abadi and Cardelli. Both our type inference algorithm and our lower bound are the first such results for a type system with selftype.

Categories and Subject Descriptors: D.3.2 [Programming Languages]: Language Classifications; F.3.3 [Logics and Meanings of Programs]: Studies of Program Constructs

Additional Key Words and Phrases: type inference, constraints

Selected references


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database