Conceptually, generic programming is quite simple: instead of requiring specific types of function parameters and the type of its result, it allows the types to be left unspecified, so that when this generic function is used the types of specific parameter values are inserted at compile time and the machine code for this specific combination of types of parameters is generated (this process is known as instantiation of the function template). The second part of generic programming is allowing the compound types (i.e. arrays, structures, or classes) to be similarly parametrized, so a whole family of similar types differing only by types of its members could be created on as-needed basis (this also serves to parametrize methods (aka member functions) of templatized classes).
This is all very useful, but what makes generic programming interesting is that it does not rely on type theory (which is problematic as foundation for practical programming, as we discussed before), the fact explicitly acknowledged by the creator of STL, Alexander Stepanov: "Generic programming... gets its inspiration from Knuth and not from type theory." The basic mathematical theories which became the foundation for STL (and generic programming as we know it) are abstract algebra (particularly group theory) and number theory (I would highly recommend the book by A.Stepanov and D.Rose From Mathematics to Generic Programming for the in-depth discussion).
This said, generic programming as implemented in C++ is still terribly flawed (other languages such as Java, Ada, Eiffel, ML, D, and others offer severely limited variants or near clones of C++ support for generic programming). As it is it fails to fulfill its objective of hiding inner workings of abstract generic algorithms even in trivial cases, as is illustrated in the following example:
Let's say we have two integer values and want to have a generic function which divides one value by another. C++ code would be:
template <typename T>Sounds simple, right? However, divide(3, 2) returns 1, while divide(3., 2.) returns 1.5. It is easy to understand why is it so in this simple example, but the point is: you cannot even write a simple generic numeric division consisting of a single operation within which would produce consistent results for numerically equal inputs!
T divide(T x, T y)
{
return x / y;
}
Now, we could write something like
template <typename T>This kind of works for both integers and floating point numbers, but now it fails to be "generic" for anything else (for example if T is a representation of a polynomial function or a complex number).
double divide(T x, T y)
{
return double(x) / double(y);
}
You cannot just assume that "divide" divides, you have to look inside the implementation to understand its properties. The abstraction is no longer usefully abstract.
Now, since this kind of nonsense is annoying and actively dangerous and defeats the purpose of having generic programming capabilities in the first place, the practical language added a bunch of workarounds. For example, we could address the issue above by using template specialization:
template <typename T>
T divide(T x, T y)
{
return x / y;
}
template <>This seems to be better (though now we have two replicas of the "generic" algorithm) - though it still fails miserably on unsigned integers and "long long" integers. The problem with full or partial template specializations is that they need matching to specific types, and there could be many of them (this problem gets especially annoying when arguments have independent types... we end up with combinatorial explosion of specialized variants if we want to write a generic function which is reliably correct). We also cannot reliably support types we're going to create in the future.
double divide<long>(long x, long y)
{
return double(x) / double(y);
}
Finally, the modern variants of C++ (which grow ever more and more complicated) provide something called type traits which, combined with a happy accident of C++ template semantics called SFINAE allows to arrive to a horribly hacky but kind-of-correct implementation of "divide":
#include <type_traits>
template <typename T>
std::enable_if<!std::is_integral<T>::value, T>::type divide(T x, T y)
{
return x / y;
}
template <typename T>
std::enable_if<std::is_integral<T>::value, double>::type divide(T x, T y)
{
return double(x) / double(y);
}
This still subtly fails for long long arguments (owing to loss of precision in cast to double) and does not handle arguments of different types, but this is enough to demonstrate the frustrating nature of writing generic code in C++. And this is an example of only one of the "gotchas", examples like the one above are dime a dozen.
The interesting question is why this situation is so bad. To answer it we need to take a look at the mathematical foundation of the generic programming: the abstract algebra. The most fundamental concept in abstract algebra is homomorphism: mapping between two algebraic structures such that all formulae from one structure will be just as true in another structure if we replace all elements from the first structure with corresponding elements from the second structure (the map establishes the correspondence). The notion of homomorphism essentially is the same as the notion of mathematical abstraction (which is not the same as operation of abstraction in λ-calculus).
Thus, when we see an operation in algebra (such as operation of division in the example above) we expect that it will behave the same way in all algebraic structures homomorphic to the one we consider. Unfortunately for an aspiring C++ template programmer the elementary, baked-in, operation of the language doesn't work this way! Real numbers form a division ring while integers don't (rational numbers do), they are not homomorphic, and our best bet is to treat integers as a subring of real or rational numbers (but not an ideal of the division ring). I.e. we'd want integer division to produce rational (or real if rationals are not supported) result, and have the "integer division" to be a separate operation complementary to remainder operation, so that if d=⌊a/b⌋ and r=a%b then a=d*b+r (this would work for both integer and real a and b!).
The interesting question is why this situation is so bad. To answer it we need to take a look at the mathematical foundation of the generic programming: the abstract algebra. The most fundamental concept in abstract algebra is homomorphism: mapping between two algebraic structures such that all formulae from one structure will be just as true in another structure if we replace all elements from the first structure with corresponding elements from the second structure (the map establishes the correspondence). The notion of homomorphism essentially is the same as the notion of mathematical abstraction (which is not the same as operation of abstraction in λ-calculus).
Thus, when we see an operation in algebra (such as operation of division in the example above) we expect that it will behave the same way in all algebraic structures homomorphic to the one we consider. Unfortunately for an aspiring C++ template programmer the elementary, baked-in, operation of the language doesn't work this way! Real numbers form a division ring while integers don't (rational numbers do), they are not homomorphic, and our best bet is to treat integers as a subring of real or rational numbers (but not an ideal of the division ring). I.e. we'd want integer division to produce rational (or real if rationals are not supported) result, and have the "integer division" to be a separate operation complementary to remainder operation, so that if d=⌊a/b⌋ and r=a%b then a=d*b+r (this would work for both integer and real a and b!).
This is just one example of how underlying basic language (in this case C++ without templates) is not homomorphism-safe, which makes abstract algebraic features such as generic templates on top of it awkward and hard to construct.
This point also happens to illustrate another deficiency of C++: while type traits are supported (to a some extent) there is no way to discover operator or function traits, and thus no way to check for them in a generic code.
However, all these details are minor annoyances compared to the real elephant in the C++ shop: template instantiation is controlled solely by the local information. There is absolutely no way to create conditions for selecting specialized templates based on how the object of the given generic type is used in all its invocations: i.e. it is impossible to write a template which would implement a collection of objects differently depending on which access and modification operations are used! This impossibility is the result of the insistence on separate compilation - something which made a lot of sense back when computers had small RAM and slow CPU, so that compiler couldn't process a big program at once. This insistence becomes ridiculous in the age of CPUs with dozens of cores and terabytes of DRAM.
And, of course, there is no way to communicate information about side effects. The abstraction level ceiling is still firmly in place with C++-style generic programming, just moved a little bit higher.
C++ style generic programming is definitely a step in the right direction, but it falls far from the goal of achieving true generic programming capabilities, something Alexander Stepanov candidly acknowledged: [Generic programming's] goal is the incremental construction of systematic catalogs of useful, efficient and abstract algorithms and data structures. Such an undertaking is still a dream.
It seems likely that this dream is similar to the dream of free flight before invention of flight control by means of changing wing geometry - and before internal combustion engines became light and powerful enough. We have powerful engines now, let's see if we can add the correct set of controls to the process of compilation.
