Template metaprogramming can initially seem baffling, but exploring its link to functional programming helps shed some light on things.
Introduction
Computing can be a surprisingly deep field at times. I find that the more I learn about it, the more I'm struck by quite how many similarities there are between different areas of the subject. I was browsing through Andrei Alexandrescu's fascinating book Modern C++ Design recently when I read about a connection which I thought was worth sharing.
As I suspect most of you will already be aware, C++ can be used for something called template metaprogramming, which makes use of C++'s template mechanism to compute things at compile time. If you take a look at a template metaprogram, however, you'll find that it looks nothing like a 'normal' program. In fact, anything but the simplest metaprogram can start to look quite intimidating to anyone who's unfamiliar with the idioms involved. This makes metaprogramming seem hard, and can put people off before they've even started.
Surprisingly, the key to template metaprogramming turns out to be functional programming. Normal programs are written in an imperative style: the programmer tells the computer to do things in a certain order, and it goes away and executes them. Functional programming, by contrast, involves expanding definitions of functions until the end result can be easily computed.
Programmers who have studied computer science formally at university are likely to have already come across some form of functional programming, perhaps in a language such as Haskell, but for many self-taught programmers the idioms of functional programming will be quite new. In this article, I hope to give a glimpse of how functional programming works, and the way it links directly to metaprogramming in C++.
For a more detailed look at functional programming, readers may wish to take a look at [ Thompson ] and [ Bird ]. Anyone who's interested in template metaprogramming in general may also wish to take a look at the Boost MPL library [ Boost ]. Finally, for a much deeper look at doing functional programming in C++, readers can take a look at [ McNamara ].
Compile-time lists
As a concrete example, I want to consider a simple list implementation. For those who are unfamiliar with them, Haskell lists are constructed recursively. A list is defined to be either the empty list, [] , or an element (of the appropriate type) prefixed, using the : operator, to an existing list. The example [23,9,84] = 23:[9,84] = 23:9:[84] = 23:9:84:[] shows how they work more clearly. Working only with lists of integers (Integers in Haskell) for clarity at the moment, we can define the following functions to take the head and tail of a list:
head :: [Integer] -> Integer
head (x:xs) = x
tail :: [Integer] -> [Integer]
tail (x:xs) = xs
The head function takes a list of integers and returns an integer (namely, the first element in the list). The tail function returns the list of integers remaining after the head is removed. So far, so mundane (at least if you're a regular functional programmer).
Now for the interesting bit. It turns out that you can do exactly the same thing in C++, using templates. (This may or may not make you think 'Aha!', depending on your temperament.) The idea (à la Alexandrescu) is to store the list as a type. We declare lists of integers as follows:
struct NullType;
template <int x, typename xs> struct IntList;
The NullType struct represents the empty list, [] ; the IntList template represents non-empty lists. Using this scheme, our list [23,9,84] from above would be represented as the type IntList<23, IntList<9, IntList<84, NullType> > > . A key point here is that neither of these structs will ever be instantiated (that's why they're just declared rather than needing to be defined): lists are represented as types here rather than objects.
Given the above declarations, then, we can implement our head and tail functions as shown in Listing 1.
template <typename T> struct Head;
template <int x, typename xs>
struct Head<IntList<x,xs> > {
enum { value = x };
};
template <typename T> struct Tail;
template <int x, typename xs>
struct Tail<IntList<x,xs> > {
typedef xs result;
};
|
| Listing 1 |
Already some important ideas are emerging here. For a start, if we ignore the fact that the C++ version of the code is far more verbose than its Haskell counterpart (largely because we're using C++ templates for a purpose for which they were never designed), the two programs are remarkably similar. We're using partial template specialization in C++ to do the job done by pattern-matching in Haskell. Integers are being defined using enum s and lists are defined using typedef s (remember once again that lists are represented as types).
Using these constructs is rather clumsy. A program outputting the head of the list [7,8] , for example, currently looks like:
#include <iostream>
int main() {
std::cout << Head<IntList<7,IntList<8,
NullType> > >::value << std::endl;
return 0;
}
To improve this sorry state of affairs, we'll use macros (this is one of those times when the benefits of using them outweigh the disadvantages). In a manner analogous to that used for 'typelists' in Modern C++ Design , we define the macros in Listing 2 to help with list creation.
#define NULLLIST NullType
#define INTLIST1(n1) IntList<n1, NULLLIST>
#define INTLIST2(n1,n2) IntList<n1, INTLIST1(n2)>
#define INTLIST3(n1,n2,n3) IntList<n1, INTLIST2(n2,n3)>
#define INTLIST4(n1,n2,n3,n4) IntList<n1, INTLIST3(n2,n3,n4)>
...
|
| Listing 2 |
We also define macros for head and tail:
#define HEAD(xs) Head<xs>::value
#define TAIL(xs) Tail<xs>::result
The improvement in the readability and brevity of the code above is striking:
std::cout << HEAD(INTLIST2(7,8)) << std::endl;
From now on, we will assume that when we define a new construct, we will also define an accompanying macro to make it easier to use.
Outputting a list
Before implementing some more interesting list algorithms, it's worth briefly mentioning how to output a list. It should come as no surprise that the form of our output template differs from the other code in this article: output is clearly done at runtime, whereas all our other list manipulations are done at compile-time. We can output lists using the code in Listing 3.
template <typename T> struct OutputList;
template <> struct OutputList<NullType> {
void operator()() {
std::cout << "Null" << std::endl;
}
};
template <int x, typename xs>
struct OutputList<IntList<x,xs> > {
void operator()() {
std::cout << x << ' ';
OutputList<xs>()();
}
};
|
| Listing 3 |
Sorting
Computing the head and tail of a list constructed in a head:tail form may seem a relatively trivial example. Our next step is to try implementing something a bit more interesting: sorting. Perhaps surprisingly, this isn't actually that difficult. The analogy between functional programming in Haskell and compile-time programming in C++ is extremely deep, to the extent that you can transform Haskell code to C++ template code almost mechanically. For this article, we'll consider two implementations of sorting, selection sort and insertion sort (it would be just as possible, and not a great deal harder, to implement something more efficient, like quicksort: I'll leave that as an exercise for the reader). I've confined my implementation to ordering elements using operator< , but it can be made more generic with very little additional effort.
A simple selection sort works by finding the minimum element in a list, moving it to the head of the list and recursing on the remainder. We're thus going to need the following: a way of finding the minimum element in a list, a way of removing the first matching element from a list and a sorting implementation to combine the two. Listing 4 shows how we'd do it in Haskell.
minElement :: [Int] -> Int
minElement [m] = m
minElement (m:ms) = if m < least then m else least
here least = minElement ms
remove :: Int -> [Int] -> [Int]
remove n (n:ms) = ms
remove n (m:ms) = m : (remove n ms)
ssort :: [Int] -> [Int]
ssort [] = []
ssort ms = minimum : ssort remainder
where minimum = minElement ms
remainder = remove minimum ms
|
| Listing 4 |
We can transform this to C++ as shown in Listing 5.
// Finding the smallest element of a list
template <typename T> struct MinElement;
template <int x>
struct MinElement<IntList<x,NullType> > {
enum { value = x };
};
template <int x, typename xs>
struct MinElement<IntList<x,xs> > {
enum { least = MinElement<xs>::value };
enum { value = x < least ? x : least };
};
// Removing the first element with a given value
// from a list
template <int n, typename T> struct Remove;
template <int n, typename xs> struct Remove<n,
IntList<n,xs> > {
typedef xs result;
};
template <int n, int x, typename xs>
struct Remove<n, IntList<x,xs> > {
typedef IntList<x,
typename Remove<n,xs>::result> result;
};
// Sorting the list using selection sort
template <typename T> struct SSort;
template <> struct SSort<NullType> {
typedef NullType result; };
template <int x, typename xs>
struct SSort<IntList<x,xs> > {
enum {
minimum = MinElement<IntList<x,xs> >::value };
typedef typename Remove<minimum,
IntList<x,xs> >::result remainder;
typedef IntList<minimum,
typename SSort<remainder>::result> result;
};
|
| Listing 5 |
The important things to note here are that each function in the Haskell code corresponds to a C++ template declaration, and each pattern-matched case in the Haskell code corresponds to a specialization of one of the C++ templates.
Implementing insertion sort is quite interesting. The essence of the algorithm is to insert the elements one at a time into an ordered list, preserving the sorted nature of the list as an invariant.
A simple Haskell implementation of this goes as follows:
insert :: Int -> [Int] -> [Int]
insert n [] = [n]
insert n (x:xs) = if n < x
then n:x:xs else x:(insert n xs)
isort :: [Int] -> [Int]
isort [] = []
isort (x:xs) = insert x (isort xs)
Translating the insert function to C++ is not entirely trivial. The problem is that we need to generate one of two different types depending on the value of a boolean condition, which is non-obvious. There are (at least) two solutions to this: we can either rewrite the Haskell function to avoid the situation, or we can write a special C++ template to select one of two typedef s based on a boolean condition.
Rewriting the Haskell code could be done as follows:
insert :: Int -> [Int] -> [Int]
insert n [] = [n]
insert n (x:xs) = smaller : (insert larger xs)
where (smaller,larger) = if n < x then (n,x)
else (x,n)
This solves the problem (generating one of two different values depending on the value of a boolean condition is easy), but at the cost of a less efficient function.
The template version (using the Select template borrowed directly from Andrei's book) does a better job:
template <bool b, typename T, typename U>
struct Select {
typedef T result;
};
template <typename T, typename U>
struct Select<false, T, U> {
typedef U result;
};
This allows us to straightforwardly transform the more efficient form of the Haskell code to C++ (Listing 6).
// Inserting a value into an ordered list
template <int n, typename T> struct Insert;
template <int n> struct Insert<n, NullType> {
typedef IntList<n, NullType> result;
};
template <int n, int x, typename xs>
struct Insert<n, IntList<x,xs> > {
typedef IntList<n, IntList<x,xs> > before;
typedef IntList<x,
typename Insert<n,xs>::result> after;
typedef typename Select<(n < x), before,
after>::result result;
};
// Sorting the list using insertion sort
template <typename T> struct ISort;
template <> struct ISort<NullType> {
typedef NullType result; };
template <int x, typename xs>
struct ISort<IntList<x, xs> > {
typedef typename Insert<x,
typename ISort<xs>::result>::result result;
};
|
| Listing 6 |
It turns out that in C++ this still isn't as efficient as it could be. The culprit is in the second specialization of Insert - by defining the before and after typedef s in the specialization itself, we force them both to be instantiated even though only one is actually needed. The solution is to introduce an extra level of indirection (Listing 7).
template <int n, int x, typename xs>
struct InsertBefore {
typedef IntList<n, IntList<x,xs> > result;
};
template <int n, int x, typename xs>
struct InsertAfter {
typedef IntList<x,
typename Insert<n,xs>::result> result;
};
template <int n, int x, typename xs>
struct Insert<n, IntList<x,xs> > {
typedef InsertBefore<n,x,xs> before;
typedef InsertAfter<n,x,xs> after;
typedef typename Select<(n < x), before,
after>::result::result result;
};
|
| Listing 7 |
This solves the problem, because now the chosen IntList template only gets instantiated if it is actually needed.
Maps and filters
One of the best things about writing in a functional language has traditionally been the ability to express complicated manipulations in a simple fashion. For example, to apply the same function f to every element of a list xs in Haskell is as simple as writing map f xs . Similarly, filtering the list for only those elements satisfying a boolean predicate p would simply be filter p xs . A definition of these functions in Haskell is straightforward enough:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = (f x) : map f xs
filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs) = if p x then x : remainder
else remainder
where remainder = filter p xs
Achieving the same thing in C++ initially seems simple, but is actually slightly subtle. The trouble is in how to define f and p . It turns out that what we need here are template template parameters. Both f and p are template types which yield a different result for each value of their template argument. For instance, a 'function' to multiply by two could be defined as:
template <int n> struct TimesTwo {
enum { value = n*2 };
};
and a predicate which only accepts even numbers could be defined as
template <int n> struct EvenPred {
enum { value = (n % 2 == 0) ? 1 : 0 };
};
The Map and Filter templates can then be defined as in Listing 8.
template <template <int> class f,
typename T> struct Map;
template <template <int> class f>
struct Map<f, NullType> {
typedef NullType result;
};
template <template <int> class f, int x,
typename xs>
struct Map<f, IntList<x, xs> > {
enum { first = f<x>::value };
typedef IntList<first,
typename Map<f,xs>::result> result;
};
template <template <int> class p, typename T>
struct Filter;
template <template <int> class p>
struct Filter<p, NullType> {
typedef NullType result;
};
template <template <int> class p, int x,
typename xs>
struct Filter<p, IntList<x,xs> > {
enum { b = p<x>::value };
typedef typename Filter<p,xs>::result remainder;
typedef typename Select<b, IntList<x,remainder>,
remainder>::result result;
};
|
| Listing 8 |
Note that we again make use of the Select template to choose between the two different result types in Filter .
Extensions
So far, we've only seen how to implement integer lists. There's a good reason for this - things like doubles, for example, can't be template parameters. All isn't entirely lost, however. It turns out that we can make lists of anything that can be represented by integers at compile-time! The code looks something like Listing 9.
template <int n> struct Int {
typedef const int valueType;
static valueType value = n;
};
template <int n, int d> struct Rational {
typedef const double valueType;
static valueType value;
};
template <int n, int d> const double
Rational<n,d>::value = ((double)n)/d;
template <typename T> struct Head;
template <typename x, typename xs>
struct Head<List<x,xs> > {
typedef x result;
};
#define HEAD(xs)Head<xs>::result::value
|
| Listing 9 |
The important change is in how we treat the head of the list - now we write typename x wherever we had int x before, and use the type's value field to get its actual value if we need it. The rest of the code can be transformed to work for generic lists in a very similar fashion. There's something to be said about how we handle ordering, but that's a topic for the next article!
Conclusion
In this article, we've seen how template metaprogramming is intrinsically related to functional programming in languages like Haskell, and implemented compile-time lists using C++ templates. Next time, I'll show one way of implementing ordering in generic lists, and consider how to implement compile-time binary search trees.
So what are the uses of writing code like this? One direct use of compile-time BSTs would be to implement a static table that is sorted at compile time. This can prove extremely helpful, particularly in embedded code. There are also indirect benefits derived from learning more about template metaprogramming in general. Writing code like this can be seen as a useful stepping stone towards understanding things like the typelists described in Andrei's book. The capabilities these provide are quite astounding and can provide us with real benefits to the brevity and structure of our code.
Till next time...
Acknowledgements
Thanks to the Overload review team for the various improvements they suggested for this article.
References
[ Bird ] Introduction to Functional Programming , Richard Bird and Philip Wadler, Prentice Hall
[ Boost ] http://www.boost.org/libs/mpl/doc/index.html
[ McNamara ] Functional Programming in C++ , Brian McNamara and Yannis Smaragdakis, ICFP '00
[ Thompson ] Haskell: The Craft of Functional Programming , Simon Thompson, Addison Wesley
