What is generic programming?

My definition of generic programming directly stems from the desire to avoid a combinatorial explosion of redundant implementations of algorithms:

© Hans-Joachim Roy - Fotolia.com

I chose the term sensible carefully. It implies that an implementation exhibits optimal performance for the supported input data. For instance, a binary search can be implemented much more efficiently on a sorted array than on a sorted list, as we can jump to any place in the array in constant time. So, although it is possible to come up with a single implementation for both cases, we would expect a sensible implementation to choose the more efficient option if available. In this particular case, we can encapsulate the difference into a small primitive to move to another place in the sequence (either jumping or step-by-step). In other words, this primitive gets specialized to the data representation capabilities. By extension, the implementation of binary search inherits this specialization.

The interplay between generalization and specialization is characteristic of generic programming. Without the capability to specialize an algorithmic component and to select it automatically based on the type of the data, we could not implement the binary search generically in a sensible way. Either, we had a single implementation, which is inefficient for arrays, or we would need two different implementations, defeating our goal. And all higher level code using the binary search algorithm would, without automatic selection of the right specialization, again face the problem of having to do this specialization explicitly itself. Specialization is thus almost always present under the hood when a generic implementation is used for a concrete input. In our sum example, the compiler will generate different code, depending on whether we use if for an array of doubles, floats, or integers. Thus we conclude:

The generation of specialized, optimal code from a unique source makes a good criterion to distinguish different approaches to generic programming. For instance, in Java, a generic source leads to a single byte code, regardless of the arguments used. Java generics thus completely loose any specific information about the actual argument type, due to type erasure. This makes it unusable with primitive type arguments and rather unattractive for performance-critical technical or scientific software. In contrast, as we have seen, C++ templates result in generating specific code for each argument type (which on the downside can lead to duplicate object code). Java Generics are, despite of superficial similarities, completeley different from C++ templates!