August 2004

Covariant Method Specialization
(Rules for Method Dispatch)

Introduction

This document is an exploration into the reasons why covariant method specialization must be used in an object oriented environment. Covariant method specialization is commonly implemented in existing languages albeit statically. You can avoid this exploration, and get a good feel for covariant method specialization, by reviewing a short program that demonstrates the difference between static and dynamic specialization.

Overview

Naively, we should be free to invent the formal definition of method subtyping, but we will find that only one definition is consistent and useful. We will investigate the possibility of using contravariant, covariant and invariant method subtyping.

We want to derive our arguments from the intuitive subtyping rule: T' is a subtype of T (written T' T) if, any only if, any member of T' can be used wherever a member of T is required.

Of course, being intuitive, this subtyping rule is not well defined, and only serves as a guide for developing formal subtyping rules. For instance, in terms of sets: S T implies S T.

Definitions

Specialization	-	creating a new object from a base object, yet maintaining the base's contracted interface.
Extension	-	creating a new object from a base object and expanding or changing the base contracted interface
Subtyping	-	the act of defining/constucting/discovering new subtypes

Object Oriented Method Subtyping

An object oriented environment adds a unique set of conditions. Among them is the relationship between class subtyping and method subtyping. What we want is a rule that encapsulates the following idea: If C' is a subtype of C, then the methods of C' should be able to be used in place of the methods of C.

Let C, C' be classes and C.f and C'.f be their respective methods.

    C C' C.f C'.f (call this the OO method rule)

To make sure I am clear, the above rule is using two concepts of subtype, the subtype relation between classes and the subtype relation between functions. We have yet to provide a definition for the latter. The rest of this document investigates our options.

Contravariant Method Subtyping

Consider a function f:A -> B. We want to define the subtype f':A' -> B' of f, (read f' f). Naively, we could allow A A' (domain of f' includes the domain of f) and B' B (the codomain of f' is a subset of that if f). Formally we define:

    (f':A' -> B') (f:A -> B) where A' A and B' B.

This is called contravariant subtyping, named because the domain subtype relationship appears in the opposite order of the function subtype relationship. Note the "contra" qualifier on the subtyping relation; we will use qualifiers to distinguish between the different kinds of proposed method subtyping.

Contravariant Inconsistency

An inconsistency between OO method subtyping and contravariant method subtyping exists. The inconsistency is revealed by the fact that the contravariant rule dictates the subtype relationship of the method domains. We consider the case of a method that acts on its own type.

(C'.f:C' -> B') (C.f:C -> B)

=> C'.f C.f

=> C' C (using contravariant rule)

=> C'.f C.f (using OO method rule)

This leads to a contradiction if C'.f is not the same as C.f. Therefore we conclude that contravariant method subtyping is not consistent in an object-oriented environment.

Invariant Method Subtyping

The contravariant inconsistency is easily avoided by realizing that strict subtyping of the domain is the cause of the inconsistency. Invariant method subtyping demands that both functions have the same domain:

    (f':A -> B') (f:A -> B) where B' B.

Although invariant rule prevents inconsistencies, it is hardly useful for inheritance because it demands complete method replacement. We do not put a qualifier on this subtyping relation because we intend to use it as THE method subtyping relation.

It would be nice to be able to keep most of parent method code, and only change the portions that need changing. Using covariant method specialization for specialization allows the programmer to use the programming-by-difference paradigm.

Covariant Method Specialization

On its own, the covariant method subtyping has its own shortcomings, but when covariant method subtyping is used for declaring method specialization, it becomes an intuitive framework for inheritance. Here is the covariant subtype definition:

    (f':A' -> B') (f:A -> B) where A' A and B' B

Here f' is NOT inherited from f, technically it is just covariant to f. We are actually defining a new function, f⁰, using f' as a partial basis for construction. Please notice that f⁰ is an invariant method subtype of f.

    f⁰:A -> B where f⁰(a)=f'(a) a A', f⁰(r)=f(r) r R, R = A - A'

In terms of an OO framework, the relation to f' and f⁰ can be made formal using instances.

Let A, A', C, C' be classes and c, c', a, r be objects such that:

C' C, c C, c' C',
A' A, a A', r A - A'

then

c.f = f
c'.f = f⁰

or, more specifically,

c.f(a) = f(a) //c.f = f by definition
c.f(r) = f(r)
c'.f(a) = f'(a) //c'.f is redefined on domain A'
c'.f(r) = f(r) //c'.f defaults to c.f outside A'

And this is exemplified in the example.

In Practice

The demand that all methods and thier specializations have the same domain is not a big issue. Going further and demanding that the domain of all methods includes all objects for all parameters is also not a big issue. We simply let methods return an UnexpectedParameterException for any domain values that do not make sense.

Summary

In an OO framework, covariant method specialization is a consistent and natural form of programming-by-difference. None of this is big news; many languages already implement a static form of covariant method specialization under the more general name of method overloading. The DBOS uses covariant method specialization to perform method specialization.

Correction to "more specifially..."
March 20 2004, Changed some terms
July 17 2002, added introduction
April 17 2002, a complete rewrite
 July 28 2001, first writing