Object Specification and Implementation

All object-oriented languages provide support for subtype polymorphism, which allows the writing of generic code that works for families of related types. There is also a need, however, to write code that is generic across types that have no real family relationship. To satisfy this need a programming language must provide a mechanism for parametric polymorphism, allowing for types as parameters to routines and types. We show that to support modular programming and separate compilation there must be a mechanism for constraining the actual parameters of the routine or type. We describe a simple and powerful constraint mechanism and compare it with constraint mechanisms in other languages in terms of both ease of use and semantic expressiveness. We also discuss the interaction between subtype and parametric polymorphism: we discuss the subtype relations that can exist between instantiations of parameterized types, and which of those relations are useful and can be implemented efficiently. We illustrate our points using examples in Theta, a new object-oriented language, and we describe the time- and space-efficient implementation of parametric polymorphism used in Theta.

Existing schemes for object layout and dispatch in the presence of multiple inheritance and separate compilation waste space and are slower than systems with single inheritance. This paper describes the bidirectional object layout, a new scheme for object layout that produces smaller objects and faster method invocations than existing schemes by automatically optimizing particular uses of multiple inheritance. The bidirectional object layout is used for the programming language Theta, and is applicable to languages like C++. This paper also demonstrates how to efficiently implement method dispatch when method signatures are allowed to change in subclasses. Most current statically compiled languages require identical signatures for efficiency.