Polymorphism (computer science)

Polymorphism (computer science)

In computer science, polymorphism is a programming language feature that allows values of different data types 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 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 is supported in many languages using function and method overloading.

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. John C. Reynolds (and later Jean-Yves Girard) formally developed this notion of polymorphism as an extension to the lambda calculus (called the polymorphic lambda calculus, or System F). 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.

In object-oriented programming, subtype polymorphism or inclusion polymorphism is a concept in type theory wherein a name may denote instances of many different classes as long as they are related by some common super class.[1] 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 and covariance and contravariance (or polarity) of type constructors.

Contents

History

Forms of polymorphism

Ad-hoc polymorphism

Chris Strachey[2] chose the term ad-hoc polymorphism 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). The term "ad hoc" 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.

Parametric polymorphism

Parametric polymorphism allows a function or a data type to be written generically, so that it can handle values identically without depending on their type.[3] 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<T> {
    class Node<T> {
        T elem;
        Node<T> next;
    }
    Node<T> head;
    int length() { ... }
}
 
List<B> map(Func<A,B> f, List<A> xs) {
    ...
}

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.

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). 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. 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 many more types.

Object-oriented programming languages 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, 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.

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();
}
 
class Cat extends Animal {
    String talk() { return "Meow!"; }
}
 
class Dog extends Animal {
    String talk() { return "Woof!"; }
}
 
static void write(Animal a) {
    System.out.println(a.talk());
}
 
static void main() {
    write(new Cat());
    write(new Dog());
}

See also

References

  1. ^ Booch, et all 2007 Object-Oriented Analysis and Design with Applications. Addison-Wesley.
  2. ^ C. Strachey, Fundamental concepts in programming languages. Lecture notes for International Summer School in Computer Programming, Copenhagen, August 1967
  3. ^ Pierce, B. C. 2002 Types and Programming Languages. MIT Press.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Covariance and contravariance (computer science) — 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 (such as parameters, generics, and return… …   Wikipedia

  • Abstraction (computer science) — In computer science, abstraction is the process by which data and programs are defined with a representation similar to its pictorial meaning as rooted in the more complex realm of human life and language with their higher need of summarization… …   Wikipedia

  • Object (computer science) — In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure. (With the later introduction of object oriented programming the same word,… …   Wikipedia

  • String (computer science) — In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet. In computer programming, a string is traditionally a sequence of… …   Wikipedia

  • Inheritance (computer science) — In object oriented programming, inheritance is a way to form new classes (instances of which are called objects) using classes that have already been defined. The inheritance concept was invented in 1967 for Simula. [ [http://heim.ifi.uio.no/… …   Wikipedia

  • Reference (computer science) — This article is about a general notion of reference in computing. For the more specific notion of reference used in C++, see Reference (C++). In computer science, a reference is a value that enables a program to indirectly access a particular… …   Wikipedia

  • Integer (computer science) — In computer science, an integer is a datum of integral data type, a data type which represents some finite subset of the mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values …   Wikipedia

  • Union (computer science) — In computer science, a union is a data structure that stores one of several types of data at a single location. There are only two safe ways of accessing a union object. One is to always read the field of a union most recently assigned; tagged… …   Wikipedia

  • Topic outline of computer science — Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. One well known subject classification system for computer science is… …   Wikipedia

  • Polymorphism — or dimorphism may refer to: Contents 1 Biology 2 Computing 3 Chemistry …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”