Sunday, November 26, 2017

Revisiting Polymorphism: It is more than Inheritance and Subtyping

This post is part of the Type class knowledge pack series in which I explore the pattern for encoding Type classes in Scala. This post will be about polymorphism.

But why Polymorphism you might ask? isn't this series about the Type class pattern? Why do we have a single post dedicated to Polymorphism?

As it turned out, the type class pattern is really just one approach to writing polymorphic code.

And from experience, having a more in-depth appreciation for what Polymorphism is, will go a long way in understanding the why and how of the Type class pattern: which is why, before I go into the actual mechanism of encoding the Type class pattern in Scala, I think it will be of utmost benefit to first explore polymorphism.


Knowledge could be blinding


If you are reading this post and you've only programmed using Object Oriented Programming languages like Java or C#, chances are that you already have a mental model of what polymorphism is.

And If I would make a guess, I would say the mental model you have is more or less about inheritance and subtyping. In fact, you might have got to learn about polymorphism while learning about the concept of inheritance and subtyping. Right?

At least, this was the case for me. Influenced by my background with Java, I had formed a mental model that inescapably tied polymorphism together with inheritance and subtyping.

Which is to be expected. Polymorphism is usually introduced as part of teaching inheritance and subtyping in Java. Even the section on the official Java tutorial on Oracle website, Polymorphism is treated in a subsection under Inheritance. You can read it here: and as can be seen, it touches on Subtyping.

As it turned out, a mental model that equated polymorphism to just inheritance and subtyping was one of the stumbling blocks that initially prevented me from, fully appreciating the Type class pattern.

Why was it a stumbling block? Well, One of the problem statement Type classes help with is the ability to write polymorphic code. And when I hear polymorphic code, because of the mental model I had, the tool I reach out for was always about extending classes. So, because of this bias, when I find myself reading about the mechanism required to achieve polymorphic code using the typeclass pattern, I instinctively would be asking: why do this? Why go through all these hassles? what is the use of all these? Why not just apply inheritance and subtyping as I know it?

It was also a stumbling block because it was a flawed model. Flawed in the sense that it was an incomplete model. It was not until I started seeing polymorphism as more than inheritance that the pieces of type class pattern started to fall into place, and all the seemingly indirection required to encode it in Scala stopped appearing like an unnecessary ceremony.

If you were like me and now wondering how can polymorphism be more than Inheritance? Perhaps you have only developed in a language that offers inheritance as the only route to achieving polymorphic code, perhaps when you think about creating polymorphic code you see something similar to this:

// in Animal.java
public abstract class Animal {
    public abstract void makeSound();
}

// in Dog.java
public class Dog extends Animal {
    @Override
    public void makeSound() {
        System.out.println("Weoofff!");
    }
}

//In Cat.java
public class Cat extends Animal {
    @Override
    public void makeSound() {
        System.out.println("Meeowww");
    }
}

// in Main.java
public class Main {

    public static void doMakeSound(Animal animal) {
        animal.makeSound();
    }

    public static void main (String[] args) throws java.lang.Exception {
        Animal dog = new Dog();
        Animal cat = new Cat();
        doMakeSound(dog);
        doMakeSound(cat);
    }
}

Or perhaps instead of using subtyping and extending classes, you reach out for implementing interfaces...then you definitely affected by the same narrow, limited mental model I also had.

I would say, do hang on, continue reading this post with an open mind, hopefully by the end of this post, things we appear a little clearer.

So with the preambles out of the way, let's dive into Polymorphism.

What is polymorphism


In computer science, and without going into much of an academic definition, polymorphism is the ability for a computation or operation to be taken and applied to different kinds of things.

To make the above layman definition more tangible, I will give a couple of examples of the concepts of polymorphism as can be observed in the "real world"

Polymorphism using everyday examples

We have established, polymorphism is being able to take one single thing (a computation, operation) and have it be applied to not just one kind of things, but to various kind of things. I am going to explore 4 examples of polymorphism using mundane, real-world examples:

  1. Counting fruits in baskets
  2. Making a drink using a coffee machine
  3. The passport controls at airports
  4. Mammalia taxonomy

Example 1: Counting fruits in baskets
So the first example would be counting things. In this case, counting fruits in baskets.

Imagine you have 3 baskets and each basket is filled up with 3 different kinds of fruits. Let us say Oranges, Apples, and Kiwis. And since you wanted to know how many fruits are in each basket, you go ahead and count.


This act of counting can be seen as an example of Polymorphism. In this case, you were able to take an operation: ("counting") and apply it to different kind of things, (different kind of fruits) and come to a meaningful outcome regardless of the fruit you are counting. This is because irrespective of the fruit that is being counted, the process of counting remains the same.

You did not have to go invent a different mechanism for counting the different kinds of fruits. You did not have to invent a counting method for oranges and another one for the Kiwis.

In computer science, this kind of polymorphism is described as parametric polymorphism. In Java, it is commonly referred to as generics.

I will show code examples, later on in the post, but before then, let us move on to the second example of polymorphism. This time, using coffee machines.

