[comp.object] Eiffel type system

dl@lynx.cat.syr.edu (Doug Lea) (02/16/91)

[Sorry if this is a repost.]

> The question represents an attempt on my part to understand
> how the contravariant rule (which may at first be theoretically
>  appealing because it makes type checking easier) can be made to
> work at all in practice. 

I don't think the solution is all that complicated or even controversial.

> Assume the following situation

[Example recast in a C++-ish form -- Sorry (especially since C++
doesn't have any any useful rules about contra- or co- variant
arguments), but I don't know Eiffel syntax well enough.  I also gave
`Register' a return value to make it easier to distinguish the cases.]

The contravariance-breaking declarations look like:

    class Driver { ... };
    class Professional_Driver : public Driver {...};

    class Vehicle
    {
       virtual int  Register(Driver& d) { return 0; }
    };
 
    class Truck : public Vehicle
    {
      virtual int Register(Professional_Driver& p) { return 1; }
    };

The first question to ask in finding a contravariance-conforming
strategy is what behavior you want in each of the following
situations, assuming Driver d, Professional_Driver p, Vehicle v, and
Truck t:

    [1] v.Register(d);
    [2] v.Register(p);
    [3] t.Register(d);
    [4] t.Register(p);

Most likely, you want cases [1], [2], and [3] to invoke
Vehicle::Register, and case [4] to invoke Truck::Register.

Since this dispatch pattern depends on the types of two kinds of
objects, the way to express it is through some form of multiple
dispatch. In a language directly supporting multiple dispatch (e.g.,
CLOS), it might be stated in this way:

    class Driver { ... };
    class Professional_Driver : public Driver {...};
 
    class Vehicle {...};
    class Truck : public Vehicle {...};

    int Register(Vehicle& v, Driver& d)            { return 0; }
    int Register(Truck& t, Professional_Driver& p) { return 1; }

This would be handled in the intended manner by CLOS-type resolution
and dispatch rules (which are implictly contravariance maintaining
when the functions are of this form.)

[Note: this is valid in C++ too, but overload resolution is only
done statically, so it doesn't always have the desired effect.]

But this resolution strategy can also be obtained with `manual' double
dispatch in other languages (including, finally, C++ and Eiffel), to
look something like

    class Driver
    {
      virtual int RegisterVehicle(Vehicle& v) { return 0; }
      virtual int RegisterTruck(Truck& t)     { return RegisterVehicle(t); }
    };

    class Professional_Driver : public Driver
    {
      virtual int RegisterTruck(Truck& t) { return 1; }
    };

    class Vehicle
    {
      virtual int Register(Driver& d) { return d.RegisterVehicle(*this); }
    };

    class Truck : public Vehicle
    {
      virtual int Register(Driver& d) { return d.RegisterTruck(*this); }
    };

which is legal, does what you want, and obeys contravariance. You
can always do this conversion mechanically (algorithmically).

A perfectly valid objection is that people don't want to have to do
conversion into double dispatch themselves, especially since the
definition of one special case involves 3 other classes besides the
one programmers have in mind.

I agree with this objection. Languages and their compilers should help
automate this. The CLOS generic function approach is one attractive
method to do this in C++-like and Eiffel-like langauges.



--
Doug Lea  dl@g.oswego.edu || dl@cat.syr.edu || (315)341-2688 || (315)443-1060
|| Computer Science Department, SUNY Oswego, Oswego, NY 13126 
|| Software Engineering Lab, NY CASE Center, Syracuse Univ., Syracuse NY 13244