Object-Orientation FAQ

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
  classes.

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

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
components."

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.]