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

[Eric Jacobs]

In article <m3k8ivfwcd.fsf_-_ at katrine.mcfhome>,
mcfarlan at neca.com (D. Michael McFarland) wrote:
> Twang! (Sound of an engineer being clothes-lined by a CS concept)
> 
> 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.
> 
> 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.

In Python currently, all type errors are run time errors. The goal
of a static type checking system to eliminate some amount of those
type errors, by attempting to identify at compile time code that
cannot possibly work correctly at run time. This is done by
annotating the source code with type definitions, and then running
some kind of deductive system to determine which types might end up
where.

The central idea is that if a programmer writes, say, x.read(10),
it doesn't make sense that x would refer to any object that doesn't
have a file-like interface. If it can be inferred that x might
contain something else, it should be a compile-time error, and
caught early. The approach taken by most type systems is to require
the programmer to decide, "hey, I have this variable x and I
believe it refers to a ??? kind of object."

Another important concept of type systems is the idea of
substitutivity, or subtyping. This applies easily to Python, where
there is the familiar type hierarchy. For example, a function that
expects a Sequence object as a parameter should accept all of
Sequence's subtypes, including Lists, Strings, and Tuples without
an error. This is because each subtype can do at least what the
abstract Sequence interface defines (and possibly more.) If it
did not, the possiblity of a run time error is reintroduced and
the type system has failed its original purpose. Therefore, in
order to be true to the idea of substitutivity, each type must be
able to do at least what all of its supertypes can do.

The issue of "covariance vs. contravariance" usually crops up
when an attempt is made to create subtypes (typically subclasses)
which in some way do not measure up to the full sum of the
parents' capabilities.

Contravariance refers to the idea that, from the programmer's
viewpoint of an abstract object, there are two _opposite_ subtyping
relationships that appear on the object at the same time. Here's
an example. Suppose that you have created a Python object that
represents some kind of supernatural file that can not only read
and write on integer offsets within the file, but any float offset
as well. So you may well do a seek(3.14159), and write there.
For the purposes of this example, I'm considering an integer as
a subtype of a float. This is, an integer can be used in a 
float variable without any loss of meaning.

That means that its tell() method would have to return a
float offset, rather than just an integer, because the file 
pointer can be any float now. So a user might say:

               fp = f.tell()
                <------

fp would have to be a float or a supertype thereof. (It could,
for example, be a complex number, because all real numbers
can be complex numbers with no imaginary component.) The
subtyping relationship is coming at you as the user. That is,
you must have a variable that's a supertype of the returned
value.

And it's seek() method would be able to now take a float as
an argument.

               f.seek(fp)
                ------->

seek() is the obvious logical counterpart of tell(), but
unfortunately the behavior is not symmetric with respect to the
type system. What type must the variable fp be now? fp must
be able to substitute into a float, which is the type of the
parameter that seek() is taking. That is, float must be a
subtype of it. fp could _not_ be a complex number, because
not all complex numbers are real. fp could be an integer,
though.

The actual parameters must be lower in the hierarchy than
the formal parameters, but the actual return value must be
higher than the formal return value.

That's the idea (and the paradox) of contravariance. Technically,
our new file object type cannot be either the subtype or the
supertype of the normal file object type. If it were a subtype,
a function that operates on all file-like objects might call
tell() and expect an integer. If it were a supertype, a function
might try a seek() with a float on a normal file object, which
wouldn't be supported.

The original poster mentioned Eiffel. Eiffel is a language that
takes the attitude that contravariance typing rules shouldn't
cause the object model to self-destruct. Instead, let the designer
create a hierarchy that makes sense for the particular application,
even if it means that strict typing cannot be established.

In Eiffel, we could put the new file object above the old one in
the hierarchy. This is known as "covariance", as the subtyping
relationship going down from the return value of tell() (from
float to integer) is the same as the relationship going down from
the parameter of seek() (also from float to integer).

In this case, the old file object does not meet its parents
capabilities, i.e., it is not able to seek() to a float. This
introduces the possibility of run-time type error. According to
covariance, it is a concession necessary to having a useful and
practical object model.

Eiffel also has the "polymorphic catcall" rule, which is designed
to reduce the possibility of run-time type errors. "CAT" stands for
"Changing Availablity or Type", or "Covariant Availability or Type".
That's too much to go into right now, but in a nutshell it means
that in order to use a method that has had its parameters' types
restricted (or the method removed) downstream in the hierarchy,
we cannot use a polymorphic variable; that is, we would have to use
a variable whose type is specifically known (not just "compatible
with x", because as we have seen, it may not be actually
compatible.) seek() would be a CAT method in the example.

(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.)

There are also issues with "reference types", meaning types that
can be assigned to. An example would be a list of integers. If you
have a function that says it can sum up a list of integers, you
could give it a list of whole numbers (>= 0) and it would still
work; a list of floats and it wouldn't. If on the other hand, you
have a function that fills a list with random integers, you could
give it a list of floats and it would be happy; a list of whole
numbers and it would bomb. A function that both reads and writes
from a list would bring back the contravariance paradox.

The problem is exactly the same as the one with the file example
above: just think of __getattr__ instead of tell and __setattr__
instead of seek.

Much of the above was inspired by the recent DCPIGgies meeting.
Many thanks to Jeremy and Scott and everyone else who made it
possible. It certainly has got me thinking about this and how
it all relates to Python. :)