About 10 years ago I bought *C++ Template Metaprogramming* by David Abrahams and Aleksey Gurtovoy. I read the book and even dabbled at template metaprogramming in the never-finished version 2.0 of KScope. My career, however, soon took me very far away from modern C++, and I have not had a chance to get fully immersed in the techniques described in the book.

A few weeks ago I decided to give the book another chance, and this time try to understand the concepts rather than the syntax of the MPL library. Things went south fairly quickly.

C++ template metaprogramming as implemented by MPL is essentially a new functional language built on top of C++ templates. The data manipulated by the language consists of types (int, long, double, structs and classes, etc.) and the manipulation is done by functions that take and return types. These functions (or *metafunctions* as they are referred to in the book), use template parameters as arguments and type definitions to return a result. For example, the following function takes a type T and returns a type that is a pointer to T:

template<T>
struct add_pointer
{
typedef T* type;
};

So far so good, as it is easy to draw parallels from the description of this language to other functional languages, such as Scheme. But this warm, fuzzy feeling of familiarity doesn’t last long.

One of the most important characteristics of functional languages is the ability to write *higher-order functions*, which are functions that take and/or return other functions. Chapter 3 in the book introduces higher-order functions using an example: the function **twice**, which takes a function and an argument, and returns the application of the function twice on that argument, i.e.:

*twice(f, x) = f(f(x))*

The problem is that with the book’s definition of a metafunction it is impossible to write one that takes another metafunction as an argument:

- Metafunctions are templates that take types as arguments
- A template is not a type

The rest of the chapter is devoted to techniques that turn metafunctions into types (metafunction classes, placeholder expressions) so that they can be passed around to and from other metafunctions.

It took me a while to understand what it is that bothers me with the treatment of this fundamental topic of functional languages by the book. I went back to my 20-year-old copy of *Structure and Interpretation of Computer Programs* by Abelson and Sussman (x2) and reread the introduction to higher-order functions. Let us consider how **twice** would have been implemented in Scheme. First, a Scheme function is really a lambda expression with a name (which, in my opinion, is better than to say that a lambda expression is an unnamed function):

(define (sum a b) (+ a b))

is really syntactic sugar (SIoCP’s favourite expression) for

(define sum (lambda (a b) (+ a b)))

Since lambda expressions in Scheme can be freely passed around as arguments to other lambda expressions, and be returned by other lambda expressions, we have a language that naturally implements higher-order functions. We can make **twice** a function that takes a function and returns another function which will apply the first one twice to its argument (note that we are returning a new function, not the application of a function to an argument):

(define (twice f) (lambda (x) (f (f x))))

And since **twice** is really just a name for a lambda expression, it can be passed around as a parameter to other functions or be returned by them.

How can we implement the same concept in C++?

First, let us change the way a metafunction is implemented from a template to a structure with a member template called **lambda**, which, in turn, defines a type called **result** (this is similar to how the book defines a metafunction class):

struct add_pointer
{
template<typename A>
struct lambda
{
typedef A* result;
};
};

Invoking the function consists of instantiating the **result** type, e.g.:

int a = 5;
add_pointer::lambda<int>::result p = &a;
std::cout << *p << std::endl;

With the new definition, we can implement **twice** as a function that takes a function and returns a function:

// The function's name.
struct twice
{
// The lambda expression that takes a function as an argument.
template<typename F>
struct lambda
{
// The result, which is itself a type.
struct result
{
// The result is a lambda expression that, when invoked,
// applies the function F twice to its argument.
template<typename A>
struct lambda
{
typedef typename F::template lambda<A>::result once;
typedef typename F::template lambda<once>::result result;
};
};
};
};

We can then name the new function that **twice** returns when invoked with **add_pointer** as its argument:

typedef twice::lambda<add_pointer>::result add_pointer_pointer;

and invoke the new function:

add_pointer_pointer::lambda<int>::result pp = &p;
std::cout << **pp << std::endl;

My approach is considerably more verbose than the one taken by MPL, and it is quite possible that it is severely limited in some way. Nevertheless, it seems to me that it is more in-line with traditional functional languages and as such easier to follow if you are familiar with functional programming.

**Desclaimer:** The above should in no way be read as criticism of either the book, its authors or the MPL. My extremely limited experience with template metaprogramming prevents me from passing judgement. The article is about my struggle with understanding the subject and the way I found to elucidate the important topic of higher-order functions using C++ templates.