Re: Polymorphism, genericity, etc.

[Michael Schuerig <michael%schuerig.de@post.strato.de>]

[Apparently Cygnus is blocking mail from acm.org...]


To clarify terminology a bit, let's have a look at

Luca Cardelli, Peter Wegner
On Understanding Types, Data Abstraction, and Polymorphism
Computing Surveys 17(4):471-522, Dec 1985

You can get it from <http://www.luca.demon.co.uk/Bibliography.html>.


They differentiate four kinds of polymorphism

                          parametric
                        /
               universal
             /          \
            /            inclusion
polymorphism
            \            overloading
             \         /
               ad-hoc
                       \
                         coercion


So, what's the difference? Some quotes from C&W (page numbers refer to
the online version):

"Universally polymorphic functions will normally work on an infinite
number of types (all the types having a given common structure), while
an ad-hoc polymorphic function will only work on a finite set of
different and potentially unrelated types." (p. 4)

"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 which need
not be disjoint, i.e. there may be inclusion of classes." (p. 5)

"Subtyping is an instance of *inclusing polymorphism*." (p. 7)

"In *overloading* the same variable name is used to denote different
functions, and the context is used to decide which function is denoted
by a particular instance of the name." (p. 5)

"Overloading is a purely syntactic way of using the same name for
different semantic objects; the compiler can resolve the ambiguity at
compile time, and then proceed as usual." (p. 5)

"A *coercion* is instead a semantic operation which is needed to
convert an argument to the type expected by a function, in a situation
which would otherwise result in a type error."


The "ad-hoc" variants appear to be irrelevant to the current
discussion. Universal polymorphism is of interest here. Here's my
attempt at applying the two kinds to mechanisms in available
programming languages:

PARAMETRIC POLYMORPHISM: generic classes in Eiffel, templates in C++,
function calls in Scheme and Haskell (I'm not sure about this case!).

INCLUSION POLYMORPHISM: explicit subtyping in Eiffel, C++, Java, etc.,
implicit subtyping in Smalltalk (also type conformance checking in C++
with gcc -fhandle-signatures), generic functions in CLOS and Dylan.


Michael