Example 2: Making a drink using a coffee machine

Imagine you have a coffee machine that can be used to brew different flavors of coffee. In fact, we can further imagine that this coffee machine is actually a multi-beverage machine, so you can also prepare a hot chocolate drink with it.


So what do you do when you need an Espresso? You put in the right coffee pad, press the corresponding button and you get your Espresso. If you want Cappuccino, you do the exact same thing: put in the right coffee pad, press the right button and you have your drink ready to go. Want a Chocolate drink instead? Then you will have to operate the coffee machine in more or less the same way.

This is also an example of Polymorphism. Where you were able to take the same drink producing operation that the machine makes available to make different kinds of drinks.

What needed to change to determine the exact outcome is the inputs (the coffee/choco pads you put it and the button you press on the machine), but the essence: preparing a drink remains the same.

You did not have to make use of a different machine to prepare the different kinds of drinks. The same machine that made you an espresso can make you a cup of chocolate, what needs to vary is the interaction with the interface of the coffee machine.

In computer science, this kind of Polymorphism is referred to as ad-hoc polymorphism. More specifically, ad-hoc polymorphism implemented via function overloading.

Example 3. Passport Control at Airports
The third example that illustrates another form of polymorphism is what you see at border control checkpoints at airports.

For example, at an airport in the European Union, you mostly find two lines. One for EU citizens, and the other for non-EU citizens.


The procedures a non-EU traveler would pass through is different from the one an EU traveler would undergo when entering into any EU country.

Having an EU citizens passing through the border control, for instance, will follow more or less the same procedure, regardless of the particular EU country, as long as they can provide proof they are indeed a citizen of one of the countries that make up the European Union.

And how does the traveler provide the needed proof? This is done via the passport they carry.

And It does not matter who or how this passport is acquired (as long as it is via legal means obviously): it could be via birth, or via naturalization. The individual could also be of any gender, race, etc but this also does not affect the border control procedure. The only thing that matters is if the traveler possesses the right passport.

This, again is another example of Polymorphism, where the same operation (border control procedure) can be taken and applied regardless of the nature of the object (traveler) being applied on, as long as the object can prove to satisfy certain requirement that is not based on the type of object it is (in this case possessing of the right passport is the requirement that needs to be satisfied).

In computer science, this kind of polymorphism is also called Ad-hoc polymorphism. But instead of being implemented via function overloading (as we saw in the coffee machine example), it is implemented via Type classes.

Example 4: Mammalian taxonomy
The last example of polymorphism takes its inspiration from the world of biological sciences.

As taught in high school's elementary biology, the animal kingdom can be classified into a tree-like taxonomy.

Where each animal in a grouping shares similar characteristics. For example with mammals: All mammals are warm-blooded. They have hair or fur on their bodies, are vertebrates, with lungs to breathe air and mammalian glands with produces milk for their babies.

Let us take having lungs and breathing air as an operation of interest to illustrate polymorphism.

A bat which belongs to the Mammalian class possesses lungs and breathes air just as the way a human does. It can then be seen that the same operation (breathing) is possible with different objects (animals) as long as they are members of the same class of animals (mammals in this case). Even though the exact form of lungs possessed and the mechanism of breathing slightly varies, the same end result is still achieved.

It is also worth mentioning that both bats and humans belong to different further sub-groupings possible within the broader mammalian grouping. Bats Chiroptera, while humans are primates. Irrespective of this difference in the further categorization, the characteristics of being mammals is shared still.

In computer science, this kind of polymorphism is called sub-typing. Where objects can be grouped into classes/sub-classes and if an object belongs to any class, it will share similar attributes with other objects in that class.

if your background has only been in Java, C# or similar language, you will be familiar with this kind of polymorphism, and perhaps assumed this is the only kind of polymorphism there is. But as we have seen, it is just one type of polymorphism.

Talk is cheap, show me some code!

Ok, we have seen 4 mundane examples that demonstrate the types of polymorphism. Let’s see how they look like with some code snippets.

Summarizing from above, there are 3 kinds of polymorphism. Parametric polymorphism, Ad-hoc Polymorphism (which can either be via function overloading or via Type Classes) and Subtype polymorphism, let's quickly go over these types but using more formal definitions and some code.

Parametric Polymorphism
Parametric Polymorphism is the kind of polymorphism that is achieved with the mechanism that allows a function or a data type to be written such that it can handle values in a similar fashion without depending on the types of the values. Java programmer will be familiar with this concept, but might only know it as Generics and not a kind of polymorphism.

For example:

case class Apple(calories:Integer)
case class Kiwi(calories:Integer)
case class Orange(calories:Integer)

List(Apple(52)).size
List(Kiwi(62), Kiwi(60)).size
List(Orange(45), Orange(45), Orange(47)).size

Where it is possible to use the same List constructor to create a list of Integer and also have the size operation provide sane results for both cases. This is possible because the List class is defined generically and thus makes parametric polymorphism possible.

An excerpt from how List is defined will reveal this:

