From: Bob Hathaway <objsys@netcom.com>
Subject: Re: comparing object-oriented platforms
Organization: Object Systems
Date: Mon, 12 Oct 1992 00:35:03 GMT

In article <MDAY.92Oct11123541@jukebox.lcs.mit.edu> mday@jukebox.lcs.mit.edu (Mark Day) writes:
   objsys@netcom.com (Bob Hathaway) writes:

   >> chambers@cs.washington.edu writes:
   >>Ad hoc ("OO-style") polymorphism is not more restrictive than
   >>parametric ("Milner-style") polymorphism; the two are incomparable in
   >>expressive power.  Certainly things like arrays of mixed integers,
   >>rationals, and floats cannot be statically-typed in ML.  

   This is jibberish.  Ad hoc polymorphism is overloading, OO typically
   provides the parameteric form based on inclusion polymorphism.  And
   since ML is statically typed, it is weaker than OO polymorphism; what
   are you thinking???

>Would it be too much to ask that you understand what someone is saying
>before you start shrieking at him?  Otherwise you do tend to look like
>rather a twit, even though yours is a common and reasonable
>misunderstanding.

In the first place, you took out half of what I was responding to!!!
Dirty pool, Day, where's Breuel's response???.  My reply referred to
both referenced participants (perhaps you misunderstood this).  Here is
the missing reply in context:

In article <1992Oct6.190729.24367@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>In article <1992Oct6.003602.21078@beaver.cs.washington.edu> chambers@cs.washington.edu writes:
>>In article <TMB.92Oct4182305@arolla.idiap.ch>, tmb@arolla.idiap.ch (Thomas M. Breuel) writes:
>>|> OO-style polymorphism is more restrictive than Milner-style
>>|> polymorphism, and also too restrictive for my tastes in the presence
>>|> of a static type checker.
>>
>>Ad hoc ("OO-style") polymorphism is not more restrictive than
>>parametric ("Milner-style") polymorphism; the two are incomparable in
>>expressive power.  Certainly things like arrays of mixed integers,
>>rationals, and floats cannot be statically-typed in ML.  

This is jibberish.  Ad hoc polymorphism is overloading, OO typically provides
the parameteric form based on inclusion polymorphism.  And since ML is
statically typed, it is weaker than OO polymorphism; what are you thinking???

...

And I'd be careful about the use of the term twit here, Day, my above comments
are correct and theirs are not and you have made several mistakes yourself,
so please be careful not to look like a twit yourself:-)  Notice the above
claim that OO uses ad hoc polymorphism.  This is wrong by Strackey's
definition, PERIOD.  If you divide the polymorphism world into two parts,
ad hoc and parametric, OO inclusion polymorphism *is* a subset of parametric
polymorphism.  In Smalltalk this is obvious and it continues from there.

And because OO often includes general dynamic dispatch and this is *not*
provided with static systems, there *is* a clear-cut case where the typical
OO form of typing is more powerful than the statically typed kind (ML)
and as I clearly pointed out, the above claim that I was responding to
was backwards!  [quote: "OO-style polymorphism is more restrictive than
Milner-style polymorphism"; wrongo, pal]  This *is* jibberish if ML can't
handle dynamic typing because then ML can't handle the most trivial
applications that OO can.  And if he's referring to some specific case,
I sure didn't see it mentioned.  And it doesn't count if I can somehow
convolute the language into providing some facility.  Discussions of power
should concentrate on provided language facilities since just because I
could provide anything found in ML and OO in assembly language doesn't
mean assembly language is more powerful.

>Craig Chambers is correct when he says that the two approaches are
>incomparable in expressive power.  Start with the universe of all
>specifiable data structures.  Consider A, the proper subset of that
>universe that can be correctly typed in a system with parametric
>polymorphism.  Now consider B, the proper subset of that universe that
>can be expressed in terms of subtypes and dynamic dispatching.  A is
>not a subset of B, nor vice-versa.

No, B is a subset of A since it *can be* a more constrained case (but
isn't with pure polymorphic objects as can be found in classical OO).  On
your non-subtyping case - if you'd been following the discussion between
Max Skaller and me however, you'd notice that we had touched on something
similar, that of enforcing a strict base interface.  This can be provided
with a single keyword in a parameter declaration (or even something for
assignment) and so can strict name equivalence (what you're claiming is
impossible).  Since I've now done the impossible, I guess I'll just have to
get out the old shirt with a big S on it again...

For an example, Ada has *both* name (derived types) and inclusion (subtypes)
equivalence available, proving they are not mutually exclusive (besides the
fact that it is obvious).

>Here's an example of something that's in A but not in B: If you want
>to say that a list is of homogeneous type, with all elements of type T
>and none of a subtype of T, you can do that in a system with
>parametric polymorphism.  There is no way to express that constraint
>in a system with only subtyping; the best you can do is to write a
             ^^^^^^^^^^^^^^^^^^^
>comment to that effect and dynamically check whenever you're about to
>add something to the list.

You're giving definitional constaints and then complaining about them.
I don't have to have these constraints and neither does OO as I pointed
out above.  Remember, OO is often defined as simply revolving around
objects; this inheritance stuff is almost peripheral.  And this checking
can be done statically with type variables, if desired.

>This "subtyping-always-allowed" quality is usually considered as an
>advantage of OO systems, but there can be times when it's a problem;
>and as a pure theoretical issue, it demonstrates that "OO
>polymorphism" does not subsume parametric polymorphism.

I said inclusion polymorphism is a subset of parametric polymorphism;
I didn't say it subsumes it.  And can you give a real example?  I don't
care about theoretical cases that are completely useless (or even worse,
are always undesirable) since I am a practitioner.  Max gave a good example
for strict base class interfaces; I'm awaiting yours...

>It's too bad, really, because the intersection between A and B is
>quite large.  

Can you give any other cases besides the one pure theoretical case in which
it has not been shown is even (or ever) desirable?  [and which has already
been shown can be trivially added to "OO"]?

>	       It would be nice if you could use only one mechanism and
>have all the expressive power of both, but you can't.

What?  A simple keyword can do the trick; I don't see your point.  I'm
glad you brought up the non-subtyping case although it's now up to you to
show it has any value.  Your above point looks like saying generics must be
pasted onto inheritance.  The two are separate facilities performing
separate functions: generics parameterizes types (or whatever) and
inheritance provides for differential programming and subtyping.  Do you
see the clear separation in function between the two?

bob
objsys@netcom.com
Newsgroups: comp.object