Substitution Polymorphism for Object-Oriented Programming

Abstract

We introduce substitution polymorphism as a new basis for typed object-oriented languages. While avoiding subtypes and polymorphic types, this mechanism enables optimal static type-checking of generic classes and polymorphic functions. The novel idea is to view a class as having a family of implicit subclasses, each of which is obtained through a substitution of types. This allows instantiation of a generic class to be merely subclassing and resolves the problems in the Eiffel type system reported by Cook. All subclasses, including the implicit ones, can reuse the code implementing their superclass.