Genericity and inheritance

We present type substitution as a new genericity mechanism for object-oriented languages. It is a subclassing concept on the same footing as inheritance, and is more flexible than parameterized classes. We prove that type substitution and inheritance together form an orthogonal basis for a general subclass relation that captures type-safe code reuse. Thus, genericity and inheritance are independent, complementary components of a unified concept. Our result is obtained in a novel model of classes which encompasses classes as types and assignments