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.]
This document was translated by ms2html v1.8 on 01.06.95.