Adhoc Polymorphism, Implicts and Pimping in Scala

In this article, we will take a look at adhoc polymorphism, implicits and pimping in Scala.

Polymorphism

Polymorphism == Many forms, in software, polymorphism denotes providing a single interface to entities of different types (or) use generic/abstract symbols which can represent multiple different types. Before we look into adhoc polymorphism we will look at two other types of polymorphism

Subtype Polymorphism

As the name suggests, Subtype polymorphism is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutability. It states that, if a method can operate on a supertype it means that the same method will be able to operate on all the subtypes of the given supertype. A common example would be if we have a method called process which takes Shape parameter, we should be able to pass any class which implements Shape, for eg: Circle, Square, Rectangle etc., and be able to invoke the function say draw() exposed by Shape interface.

As we can see in the above picture, we are able to pass different implementations of Shape interface. The key takeaway here is the instance method which needs to be called is determined during run time as opposed to compile time. Hence this is also known as run time polymorphism. We can implement subtype polymorphism in many languages like C++, Java and C++ uses something called vtable to call the right instance method during runtime.

Parametric polymorphism

In the case of parametric polymorphism we use symbols which stand for any type. The best example that we can quote is Generics in Java. All the collection classes that we have in java.util package like List<E>, Set<E>, Map<K,V> etc., are parametrized so that it can hold any value. For example, if we can look at the put function of Map<K,V> we can see that it takes any value of type K and any value of type V.

V put(K key, V value)

Type safety is checked during compile time so that developers will get lots of confidence that the code will not blow up during runtime in production. Since we are generalizing over any type, the logic will be totally agnostic of the type, which means we will not be doing anything special for any type. This means most of the logic will write itself due to the abstract nature of using symbols. Parametric polymorphism naturally fits in implementing data structures like List, Set, Map etc., since their implementation is very generic and stays the same for all types. One way to think about parametric polymorphism in the context of Java Generics is to visualize a box which holds something but we don’t care what is actually present inside the box but provide generic operations to operate across all types.

Adhoc polymorphism

Adhoc polymorphism is an extremely powerful type of polymorphism. It allows us to define a common interface for an arbitrary set of individually specified types. They help us to write code which are formally and precisely defined and hence they are extremely general. In Haskell, we implement adhoc polymorphism using typeclasses. In Scala, we use trait which captures the typeclass interface and various implementations of that interface for different concrete types. The canonical example to understand Adhoc polymorphism is to look at a very generic structure from functional programming called Monoid.

Monoid

In abstract algebra, which is a branch in mathematics, defines monoid as a set equipped with a associated binary operation and an identity element. For example, Integer addition is a monoid with identity element as 0

1 + 0 = 1 // Left Identity

0 + 1 = 1 // Right Identity

1 + (2 + 3) == (1 + 2) + 3 //Associativity

Formally, a monoid needs to satisfy identity laws (left and right) and associativity laws.

-- Identity laws (Left and Right)
x <> mempty = x
mempty <> x = x

-- Associativity
(x <> y) <> z = x <> (y <> z)

Likewise Integer multiplication, string concatenation etc., form a monoid. The following code demonstrates the implementation of Monoid typeclass, integer addition instance and its corresponding usage in Scala,

trait Monoid[A] {
  def combine(x: A, y: A): A
  def empty: A
}

object Monoid {
    val intAddition = new Monoid[Int] {
        def combine(x: Int, y: Int): Int = x + y
        def empty: Int = 0
    }
}

object MonoidalOperation {
    def monoidalCombineOperation[A](a: A, b: A, monoid: Monoid[A]): A = monoid.combine(a, b)
    def monoidalEmptyElement[A](monoid: Monoid[A]): A = monoid.empty
}

To invoke monoidalCombineOperation and monoidalEmptyElement we can do the following:

MonoidalOperation.monoidalCombineOperation(2, 3, Monoid.intAddition)
MonoidalOperation.monoidalEmptyElement(Monoid.intAddition)

Typeclass and types

In the above implementation, we have a Monoid trait which describes 2 generic methods called combine and empty for type A which needs to follow the identity laws (left and right) and associativity laws which are formally defined. Any type instance which we write for Monoid should strictly obey the laws put forth for that given typeclass. The best part is, when we invoke monoidalCombineOperation and monoidalEmptyElement, compiler will make sure that all the types are aligned and matching properly, else it will throw a compilation error.

There are a wide variety of highly general purpose typeclasses which defines its corresponding laws and the type instances which are implemented for those typeclasses, strictly obeys these laws. Some of the examples are:

Implicits

If we look at the below code:

MonoidalOperation.monoidalCombineOperation(2, 3, Monoid.intAddition)
MonoidalOperation.monoidalEmptyElement(Monoid.intAddition)

for Int type, what if we want one default type instance which is Monoid.intAddition to be picked up by the compiler? If the compiler makes sure A and Monoid[A] are in alignment, how about the compiler automatically pass our default Monoid[A] if present for a given value A. This auto-magic way of compiler passing a given parameter is achieved via implicits through a mechanism called implicit resolution . We need to make the below changes to make this happen:

Now we can simply pass the Int values and Scala compiler will implicitly pass the Monoid[Int] instance intAddition to MonoidalOperation.monoidalCombineOperation and MonoidalOperation.monoidalEmptyElement since intAddition is the only default instance of Monoid[Int] available. If there were more than one instance, then we would get a compilation error.

MonoidalOperation.monoidalCombineOperation(2, 3)
MonoidalOperation.monoidalEmptyElement

Pimping

As we saw before, we achieve adhoc polymorphism by defining a common interface for an arbitrary set of individually specified types. How about we expose those interface methods directly on the type itself? The challenge is, if those types are coming from a util package (or) from a 3rd party library how do we go about enriching those types with the interface methods as we don’t own the source code. We can achieve it through a mechanism using Scala Pimping.

In the above Monoidal Integer Addition example, we would like to call combine operation using |+| syntax on the Int type itself, as shown below:

2 |+| 3

Using the power of implicits we can achieve it using the following snippet of code:

We can invoke the function |+| via pimping by calling it directly on the Int type using the below syntax:

import MonoidSyntax._

2 |+| 3

Summary

Adhoc polymorphism is a powerful type of polymorphism, using which we can write highly generic functions with defined laws which all the type instances needs to obey. From this blog post, we can clearly see how Adhoc polymorphism is implemented so elegantly in Scala using implicits and pimping and how all the 3 concepts are inter-twined to write software which are highly generic, extensible, verifiable and also at the same time statically type checked during compile time.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s