Your boss wants a function that calculates the maximum of two numbers. That's easy enough, but not much fun. As a developer, you feel a moral obligation to get the most out of this assignment. Why stop at calculating the maximum of numbers? What about strings, dates, and other ordered types?

Dynamic duck typing

Suppose we write our simple function in PHP first:

 

  function mymax($x,$y) {
    if($x > $y) return $x; return $y;
  }

 

It seems to return the largest of 2 numbers, but watch how we invoke it:

 

  echo mymax(10, 20);                // 2 integers
  echo mymax(5.0, 3.5);              // 2 reals
  echo mymax("aardvark", "zebra");   // 2 strings

 

When we pass numbers to the function, it returns the largest one in numeric order. When we pass strings, it returns the largest one in lexicographic order. So our innocent-looking function actually performs very different actions depending on the types of its inputs! This is known as polymorphism: behavior that depends on the types of the arguments.

With only a few lines of code, we cover all possible types at once. Well, almost all. Since PHP is dynamically typed, it does not impose any restrictions on the types of x and y. However, we do use the '>' operator in the implementation of our function; this will only work if the operator is defined for x and y. This is the only real restriction here: Any types x and y for which the operator '>' is defined, are accepted. This is known as dynamic duck typing: If it looks like a duck, and it quacks like a duck, then for all practical purposes it is a duck. If it has a '>' operator defined, it looks and acts like an ordered type, and so we can calculate a maximum.

Overloading

In a statically typed language like C++, we have to choose specific types for our parameters:

 

  int mymax(int x, int y) {
    if(x > y) return x; return y;
  }
  long mymax(long x, long y) {
    if(x > y) return x; return y;
  }
  ... 

 

C++ allows you to overload a set of functions. They can all have the same name, as long as the argument types are different so that any call can be resolved unambiguously. This is often called ad-hoc polymorphism: It looks as though a single 'mymax' function behaves differently depending on its argument types; but in reality we just have different functions that happen to have the same name. The polymorphism is a bit fake in this case, but it still works.

Now, you probably noticed that it becomes tedious to write all these separate versions. Every time a new ordered type comes along, we have to add a new function to the list of overloads. Is there an easier way? Of course. But we take a detour first.

Object-orientation

There are many definitions of object-oriented programming, but the most relevant feature for us here, is the use of interfaces, inheritance, and virtual functions.

Let's use an imaginary object-oriented language, to avoid syntactic clutter. It is a statically typed language, so that our overloading issue is still relevant. Typically, we would start like this:

 

  interface Ordered {
    abstract bool larger_than(Ordered other);
  }

  class Integer implements Ordered {
    int value;
    virtual bool larger_than(Ordered other) {
      if(other is an Integer too) // dynamic type check; details omitted.
        return this.value > other.value;
      else
        ERROR("Invalid type");
    }
  }

  Ordered mymax(Ordered x, Ordered y) {
    if(x.larger_than(y)) return x; return y;
  }

 

We no longer have a gazillion overloads, just a single implementation of 'mymax'. And it looks just as simple as before. Some languages even allow us the write 'larger_than' as an operator, to make the function almost identical to the original!

How did we turn those various overloads into a single function? We defined an interface. A single type Ordered serves as a "base class" or "interface" for all ordered types. Our function does not have to know the actual types of the arguments, only that they implement the Ordered interface. This pretty neat trick is the crux of object-orientation.

Interface inheritance is known as dynamic polymorphism. The call to larger_than gets resolved at runtime, hence "dynamic". It resolves to a more specific implementation in a derived class like Integer. This is how the runtime behaviour adapts itself to the actual argument types, hence "polymorphism".

Unfortunately, and in spite of all our progress, we have now reached one of the ugly corners of object-oriented programming: Dynamic type checking. The virtual larger_than function takes an object of type Ordered. The whole point of the Ordered interface is that we do not want to know the exact object type. But here, we have to know, because we can compare Integers only to other Integers. So we need to verify that the 'other' parameter is indeed an Integer. And we can verify this only at runtime, throwing a big fat exception if the types do not match.

Dynamic type checking can often be avoided, at the cost of making the code much more complicated. It would be better if we could find a different approach.

Static duck typing

Well then. How can we avoid overloading, and avoid runtime type checks at the same time? Enter generics:

 

  template<typename T>
  T mymax(T x, T y) {
    if(x > y) return x; return y;
  }

 

This looks like a function, but it's not. It's a template from which functions are generated on the fly. Whenever we invoke mymax, the template gets "instantiated" for the correct type. This means that we still end up with multiple overloads of 'mymax', but this time we do not have to write them by hand: The overloads are generated automatically by the compiler. We just got the best of both worlds: The full static type-safety of overloads, without all the work.

This technique is known as parametric polymorphism. This simply means that the overloads behave differently depending on the type T, which is a parameter to the template. You can think of 'mymax' as a generic function: It makes total abstraction of its argument types.

Now for a little surprise. We can instantiate this template with any type T, as long as it supports a '>' operator. Sounds familiar? If T quacks like an ordered type, we can treat it as an ordered type. We just re-invented duck typing, but this time it is static duck typing. All the type-checking happens at compile time!

Static interfaces

In 2017, C++ will be upgraded to a new major standard. One of the new feautures that I'm personally most excited about, is concepts. I think of them as "static interfaces": They specify constraints that must be statically met by a type.

The syntax for C++ concepts is not final yet, so I'll just invent my own simple syntax for a moment, in the imaginary language we were using earlier:

 

  concept Ordered {
    Ordered operator>(Ordered me, Ordered you);   
  };

  template<Ordered T>
  T mymax(T x, T y) {
    if(x > y) return x; return y;   
  }

  mymax(5, 4);   
  mymax("aardvark", "zebra");  

 

The only change to the template is that instead of any type T, it now accepts only types that satisfy Ordered. The compiler verifies that T implements a '>' operator, before allowing the template to be instantiated. You can think of Ordered as an "interface", and type T as a specific "implementation" of this interface. But this time, there is no inheritance anymore! Types like int, string and double are totally unrelated to each other; they do not have to inherit from each other or from some common base class. And yet, they can all safely be used as types for the 'mymax' function. All they have to do is implement the Ordered interface statically, as verified by the compiler.