Class 5.3: Generics and templates (parametric polymorphism)

Summary

Generic code

As we have seen, many of the more recent developments in programming languages have to do with programmer convenience: making it easier to write more maintainable code, and to avoid the need to copy the same chunks of code between different places in your program. Another development in this direction is the use of generic code.

This term has slightly different meanings depending on who you ask, but by generic code we mean code that can be used in an identical way to handle many different types. A simple example is a “least” function that takes two arguments and returns whichever one is smaller. What generic code helps us avoid is the need to write different versions of “least” for every different type of thing we might want to compare. Let’s see how we could do this in a few different languages.

In Python, it’s pretty darn easy: 

define least(a, b):
    if a <= b:
        return a
    else:
        return b

The reason it’s so simple in Python is that there are no declared types, and no static (compile-time) type checking. This basically makes all code generic code! The least function above can be used to find the smaller of two things, no matter what their types are, as long as the less-than operator works.

Things start to get more interesting when we think about a language with explicit, static types.

C++ templates

The C++ language was innovative in how it handled generic types, when it introduced templates in the 1990s. To write a templatized version of a class or function, you prefix the definition with a template declaration, like this:

template<typename T>
T least(T a, T b) {
  if (a <= b) return a;
  else return b;
}

This actually works (and is in fact a provided function by the C++ standard template library).

The fancy term for this is parametric polynomirphism — the type name T is treated like a parameter to the function definition itself.

Following along C++’s general design strategy of compiling in stages, and optimizing for run-time speed over everything else, the C++ compiler deals with templates like this (roughly):

  1. After parsing the code, first go through and find everywhere that a template function/class is defined or used.
  2. At the AST level, generate complete copies of the template definition for each type that template is actually used on.
  3. Compile the code as usual.

So for example, if our code uses least to compare ints sometimes, and to compare strings some other times, then at compile-time there will be two least functions created: one for ints, and one for strings. This is why it’s called “template” programming: all we are really writing is a template for the code that’s going to get generated by the compiler.

This process is called monomorphization because the compiler is basically taking your polymorphic generic code (the template function or class), and turning it into multiple copies that no longer use polymorphism.

The C++ template approach to allowing generics by code generation is an extremely powerful feature - in fact, whole books have been written on the subject of template programming in C++! This is a form of metaprogramming, because it’s telling the compiler to write new code for you, and then to compile that code that it just wrote! The downside is that there is a potential for “code bloat”, where the size of the executable could get really large if the C++ template mechanism has to generate many, many copies of different classes and functions for the various template type parameters. Fortunately, this won’t happen if you only use templates in the simple way shown above. But believe me, it’s possible!

Java generics

The “Java way” of getting generic code looks pretty similar to the C++ approach:

static <T extends Comparable<T>> T least(T a, T b) {
  if (a.compareTo(b) < 0) return a;
  else return b;
}

(Note that the Comparable interface is what specifies the compareTo function. This is necessary because Java doesn’t allow you to overload operators like <.)

This is an example of parametric polynmorphism in Java. You have certainly seen this already when you use library classes like ArrayList.

So Java uses angle brackets and type names just like C++ templates. Are they the same “under the hood”? Somewhat surprisingly, Java generics are completely different from C++ templates.

The way Java deals with the issue is much simpler: at compile-time, all the type checking is done according to the template parameters, filling in a name like T for whatever type the function is being called on. This is similar to C++, but where they differ is that Java does not make any copies of the generic method or class.

Instead, after doing the static type checking, the Java compiler does something called type erasure; basically, all of the template types like T revert back to Object, which you know is the super-class of every type in Java. So at run-time, there is only a single copy of any generic class or method, and it has Object types instead of T (or whatever else the generic type was called). This is only possible because Java actually has the class hierarchy where Object is the superclass of everything, unlike C++.

The advantages to Java’s approach are that it is simpler and “cleaner” to implement, it makes the compiler run faster, and (importantly) it can never make the size of the compiled code “bloat” up too much. But the fact that no code generation occurs also limits the capabilities. For example, Java generics do not allow one to create new instances of the generic type. The reason is that something like making a new instance requires that type to be known at run-time. But with Java generics, the type information is erased at run-time, making that kind of thing impossible!

Other languages

There are many other languages which have their own approaches to generic programming (which we won’t get into here):