Kai Quale posed a question on comp.lang.sather regarding Bertrand Meyer's SKIER example and his paper about polymorphic catcalls. As it turns out, most of what Meyer says is not relevant to Sather due to Sather's separation of subtyping and code inheritance. There were several good responses, amid a very enlightened contravariance debate. Mark Wilkinson (mhw@minster.york.ac.uk) posted an excellent response, and Kevin Lewis (of the sather emacs mode fame) posted a 1.1 solution. Feldman extended the original problem to prohibit same-sex dating. This is interesting since techniques that rely on special treatment of arguments of type ``SAME'' no longer work.
The question and these above mentioned responses are (partially) replicated below.
As an aside, this skier example was a pleasant diversion from the ``standard'' contravariance example, which centers around the fact that cows can't eat any non-vegetarian food, since they are herbivores. Claudio Fleiner pointed out that cows do, in fact, eat meat and sometimes go mad doing so.
> There is only one feature of Sather that stands out like a sore > thumb to me - the choice of contravariant routine parameters. I have > read it is necessary for type-safety, but it seems to be like saying > "since we can't build a perfect security rail we'll just force > people to drive at walking speed." Bertrand Meyer has an article on > the ObjectCurrents home page (http://www.sigs.com/objectcurrents/) > about the merits of Covariance, which Eiffel uses: > > class SKIER feature > roommate:SKIER; > share (other: like roommate) is -- Anchored declaration > require > other /= Void -- Precondition > do > roommate := other -- Choose other as roommate > end > ... > end > > class GIRL inherit > SKIER > redefine roommate end > feature > roommate:GIRL; > ... > end > > class BOY inherit > SKIER > redefine roommate end > feature > roommate:BOY; > ... > end
The thing you should really think about here is what is the keyword `inherit' being used for. Is it a declaration that GIRL and BOY are substitutable for SKIER, or is it a declaration that they want to reuse code defined by SKIER, or both?
In Eiffel, C++, Smalltalk and all the other languages which have this kind of inheritance system, `inheritance' can mean all of these things at the same time and it's up to the programmer to make sure mistakes aren't made. The intention in the example above seems to be that code is shared and there's some idea of substitution, but doing both things with one construct (inheritance) confuses matters.
The fact of the matter is that GIRL and BOY are not really substitutable for each other or for SKIER. That's why this code goes wrong
> skier:SKIER; GIRL:girl; boy:BOY; > ... > skier := boy; > skier.share(girl); -- which parents would find hard to swallow.
The problem is that we've said that BOY is substitutable for SKIER (that's what inherit means), SKIERs can share rooms with SKIERs, and that BOYs can only share rooms with BOYs. These three claims are in conflict with each other and we need some way to resolve to conflict.
In the book "Eiffel: The Language," Meyer defines the system validity check to ensure that method calls should be valid once it knows the whole inheritance graph. This would be Ok, but the check is conservative (ie. it can reject programs which are actually safe) and has not yet been implemented (Meyer says as much in the Object Currents article you cite). It's this system validity check which should catch the problem above at compile time. The `catcall' rule which he defines in the same article appears to be a more conservative check which can be applied without knowledge of the rest of the system.
If these compile time checks aren't done an Eiffel compiler could generate an implicit run-time type check on the parameter of BOY.share to make sure it's another BOY. In other words, the restricted argument type declared in BOY.share can be converted into a less restricted argument type and a run-time type check. If you make a mistake you get a run-time error. This is exactly what Sather does, but it requires you to do it explicitly using the typecase construct.
The final possibility is to find an algorithm to infer the concrete types of objects from the program text. I've got a thesis sitting in front of me which describes something like this: Concrete Type Inference: Delivering Object-Oriented Applications by Ole Agesen, available from http://self.smli.com/ agesen/papers/phd-thesis.html
So the long and the short of it is that Sather allows you a bit more flexibility if you need it (see below for an example) but won't check for covariant redefinition automatically (you need to do the check yourself). In addition, Sather's check must be done at run-time whilst Eiffel can perform some checking at compile time.
But wait, there's more! As you mentioned earlier in your article, Sather separates out orthogonal concepts and inheritance is no exception. It is replaced by subtyping and code inclusion as two distinct language features which can be combined to get the effect you want. The bonus is that because the language is richer you can explain exactly what you want in more precise terms. Rather than overloading the class construct by making it represent type (ie. the interface of an object) and implementation we can separate those things out.
So, lets look at Meyer's example and break out the two different meanings of inheritance. We want objects to represent GIRLs and BOYs and there's likely to be some skiing behaviour (both interface and implementation) shared between them. There's also this idea of GIRLs and BOYs sharing rooms with a constraint that only GIRLs can share with GIRLs and BOYs can share with BOYs. The implementation of this room sharing is similar, but we can't say that it's interface is the same because of the constraint. Here's some code:
type $SKIER is
ski;
chairlift;
apres_ski;
end;
type $ROOMMATE{T} is
roommate: T;
share(r: T);
end;
class SKIER < $SKIER is
ski is #OUT+"ski\n"; end;
chairlift is #OUT+"lift\n"; end;
apres_ski is #OUT+"party!\n"; end;
end;
class ROOMMATE < $ROOMMATE{SAME} is
readonly attr roommate: SAME;
share(r: SAME) is roommate := r; end;
end;
class GIRL < $SKIER, $ROOMMATE{SAME} is
include SKIER;
include ROOMMATE;
create: SAME is return new; end;
end;
class BOY < $SKIER, $ROOMMATE{SAME} is
include SKIER;
include ROOMMATE;
create: SAME is return new; end;
end;
class MAIN is
main is
skier: $SKIER;
girl: GIRL := #GIRL;
boy: BOY := #BOY;
skier := boy;
skier.share(girl);
end;
end;
The compiler can check this statically, and as you might expect it'll tell
you the code won't work:
; cs -verbose skier.sa Parsing non-library files... (0 seconds) Finding types and parsing library... (2 seconds) Type graph, conformance, main, init... (1 seconds) Type check, generate, inline, optimize, and make C... skier.sa:47:27: No match for the call $SKIER::share(GIRL). (0 seconds)
We've pulled the roommate interface out into a separate parameterised type, and suddenly all the covariance has disappeared. Have we lost anything in doing this? Other than the possibility of making mistakes and getting type errors at run-time by putting BOYs and GIRLs in the same room, I don't think so. That's because the whole idea of putting the roommate/share interface into SKIER was probably a mistake in the first place.
So, given that covariance can either be replaced with an explicit type check or a more accurate description of the types involved, is contravariance any good either? Well firstly, contravariance is the right way of subtyping functions in an object-oriented type system from a type theory point of view. Given that Sather separates types from classes it's easy enough to follow through and make the type system contravariant.
Here, though is an example of how contravariance appears in the real problem of event handling in a user interface. The Sather interface to the X window system defines a set of event classes which subtype from the type $X_EVENT:
type $X_EVENT is
Type: INT;
Type(t: INT);
serial: INT;
etc.
end;
class X_EXPOSE_EVENT < $X_EVENT is
r: X_RECTANGLE is ... end;
end;
class X_BUTTON_PRESS_EVENT is
p: X_POINT is ... end;
button: INT is .. end;
end;
I want to declare handlers for events, so I do it like this:
type $E_ANY_HANDLER is end;
type $E_HANDLE{T} < $E_ANY_HANDLER is
handle(event: T);
end;
type $E_HANDLE_ANY < $E_HANDLE{X_KEY_PRESS_EVENT},
$E_HANDLE{X_KEY_RELEASE_EVENT},
$E_HANDLE{X_BUTTON_PRESS_EVENT},
$E_HANDLE{X_BUTTON_RELEASE_EVENT},
$E_HANDLE{X_ENTER_WINDOW_EVENT},
is
handle(event: $X_EVENT);
end;
Which states that event handlers which can handle any type of event are
subtypes of all the specific handlers. I can then declare specific event
handlers:
class EXPOSE_HANDLER < $E_HANDLE{X_EXPOSE_EVENT} is
handle(e: X_EXPOSE_EVENT) is
-- handle redraw event
end;
end;
and more general ones:
class EVENT_MONITOR < $E_HANDLE_ANY is
handle(e: $X_EVENT) is
#OUT+"event type "+e.Type.str+"\n";
end;
end;
and use them with complete safety:
class EVENT_QUEUE{T < $E_ANY_HANDLER} is
register(e: T) is ... end;
end;
expose_queue: EVENT_QUEUE{X_EXPOSE_EVENT};
button_queue: EVENT_QUEUE{X_BUTTON_PRESS_EVENT};
expose_queue.register(#EXPOSE_HANDLER);
expose_queue.register(#EVENT_MONITOR);
button_queue.register(#EVENT_MONITOR);
button_queue.register(#EXPOSE_MONITOR); -- type error!
Notice how contravariance leads the event handler hierarchy to be inverted with respect to the event hierarchy.
> Meyer proceeds to define a function "fitted" on GENERAL (the most general > type in Eiffel) that tests if an object is of exactly the same type as the > current object. This solves the room-sharing problem, but smacks of the > reviled isKindOf in Smalltalk - a feature that shouldn't be necessary, the > use of which suggests bad design.
I don't see this as being a problem as long as the context is right. You can distinguish between objects using either type or state; design is the art of choosing how much type information to use. In the example above you could just forget about GIRL and BOY classes and have a SKIER class with a Boolean attribute to indicate whether a skier is male or female. Whether this is the right thing to do depends on how well your application can be made to fit the type system of the language you're using. By using types you can get the compiler to enforce type constraints at compile time instead of checking them yourself at run time. You can also use the type enquiry constructs in the language to get at the actual type when you need it.
In the event handling example above, attaching types to event and handlers allows type checking of event handling (something which is difficult to do in general in other languages).
> If I understand contravariance correctly, Sather forces you to declare the > argument of GIRL.share as a supertype of SKIER, i.e. routine arguments in > descendants must be supertypes of arguments of the corresponding routine > in parents. Which leads to an even worse problem - girl could share room > with any kind of PERSON, or even any kind of OBJECT. Have I missed > something here ?
No you haven't missed anything, other than the argument doesn't _have_ to be a supertype - it can remain the same type instead. That's the way it has to work for guaranteed substitutability in the absence of more specific type information at routine-call time.
> And how about the implicit assignment routines in Sather ? If CLASS has > attrib:SAME, the implicit assignment routine in DESCENDANT can't have an > argument of DESCENDANT type. How is this solved ?
By working out what really is shared behaviour and what is just code reuse. The interface to attrib's reader and writer routines would be moved into a type which CLASS and DESCENDANT should be a subtype of (note that the subtype relation doesn't apply between classes, only between classes and types and between pairs of types). Restricting the argument type of attrib's writer routine in either CLASS or DESCENDANT with respect to that declared in the type breaks substitutablility and should probably be rethought; usually you'll find that it shouldn't really be in the interface the type declares at all.
Kevin Lewis posted a solution, which I've modified trivially to conform to 1.1 syntax.
--- ski.sa ---
-- Attempted implementation of the Skier example presented by Bertrand
-- Meyer on the ISE home page,
-- <http://www.eiffel.com/doc/manuals/technology/typing/paper/index.html>
type $SKIER < $IS_EQ{$SKIER}, $STR
-- Some class of skiers.
is
name:STR;
has_roommate:BOOL;
is_eq(other:$SKIER):BOOL;
is_neq(other:$SKIER):BOOL;
str:$STR;
end;
partial class SKIER < $SKIER
-- `SKIER' mixin class for subs of `$SKIER'.
is
attr roommate:SAME; -- This skier's roommate (has the same type).
attr name:STR; -- This skier's name.
stub create(name:STR):SAME;
share(other:SAME)
pre
~void(other)
-- Choose `other' as roommate.
is
roommate:=other;
other.roommate:=self;
#OUT + name + " with " + other.name + '\n';
end;
has_roommate:BOOL is
return ~void(roommate);
end;
is_eq(other:$SKIER):BOOL is
return name = other.name;
end;
is_neq(other:$SKIER):BOOL is
return name /= other.name;
end;
str:$STR is
return name;
end;
end;
class BOY_SKIER < $SKIER is
include SKIER;
create(name:STR):SAME is
res:SAME:=new;
res.name:=name;
return res;
end;
end;
class GIRL_SKIER < $SKIER is
include SKIER;
create(name:STR):SAME is
res:SAME:=new;
res.name:=name;
return res;
end;
end;
class SKI is
choose_roommates(skiers:FLIST{$SKIER}) is
loop
s1:$SKIER := skiers.elt!;
loop
s2:$SKIER := skiers.elt!;
if s1 /= s2 and ~s1.has_roommate and ~s2.has_roommate then
if s1 /= s2 and ~s1.has_roommate and ~s2.has_roommate then
typecase s2
when BOY_SKIER then
typecase s1 when BOY_SKIER then s1.share(s2); else end;
when GIRL_SKIER then
typecase s1 when GIRL_SKIER then s1.share(s2); else end;
else
-- Don't share.
end;
end; -- if
end; -- loop, s2
end; -- loop, s1
end; -- choose_roommates
main:INT is
-- Some boy and girl skiers.
boy_names:ARRAY{STR} := |"Alan", "Bobby", "Carl"|;
girl_names:ARRAY{STR} := |"Alice", "Betty", "Cathy"|;
skiers:FLIST{$SKIER} := #FLIST{$SKIER}; -- List of all the skiers.
loop skiers := skiers.push(#BOY_SKIER(boy_names.elt!)); end;
loop skiers := skiers.push(#GIRL_SKIER(girl_names.elt!)); end;
choose_roommates(skiers);
return 0;
end;
end;
Surely parents who want single-sex rooming will also want their children to date people of the opposite sex. Most of the proposed solutions (incuding Meyer's) don't extend at all well to this closely related problem. One that does was submitted by Mark Wilkinson and is now part of Ben Gomes' eclectic tutorial. It was almost trivial to extend this to include the dating constraint . The code is minimal, it is easy to combine this with the $ROOMMATE solution. The compiler will catch any the appropriate errors and one can also use typecase to do dynamically correct roommate and date assignment. In fact, the solution is deceptively clean; we can not solve all specialization tasks this well.
--date2.sa April 1996 example on skier example, after Mark Wilkinson
type $SKIER is
ski;
chairlift;
apres_ski;
end;
type $DATE{T} is -- parallel to mhw's $ROOMMATE
date: T;
pickup(r: T);
end;
type $GIRL < $SKIER, $DATE{BOY} is -- for David Shang, boys date any $GIRL
name:STR
end;
class SKIER < $SKIER is
ski is #OUT+"ski\n"; end;
chairlift is #OUT+"lift\n"; end;
apres_ski is #OUT+"party!\n"; end;
end;
class DATE{T} < $DATE{T} is
readonly attr date: T;
pickup(r: T) is date := r; end;
end;
class GIRL < $GIRL is -- could add ranked girl, etc.
attr name:STR;
include SKIER;
include DATE{BOY};
create: SAME is t::=new; t.name:="Mary"; return t end;
end;
class BOY < $SKIER, $DATE{$GIRL} is
include SKIER;
include DATE{$GIRL};
create: SAME is return new; end;
end;
class MAIN is
main is
skier: $SKIER;
girl: GIRL := #GIRL;
boy: BOY := #BOY;
skier := boy;
boy.pickup(girl); -- see below for boy.pickup(boy)
#OUT + boy.date.name + '\n';
end;
end;
Interestingly, the current ICSI compiler responds as follows when given the program with the substitution boy.pickup(boy):
date2.sa:51:26: No match for the call BOY::pickup(BOY)
Suggest:BOY::pickup($GIRL)