Polymorphism (computer science)

: In computer science, polymorphism is the idea of allowing the same code (computer programming) to be used with different class (set theory) of data (which classes in typed languages correspond to data type), resulting in more general and abstract implementations. The concept of polymorphism applies to functions as well as types. A function (programming) that can evaluate to and be applied to values of different types is known as a ''polymorphic function''. A datatype that contains elements of an unspecified type is known as a ''polymorphic datatype''. There are two fundamentally different kinds of polymorphism. If the range of actual types that can be used is finite and the combinations must be specified individually prior to use, it is called ''ad-hoc polymorphism''. 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''. Programming using the latter kind is called ''generic programming'', particularly in the object-oriented community. However, in many static typing functional programming languages the notion of parametric polymorphism is so deeply ingrained that most programmers simply take it for granted. Polymorphism has another view, a ''dual'', called Inheritance (object-oriented programming), which describes computer modules as sharing interfaces. Polymorphism gained most of its momentum with object-oriented programming and is just one of many reasons why OOP has trumped other methodologies such as procedural programming. == Parametric polymorphism == Using parametric polymorphism, a function or datatype can be written generically so that it can deal equally well with objects of various types. For example, a function append that joins two lists can be constructed so that it does not depend on one particular type of list: it can append lists of integers, lists of real numbers, lists of strings, and so on. Let a denote the type of elements in the lists. Then append can be typed [a] × [a] → [a], where [a] denotes a list of elements of type a. We say that the type of append is ''parameterized by a''. (Note that since there is only one type parameter, the function cannot be applied to just any pair of lists: they must consist of the same type of elements.) Parametric polymorphism was the first type of polymorphism developed, first identified by Christopher Strachey in 1967. It was also the first type of polymorphism to appear in an actual programming language, ML programming language in 1976. It exists today in Standard ML, O'Caml, Haskell programming language, and others. Some argue that template (programming) should be considered an example of parametric polymorphism, though instead of actually reusing generic code they rely on macros to generate specific code (which can result in ''code bloat''). Parametric polymorphism is a way to make a language more expressible, while still maintaining full static type-safety. It is thus irrelevant in dynamically typed languages, since ''by definition'' they lack static type-safety. However, any dynamically typed function ''f'' that takes ''n'' arguments can be given a static type using parametric polymorphism: ''f'' : ''p₁'' × ... × ''p_n'' → ''r'', where ''p₁'', ..., ''p_n'' and ''r'' are type parameters. Of course, this type is completely insubstantial and thus essentially useless. === Impredicative polymorphism === This is a more powerful form of parametric polymorphism. The most common form of this in general use today is ML-style polymorphism (also called let-polymorphism). === Predicative polymorphism === This type of polymorphism is similar to the impredicative polymorphism but a little less powerful in the sense that the type applications can only take actual concrete types as arguments while in impredicative polymorphism, type application can be passed arbitrary type schemas as argument(s). == Subtyping 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 or dynamic typing) 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 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 (object-oriented programming). 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—as a ''numerical tower'', and usually contains a lot more types. Object-oriented programming environments such as C Plus Plus and GObject implement subtyping polymorphism using ''subclassing'' (also known as ''inheritance in object-oriented programming''). In C++, 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'', 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, provide ''multiple dispatch'', under which method calls are polymorphic in ''all'' arguments. == Ad-hoc polymorphism == Ad-hoc polymorphism usually refers to simple function overloading, but sometimes automatic type conversion, known as coercion, is also considered to be a kind of ad-hoc polymorphism (see the example section below). Common to these two types is the fact that the programmer has to specify exactly what types are to be usable with the polymorphic function. The name refers to the manner in which this kind of polymorphism is typically introduced: “Oh, hey, let’s make the + operator work on strings, too!” Some argue that ad-hoc polymorphism is not polymorphism in a meaningful computer science sense at all—that it is just syntactic sugar for calling append_integer, append_string, etc., manually. One way to see it is that * to the user, there appears to be only one function, but one that takes different types of input and is thus type polymorphic; on the other hand, * to the author, there are several functions that need to be written—one for each type of input—so there’s essentially no polymorphism. === Overloading === Overloading allows multiple functions taking different types to be defined with the same name; the compiler or Interpreter (computing) automatically calls the right one. This way, functions appending lists of integers, lists of strings, lists of real numbers, and so on could be written, and all be called ''append''—and the right ''append'' function would be called based on the type of lists being appended. This differs from parametric polymorphism, in which the function would need to be written ''generically'', to work with any kind of list. Using overloading, it is possible to have a function perform two completely different things based on the type of input passed to it; this is not possible with parametric polymorphism. This type of polymorphism is common in object-oriented programming languages, many of which allow operators to be overloaded in a manner similar to functions (see operator overloading). It is also used extensively in the purely functional programming language Haskell programming language. Many languages lacking ad-hoc polymorphism suffer from long-winded names such as print_int, print_string, etc. (see Objective Caml). An advantage that is sometimes gained from overloading is the appearance of specialization, e.g., a function with the same name can be implemented in multiple different ways, each optimized for the particular data types that it operates on. This can provide a convenient interface for code that needs to be specialized to multiple situations for performance reasons. In general, overloading is done at compile time, so it is not a substitute for Double dispatch or multiple dispatch. === Type Classes === The type system of Haskell programming language includes a construct called the type class that provides a powerful form of ad-hoc polymorphism. A type class is defined by giving a set of operations (or "methods") that must be implemented for every type in the class. For example, the predefined class Ord contains types that are ''ordered'', that is, types whose elements may be compared using < or <=. A function to sort a list (using <= for comparison) is given the type Ord a => ([a] -> [a]). That is, it is a function that can take a list of elements of type a and return a list of the same type, ''provided'' that a is in the class Ord. The parentheses in the type are unnecessary but make its meaning clearer: this type captures the fact that the sorting function can take elements of many different types (and is therefore polymorphic), but that the elements of a list to be sorted cannot be just anything: it must be possible to compare them. A programmer can make any type t a member of a given class C using an ''instance declaration'' that defines implementations of all of C's methods for the particular type t. For instance, if a programmer defines a complex new data type, she may then make her new type an instance of Ord by providing a function to compare values of that type in whatever way she considers appropriate. Once she has done this, she may use a sorting function of the type just given to sort lists of elements of her type. Programmers may also define new type classes of their own. Note that type classes are rather different from Class (computer science) in object-oriented languages; in particular, Ord is not a type, so there is no such thing as a value of type Ord. Thus the Haskell approach to a generic sorting function as outlined here is quite different from the subtyping-based approach often seen in object-oriented programming. Type classes are in fact much more closely related to parametric polymorphism (note that the type of the sorting function would be the parametrically polymorphic type [a] -> [a] if it were not for the type class constraint "Ord a =>"); however, Haskell programmers tend to consider them a form of ad-hoc polymorphism, probably because their most pervasive use is for the overloaded arithmetic and comparison operators. === Coercion === Due to a concept known as coercion, a function can become polymorphic without being initially designed for it. Let f be a function that takes an argument of type T, and S be a type that can be ''automatically converted'' to T. Then f can be said to be polymorphic with respect to S and T. Some languages (e.g., C (programming language), Java (programming language)), provide a fixed set of conversion rules, while others (e.g., C Plus Plus) allow new conversion rules to be defined by the programmer. While calling C “polymorphic” is perhaps stretching it, the facility for automatic conversion (i.e., ''casting operators'') found in C++ adds a whole new class of polymorphism to the language. == Example == This example aims to illustrate the three different kinds of polymorphism described in this article. Though overloading an originally arithmetic operator to do a wide variety of things in this way may not be the most clear-cut example, it allows some subtle points to be made. In practice, the different types of polymorphism are not generally mixed up as much as they are here. Imagine, if you will, an operator + that may be used in the following ways: # 1 + 2 → 3 # 3.14 + 0.0015 → 3.1415 # 1 + 3.7 → 4.7 # [1, 2, 3] + [4, 5, 6] → [1, 2, 3, 4, 5, 6] # [true, false] + [false, true] → [true, false, false, true] # "foo" + "bar" → "foobar" === Overloading === To handle these six function calls, four different pieces of code are needed—or ''three'', if strings are considered to be lists of characters: * In the first case, integer (computer science) addition must be invoked. * In the second and third cases, floating point addition must be invoked. * In the fourth and fifth cases, list concatenation must be invoked. * In last case, literal string concatenation must be invoked, unless this too is handled as list concatenation (as in, e.g., Haskell (programming language)). Thus, the name + actually refers to three or four completely different functions. This is an example of ''overloading''. === Coercion === As we’ve seen, there’s one function for adding two integers and one for adding two floating-point numbers in this hypothetical programming environment, but note that there is no function for adding an integer to a floating-point number. The reason why we can still do this is that when the compiler/Interpreter (computing) finds a function call f(a1, a2, ...) that no existing function named f can handle, it starts to look for ways to convert the arguments into different types in order to make the call conform to the signature of one of the functions named f. This is called ''coercion''. Both coercion and overloading are kinds of ''ad-hoc polymorphism''. In our case, since any integer can be converted into a floating-point number without loss of precision, 1 is converted into 1.0 and floating-point addition is invoked. There was really only one reasonable outcome in this case, because a floating-point number cannot generally be converted into an integer, so integer addition could not have been used; but significantly more complex, subtle, and ambiguous situations can occur in, e.g., C Plus Plus. === Parametric polymorphism === Finally, the reason why we can concatenate both lists of integers, lists of booleans, and lists of characters, is that the function for list concatenation was written without any regard to the type of elements stored in the lists. This is an example of ''parametric polymorphism''. If you wanted to, you could make up a thousand different new types of lists, and the generic list concatenation function would happily and without requiring any augmentation accept instances of them all. It can be argued, however, that this polymorphism is not really a property of the function ''per se''; that if the function is polymorphic, it is due to the fact that the ''list datatype'' is polymorphic. This is true—to an extent, at least—but it is important to note that the function could just as well have been defined to take as a second argument an ''element'' to append to the list, instead of another list to concatenate to the first. If this was the case, the function would indisputably be parametrically polymorphic, because it could then not know ''anything'' about its second argument, except that the type of the element should match the type of the elements of the list. The notion of parametric polymorphism was first described by Christopher Strachey. System F is a lambda calculus with parametric polymorphism. ------------------------------------------------------------ Polymorphism also refers to polymorphic code, computer code that mutation for each new time it is executed. This is sometimes used by computer viruses, computer worms and shellcodes to hide the presence of their decryption engines. Computing Object-oriented programming computer science Software design patterns == Reference == * Luca Cardelli, Peter Wegner. ''On Understanding Types, Data Abstraction, and Polymorphism,'' from Computing Surveys, (December, 1985) [http://research.microsoft.com/Users/luca/Papers/OnUnderstanding.pdf] * Paul Hudak, John Peterson, Joseph Fasel. ''A Gentle Introduction to Haskell Version 98''. [http://www.haskell.org/tutorial/]

