| Polymorphism |
|---|
| Ad hoc polymorphism |
| Parametric polymorphism |
| Subtyping |
Inprogramming language theory andtype theory,polymorphism is the use of one symbol to represent multiple different types.[1]
Inobject-oriented programming, polymorphism is the provision of oneinterface to entities of differentdata types.[2] The concept is borrowed from a principle inbiology where an organism or species can have many different forms or stages.[3]
The most commonly recognized major forms of polymorphism are:
Interest in polymorphictype systems developed significantly in the 1990s, with practical implementations beginning to appear by the end of the decade.Ad hoc polymorphism andparametric polymorphism were originally described inChristopher Strachey'sFundamental Concepts in Programming Languages,[5] where they are listed as "the two main classes" of polymorphism. Ad hoc polymorphism was a feature ofALGOL 68, while parametric polymorphism was the core feature ofML'stype system.
In a 1985 paper,Peter Wegner andLuca Cardelli introduced the terminclusion polymorphism to model subtypes andinheritance,[1] citingSimula as the first programming language to implement it.
Christopher Strachey chose the termad 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 asfunction overloading oroperator overloading).[5] The term "ad hoc" in this context is not pejorative: instead, it means that this form of polymorphism is not a fundamental feature of the type system. In theJava example below, theadd functions seem to work generically over two types (integer andstring) when looking at the invocations, but are considered to be two entirely distinct functions by thecompiler for all intents and purposes:
classAdHocPolymorphic{publicStringadd(intx,inty){return"Sum: "+(x+y);}publicStringadd(Stringname){return"Added "+name;}}publicclassAdhoc{publicstaticvoidmain(String[]args){AdHocPolymorphicpoly=newAdHocPolymorphic();System.out.println(poly.add(1,2));// prints "Sum: 3"System.out.println(poly.add("Jay"));// prints "Added Jay"}}
Indynamically typed languages the situation can be more complex as the correct function that needs to be invoked might only be determinable at run time.
Implicit type conversion has also been defined as a form of polymorphism, referred to as "coercion polymorphism".[1][6]
Parametric polymorphism allows a function or a data type to be written generically, so that it can handle valuesuniformly without depending on their type.[7] Parametric polymorphism is a way to make a language more expressive while still maintaining full statictype safety.
The concept of parametric polymorphism applies to bothdata types andfunctions. A function that can evaluate to or be applied to values of different types is known as apolymorphic function. A data type that can appear to be of a generalized type (e.g., alist with elements of arbitrary type) is designatedpolymorphic 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 inHaskell shows a parameterized list data type and two parametrically polymorphic functions on them:
dataLista=Nil|Consa(Lista)length::Lista->IntegerlengthNil=0length(Consxxs)=1+lengthxsmap::(a->b)->Lista->ListbmapfNil=Nilmapf(Consxxs)=Cons(fx)(mapfxs)
Parametric polymorphism is also available in several object-oriented languages. For instance,templates inC++ andD, or under the namegenerics inC#,Delphi, Java, andGo:
classList<T>{classNode<T>{Telem;Node<T>next;}Node<T>head;intlength(){...}}List<B>map(Func<A,B>f,List<A>xs){...}
John C. Reynolds (and laterJean-Yves Girard) formally developed this notion of polymorphism as an extension to lambda calculus (called the polymorphic lambda calculus orSystem 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 ofparametricity.
Some languages employ the idea ofsubtyping (also calledsubtype polymorphism orinclusion 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 typeT, but also work correctly, if passed an object that belongs to a typeS that is a subtype ofT (according to theLiskov substitution principle). This type relation is sometimes writtenS <:T. Conversely,T is said to be asupertype ofS, writtenT :>S. Subtype polymorphism is usually resolved dynamically (see below).
In the following Java example cats and dogs are made subtypes of pets. The procedureletsHear() accepts a pet, but will also work correctly if a subtype is passed to it:
abstractclassPet{abstractStringspeak();}classCatextendsPet{Stringspeak(){return"Meow!";}}classDogextendsPet{Stringspeak(){return"Woof!";}}staticvoidletsHear(finalPetpet){println(pet.speak());}staticvoidmain(String[]args){letsHear(newCat());letsHear(newDog());}
In another example, ifNumber,Rational, andInteger are types such thatNumber :>Rational andNumber :>Integer (Rational andInteger as subtypes of a typeNumber that is a supertype of them), a function written to take aNumber will work equally well when passed anInteger orRational as when passed aNumber. The actual type of the object can be hidden from clients into ablack box, and accessed via objectidentity. If theNumber type isabstract, it may not even be possible to get your hands on an object whosemost-derived type isNumber (seeabstract data type,abstract class). This particular kind of type hierarchy is known, especially in the context of theScheme language, as anumerical tower, and usually contains many more types.
Object-oriented programming languages offer subtype polymorphism usingsubclassing (also known asinheritance). In typical implementations, each class contains what is called avirtual table (shortly calledvtable) — 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:
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 asCommon Lisp Object System, providemultiple dispatch, under which method calls are polymorphic inall arguments.
The interaction between parametric polymorphism and subtyping leads to the concepts ofvariance andbounded quantification.
Row polymorphism[8] is a similar, but distinct concept from subtyping. It deals withstructural types. It allows the usage of all values whose types have certain properties, without losing the remaining type information.
A related concept ispolytypism (ordata 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".[9]
Rank polymorphism is one of the defining features of thearray programming languages, likeAPL. The essence of the rank-polymorphic programming model is implicitly treating all operations as aggregate operations, usable on arrays with arbitrarily many dimensions,[10] which is to say that rank polymorphism allows functions to be defined to operate on arrays of any shape and size.
Polymorphism can be distinguished by when the implementation is selected: statically (at compile time) or dynamically (at run time, typically via avirtual function). This is known respectively asstatic dispatch anddynamic dispatch, and the corresponding forms of polymorphism are accordingly calledstatic polymorphism anddynamic polymorphism.
Static polymorphism executes faster, because there is no dynamic dispatch overhead, but requires additional compiler support. Further, static polymorphism allows greater static analysis by compilers (notably for optimization), source code analysis tools, and human readers (programmers). Dynamic polymorphism is more flexible but slower—for example, dynamic polymorphism allowsduck typing, and a dynamically linked library may operate on objects without knowing their full type.
Static polymorphism typically occurs in ad hoc polymorphism and parametric polymorphism, whereas dynamic polymorphism is usual for subtype polymorphism. However, it is possible to achieve static polymorphism with subtyping through more sophisticated use oftemplate metaprogramming, namely thecuriously recurring template pattern.
When polymorphism is exposed via alibrary, static polymorphism becomes impossible fordynamic libraries as there is no way of knowing what types the parameters are when theshared object is built. While languages like C++ and Rust usemonomorphized templates, theSwift programming language makes extensive use of dynamic dispatch to build theapplication binary interface for these libraries by default. As a result, more code can be shared for a reduced system size at the cost of runtime overhead.[11]
polymorphism – providing a single interface to entities of different types.