Contravariance [Was Re: what is easier to learn first?...]

[William Tanksley]

On Wed, 22 Mar 2000 02:39:40 -0500, Eric Jacobs wrote:
>mcfarlan at neca.com (D. Michael McFarland) wrote:

>> Twang! (Sound of an engineer being clothes-lined by a CS concept)

Happens to me all the time.

>> I spent much of the last couple of weeks working on a tensor class
>> (based on code from Konrad Hinsen's Scientific package, stolen and
>> mangled beyond recognition), implementing some of the many shorthand
>> notations for contraction of mixed tensors, so the words
>> "contravariance" and "covariance" here caught my eye.

No relation, unfortunately.

>> I hate to reveal my ignorance to this group (again), but I have to
>> ask: What do these terms mean in this context?

>That's okay. Contravariance and covariance here refer to something
>that Python doesn't have, at least not yet: a static type system.

Right.

The question these two design approaches take is what types of things
cause type errors.

You know that OO in general allows "subclass substitution", right?  That
is, anyplace I have a class I'm allowed to substitute a subclass of that
class.  (This works in Python, of course.)  For example, anyplace a
general WheeledVehicle is allowed, a Bicycle will also be allowed.

The problem is that Bertrand Meyer, the inventor of Eiffel and the author
of the classic "Object Oriented Software Construction" (a book which I did
not enjoy as much as I had anticipated, thanks to its huge emphasis on
language design rather than software design), believes that an important
part of language design is to allow the programmer to catch as many errors
as possible; thus, according to him, subclassing should be possible in a
manner which makes the subclasses able to accept *fewer* inputs than the
superclass.

For an example of this, imagine if The Programmer had defined 'Roads' to
handle WheeledVehicles.  He could then, using Eiffel, define 'Path' as a
subclass of Roads, and define Path as only handling Bicycles.  If you try
to put a Vehicle on a path, and the vehicle isn't a type of Bicycle,
you'll get an error.

This scheme, used by Eiffel, is called "covariance", because you're
allowed to change the types of arguments given to functions in subclasses.
In other words, a subclass can handle a subclass.  The two vary together.

In Sather, on the other hand, subclasses have to be able to handle MORE
input than their parents.  In other words, redefined methods in a subclass
are allowed to take a _superclass_ as an argument.  This is called
'contravariance', since _sub_classes can take _super_classes as arguments.

There's a third type of variance, by the way; the type used in C++ and
Java.  It's called 'novariance'.  In those languages, you can never
redefine the type taken by a subclass without using overloading (which is
an entirely different issue).

Now, why would you want to choose one of these over the other?  Covariance
has the advantage of allowing some interesting error-catching -- but the
problem is that it can't catch all of the errors at compile time.  In
other words, by using it you're running the risk of allowing your user to
trigger a type error.

>(The other "tower" language, Sather, is strictly contravariance-
>only. Its philosophy is that the type system should encompass all
>run-time possibilities. Thus, Sather would have us "chase" our
>parameter declarations of methods in derived classes up to the
>highest point where that method was defined. So, we would allow
>old file objects to seek() to a float, but we would insert a run
>time check to raise a type error if the argument was not an
>integer.)

No, that would be bad.  No run-time checks needed, nor modification of
existing code.  What we'd do there is define our new subclass of File with
an additional ftell() method which could return a float.  Thus, old
integer-file programs could still use our new class without possibility of
error; new programs would use ftell, and could pass floats to seek.

How would you handle this in Eiffel?  It turns out that it would be
impossible; floats are a subclass of integers, so we wouldn't be able to
define 'seek' to accept a float.  We'd have to create a new function,
fseek.  Old programs would runtime-error when calling tell, since we were
returning floats when they expected integers.

(Of course, it's also interesting to note that it's possible to build an
OO language which doesn't _need_ to worry about this; that's "multiple
dispatch", and it's another very interesting topic entirely.)

-- 
-William "Billy" Tanksley