Polymorphism (computer science): Difference between revisions

Revision as of 08:44, 29 January 2022

Latest revision as of 22:54, 4 August 2025

(45 intermediate revisions by 38 users not shown)

Line 1:

{{Short description|ProgrammingUsing languageone conceptinterface or symbol with regards to multiple different types}}

{{distinguishDistinguish|Polymorphic code}}

{{Polymorphism}}

In [[programming language theory]] and [[type theory]], '''polymorphism''' is the approach that allows a value type to assume different types.<ref name="Luca">{{Cite journal |last1=Cardelli |first1=Luca |author1-link=Luca Cardelli |last2=Wegner |first2=Peter |author2-link=Peter Wegner (computer scientist)|doi=10.1145/6041.6042 |title=On understanding types, data abstraction, and polymorphism |journal=[[ACM Computing Surveys]] |volume=17 |issue=4 |pages=471–523 |date=December 1985 |url=http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf |citeseerx=10.1.1.117.695 |s2cid=2921816}}: "Polymorphic types are types whose operations are applicable to values of more than one type."</ref>

In [[programming language]]s and [[type theory]], '''polymorphism''' is the provision of a single [[interface (computing)|interface]] to entities of different [[Data type|type]]s<ref>

{{cite web | url=http://www.stroustrup.com/glossary.html#Gpolymorphism | author=Bjarne Stroustrup | title=Bjarne Stroustrup's C++ Glossary | date=February 19, 2007 | quote=polymorphism – providing a single interface to entities of different types.}}</ref> or the use of a single symbol to represent multiple different types.<ref name="Luca">{{Cite journal | last1 = Cardelli | first1 = Luca| author-link1 = Luca Cardelli| last2 = Wegner | first2 = Peter| author-link2 = Peter Wegner| doi = 10.1145/6041.6042| title = On understanding types, data abstraction, and polymorphism| journal = [[ACM Computing Surveys]]| volume = 17| issue = 4| pages = 471–523| date=December 1985 | url = http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf| citeseerx = 10.1.1.117.695| s2cid = 2921816}}: "Polymorphic types are types whose operations are applicable to values of more than one type."</ref>The concept is borrowed from a principle in biology where an organism or species can have many different forms or stages.<ref name="Moved">{{cite web | title=Polymorphism |work=The Java™ Tutorials: Learning the Java Language: Interfaces and Inheritance |publisher=Oracle | url=https://docs.oracle.com/javase/tutorial/java/IandI/polymorphism.html | access-date=2021-09-08}}</ref>

In [[object-oriented programming]], polymorphism is the provision of one [[Interface (object-oriented programming)|interface]] to entities of different [[data type]]s.<ref>{{cite web | url=http://www.stroustrup.com/glossary.html#Gpolymorphism |last1=Stroustrup author|first1=Bjarne |author1-link=Bjarne Stroustrup | title=Bjarne Stroustrup's C++ Glossary | date=February 19, 2007 | quote=polymorphism – providing a single interface to entities of different types.}}</ref> or the use of a single symbol to represent multiple different types.<ref name="Luca">{{Cite journal | last1 = Cardelli | first1 = Luca| author-link1 = Luca Cardelli| last2 = Wegner | first2 = Peter| author-link2 = Peter Wegner| doi = 10.1145/6041.6042| title = On understanding types, data abstraction, and polymorphism| journal = [[ACM Computing Surveys]]| volume = 17| issue = 4| pages = 471–523| date=December 1985 | url = http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf| citeseerx = 10.1.1.117.695| s2cid = 2921816}}: "Polymorphic types are types whose operations are applicable to values of more than one type."</ref>The concept is borrowed from a principle in [[biology]] where an organism or species can have many different forms or stages.<ref name="Moved">{{cite web | title=Polymorphism |work=The Java™Java Tutorials: Learning the Java Language: Interfaces and Inheritance |publisher=Oracle | url=https://docs.oracle.com/javase/tutorial/java/IandI/polymorphism.html | access-date=2021-09-08}}</ref>

The most commonly recognized major classes of polymorphism are::::::::::::;::::

The most commonly recognized major classesforms of polymorphism are::::::::::::;::::

* ''[[Ad hoc polymorphism]]'': defines a common interface for an arbitrary set of individually specified types.

* ''[[Parametric polymorphism]]'': whennot onespecifying or moreconcrete types areand notinstead specified by name but byuse abstract symbols that can representsubstitute for any type.

* ''[[Subtyping]]'' (also called ''subtype polymorphism'' or ''inclusion polymorphism''): when a name denotes instances of many different classes related by some common superclass.<ref name="gbooch">{{cite book |last1=Conallen |first1=J. |last2=Engle |first2=M. |last3=Houston |first3=K. |last4=Maksimchuk |first4=R. |last5=Young |first5=B. |last6=Booch |first6=G. |author6-link=Grady Booch |date=2007 |title=Object-Oriented Analysis and Design with Applications |publisher=Pearson Education |edition=3rd |date=2007 |isbn=9780132797443 |pages= }}</ref>

==History==

Interest in polymorphic [[type system]]s developed significantly in the 1960s1990s, with practical implementations beginning to appear by the end of the decade. ''Ad hoc polymorphism'' and ''parametric polymorphism'' were originally described in [[Christopher Strachey]]'s ''[[Fundamental Concepts in Programming Languages]]'',<ref name=Strachey00>{{cite journal |last1=Strachey |first1=Christopher |author1-link=Christopher Strachey |date=2000 |title=Fundamental Concepts in Programming Languages |journal=[[Higher-Order and Symbolic Computation]] |date=2000 |volume=13 |issue=1/2 |pages=11–49 |doi=10.1023/A:1010000313106 |issn=1573-0557 |citeseerx=10.1.1.332.3161 |s2cid=14124601 }}</ref> where they are listed as "the two main classes" of polymorphism. Ad hoc polymorphism was a feature of [[AlgolALGOL 68]], while parametric polymorphism was the core feature of [[ML (programming language)|ML]]'s [[type system]].

In a 1985 paper, [[Peter Wegner (computer scientist)|Peter Wegner]] and [[Luca Cardelli]] introduced the term ''inclusion polymorphism'' to model subtypes and [[Inheritance (object-oriented programming)|inheritance]],<ref name="Luca"/> citing [[Simula]] as the first programming language to implement it.

==TypesForms==

===Ad hoc polymorphism===

{{mainFurther|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]]).<ref name=Strachey00/> The term "[[ad hoc]]" in this context is not intendedpejorative: to be pejorative;instead, it refers simply to the factmeans that this typeform of polymorphism is not a fundamental feature of the type system. In the [[PascalJava (programming language)|Pascal]] / [[Delphi (programming language)|DelphiJava]] example below, the <code>Addadd</code> functions seem to work generically over varioustwo types ([[Integer (computer science)|integer]] and [[String (computer science)|string]]) when looking at the invocations, but are considered to be two entirely distinct functions by the [[compiler]] for all intents and purposes:

<syntaxhighlight lang="Pascaljava">

class AdHocPolymorphic {

program Adhoc;

public String add(int x, int y) {

return "Sum: " + (x + y);

}

public String add(String name) {

function Add(x, y : Integer) : Integer;

return "Added " + name;

begin

Add := x + y}

}

end;

public class Adhoc {

function Add(s, t : String) : String;

public static void main(String[] args) {

begin

AdHocPolymorphic poly = new AdHocPolymorphic();

Add := Concat(s, t)

end;

System.out.println(poly.add(1,2)); // prints "Sum: 3"

begin

System.out.println(poly.add("Jay")); // prints "Added Jay"

Writeln(Add(1, 2)); (* Prints "3" *)

}

Writeln(Add('Hello, ', 'Mammals!')); (* Prints "Hello, Mammals!" *)

}

end.

</syntaxhighlight>

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.

[[Implicit type conversion]] has also been defined as a form of polymorphism, referred to as "coercion polymorphism".<ref name="Luca"/><ref name="Tucker2004">{{cite book |firstlast1=Tucker |first1=Allen B. |lastdate=Tucker2004 |title=Computer Science Handbook |edition=2nd |url=https://books.google.com/books?id=9IFMCsQJyscC&pg=SA91-PA5|date=2004 |publisher=Taylor & Francis |pages=91– |isbn=978-1-58488-360-9|pages=91–}}</ref>

===Parametric polymorphism===

{{mainFurther|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.<ref name="bjpierce">{{cite book |firstlast1=Pierce |first1=B.C. |lastdate=Pierce2002 |chapter=23.2 Varieties of Polymorphism |chapter-url=https://books.google.com/books?id=ti6zoAC9Ph8C&pg=PA340 |title=Types and Programming Languages |publisher=MIT Press |date=2002 |isbn= 9780262162098 |pages=340–1 |url=}}</ref> 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 type]]s and [[functionFunction (computer programming)|functionfunctions]]s. 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 [[listList (computingabstract data type)|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 followingnext example in [[Haskell (programming language)|Haskell]] shows a parameterized list data type and two parametrically polymorphic functions on them:

<syntaxhighlight lang="Haskell">

Line 63 ⟶ 66:

</syntaxhighlight>

Parametric polymorphism is also available in several object-oriented languages. For instance, [[Template (C++)|templates]] in [[C++]] and [[D (programming language)|D]], or under the name [[Generics in Java|generics]] in [[C Sharp (programming language)|C#]], [[Delphi and(software)|Delphi]], Java, and [[Go (programming language)|Go]]:

<syntaxhighlight lang="CSharp">

Line 83 ⟶ 86:

===Subtyping===

{{MainFurther|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 {{nowrap|''S''&nbsp;&lt; <:&nbsp; ''T''}}. Conversely, ''T'' is said to be a ''supertype'' of ''S''—written, written {{nowrap|''T''&nbsp; :&gt;&nbsp;> ''S''}}. Subtype polymorphism is usually resolved dynamically (see below).

In the following Java example we make cats and dogs are made subtypes of animalspets. The procedure <code>letsHear()</code> accepts ana animalpet, but will also work correctly if a subtype is passed to it:

<syntaxhighlight lang="Javajava">

abstract class AnimalPet {

abstract String talkspeak();

}

class Cat extends AnimalPet {

String talkspeak() {

return "Meow!";

}

}

class Dog extends AnimalPet {

String talkspeak() {

return "Woof!";

}

}

static void letsHear(final AnimalPet apet) {

System.out.println(apet.talkspeak());

}

Line 115 ⟶ 118:

</syntaxhighlight>

[[File:UML class pet.svg]]

In another example, if ''Number'', ''Rational'', and ''Integer'' are types such that ''Number''&nbsp;:&gt;&nbsp;''Rational'' and ''Number''&nbsp;:&gt;&nbsp;''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 (systems)|black box]], and accessed via object [[identity (object-oriented programming)|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 class]]). This particular kind of type hierarchy is known—especially in the context of the [[Scheme (programming language)|Scheme programming language]]—as a ''[[numerical tower]]'', and usually contains many more types.

In another example, if ''Number'', ''Rational'', and ''Integer'' are types such that {{nowrap|''Number''&nbsp; :&gt;&nbsp;> ''Rational''}} and {{nowrap|''Number''&nbsp; :&gt;&nbsp;> ''Integer''}} (''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 (systems)|black box]], and accessed via object [[identity (object-oriented programming)|identity]]. 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 class]]). This particular kind of type hierarchy is known, especially in the context of the [[Scheme (programming language)|Scheme language]], as a ''[[numerical tower]]'', and usually contains many more types.

[[Object-oriented programming language]]s offer subtype polymorphism using ''[[Subclass (computer science)|subclass]]ing'' (also known as ''[[inheritance in object-oriented programming|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:

[[Object-oriented programming language]]s offer subtype polymorphism using ''[[Subclass (computer science)|subclass]]ing'' (also known as ''[[inheritance in object-oriented programming|inheritance]]''). In typical implementations, each class contains what is called a ''[[virtual table]]''—a (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 <code>this</code> 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.

Line 126 ⟶ 130:

===Row polymorphism===

{{mainFurther|Row polymorphism}}

{{see also|Duck typing}}

Row polymorphism<ref>

{{cite conference

| first = Mitchell

| last = Wand

| title = Type inference for record concatenation and multiple inheritance

| book-title = Proceedings. Fourth Annual Symposium on Logic in Computer Science

| pages = 92–97

| date = June 1989

| doi = 10.1109/LICS.1989.39162

}}

</ref> is a similar, but distinct concept from subtyping. It deals with [[Structural type system|structural types]]. It allows the usage of all values whose types have certain properties, without losing the remaining type information.

===Polytypism===

{{mainFurther|Generic programming#Functional languages}}

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".<ref>{{cite book |first1=Ralf |last1=Lämmel |first2=Joost |last2=Visser |chapter=Typed Combinators for Generic Traversal |title=Practical Aspects of Declarative Languages: 4th International Symposium |publisher=Springer |date=2002 |isbn=354043092X |pages=137–154, See p. 153 |citeseerx=10.1.1.18.5727 |url=}}</ref>

===Rank polymorphism===

Rank polymorphism is one of the defining features of the [[array programming]] languages, like [[APL (programming language)|APL]]. The essence of the rank-polymorphic programming model is implicitly treating all operations as aggregate operations, usable on arrays with arbitrarily many dimensions,<ref>{{cite arXiv |last1=Slepak |first1=Justin |last2=Shivers |first2=Olin |last3=Manolios |first3=Panagiotis |date=2019 |title=The semantics of rank polymorphism |class=cs.PL |eprint=1907.00509}}</ref> which is to say that rank polymorphism allows functions to be defined to operate on arrays of any shape and size.

==Implementation aspects==

===Static and dynamic polymorphism===

{{mainFurther|Static polymorphism|Late binding|Dynamic dispatch}}

Polymorphism can be distinguished by when the implementation is selected: statically (at compile time) or dynamically (at run time, typically via a [[virtual function]]). This is known respectively as ''[[static dispatch]]'' and ''[[dynamic dispatch]],'' and the corresponding forms of polymorphism are accordingly called ''static polymorphism'' and ''dynamic 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 allows [[Duck typing|duck 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 of [[template metaprogramming]], namely the [[curiously recurring template pattern]].

When polymorphism is exposed via a [[Library (computing)|library]], static polymorphism becomes impossible for [[dynamic libraries]] as there is no way of knowing what types the parameters are when the [[shared object]] is built. While languages like C++ and Rust use [[monomorphization|monomorphized]] templates, the [[Swift programming language]] makes extensive use of dynamic dispatch to build the [[application 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.<ref>{{cite web |last1=Beingessner |first1=Alexis |title=How Swift Achieved Dynamic Linking Where Rust Couldn't |url=https://gankra.github.io/blah/swift-abi/ }}</ref>

==See also==

* [[Duck typing]] for polymorphism without (static) types

* [[Polymorphic code]] (computer virus terminology)

* [[System F]] for a [[lambda calculus]] with parametric polymorphism.

* [[Type class]]

* [[Type theory]]

* [[Virtual inheritance]]

==References==

{{reflist|30emReflist}}

==External links==

Line 178 ⟶ 181:

{{DEFAULTSORT:Polymorphism}}

[[Category:Polymorphism (computer science)| ]]

[[Category:Articles with example C Sharp code]]

[[Category:Articles with example Haskell code]]

[[Category:Articles with example Java code]]

[[Category:Articles with example Pascal code]]

[[Category:Data types]]

[[Category:Functional programming]]

Line 188 ⟶ 187:

[[Category:Type theory]]

[[Category:Generic programming]]

[[Category:Programming language comparisons]]

<!-- Hidden categories below -->

[[Category:Articles with example C Sharp code]]

[[Category:Articles with example Haskell code]]

[[Category:Articles with example Java code]]

[[Category:Articles with example Pascal code]]