previous page: 2.1) What Is Polymorphism? (Typing - Object-Oriented Technology)
page up: Object-Oriented Technology FAQ
next page: 2.1) What Is Polymorphism? Other Definitions

2.1) What Is Polymorphism? Cardelli and Wegner's Definition [Cardelli 85]:


This article is from the Object-Oriented Technology FAQ, by Bob Hathaway rjh@geodesic.com with numerous contributions by others.

2.1) What Is Polymorphism? Cardelli and Wegner's Definition [Cardelli 85]:

C+W refine Strachey's definition by adding "inclusion polymorphism" to model
subtypes and subclasses (inheritance). Strachey's parametric polymorphism is
divided into parametric and inclusion polymorphism, which are closely related,
but separated to draw a clear distinction between the two forms, which are then
joined as specializations of the new "Universal" polymorphism.

                                 |-- parametric
                 |-- universal --|
                 |               |-- inclusion
  polymorphism --|
                 |               |-- overloading
                 |-- ad hoc    --|
                                 |-- coercion

Polymorphic Languages: some values and variables may have more than one type.

Polymorphic Functions: functions whose operands (actual parameters) can
have more than one type. [...] If we consider a generic function to be
a value, it has many functional types and is therefore polymorphic.

Polymorphic Types: types whose operations are applicable to operands of more
than one type.

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.

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

The two forms of "Universal Polymorphism", parametric and inclusion are closely
related, but are distinct enough in implementation to justify separate

Parametric polymorphism is referred to as generics. Generics can be syntactic,
where each instantiation creates a specialized version of the code allowing
fast running execution, but in a "true polymorphic system", only a single
implementation is used.

On inheritance is subtype polymorphism:
"Subtyping on record types corresponds to the concept of inheritance
(subclass) in languages, especially if records are allowed to have functional

Author's Notes:
Implicit parametric polymorphism can be implemented with type inferencing
schemes [Aho 85]. ML is prototypical in providing this facility.

Inclusion polymorphism is common and is found in languages such as Simula,
Ada95, C++, CLOS, Eiffel and etc. (subclass polymorphism). Smalltalk also
uses inclusion polymorphism; its used in declaring classes, and subclass
polymorphism is used in practice but not enforced. For inheritance, inclusion
polymorphism specifies an instance of a subclass can appear wherever an
instance of a superclass is required. For subtyping (subtype polymorphism),
the same applies because all operations required by the supertype are present
in the subtype (subtype is subset of supertype). Cardelli and Wegner view
classes as sets of objects (resulting in subtype objects are a subset of
supertype objects, or an extensional view), as contrasted with a feature based
(intensional) approach (where subtypes are supersets of (contain) supertypes).
MI provides an interesting example here, as it is set intersection with an
extensional view and set union with an intensional view. Details are left as
an exercise for the reader.

Ada generics and C++ templates provide explicit syntactic generics. While
Ada may infer some actual generic parameters (operations) and C++ doesn't
require explicit instantiation of its template functions, formal generic
parameters must still be declared and many bodies are generated.

Inclusion polymorphism can refer to subtyping, or having at least as much or
more than required. Since derived classes can inherit structure and behavior
from base classes, such inheritance is an example of inclusion polymorphism
with respect to representation (subclassing). An example of inclusion
polymorphism with respect to assignment (and initialization, or replacement if
viewed in an almost symbolic way) occurs when object types may be specified and
assignment is based on actual object membership in that type (often of the CLOS
is-a-member-of form in OO). Emerald provides another example of an object-
oriented language using inclusion polymorphism with respect to replacement;
however, inclusion is with respect to subtyping only with abstract types
("bounded quantification" by C+W. C+W's parameters are subtype polymorphic
but lose the inherent type). Any object possessing all required operations is
acceptable and no inheritance relation is required (subtype polymorphism).
They refer to this as "best-fitting" types [Black 86]. The original Trellis/
Owl also had such a facility but with two separate inheritance hierarchies,
although it was abandoned in favor of a single class-based approach for
simplicity. See also section 2.7.

[As inclusion polymorphism covers both subtype and subclass polymorphism,
perhaps IP could be further divided in C+W's above classification.]


Continue to:

previous page: 2.1) What Is Polymorphism? (Typing - Object-Oriented Technology)
page up: Object-Oriented Technology FAQ
next page: 2.1) What Is Polymorphism? Other Definitions