Sunday, May 22, 2011

Covariance and Contravariance

Type declarations on method parameters and return values are also constraints on the possible values that can be passed between a method and its caller.  As such, they form part of the contract for the method.  This is, in fact, a required part of the contract in statically-typed languages.  (Unfortunately, this is typically the only part of the contract that gets written.)

Suppose you have a class called Complex representing complex numbers, and a method that adds two numbers and returns the result.  In an object-oriented fashion, the method signature will be Complex add(Complex other), and a call c1.add(c2) will add the numbers c1 and c2 and return the sum.  The type declaration "Complex other" in the method signature is a precondition that requires callers to pass only objects of type Complex to this method, and the declaration that the result is Complex is a postcondition ensuring that only Complex objects will ever be returned by the method.

Normally, we don't really think of type declarations as a contract, since they are enforced by the compiler and no further action is required by the programmer to ensure that the contracts are indeed satisfied.  But if you think of type declarations as contracts in the context of Liskov's Behavioral Subtyping Principle, they have interesting consequences.  One is that subclasses are only allowed to strengthen postcondition but never weaken them.  This means that subclasses may return more specialized types than Complex.  This is not surprising; it is quite likely that there are several implementations of complex number, all of which are subtypes of Complex; for example, ComplexAsCartesian and ComplexAsPolar, referring to the two most common representations of complex numbers.  It is perfectly permissible for the add method of each subclass to return elements of that subclass (although that is not always the best policy).  But can you redefine the return type of ComplexAsCartesian.add to be ComplexAsCartesian rather than just Complex as in the superclass?  The answer depends on the programming language, and even on the language version.  For example, Java originally didn't allow any changes in method signatures, but since Java 5 it is possible to redeclare more specific types (that is, subtypes) for method return values.

This kind of change, where subclasses use subtypes of those used in their superclasses, is called a covariant change, since the direction of change is the same: as you go down the inheritance hierarchy, types get more specialized (that is, also go down).  Covariance is very natural to use in practice.  In addition to the example above, you can think of modeling artifacts (physical or virtual) that need to be connected in various ways.  Often, as you become more specific in one dimension, you need to be more specific in others.  For example, every laptop needs a power supply.  But specific laptops have dedicated power supplies, and you can't use any power supply with any laptop.  So the most abstract Laptop class may define an attribute called powerSupply, whose type is PowerSupply.  But an ABCLaptop requires an XYZPowerSupply, so the type of the power supply goes down the hierarchy as the type of the laptop goes down.

Covariance is all very well for method return types, where it fits the Behavioral Subtyping Principle.  But it contradicts the principle for method arguments.  The type of a method argument is like a precondition, since it constrains the values that the caller can pass to the method.  Preconditions may only be weakened in subtypes; this means that argument types can only be generalized in subtypes.  This is called contravariance, since argument types to up the hierarchy in subtypes.  So here we have a conflict between what is theoretically correct (contravariance for argument types) and what is useful (covariance).

There is a large debate on this issue, and different languages treat it differently.  None of C/C++, Java, or C# allow any change in argument types (this is called invariance).  This is, in fact, unrelated to the issue of covariance versus contravariance; it is a consequence of the fact that these languages support overloading (see Overriding and Overloading).  As a result, any change in method argument types defines an overloaded method, which is unrelated to the original method.  Eiffel follows the practical route, supporting covariance of argument types, and incurring the inevitable cost.  This cost is the lack of compile-time type checking for these cases.  In statically-typed languages, including all the ones mentioned above, we expect the compiler to type-check the program so that no type violations will occur at runtime (with some other notable exceptions, such as type casting and some uses of generics in Java).  Covariance creates another exception to this rule.

Of course, preventing covariance in the language doesn't solve anything, since in practice it is still necessary.  What programmers do when the language doesn't support covariance is to write their own tests in subclasses, checking for the correct subtypes and throwing exceptions when they are incorrect.  So even though the program is fully type-checked, there are still type-related exceptions at runtime.  But because these are programmed manually rather than being thrown by the language runtime, language designers feel it isn't their responsibility.  This ostrich effect is, of course, completely pointless.

No comments:

Post a Comment