sealed abstract class List[+A]...

Where the List[+A] notation indicates it is generic. The + in the notation has to do with variance. Which you can ignore for now as it would be covered in the Review of  Type Annotation post, which is the 3rd post in this series.

Ad-hoc polymorphism
Here we will look at two ways of ad-hoc polymorphism can be achieved: function overloading and type-class

First, the definition of ad-hoc polymorphism via function overloading.


Wikipedia puts the definition as
"a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument(s) to which it is applied"
.

Java developers would know this as method overloading.

case class EspressoPad()
case class CappuccinoPad()
case class Milk()
case class ChocoPad()

object CoffeeMachine {
  def make(pad:EspressoPad) = println("Making an espresso...")
  def make(pad: CappuccinoPad) = println("Making a cuppccino...")
  def make(pad: ChocoPad, milk: Milk) = println("Making a chocoloate drink...")
}

CoffeeMachine.make(EspressoPad())
CoffeeMachine.make(CappuccinoPad())
CoffeeMachine.make(ChocoPad(), Milk())

Second, the definition of ad-hoc polymorphism via typeclass

Wikipedia puts the definition of Typeclass as:
"In computer science, a type class is a type system construct that supports ad hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and a type variable a, and means that a can only be instantiated to a type whose members support the overloaded operations associated with T."

In code, this would look like this:

trait Passport[A] {
  def validate(traveller:A): Boolean
}

case class Dutch()
case class German()

implicit val dutchPassport: Passport[Dutch] = new Passport[Dutch] {
    def validate(value: Dutch): Boolean = true
}

implicit val germanPassprt: Passport[German] = new Passport[German] {
  def validate(value: German): Boolean = true
}

object CustomCheck {
  def control[A](traveller: A)(implicit passport: Passport[A]): Boolean = passport.validate(traveller)
}

CustomCheck.control(Dutch())(dutchPassport)
CustomCheck.control(German())(germanPassprt)

Do not worry if you could not follow everything going on in the above snippet. The moving parts would be explored in the Encoding Type class in Scala post, which is the fourth post in this series on Typeclass.

What to take away from the snippet is the fact that the control method in the CustomCheck object is the part that demonstrates the typeclass ad-hoc polymorphism at play. As you can see, it is a generic method, but which ended being applied to a Dutch and German object and everything works fine as long as instances of the Passport is provided.

Subtype polymorphism
Paraphrasing Wikipedia, Subtype polymorphism is a form of type polymorphism in which a subtype is that is related to another type (the supertype) by some notion of substitutability, such that code written to operate on elements of the supertype can also operate on elements of the subtype.

abstract class Mammal {
  def breath
}

class Bat extends Mammal {
  override def breath: Unit = println("breathing with my bat lungs")
}

class Human extends Mammal {
  override def breath: Unit = println("breathing with my human lungs")
}

def respire(animal: Mammal) = {
  println(animal.breath)
}

respire(new Bat) // breathing with my bat lungs
respire(new Human) //breathing with my human lungs

Since both Bat and Human are a subtype of Mammal, the respire function is then polymorphic since it is written in terms of Mammal and can be used on both instances of Bat and Human. This is sub-type polymorphism.

Still finding hard to see past inheritance and subtyping?


If after reading about the various kinds of polymorphism and, like me, still struggled with accepting the fact that inheritance and subtyping do not equate to polymorphism but it is one of the various kinds of polymorphism. If you still feel that the other kinds of polymorphism are not the real deal and that subtype polymorphism via inheritance is the real polymorphism, then perhaps the analogy below will help with this struggle.

The Analogy:

Do imagine, that the only fruits you thought existed were apples. (for whatever reason that was) Apples were the only fruits you saw, the only fruits you ate, the only fruits you knew. You know of no other fruits than apples.

In such a worldview, Apples are fruits (which is correct), but you will also think that fruits equate to apples right?...and that is incorrect.

Polymorphism is like the fruit, Inheritance is like the apple. Just as the apple is a kind of fruit, inheritance is one of the means of achieving polymorphism.

Now Imagine going from a worldview where apples are the only fruits to one where you are introduced to oranges and kiwis...it is only normal to want to view the other kinds of fruits as not real fruits...right? Not hard to imagine I guess?

Having lived so many years thinking Apples where the only kind of fruits, it would definitely take some getting used to, to accept that this is not the case. And trying to justify Apples as the only real fruit would be well, a little bit stupid :)

Now you know the kind of response to give yourself if you ever find your brainwashed mind thinking that subtyping polymorphism via inheritance is the real polymorphism...and these other ones (ad hoc, parametric) are in some sort of way inferior to polymorphism.

Hopefully, this analogy helps with rethinking polymorphism.

Next step.

Now that we have revisited polymorphism and saw how the Type-class pattern is nothing but another form of polymorphism, albeit, ad-hoc polymorphism. Next, we move ahead to explore one of the two language feature in Scala, that come into play when encoding Type classes. Implicits and Implicits Resolutions



No comments: