Ad hoc polymorphism Christopher Strachey chose the term
ad hoc polymorphism to refer to polymorphic functions that can be applied to arguments of different types, but that behave differently depending on the type of the argument to which they are applied (also known as
function overloading or
operator overloading).
Parametric polymorphism Parametric polymorphism allows a function or a data type to be written generically, so that it can handle values
uniformly without depending on their type. Parametric polymorphism is a way to make a language more expressive while still maintaining full static
type safety. The concept of parametric polymorphism applies to both
data types and
functions. A function that can evaluate to or be applied to values of different types is known as a
polymorphic function. A data type that can appear to be of a generalized type (e.g., a
list with elements of arbitrary type) is designated
polymorphic data type like the generalized type from which such specializations are made. Parametric polymorphism is ubiquitous in functional programming, where it is often simply referred to as "polymorphism". The next example in
Haskell shows a parameterized list data type and two parametrically polymorphic functions on them: data List a = Nil | Cons a (List a) length :: List a -> Integer length Nil = 0 length (Cons x xs) = 1 + length xs map :: (a -> b) -> List a -> List b map f Nil = Nil map f (Cons x xs) = Cons (f x) (map f xs) Parametric polymorphism is also available in several object-oriented languages. For instance,
templates in
C++ and
D, or under the name
generics in
C#,
Delphi,
Java, and
Go: class List { class Node { T elem; Node next; } Node head; int length() { ... } } List map(Func f, List xs) { ... }
John C. Reynolds (and later
Jean-Yves Girard) formally developed this notion of polymorphism as an extension to lambda calculus (called the polymorphic lambda calculus or
System F). Any parametrically polymorphic function is necessarily restricted in what it can do, working on the shape of the data instead of its value, leading to the concept of
parametricity.
Subtyping Some languages employ the idea of
subtyping (also called
subtype polymorphism or
inclusion polymorphism) to restrict the range of types that can be used in a particular case of polymorphism. In these languages, subtyping allows a function to be written to take an object of a certain type
T, but also work correctly if passed an object that belongs to a type
S that is a subtype of
T (according to the
Liskov substitution principle). This type relation is sometimes written . Conversely,
T is said to be a
supertype of
S, written . Subtype polymorphism is usually resolved dynamically (see below). In the following Java example cats and dogs are made subtypes of pets. The procedure letsHear() accepts a pet, but will also work correctly if a subtype is passed to it: abstract class Pet { abstract String speak(); } class Cat extends Pet { String speak() { return "Meow!"; } } class Dog extends Pet { String speak() { return "Woof!"; } } static void letsHear(final Pet pet) { System.out.println(pet.speak()); } static void main(String[] args) { letsHear(new Cat()); letsHear(new Dog()); } In another example, if
Number,
Rational, and
Integer are types such that and (
Rational and
Integer as subtypes of a type
Number that is a supertype of them), a function written to take a
Number will work equally well when passed an
Integer or
Rational as when passed a
Number. The actual type of the object can be hidden from clients into a
black box, and accessed via object
identity. If the
Number type is
abstract, it may not be possible to access an object whose
most-derived type is
Number (see
abstract data type,
abstract class). This particular kind of type hierarchy is known, especially in the context of the
Scheme language, as a
numerical tower, and usually contains many more types.
Object-oriented programming languages offer subtype polymorphism using
subclassing (also known as
inheritance). In typical implementations, each class contains what is called a
virtual table (shortly called
vtable) – a table of functions that implement the polymorphic part of the class interface—and each object contains a pointer to the vtable of its class, which is then consulted whenever a polymorphic method is called. This mechanism is an example of: •
late binding, because virtual function calls are not bound until the time of invocation; •
single dispatch (i.e., single-argument polymorphism), because virtual function calls are bound simply by looking through the vtable provided by the first argument (the this object), so the runtime types of the other arguments are completely irrelevant. The same goes for most other popular object systems. Some, however, such as
Common Lisp Object System, provide
multiple dispatch, under which method calls are polymorphic in all arguments. The interaction between parametric polymorphism and subtyping leads to the concepts of
type variance and
bounded quantification.
Row polymorphism Row polymorphism is a similar, but distinct concept from subtyping. It deals with
structural types. It allows the usage of all values whose types have certain properties, without losing the remaining type information.
Polytypism A related concept is
polytypism (or
data type genericity). A polytypic function is more general than polymorphic, and in such a function, "though one can provide fixed ad hoc cases for specific data types, an ad hoc combinator is absent".
Rank polymorphism Rank polymorphism is one of the defining features of the
array programming languages, like
APL. The essence of the rank-polymorphic programming model is implicitly treating all operations as aggregate operations, usable on arrays with arbitrarily many dimensions, which is to say that rank polymorphism allows functions to be defined to operate on arrays of any shape and size. ==Implementation aspects==