Table of content
In computer science or in general when someone is approaching to a programming language it is usual to hear about Polymorphism. In this post I’m going to explain :
a lot of different types of polymorphism
some real example of how these concepts are applied in reality, and how real programming language (such as C++, Java, Haskell, Scala, C# etc…) deal with polymorphism
So it is going to be a quick overview of computer science notions that I’ve studied during the Master course of Advanced Programming in the University of Pisa. This post is divided into two parts because it’s a huge subject, although I have synthesized a lot and it is not my intention to be neither exhaustive nor 100% accurate there is a lot to say.
But first of all: What is Polymorphism?
In a programming language we have Polymorphism when an expression can represent values of different types. So it is the important characteristic of being able to assign a different meaning or usage to something in different contexts.
Let’s imagine a function
fun that takes one argument, does some stuff and returns a value. The argument can be of different type. So there is polymorphism, but there is an important question that can be asked: this function
fun use the same algorithm for all different types of its argument or use a different algorithm depending on the types of the parameter? If we are in the first situation we have Universal Polymorphism, if we are in the second we have Ad Hoc Polymorphism. As said in this book, these are the first two big type of Polymorphism.
In this image there is a small summary of what it is said above.
Ad Hoc Polymorphism
It is right to mention a simple example of Ad Hoc Polymorphism : Overloading. In a lot of programming language the basic arithmetic operators (such as +, - , *, /, == etc…) are overloaded. This simple example is taken from this very interesting book about Haskell Programming.
let plus x y = x + y
plus 1 2 // = 3
plus 3,14 2,17 // = 5.3
The + function can take as the argument, for example, both Integer and Float, and the algorithm associated to the function call have to be different because Integers are represented in memory using the binary form ( and maybe using two’s complements) and Float are represented with significant and exponent. So the symbol + is overloaded, overburden of more meanings. More than one algorithm is associated with it, so this is a clear example of Ad Hoc polymorphism. How to deal with this type of polymorphism? Haskell uses Type Classes.
To explain Type classes let make this example, taken from this book. We want to overload the symbol == in order to use it for different type of data. Furthermore, we want to define precise algorithms to use for each type. For example, for integers we want that == is bitwise equality but for a particular class we want that for it == has a totally different meaning, for example, the equality of just one field. Type classes are a powerful and concise solution for this problem. They are composed of tree component:
Let’s quickly explain them using the piece of code below. Keeping in mind the example above, we want to define a class of types that are comparable, or that can be equivalent. So we can start with the type class declaration of Eq type class. Type class declaration (fig A) means: “any type a that belong to the class that I’m declaring has this operator with this type”. To use this class we have to declare an actual type, an instance of this type class, for example the type of integer value. Type class instance declaration (fig B) means: “I’m declaring a type class that belongs to the type class Eq so I’ve to bind actual function to the function in the type class definition.” The compiler will check the type. At last we can use the type class, using qualified types that concisely express the operation required to convert an overloaded function in a polymorphic one. The signature in fig C means: ” for all type that belongs the type class Eq the function member does…” then in the definition of the function member we can safely use the symbol == or /=.
For more information about Type Classes I suggest reading Concepts in Programming Languages of John C. Mitchell, linked above.
Universal Polymorphism has 3 main “shade” of polymorphism:
Implicit, automatic type conversion has been defined as a Coercion polymorphism, which is the opposite of Casting that is explicit. This is a degenerate case of polymorphism, not very interesting.
Here there is a schematic image of the type of polymorphism just introduced.
Instead, Inclusion polymorphism is very interesting. Now let’s focus on it. It is also called Sub Typing polymorphism or just Inheritance. Correctness is ensured by Barbara Liskov’s Substitution Principle. She won the Turing Award also for this concept, that is well explained in this book. If a programming language support this kind of polymorphism we can represent the concept of “IS A”. Let make a generic example. In this image there is a superclassb A that has two subclass B and C B “is a” A C “is a” A. The whole Object Oriented Paradigm is based on this concept. So for example in C++ I can write:
/*Creating a new object of type B*/
B b = new B( );
/*Assigning to a the address of b*/
A a = &b;
a.methodA(); //the code defined in A is executed
So the class B and C inherited method (and also member variable) from A.
Now, one important question: Are Ad Hoc and Universal Polymorphism really so separated? They don’t share anything? Is there something between them? Let’s continue with the last example and let’s start with an other question: what about if B or C want to redefine a method of A? They are a specialization of the class A, so it’s legit that they want to expose an other behavior, but if B would have a different implementation of the method methodA(), it will be executed the A code anyway. Why? Because we are using Static Binding, this means that which code to execute is selected statically, and as you can see at line 5 of the piece of code above, the static type of the variable a is A, but we want to consider the dynamic type of the variable a that is B.
How can we do that? How can we Override a method of the superclass? We need Dynamic Binding and in C++ we can introduce it with the “virtual” before the name of the function. How is this done? When the compiler encounters a class with virtual method, add a hidden member variable that points to an array of pointers to each virtual function (this array is called v-table), so a subclass inherits that pointer and can use it to access super method if it doesn’t redefine them.
Dynamic binding and in general true overloading is a very important feature of modern programming languages, for example them allow us to Program to Interface ( important consideration about the importance of programming to interface are at this link).
Instead Java has by default “virtual method”, so we always have dynamic binding (not really always, for example we don’t have dynamic binding where the method are private, final and static. Check this Stack-overflow question for more information) .
Overriding introduces ad hoc polymorphism in the universal polymorphism of inheritance because in inheritance we have two different classes (A and B) that share the same code (the inherit code). But if B want to override a method we have that the same method call can at runtime start two different execution, the one defined in A, and the one defined in B.
So in this part we discussed the difference between Ad Hoc Polymorphism and Universal Polymorphism, Overloading and how Haskell deals with it. Then Coercion, Inclusion and Overriding and about the latter we have seen how C++ uses it. Introducing the concepts of Dynamic and Static Binding.
What we are going to discuss in Part 2?
In the next part there will be a quick overview of Parametric Polymorphism, so C++ templates and Java Generics as an example of Explicit Parametric, and Type Inference as an example of Implicit Parametric. Then the relationship between Parametric Polymorphism and Inclusion Polymorphism that is the variance problem and how different language (Java, Scala and C#) solve this problem.
Thanks for reading. Stay tuned!