What is a concise definition of polymorphism?

Cardelli's On Understanding Types, Data Abstraction, and Polymorphism

Answer by Quildreen Motta:

THE SHORT STORY
TL;DR: Polymorphism simply means that the same code supports many shapes (or types).
THE LONG, AND THOROUGH, AND PAINFUL STORY
A shape can be thought of as a "type," but it really means "how your value looks like considering the properties your operation is interested in" — otherwise we're excluding the idea of polymorphism in dynamically typed languages, which don't have types [1] . That said, the concept of polymorphism is much more useful in typed languages.
There are several different types of polymorphism, most of which people in mainstream object-oriented languages aren't aware of. Cardelli's On Understanding Types, Data Abstraction, and Polymorphism [2]  is probably the best resource and most thorough resource on the subject.
Cardelli, in that paper, separates polymorphic code in a few categories:
  • Parametric polymorphism denotes operations that support many shapes, and works in the same way for all of them. This kind of polymorphism only occurs in typed languages, and to support it, languages will have a concept of "parametric types" (also called Generics in Java and C#). While somewhat used in common OO languages, like Java and C#, this kind of polymorphism is much more common in functional programming languages, like Haskell and Standard ML.
  • Subtype (or Inclusion) polymorphism, denotes operations that support many shapes, as long as those shapes are a subset (or subtype) of some expected shape. This is what people usually mean when they say "polymorphism" in the context of object-oriented programming.
  • Overloading polymorphism, denotes cases where the same name denotes different operations. It's the case for the operation
    +

    , for example, which can be used with floating point or integer operands, and even though the name of the operation is still

    +

    , the operation selected is different depending on what its arguments are. Java supports overloading methods if the operands have different types or arities, for example.

  • Coercion polymorphism, denotes operations that automatically coerce their operands to a particular type before executing the operation. Java does this when boxing primitives, or when concatenating a String with some other primitive type.
It should be noted (and Cardelli acknowledges it), that the line between overloading polymorphism and coercion polymorphism is quite blurry. I'd particularly just categorise all of them as overloading polymorphism, because you can see them as that semantically. But I digress.
Now, since Cardelli, people kept coming with other kinds of polymorphism, specially in functional languages, where most of the polymorphism advances seem to happen at:
  • Higher-Kinded Polymorphism, which is a kind of parametric polymorphism where the type parameter is a function from type to type (also called a Kind). One of the few (if not the only) OO languages that support this today is Scala, and it's a functionality required for writing more advanced data structures, like Monads or Applicative Functors.
  • Structural Polymorphism, where an operation works on a particular "structure" of a value, so it works for all values that are a superset of that structure. Most typed languages use nominal types, so they don't support structural polymorphism, however, Java's usage of interfaces can be seen as a kind of structural polymorphism. Better support for this exists in languages like Scala and TypeScript.
  • Row Polymorphism, like Structural polymorphism, denotes an operation that works on a particular "structure" of a value, and the remaining structure is captured by a variable (called "row variable"). This allows operating on a subset of a value without losing its additional properties, as it's the case with Subtyping and Structural polymorphisms. Mostly only concatenative and functional languages (like Elm and PureScript) support this.
Okay, welp, that was a lot of different polymorphisms, and there are probably many more forms. What do I know, people come up with new polymorphisms for breakfast, everyday!
But if we look at each one of these, we can see a common pattern: they all exist so an operation can support more than one kind/type/shape of value. But supporting more than one type in an operation is a hard thing when you have a typed language, because if your

+

method supports both numbers and strings, for example, what should the return value of it be? So, each one of the kinds of polymorphism above are different answers to that question.

THE DIFFERENT KINDS OF POLYMORPHISM, EXEMPLIFIED
I'll use a language with Java-like syntax, but which is not Java, for all of the examples below, so it should be easier to understand if you're familiar with C-family languages. The only change I'm going to make is regarding the type annotation.
Instead of annotating a function like this:
int plus(int a, int b) { ... }
We'll annotate the function like this:
plus(a: int, b: int): int { ... }
Overloading Polymorphism
Suppose you have a function that inverts a pair of two integers. You could easily write it as such:
invertPair(pair: IntPair): IntPair {
 return new IntPair(pair.right, pair.left);
}
But what if we wanted to invert a pair of strings? Well, we could write a new function

invertStringPair

, but if we keep adding new functions, we'll have a lot of names to remember.

What if we could give different meanings to the name

invertPair

instead? If we give it two integers, it'll give us an

IntPair

. If we give it two strings, it'll give us an

StringPair

, and so on, and so forth:

sub(pair: IntPair): Int {
  return pair.left - pair.right;
}
join(pair: StringPair): String {
  return pair.left <> " " <> pair.right;
}

invertPair(pair: IntPair): IntPair {
  return new IntPair(pair.right, pair.left);
}
invertPair(pair: StringPair): StringPair {
  return new StringPair(pair.right, pair.left);
}
invertPair(pair: BoolPair): BoolPair {
  return new BoolPair(pair.right, pair.left);
}

( ... )

sub(invertPair(new IntPair(1, 3))) 
// => 2

join(invertPair(new StringPair("hello", "world"))) 
// => "world hello"
Okay, so now we can use the same name

invertPair

for all our types, and it'll just do the right thing. However, we still have to write one version of

invertPair

for each one of them, and this doesn't really scale well. What if we want to have pairs of any and every thing?!

Subtype Polymorphism
Overloading Polymorphism has allowed us to reuse the same name to mean different things, but we still have to write all of those things. Soon we'd have more

invertPair

functions than stars in the sky, and as poetic as that sounds I wouldn't really look forward to it.

What would be really good is if we could write a single

invertPair

function and it magically worked for every type we had. Well, it really should, because

invertPair

doesn't really care about which arguments you give it, it just rearranges those arguments in the pair!

So, let's think, how could we make it so

invertPair

accepts any type? Well, we could just get rid of types entirely, then

invertPair

would not be able to do anything besides accepting all of our values. But then we wouldn't be able to use the types to describe what works and what doesn't in our program anymore, so that isn't really a great option.

If only we could tell the

invertPair

function that it could accept any type that looks like something in particular… oh wait, maybe we can!

Subtyping allows us to have a hierarchy of types, where each type up the hierarchy is more "generic", and each type down the hierarchy is a more specific type. So, a [math]Number[/math] is a generic type, it has certain properties that are valid for all numbers, but an [math]Integer[/math] is a specific type, it concerns only [math]Numbers[/math] that are integral values. We say that [math]Integer[/math] is a subset of [math]Number[/math], or [math]Integer \subseteq Number[/math].
We'll say that the topmost type in the hierarchy is called

Root

. Every type in our system is a subtype of

Root

. So, it's only natural that our

invertPair

return a

RootPair

, since it'll work for all things.

invertPair(pair: P ⊆ RootPair): RootPair {
  return new RootPair(pair.right, pair.left);
}
This solves our immediate problem: we just have to write a single

invertPair

function. But now we have another problem. The result of

invertPair

is always a

RootPair

, no matter which type we pass into the function, and because of this we can't use

sub

anymore:

sub(invertPair(new IntPair(1, 2)))
// => Error: expected IntPair, got RootPair
Parametric polymorphism
We want to write

invertPair

just once, but we don't want to lose the types in the process. So, maybe there's another way of… hey, what if each type also carried the types it contains? That way we wouldn't even need a

RootPair

and an

IntPair

, there would be only

Pair

, and

Pair

would say what kind of pair it is.

First, let's define

Pair

this way:

<Left, Right>
class Pair(l: Left, r: Right) {
  property left: Left = l;
  property right: Right = r;
}
Okay, so when we say [math]\langle Left, Right \rangle class \, Pair[/math], we're saying that a

Pair

is a structure that contains a

Left

type and a

Right

type, whatever those types might be (

Pair

doesn't really care).

tangent: In logic, those would be written as [math]\forall Left, Right. Pair(l: Left, r: Right)[/math], so the angle brackets in this example really is just introducing a type variable in the expression.
We can then proceed to define both

invertPair

and

sub

in terms of this shiny new thing:

sub(pair: Pair<Int, Int>) {
  return pair.left - pair.right;
}

<Left, Right>
invertPair(pair: Pair<Left, Right>): Pair<Right, Left> {
  return new Pair(pair.right, pair.left);
}

sub(invertPair(new Pair(1, 3))) // => 1
Okay, great.

sub

now works fine. As a side effect, we can now also create pairs of non-uniform types, because we specify the types we're using in those funny brackets.

Structural Polymorphism
Suppose we now make a new object, lets call it

Triple

. It'll contain a

left

,

middle

, and right elements:

<Left, Middle, Right>
class Triple(l: Left, m: Middle, r: Right) {
  property left: Left = l;
  property middle: Middle = m;
  property right: Right = r;
}
It would be nice if our

sub

function could work for this too, after all, it only needs the thing to have

left

and

right

properties, and

Triple

fits that bill pretty nicely. Alas

sub

says it'll only work on

Pairs

, and

Triples

aren't

Pairs

. We could have made a

Triple

a subtype of a

Pair

, but our developer did not know about

Pairs

at the time they went about writing

Triple

, so that's not possible.

Can we make

Triple

work with sub even though they are both unaware of each other? Well, what if sub said what kind of properties it needs to work with, rather than which set in the hierarchy it works on? This is precisely what structural polymorphism is about:

<Left, Right>
interface IPair {
  property left: Left;
  property right: Right;
}

sub(pair: IPair<Int, Int>) {
  return pair.left - pair.right
}
Now our

sub

function is said to work on anything that has a

left

and a

right

property, not on a particular type.

sub

cares about structures, not names. We can readily use

sub

for the

Triple

value:

sub(new Pair(3, 1))       // => 2
sub(new Triple(3, 2, 1))  // => 2
Our

invertPair

function also only cares about the structure of our pairs, so we could do the same thing to this function:

<Left, Right>
invertPair(pair: IPair<Left, Right>): IPair<Left, Right> {
  return new Pair(pair.right, pair.left);
}
But oops, since we're getting something that "has some properties", rather than a concrete type, we don't really know which is the right type to construct in the return of the function! We're back in the same problem we had with subtyping.
Row Polymorphism
Fortunately, there's another kind of structural polymorphism that combines all of the power of Parametric Polymorphism with all of the niceties of Structural Polymorphism, we call it row polymorphism. Why row? Well, because someone decided to name the particular type parameter it uses the row type (or [math]\rho[/math]).
The idea of row polymorphism is that you match on a particular structure of a type, and capture the part that you didn't match. This way you can completely reconstruct the type in the result, and the value.
For this, we'll stop using classes, and start using "records". Records are very much like classes, but they're simpler and more free form; a record is simply a collection of pairs of names and values, so if we were to represent our previous pairs and triples:
pairA = { left: 1, right: 3 };
pairB = { left: "hello", right: "world" };
tripleA = { left: 1, middle: 2, right: 3 };
We'll use type annotations that resemble the usage notation, so the types for the items above would be:
pairA : { left: Int, right: Int };
pairB : { left: String, right: String };
tripleA : { left: Int, middle: Int, right: Int };
Writing

sub

by using structural typing is still very trivial, we just accept anything that has a

left

and

right

property:

<Left, Right>
sub(pair: { left: Left, right: Right, ... }): Int {
  return pair.left + pair.right
}
In this example, the ellipsis (

...

) denote that the

pair

value may have more properties than what we get, but we don't care about them.

invertPair

is written similarly, but now we do care about the additional properties. After all, we want to return triples when we get triples, and pairs when we get pairs. For this, we just need one simple addition to the notation above:

<Left, Right, Row>
invertPair(pair: { left: Left, right: Right, ...Row })
: { left: Left, right: Right, ...Row } {
  return { ...pair, right: pair.left, left: pair.right }
}
So, note that we now use

...Row

. This means that whatever we ignored before is now stored in the type variable

Row

. Because of how type systems work, the Row variable must have the same value everywhere, which means that the input type and the output type have the same properties.

If we instead wrote something like:

{ left: Left, ...Row }

for the output, then feeding it a triple, would give us back a value that has only

left

and

middle

properties!

The

...pair

in the body of the function works in a similar fashion. It means that the value will contain, additionally, the properties that pair does. Any property defined after that, with the same name, will overwrite an existing property, though, so we can use this to redefine

left

and

right

.

THIS IS A LOT, DO WE REALLY NEED ALL OF THIS?!
For typed languages, yes, we need each and every one of those (I didn't even cover higher-kind polymorphism in there because that alone would require a whole answer of this size just to explain :P). But for untyped languages? Nope, not really. You usually don't care about any of these in a language like Python, JavaScript, or Ruby, because they all emerge naturally from the use of higher-order functions, and more generally dynamic dispatching.
However, you also get no feedback from those languages when you give a pair to a function that only accepts triples, which is, in fact, neatly covered in this aptly named The Abject Failure of Weak Typing [3] article from REA.

[1] On typed, untyped, and “uni-typed” languages

[2] Page on lucacardelli.name

[3] The abject failure of weak typing

What is a concise definition of polymorphism?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s