Index Home About Blog
From: (Henry Spencer)
Newsgroups: comp.compilers
Subject: Re: Implementing OO
Date: 17 Apr 2006 23:46:16 -0400
Message-ID: <06-04-115@comp.compilers>
Keywords: OOP

Dmitry A. Kazakov <> wrote:
>>> - convariant vs. contravariant,
>> And i've never been sure of what those words means -- feel free to
>> enlighten me :)
>Whether the parameters of a subprogram are covariant (hence dispatching) or
>not. In C++ the first (hidden) parameter is covariant all others and the
>result are contravariant. It is a quite strange choice, because there is
>nothing special in the first parameter...

It's actually a very natural choice, provided you wish to dispatch on only
one parameter, for encapsulation or performance (and a big reason for C++'s
success is its performance).  That decision means that the dispatch-on
parameter *is* special, inherently different from all the other parameters.

To respond to Oliver's request for enlightenment...

+ Covariance means that parameters or results of a method redefined in a
child type can be more specific than their counterparts in the parent's
method (i.e., their types can be children of the types named by the
parent's method).

+ Contravariance means that if they are different, they have to be *less*

Why might you want covariance?  Well, if the parent's method for, say,
addition takes two parameters of the parent type and yields the parent
type, it would seem natural that the child's method would take two
parameters of the child type and yield the child type:  if the parent type
is P and the child type is C, the parent's method has the signature
ADD(P,P):P and the child's has ADD(C,C):C.

Why might you want contravariance?  Consider when a method Y can safely be
substituted for a method X:  when Y's preconditions are the same or weaker
(so that any call which satisfies X's preconditions will also satisfy Y's)
and Y's postconditions are the same or stronger (so that the results from
Y will always satisfy X's postconditions).  If you think of parameter type
compatibility as being part of the preconditions -- declaring parameter P
to be of type T implicitly adds a precondition "P is of type T" -- then a
weaker form of such a precondition must require a *less* specific type.

You can't safely substitute ADD(C,C):C for ADD(P,P):P, because ADD(C,C):C
has more-specific preconditions, not less-specific ones:  what happens if
it's called with parameters of the parent type?  ADD(P,P):C would be okay:
covariance of *results* is safe, because it strengthens *postconditions*.
But combining covariance of parameters with type safety is really tricky
unless you dispatch on all parameters (so each method sees only the
combination of parameter types it's prepared for), which unfortunately
tends to be slow and incurs other hassles.

>A subroutine can be a method (subject of inheritance) or not. Depending on
>that it will be either overloadable or overridable. It can't be both
>(better not.)

Actually, one solution to the co/contravariance problem relies on being
able to do both:  <>.  The key
observation is that covariance is to contravariance as overloading is
to overriding.  Overriding must be contravariant for type safety, but
overloading lets you provide type-safe covariance.

>...There is no
>way to make all objects polymorphic, because that would exclude small
>objects like bits, pointers and the values of type tags itself.

This can be treated as an optimization problem rather than a matter of
language definition.  Small objects can be used by the implementation when
the value in question is known at compile time not to be polymorphic.
This does put more of a burden on the compiler, making this particular
"optimization" crucial to usability; that tempts people to make the
distinction in the language itself, to make it easier for the compiler
(and to force compiler implementers to do it).

>> Runtime type creation?  Possible but not *required* for OO, in fact
>> I'm not sure how any non-vm/interpreted language could generate new
>> types at runtime, as it requires codegen...

Note that dynamic loading of separately-compiled code has much the same
effect:  you may know the interface of the type, but you inherently don't
know anything else about it until it gets loaded at runtime.  Loading one
is pretty much akin to creating a new type at runtime.
-- is temporarily off the air;               |   Henry Spencer
mail to henry at instead.               |

Index Home About Blog