Polymorphism (computer science)

Much of the stuff under "Subtyping polymorphism" (including most of the stuff I just added) does not belong under "Parametric polymorphism", but I don't have time to fix that right now. —User:Daniel Brockman 16:19, Jun 1, 2004 (UTC) ---- I've never come across ad-hoc polymorphism as described in the article (although of course I understand overloading and coercion), only the type described as parametric polymorphism. Seems to me that this could usefully be split into two sections: one on polymorphisms of data types and one on polymorphism of functions (in the broadest sense - to include procedures, members etc.). A data type is polymorphic in that it has a member whose type may be parametric or ad-hoc (as per the article). A type which is used to store a stack node would normally have two data members: the data held at a position in the stack and the next node below it. Manipulation of the stack itself doesn't need any knowledge of the data value type. How this type is applied to the stack node depends on the implementation language but falls neatly in the ad-hoc/parametric view explained in the article. I think though that for functions (procedures, members etc.) there are three ways of looking at the issue which makes it easier to see what is going on: * Inclusional polymorphism (called subtype polymorphism in the article) is where a function that expects (or returns) one type may in fact take or return any legal subtype. * Parametric polymorphism is where the type is applied to the function in the source code (either explicitly or implicitly). * Operational polymorphism is where the function assumes that some other function/operator will work on the type and the code is written in terms of that. This is the contract that a template implementation of, for example, min() works in C++ and is also the way that most object-based languages work. C++ is rare in that it allows all of the three forms. I wouldn't consider overloading a type of polymorphism in the same way that the others are. It really is a way of looking operation polymorphism - the overload itself is not polymorphic, but the function that makes use of the overload is assuming operational polymorphism on the types that it is using. --User:KayEss 02:13, 16 Sep 2004 (UTC) :This isn't entirely consistent with the use of the terms I'm familiar with. I'm familiar with the term "parametric polymorphism" being applied to functions, and meaning roughly what you call "operational polymorphism". An ML "append-to-list" function is often described as parametric polymorphic, for example, since it can append an element to any type of list by being written generically using only operators that work on any type of list. --User:Delirium 14:53, Sep 16, 2004 (UTC) :: The operational polymorphism comes into its own in weakly typed languages (I was particularly thinking of JavaScript/ECMAScript/JScript here). You write a function that takes an argument for which you make certain assumptions about the members available on that object. My guess is that a C++ programmer would probably think about min() in an operationaly polymorphic way, although strictly, you're right, it is parametric polymorphism. It was a (badly chosen) example... I guess the use of a min macro would be nearer the mark --User:KayEss 12:49, 18 Sep 2004 (UTC) == History of the term == I think this article could be improved by adding a little history about the term. Should be noted that was Christopher Strachey who invented it in 1967, and is his definition which's showed here. Latter, in 1985, Cardelli and Wagner [http://citeseer.ist.psu.edu/cardelli85understanding.html]refinedthat definition, adding the concept of universal polymorphism("true polymorphism"). Also should be noted that some authors(Booch and Rumbaugh) call polymorphism only to inclusion polymorphism or polymorphism of intheritance, which leads to misunderstandings. All of this is explained in the [http://burks.brighton.ac.uk/burks/pcinfo/progdocs/oofaq/]comp.object Usenet's group FAQ. I would do by myself, but english is not mi first language and I'm a little afraid of doing something unintelligible :-( == Removed sentence == I removed the following recently-added sentence from the end of the very first paragraph: : Polymorphism can be very useful in having many other applications use a common function or library, which is good because a function that does one thing does not have to be rewritten many different times to accomodate many datatypes. It needs to be reformulated, but I'm not sure how. —User:Daniel Brockman 20:47, Dec 22, 2004 (UTC) Whoever added it was right, though: something similar needs to be put there. —User:Daniel Brockman 20:50, Dec 22, 2004 (UTC) ------ I don't like polymorphism definitions based heavily on "types". Many OOP languages don't even have formal types. : Well, then they don't really have polymorphism. :) Seriously, though, I take the opposite view to yours, and bristle when people use the word "polymorphism" for anything other than parametric polymorphism, which as far as I can tell makes no sense without types. I think this article is right to discuss the all the uses of the word that one finds in different communities of programmers, but I think it could do a better job in terms of overall coherence and explaining how the different meanings of "polymorphism" relate to each other. -- User:Cjoev 19:41, 29 Mar 2005 (UTC) == Type classes == I have removed the existing discussion of Haskell's type classes (from the subtype polymorphism section), and put a new bit about them in the ad-hoc polymorphism section. I'm not a Haskell expert; those who are may find things wrong with what I've done. There were several things wrong with the old paragraph on type classes that even I could see, including the fact that it was in the subtyping section. Here it is just in case anyone wants it: "Haskell’s type system implements subtyping polymorphism using ''type classes''. Analoguously to interfaces in Java programming language, a type class declares a set of polymorphic operations that can be performed on any object whose type belongs to the class. This is then used to add ''constraints'' to types, limiting the set of objects that belong to them, while reciprocally expanding the set of things that can be done to the objects. For example, a list of ordered elements is typed (Ord a) => [a]. (The class Ord declares ordering relations such as =>, <, etc., and provides default implementations for most of them.) " -- User:Cjoev 20:51, 29 Mar 2005 (UTC) == Polymorphism and types == Here's my argument for stretching polymorphism beyond data types: the notion, I think, is wider. It's been alive for a very long time, even if it was conceived differently. (Abelson and Sussman call it "message-passing", for instance - and that was 1985!) In the end, polymorphism is polymorphism. --User:VKokielov 04:50, 12 Apr 2005 (UTC) == Proposed Merge from "Theoretical foundations..." == I think User:TakuyaMurata's proposed merge of the content from Theoretical foundation of polymorphism needs some discussion. (I hope I manage to start a debate rather than a flamewar here, but I may be on shaky ground...) In particular, before we move material from that article into this one we must answer the question: does that article mean the same thing by the word "polymorphism" as this one does? I say the relationship is at best unclear and needs to be clarified if the merger is to make this article better rather than less good. This article lists several different kinds of polymorphism, and I don't think that article is really talking about any of them: It's not about parametric polymorphism, because all the functions in the example have simple (''i.e.,'' monomorphic) types; it's not about subtype polymorphism, because there is no issue of one type ''containing'' or ''subsuming'' another; it's not about ad-hoc polymorphism, and it's not about coercion. Is there some other meaning of polymorphism we haven't covered yet? Perhaps the abstract exposition in the other article is good even though the extended example forming the bulk of it misses the mark? Maybe, but I find it difficult to understand. I think it's mostly focused on the idea of Abstraction (computer science) rather than polymorphism. I realize the two are related, but their relationship is very deep and subtle and should be explained as carefully and clearly as possible -- if we're not ready to do that we should leave it alone. User:Cjoev 18:24, 29 May 2005 (UTC) == Space between all and nothing == I have some problems with the statement at the top of the page, saying that there are two kinds of polymorphism. I find it neither practical, nor really fair: there is a lot of space between all and nothing. Typically one wants to ''constrain'' polymorphism, so that the set of actual types is potentially infinite, yet partly specified. Types may be used to express these partial specifications: this is the role of hierarchies. Hence a third kind of polymorphism: allow to express constraints relevant to a specific context. User:Marc Girod 06:29, 1 Jun 2005 (UTC) : This is a good point. Type classes, which are discussed briefly, are one form of this kind of constraint. Subtype-bounded polymorphism, which comes up all the time in type-theoretic studies of languages but I am ashamed to admit I don't really know the syntax for in any real language without looking it up, should also be mentioned but isn't. I think it should go somewhere under parametric polymorphism. Are there other forms of constraint as well? User:Cjoev 14:44, 1 Jun 2005 (UTC)

See other meanings of words starting from letter:

P

PA | PB | PC | PD | PE | PF | PG | PH | PI | PJ | PK | PL | PM | PN | PO | PR | PS | PT | PU | PW | PX | PY | PZ |

Words begining with Polymorphism_(computer_science):

Polymorphism_(computer_science)
Polymorphism_(computer_science)