Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
s to be handled using a uniform interface. 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.
There are several fundamentally different kinds of polymorphism, two of which were originally informally described by Christopher Strachey
Christopher Strachey
Christopher Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design...
in 1967. If the function denotes different and potentially heterogeneous implementations depending on a limited range of individually specified types and combination, it is called ad-hoc polymorphism
Ad-hoc polymorphism
In programming languages, ad-hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument to...
. Ad-hoc polymorphism is supported in many languages using function and method overloading
Method overloading
Function overloading or method overloading is a feature found in various programming languages such as Ada, C#, VB.NET, C++, D and Java that allows the creation of several methods with the same name which differ from each other in terms of the type of the input and the type of the output of the...
.
If all code is written without mention of any specific type and thus can be used transparently with any number of new types, it is called parametric polymorphism
Parametric polymorphism
In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without...
John C. Reynolds is an American computer scientist.John Reynolds studied at Purdue University and then earned a PhD in theoretical physics from Harvard University in 1961. He was Professor of Information science at Syracuse University from 1970 to 1986. Since then he has been Professor of Computer...
Jean-Yves Girard is a French logician working in proof theory. His contributions include a proof of strong normalization in a system of second-order logic called system F; the invention of linear logic; the geometry of interaction; and ludics...
) formally developed this notion of polymorphism as an extension to lambda calculus (called the polymorphic lambda calculus, or System F
System F
System F, also known as the polymorphic lambda calculus or the second-order lambda calculus, is a typed lambda calculus that differs from the simply typed lambda calculus by the introduction of a mechanism of universal quantification over types...
). Parametric polymorphism is widely supported in statically typed functional programming languages. In the object-oriented programming community, programming using parametric polymorphism is often called generic programming
Generic programming
In a broad definition, generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters...
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
In programming language theory, subtyping or subtype polymorphism is a form of type polymorphism in which a subtype is a datatype that is related to another datatype by some notion of substitutability, meaning that program constructs, typically subroutines or functions, written to operate on...
or inclusion polymorphism is a concept in type theory
Type theory
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
wherein a name may denote instances of many different classes as long as they are related by some common super class. Inclusion polymorphism is generally supported through subtyping, i.e., objects of different types are entirely substitutable for objects of another type (their base type(s)) and thus can be handled via a common interface. Alternatively, inclusion polymorphism may be achieved through type coercion, also known as type casting.
Interaction between parametric polymorphism and subtyping leads to the concepts of bounded quantification
Bounded quantification
In type theory, bounded quantification refers to universal or existential quantifiers which are restricted to range only over the subtypes of a particular type. Bounded quantification is an interaction of parametric polymorphism with subtyping...
Within the type system of a programming language, covariance and contravariance refers to the ordering of types from narrower to wider and their interchangeability or equivalence in certain situations ....
In the area of mathematical logic and computer science known as type theory, a type constructor is a feature of a typed formal language that builds new types from old. Typical type constructors encountered are product types, function types, power types and list types. Basic types are considered...
In programming languages, ad-hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument to...
to refer to polymorphic functions which can be applied to arguments of different types, but which behave differently depending on the type of the argument to which they are applied (also known as function overloading or operator overloading
Operator overloading
In object oriented computer programming, operator overloading—less commonly known as operator ad-hoc polymorphism—is a specific case of polymorphism, where different operators have different implementations depending on their arguments...
Ad hoc is a Latin phrase meaning "for this". It generally signifies a solution designed for a specific problem or task, non-generalizable, and not intended to be able to be adapted to other purposes. Compare A priori....
" in this context is not intended to be pejorative; it refers simply to the fact that this type of polymorphism is not a fundamental feature of the type system. In the example below, the Add functions seems to work generically over various types when looking at the invocations, but are considered to be two entirely distinct functions by the compiler for all intents and purposes:
program Adhoc;
function Add( x, y : Integer ) : Integer;
begin
Add := x + y
end;
function Add( s, t : String ) : String;
begin
Add := Concat( s, t )
end;
begin
Writeln(Add(1, 2));
Writeln(Add('Hello, ', 'World!'));
end.
In dynamically typed languages the situation can be more complex as the correct function that needs to be invoked might only be determinable at run time.
In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without...
allows a function or a data type to be written generically, so that it can handle values identically without depending on their type. Parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety.
Parametric polymorphism is ubiquitous in functional programming, where it is often simply referred to as "polymorphism". The following example shows a parametrized 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, where it goes under the name "generics":
class List {
class Node {
T elem;
Node next;
}
Node head;
int length { ... }
}
Any parametrically polymorph 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
Parametricity
Parametricity is a result in the theory of programming languages in computer science. The principle of parametricity dictates that functions with similar types have similar properties.- Theory of parametricity :...
.
Subtype polymorphism (or inclusion polymorphism)
Some languages employ the idea of subtypes to restrict the range of types that can be used in a particular case of parametric polymorphism. In these languages, subtyping polymorphism (sometimes referred to as dynamic polymorphism) 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
Liskov substitution principle
Substitutability is a principle in object-oriented programming. It states that, in a computer program, if S is a subtype of T, then objects of type T may be replaced with objects of type S without altering any of the desirable properties of that program...
). This type relation is sometimes written S <: T. Conversely, T is said to be a supertype of S—written T :> S.
For example, if Number, Rational, and Integer are types such that Number :> Rational and Number :> Integer, 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
Identity (object-oriented programming)
An identity in object-oriented programming, object-oriented design and object-oriented analysis describes the property of objects that distinguishes them from other objects. This is closely related to the philosophical concept of identity....
.
In fact, if the Number type is abstract, it may not even be possible to get your hands on an object whose most-derived type is Number (see abstract data type
Abstract data type
In computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...
, abstract class). This particular kind of type hierarchy is known—especially in the context of the Scheme programming language—as a numerical tower
Numerical tower
In Scheme and some other Lisp dialects, a numerical tower is the set of data types that represent numbers in a given programming language.Each type in the tower conceptually "sits on" a more fundamental type, so an integer is a rational number and a number, but the inverse is not necessarily true,...
This is a list of object-oriented programming programming languages.-Languages with object-oriented features:*ABAP*Ada 95*AmigaE*BETA*Blue*Boo*C++*C#*COBOL*Cobra*ColdFusion*Common Lisp*COOL*CorbaScript*Clarion*CLU*Curl*D*Dylan*E*Eiffel...
s offer subtyping polymorphism using subclassing (also known as inheritance). In typical implementations, each class contains what is called a virtual table—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 is a computer programming mechanism in which the method being called upon an object is looked up by name at runtime. This is informally known as duck typing or name binding....
, because virtual function calls are not bound until the time of invocation, and
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 CLOS
CLOS
The Common Lisp Object System is the facility for object-oriented programming which is part of ANSI Common Lisp. CLOS is a powerful dynamic object system which differs radically from the OOP facilities found in more static languages such as C++ or Java. CLOS was inspired by earlier Lisp object...
Multiple dispatch or multimethods or function overloading is the feature of some object-oriented programming languages in which a function or method can be dynamically dispatched based on the run time type of more than one of its arguments...
, under which method calls are polymorphic in all arguments.
In the following example we make cats and dogs subtypes of animals. The procedure write accepts an animal, but will also work correctly if a subtype is passed to it:
abstract class Animal {
String talk;
}
Subtype polymorphism, almost universally called just polymorphism in the context of object-oriented programming, is the ability to create a variable, a function, or an object that has more than one form. The word derives from the Greek "πολυμορφισμός" meaning "having multiple forms"...
In computer programming with object-oriented programming languages, duck typing is a style of dynamic typing in which an object's current set of methods and properties determines the valid semantics, rather than its inheritance from a particular class or implementation of a specific interface...
In computer terminology, polymorphic code is code that uses a polymorphic engine to mutate while keeping the original algorithm intact. That is, the code changes itself each time it runs, but the function of the code will not change at all...
System F, also known as the polymorphic lambda calculus or the second-order lambda calculus, is a typed lambda calculus that differs from the simply typed lambda calculus by the introduction of a mechanism of universal quantification over types...
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
Virtual inheritance is a topic of object-oriented programming. It is a kind of inheritance in which the part of the object that belongs to the virtual base class becomes common direct base for the derived class and any next class that derives from it...
