Xref: utzoo comp.object:3393 comp.lang.misc:7654 comp.lang.eiffel:1550
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!ub!oswego!oswego.oswego.edu!dl
From: dl@g.g.oswego.edu (Doug Lea)
Newsgroups: comp.object,comp.lang.misc,comp.lang.eiffel
Subject: Re: A Hard Problem for Static Type Systems
Message-ID: <DL.91Apr29083852@g.g.oswego.edu>
Date: 29 Apr 91 12:38:52 GMT
References: <1991Apr20.010347.28984@leland.Stanford.EDU> <554@eiffel.UUCP>
	<1991Apr26.203642.17387@leland.Stanford.EDU> <556@eiffel.UUCP>
Sender: news@oswego.oswego.edu (Network News)
Reply-To: dl@g.oswego.edu
Organization: SUNY Oswego
Lines: 111
In-Reply-To: bertrand@eiffel.UUCP's message of 28 Apr 91 22:50:03 GMT


[I attempted to post this 3 months ago in reply to a similar
posting about contravariance, etc., but apparently the posting
never made it out. Now seems as good a time as any to try again.]

Bertrand Meyer wrote:
> 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