Re: OO polymorphism

From: Lauri Alanko <la@iki.fi>
> I was having a minor terminological squabble with someone, and since we
> reached no solution, I thought to ask the experts.
> Here's the issue. In the object-oriented culture, "polymorphism"
> typically means dynamic dispatching: methods in subclasses can operate
> differently from methods in superclasses. The question is: where does
> this sort of behavior fit in the Cardelli/Wegner taxonomy of different
> kinds of polymorphism [CW85]?

I must say that I also sometimes have trouble about how to
characterize OO polymorphism.
Note that Cardelli&Wegner are careful to state that their taxonomy
is about type systems, not language features. Yet it is strange to
find there parametric polymorphism, which usually is charaterized by
coherence of the implementation, rather than by the type system

For me there are two distinct axes:
* Universal (or F-style) polymorphism vs inclusion (subtyping)
  polymorphism. This is purely a type-level distinction.
  This is what Cardelli&Wegner talk about.
* Parametric (type-independent) polymorphism vs. ad hoc (overloaded)
  polymorphism. This is a semantic distinction, whether types play a
  role or not in the evaluation. There may be some forms of more
  controlled (less ad hoc) type dependency in between.

O.O. itself is probably on the inclusion side, but not necessarily on
the ad hoc side.

> My view is that this is a special, systematic form of ad
> hoc-polymorphism: an operation can have multiple differing
> implementations, one of which is chosen depending on the type of the
> function's argument. Although in OO languages this dispatching is
> dynamic and based on an object's runtime _class_, and a strict
> interpretation of "type" limits the concept of polymorphism to a purely
> static context, nevertheless in Benjamin Pierce's types book [Pie02, p.
> 340] the statically untyped multimethods of CLOS are counted as ad
> hoc-polymorphism. To my mind single-dispatch OO is essentially a limited
> version of the same.

You are talking about the second axis, making the extra assumption that
a class is similar to a type.
If classes are just data, then there is nothing non-parametric in
dispatching on them at run-time.
Objective Caml is an example of that: two otherwise unrelated classes
may produce objects of excactly the same type. The class information is
contained in the object closure.

On the other hand, many OO languages link classes and types, and give
run-time access to the type through introspection, which seems clearly
add hoc.

> My opponent contends that what is found in the methods of eg. C++ and
> Java is, in fact, inclusion polymorphism: an argument of a subtype can
> be used wherever an argument of a supertype can. Both the
> Cardelli/Wegner paper and Pierce's book seem to imply the same. However,
> in the original paper it is said of inclusion polymorphism [CW85, p.
> 478]:
> 	Similarly, operations are careful to interpret the
> 	representations uniformly so that they can work uniformly on
> 	elements of subtypes and supertypes.
> Dynamic dispatch doesn't seem to me to be "uniform" to me, although of
> course at the implementation level there usually is a "uniform"
> operation of looking up the implementation from a vtable and jumping to
> that. So I'd limit pure inclusion polymorphism to such things as union
> types, record types and non-virtual methods: the "same thing" is done to
> all arguments regardless of their exact type (or class).

This uniformity seems to me rather a problem of implementation: if you
want your colored point to be viewable as a normal point, they must
share part of their representation. And if an operation uses directly
the type of an object to access its representation, it might be unable
to work properly on one of its subtypes.
This can also be seen as adequation between the type system and the
language: if a language has both inclusion polymorphism, and allows
uncontrolled type dispatch, you may easily loose type safety (cast
failure). Java and C++ clearly fail here, but this doesn't mean that
they do not attempt to implement inclusion polymorphism.

Jacques Garrigue      Kyoto University     garrigue at kurims.kyoto-u.ac.jp
		<A HREF=http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/>JG</A>