From: Bob Hathaway <objsys@netcom.com>
Subject: Polymorphism in Object-Oriented Languages
Organization: Object Systems
Date: Sat, 12 Dec 1992 02:14:17 GMT

[This is a long general reply to some previous responses to which I have not
had the time to reply (my apologies).  It is a discussion of polymorphism
in object-oriented languages and also contains a refute on the closely
related and controversial downcasting at the very end.  Please forgive
me if these subjects have already been over-discussed in my absence (I've
been too busy to read news and can't even access my netcom account right
now:-).  Also this article is for the somewhat technically-oriented, but
such were the former participants.]

I've read Cardelli and Wegner's (henceforth referred to as Wegner's) paper
and several allusions to Strachey's original work; however, my local library
has lost a book by Strachey and can't seem to get its act together so I'm
temporarily giving up on finding his original work.  But Wegner's classic
paper (Computing Survey's 12/1985) covers a type system model for analyzing
and categorizing most existing object-oriented languages.

By Wegner's conveyance of Strachey's definitions, polymorphism is divided
into two major forms, parametric and ad-hoc.  "Parametric polymorphism
is obtained when a function works uniformly on a range of types; these
types normally exhibit some common structure.  Ad-hoc polymorphism is
obtained when a function works, or appears to work, on several different
types (which may not exhibit a common structure) and may behave in
unrelated ways for each type."

Smalltalk's brand of polymorphism was previously under discussion.  In
Smalltalk, parameters (and also polymorphic objects) are not type-checked
(from whence the term 'typeless' appeared), meaning *any* Smalltalk object
may be passed into one of Smalltalk's methods or assigned to any formal object
and the same method will work uniformly on any of these object's types.
Typically formal parameters will be super-classes and derived classes will
be expected to allow specialized behavior based on the actual object (the
common structure).  This seems to fit in perfectly with Strachey's original
definition of parametric polymorphism.

Now the term "Universal Polymorphism" comes into the picture.  Wegner's
article (as pointed out by Craig Chambers) discusses the "new" breakdown
as:
                               |-- parametric
               |-- Universal --|
               |               |-- inclusion
polymorphism --|
               |               |-- overloading
               |-- Ad-hoc -----|
                               |-- coercion

Wegner: "In parametric polymorphism, a polymorphic function has an implicit
or explicit type parameter which determines the type of the argument for
each application of that function.  In inclusion polymorphism an object
can be viewed as belonging to many different classes that need not be
disjoint, that is, there may be inclusion of classes.  These two views of
universal polymorphism are not unrelated, but are sufficiently distinct in
theory and in practice to deserve different names."

Closer inspection of the paper; however, reveals the above description to
be misleading; so misleading in fact, that I can formally discuss some of
the former participants confusion.  Since inclusion polymorphism is a
commonly used term, I feel its a good idea investigate the term in depth.
The above hierarchy is really broken into two halves, one side for typing
and another for representation (the previously called separation between
type and class which has been around for over 20 years as the canonical
understanding of type systems).  Here is Wegner's "real" categorization:

       Typing Side                          Abstract Types, Representation Side


                            BOUNDED QUANTIFIERS
                         /  flexible interfaces  \ 
                       /           BUE             \
                     /              |                \
                   /                |                  \
      BOUNDED UNIVERSAL         QUANTIFIERS             BOUNDED EXISTENTIAL
    universal polymorphism   /    modules    \       /    abstract subtypes
           BU             /         AE          \   /           BE
            |          /                          /\
            |       /                           /     \
        UNIVERSAL             FUNCTIONAL SUBTYPES         EXISTENTIAL 
  parametric polymorphism    inclusion polymorphism      abstract types
           A                       functions, B               E
           |                   /               \
           |                 /                  \
      SIMPLE UNIVERSAL     /                    SUBTYPES
      ML polymorphism    /                 multiple inheritance
        restricted A    /                          B
            |         /                            |
            |        /                             |
        HIGHER-ORDER                        SIMPLE SUBTYPES
        monomorphism                      single inheritance
         functions                          restricted B
                      \                 /
                        \             /
                          FIRST ORDER
                  records, variants, restricted functions
              Cartesian product, overloading, restricted functions

A: Universal Quantification
    - Logic's upside down A: for all.
    - Used for parameterized typing.
E: Existential Quantification
    - Logic's backward E: there exists one instance.
    - Used for Data Abstraction.
B: Bounded Quantification
    - Inclusion polymorphism (don't be missled by the diagram).
    - Used for type inheritance.

The type half uses inclusion polymorphism (the bounded cases) to avoid a
loss of dynamic type and the representation side uses inclusion polymorphism
for the same purpose and for sharing of behavioral and structural
representation.  With respect to return values (one real difference between
the bounded and unbounded case), I used to refer to the "parametric" case
as non-polymorphic and the bounded case as "polymorphic return values", so
I don't even like Wegner's "parametric" case at all (it loses the dynamic
type).  I believe consistency (or orthogonality) in the simplist case would
call for only the more powerful bounded case.

It can be confusing to work in languages with only one hierarchy used for
both typing and representation (Smalltalk has just one hierarchy, but at
least doesn't use it for typing).  Defining objects and operations is
usually the starting point for most methodologies and classes will be so
defined.  However, certain classes will play a dual role and also be used
for typing purposes, but they will now entail forcing the inclusion of a
representation for type-compatible actual objects as well!  [Hint: use
extensions with a separate type structure:-]

Bounded (inclusive) quantification is really just a constraint that is
added to the non-inclusive case (inclusion) and the parametric case can be
viewed as the inclusive hierarchical static case where the parametric type
bound is the top of the type lattice (reverse inclusion in the original
diagram).  This seems to show that the "new and improved" hierarchical view,
as shown in the first diagram, is really arbitrary, as is shown by the more
precise second diagram.  Implementation may differ to allow the greater
power required by the inclusive (bounded) typing case, but this is besides
the point.  [I'll also be investigating some of the more powerful type
systems and more powerful implementation techniques (typing isn't
everything), and can already see at least one dynamic case where the type
system model will be extended.]

Anyway, back to the original discussion.  As I said before, Smalltalk
has inclusion polymorphism on the existential (representation) side
but provides no type checking (the unbounded parametric case) on parameters
and formal (polymorphic) objects, meaning it does not provide inclusion
polymorphism on the typing side (although this can and usually should
occur for the common structure of the parametric case anyway).  This
(statically) "typeless" approach is most general and at least helps to
avoid type dependencies.  Wegner discussed inclusion polymorphism for
Smalltalk on the representation side but only in terms of his ambiguous
first hierarchy, potentially causing confusion by not explicitly referring
to his more detailed type system analysis model.  Abstract types in
Wegner's terminology refer to existentially quantified types which are
representation independent types (specifications or interfaces) for
representations (or conversely can be derived from representations).
These abstract types are distinct from the ((un)bounded (or universally
polymorphic)) parametric types.  Maybe someone can explain why the
parametric polymorphic definition was name-changed instead of leaving
the parametric case alone and subclassing it into the bounded and
unbounded cases, or even just deriving the bounded case as a
specialization of parametric polymorphism, thus avoiding any conflict
with Strachey's classical definitions.

For more definitions, Wegner calls a type specification and implementation
a package, and with its existentially quantified type (abstract type)
a module.  This corresponds to the formal type system definitions (as
in ML) and are quite distinct from the object-based uses of these terms. 

I therefore conclude that previously I was quite correct in my categorization
of polymorphism in several languages and any confusion was due to alternate
'views' of polymorphism or even Wegner's redefinition of the term parametric
polymorphism.

On another track, the issue of downcasting has arisen.  I've been awfully
busy with the C++ implementation of my designs and have had recent 
exposure to downcasting.  One, with advanced applications, always embed
a dynamic typing scheme (simple and elegant).  Two, if you want reliable
(meaning *guaranteed* integrity, as required by some system components)
implementation-independent interfaces, always use abstract types
(inheritance in systems without abstract types is often an easily breakable
mess).  Three, use virtual constructors when the parameters distinguishing
the polymorphic object to be constructed can also be polymorphic [by
virtual constructor, I mean a constructor with an inclusive polymorphic
return type].  These aren't all specific to downcasting (and rather have
more to do with polymorphism), but are used below to demonstrate the
necessity of downcasting.

Anyway, on with downcasting.  Without it, advanced code will not function
well.  The simple case of a virtual constructor can serve as an example.
Some previously constructed polymorphic objects can be passed in to the
constructor, which then determines which type of object to return
based on these actual objects dynamic types.  Therefore, the virtual
constructor must query the actual arguments dynamic type.  Now, if certain
information is required from the actual parameter objects to construct the
new to-be-returned object, downcasting is required.  The function therefore
returns different types of objects based on what is actually passed in.
These actual objects contain information (which may *not* be contained
in their siblings) and therefore downcasting must be used to access this
specific information.  This is just one of many clear-cut cases where
downcasting is required, but I use an analogous relationship to records
below to generalize (I also show downcasting is required for multi-methods).

Another way of looking at downcasting is thru inheritance's similarity with
variant records.  For example, I can have a Person record with two variant
parts, Man and Woman.  This corresponds to a Person base class and Man
and Woman derived classes.  The Man and Woman's class information is
disjoint.  Now imagine trying to write code which could not access the
variant parts; this is ridiculous.  A function taking a person record will
usually require access to variant information.  If I'm worried about
spreading type information around, I can simply put the equivalent of an
otherwise (or else) clause in a case statement (a typecase statement).
Accessing the variant parts is called downcasting.  The alternative is
to never access the variant parts (??) or to declare something in the
person record for every variant part (???) that could be used and default
if the specific variant is not present.  The special case of wanting all
variants to support some member in their own way corresponds to virtual
members, an interesting addition to variant records, but still doesn't
cover the simple original case of accessing the variants specific
information (i.e. it is an incomplete facility).

Multi-methods are another important general case requiring downcasting.
Since (unlike vanilla virtual functions) many overriding methods require
covariant bounded specialization on their argument types (a multi-method
(or multi-method-like specialization ability, for those sensitive few),
this kind of member selection performs implicit downcasting based on the
dynamic types of the actual arguments.  Therefore, to argue against
downcasting is to argue against multi-methods (or even other less
restrictive forms), a position so untenable the refutation is left as
obvious.

Its also noteworthy that C++'s virtual base classes will often be
"unvirtualized" because of the preclusion of downcasting because of concern
for the efficient implementation of multiple-inheritance, a restriction
which is uniformly enforced even in cases of single-inheritance!  This non-
orthogonal "feature" of C++'s virtual bases makes them non-upward
compatible with future downcasting requirements.  Are pointers to derived
subobjects for virtual (shared) bases really that undesirable?

Comments on C+W or on my comments are welcome.

bob
objsys@netcom.com

P.S.  I should have a FAQ out eventually (assuming no one else gets around
  to doing it (and my genuine apologies to those zealous individuals
  awaiting one)).  Its just a matter of time and it was a good idea to
  reread Cardelli and Wegner's article in depth first, anyway.  Anyone
  confused about types or even about object-oriented programming languages
  (as derived from imperative languages) should find it interesting reading,
  albeit a little formal.  It'll certainly be referenced in my FAQ.

P.P.S:  Maybe it should be a VAHOGPC human-computer interface?  
    - This should be my last entry on this one...

  "Its really surprising that Madonna is coming out with a book on sex in
  these days of the 90's; the decade of safe-sex.  But; of course, in the
  90's reading a book on sex *is* having safe sex."
    - Jay Lenno
Newsgroups: comp.object