From: chambers@klamath.cs.washington.edu (Craig Chambers)
Subject: Re: Polymorphism (was: Re: comparing object-oriented platforms)
Reply-To: chambers@cs.washington.edu
Organization: University of Washington
Date: Thu, 15 Oct 92 02:35:50 GMT

In article <1992Oct14.200408.17846@dec254.uucp>, hall@dec254.uucp (Phil Hall) writes:
|> [CARD85] says:
|>   "The semantics of generic procedures is macroexpansion driven by the type
|>    of the arguments.  Thus generic procedures can be considered
|>    abbreviations for sets of monomorphic procedures."
|> 
|> The way I understand [CARD85]'s parametric polymorphism is that 
|> the same *implementation* accepts a parameter of any type or some set
|> of types.  I've heard the "any type" version refered to as "pure" 
|> polymorphism.  This assessment would label "parameterized
|> types/generics/ML-style polymorphic functions" as overloading
|> rather the parametric polymorphism.

There's a difference between an interpretation in terms of the
semantics of the language construct (the quote above) and an
explanation in terms of a *possible* implementation.  Take polymorphic
functions as an example.  The semantics of a ML polymorphic function
could be described as instantiating a distinct non-polymorphic
function for each type of argument passed to the function.  That's
what the quote of Cardelli & Wegner refers to.  However, in real ML
implementations, the same compiled code is run independent of how the
function gets instantiated in the type system.  Since the body of the
function doesn't depend on the type of argument that's passed, this
implementation strategy works well.

For parameterized classes/types/modules, different implementation
strategies are sometimes used, with multiple implementations of the
module created for each different instantiation.  The semantics need
not be affected by these implementation decisions.

If a variable in a function (say, an argument) is parametrically
polymorphic, then the body of the function will work on all possible
arguments.  Conversely, the function can make no assumptions about the
properties or operations of the argument and can only assign it to
other variables of the same (polymorphic) type.

If a variable in a function (again, e.g. an argument) is inclusion
polymorphic (or whatever the adjective would be), then there is some
information known about the argument, i.e., that it's a subtype of
some known type.  This restricts the kinds of arguments that may be
used in the function but allows the function to do more interesting
things with the argument.  This works especially well when the
implementations of the operations that can be performed on the
variable differ depending on the instantiating type of the argument,
i.e., if dynamically-resolved overloaded functions/methods are
supported.

Cardelli and Wegner unify parametric and inclusion polymorphism in
their article, calling them both "quantification".  Parametric
polymorphism corresponds to universal quantification over the type of
the polymorphic variable, while inclusion polymorphism corresponds to
bounded quantification, where the bound is the type that the variable
must be a subtype of.  In this view, parametric polymorphism is a
special case of inclusion polymorphism, where the bound is the
universal type with no defined operations.

In real OO languages, type variables aren't normally as manipulable as
in the theoretical languages explored by Cardelli and many others,
hence these languages often support both inclusion polymorphism and
parametric polymorphism as separate language constructs.  If real
languages made type variables more first-class, and allowed more
constructs to be quantified over, then maybe parametric polymorphism
would be unnecessary.  SML's modules probably derive much of their
power by allowing this sort of wide-ranging quantification (although
they still don't support bounded quantification, only universal
quantification, I think).  I'm working on a type system for Cecil more
along the lines of extending inclusion polymorphism to incorporate
type variables.  It's not done yet, but I think it's promising.

-- Craig Chambers
Xref: sparky comp.object:3879 comp.lang.functional:1228