“I’ve been doing some template metaprogramming lately,” he said nonchallantly.

Why is it funny? Because template metaprogramming is considered really hard. I mean, über-guru-level hard. I’m lucky to be friends with two such gurus, Andrei Alexandrescu who wrote the seminal “Modern C++ Programming,” and Eric Niebler, who implemented the Xpressive library for Boost; so I know the horrors.

But why is template metaprogramming so hard? Big part of it is that C++ templates are rather ill suited for metaprogramming, to put it mildly. They are fine for simple tasks like parameterized containers and some generic algorithms, but not for operations on types or lists of types. To make things worse, C++ doesn’t provide a lot in terms of reflection, so even such simple tasks like deciding whether a given type is a pointer are hard (see the example later). Granted, C++0x offers some improvements, like template parameter packs; but guru-level creds are still required.

So, I’ve been doing some template metaprogramming lately… in D. The D programming language doesn’t have the baggage of compatibility with previous botched attempts, so it makes many things considerably easier on programmers. But before I get to it, I’d like to talk a little about the connection between generic programming and functional programming, give a short intro to functional programming; and then show some examples in C++ and D that involve pattern matching and type lists.

It’s not your father’s language

The key to understanding metaprogramming is to realize that it’s done in a different language than the rest of your program. Both in C++ and D you use a form of functional language for that purpose. First of all, no mutation! If you pass a list of types to a template, it won’t be able to append another type to it. It will have to create a completely new list using the old list and the new type as raw materials.

Frankly, I don’t know why mutation should be disallowed at compile time (all template calculations are done at compile time). In fact, for templates that are used in D mixins, I proposed not to invent a new language but to use a subset of D that included mutation. It worked just fine and made mixins much easier to use (for an example, see my DrDobbs article).

Once you disallow mutation, you’re pretty much stuck with functional paradigm. For instance, you can’t have loops, which require a mutable loop counter or some other mutable state, so you have to use recursion.

You’d think functional programmers would love template metaprogramming; except that they flip over horrendous syntax of C++ templates. The one thing going for functional programming is that it’s easy to define and implement. You can describe typeless lambda calculus with just a few formulas in operational semantics.

One thing is important though: meta-language can’t be strongly typed, because a strongly typed language requires another language to implement generic algorithms on top of it. So to terminate the succession of meta-meta-meta… languages there’s a need for either a typeless, or at least dynamically-typed, top-level meta-language. My suspicion is that C++0x concepts failed so miserably because they dragged the metalanguage in the direction of strong typing. The nails in the coffin for C++ concepts were concept maps, the moral equivalent of implicit conversions in strongly-typed languages.

Templates are still not totally typeless. They distinguish between type arguments (introduced by typename or class in C++), template template arguments, and typed template arguments. Here’s an example that shows all three kinds:

template<class T, template<class X> class F, int n>

Functional Programming in a Nutshell

“Functions operating on functions”–that’s the gist of functional programming. The rest is syntactic sugar. Some of this sugar is very important. For instance, you want to have built-in integers and lists for data types, and pattern matching for dispatching.

-Functions

Here’s a very simple compile-time function in the C++ template language:

template<class T> 
struct IsPtr {
    static const bool apply = false;
}

If it doesn’t look much like a function to you, here it is in more normal ad-hoc notation:

IsPtr(T) {
    return false;
}

You can “execute” or “call” this meta-function by instantiating the template IsPtr with a type argument and accessing its member apply:

IsPtr<int>::apply;

There is nothing magical about “apply”, you can call it anything (“result” or “value” are other popular identifiers). This particular meta-function returns a Boolean, but any compile-time constant may be returned. What’s more important, any type or a template may be returned. But let’s not get ahead of ourselves.

-Pattern matching

You might be wondering what the use is for a function (I’ll be dropping the “meta-” prefix in what follows) that always returns false and is called IsPtr. Enter the next weapon in the arsenal of functional programmers: pattern matching. What we need here is to be able to match function arguments to different patterns and execute different code depending on the match. In particular, we’d like to return a different value, true, for T matching the pattern T*. In the C++ metalanguage this is done by partial template specialization. It’s enough to define another template of the same name that matches a more specialized pattern, T*:

template<class T>
struct IsPtr<T*> {
    static const bool apply = true;
}

When faced with the call, 

IsPtr<int*>::apply

the compiler will first look for specializations of the template IsPtr, starting with the most specialized one. In our case, the argument int* matches the pattern T* so the version returning true will be instantiated. Accessing the apply member of this instantiation will result in the Boolean value true, which is exactly what we wanted. Let me rewrite this example using less obfuscated syntax.

IsPtr(T*) {
    return true;
}
IsPtr(T) { // default case
    return false;
}

D template syntax is slightly less complex than that of C++. The above example will read:

template IsPtr(T) {
    static if (is (T dummy: U*, U))
        enum IsPtr = true;
    else
        enum IsPtr = false;
}
// Compile-time tests
static assert( IsPtr!(int*) );
static assert( !IsPtr!(int) );

As you can see, D offers compile-time if statements and more general pattern matching. The syntax of pattern matching is not as clear as it could be (what’s with the dummy?), but it’s more flexible. Compile-time constants are declared as enums.

There is one little trick (a hack?) that makes the syntax of “function call” a little cleaner. If, inside the template, you define a member of the same name as the template itself (I call it the “eponymous” member) than you don’t have to use the “apply” syntax. The “call” looks more like a call, except for the exclamation mark before the argument list (a D tradeoff for not using angle brackets). You’ll see later how the eponymous trick fails for more complex cases.

-Lists

The fundamental data structure in all functional languages is a list. Lists are very easy to operate upon using recursive algorithms and, as it turns out, they can be used to define arbitrarily complex data structures. No wonder C++0x felt obliged to introduce a compile-time type list as a primitive. It’s called a template parameter pack and the new syntax is:

template<class... T>Foo

You can instantiate such a template with zero arguments,

Foo<>

one argument,

Foo<int>

or more arguments,

Foo<int, char*, void*>

How do you iterate over a type list? Well, there is no iteration in the metalanguge so the best you can do is to use recursion. To do that, you have to be able to separate the head of the list from its tail. Then you perform the action on the head and call yourself recursively with the tail. The head/tail separation is done using pattern matching.

Let me demonstrate a simple example from the paper Variadic Templates by Garry Powell et al. It calculates the length of a pack using recursion. First, the basic case–length-zero list:

template<>
struct count <> {
    static const int value = 0;
}

That is the full specialization of a template, so it will be tried first. Here’s the general case:

template<typename Head, typename... Tail>
struct count<Head, Tail...> {
    static const int value = 1 + count<Tail...>::value;
}

Let’s see what it would look like in “normal” notation:

count() {
    return 0;
}
count(head, tail) {
    return 1 + count(tail);
}

And here’s the D version:

template count(T...) {
    static if (T.length == 0)
        enum count = 0;
    else
        enum count = 1 + count!(T[1..$]);
}
// tests
static assert( count!() == 0);
static assert( count!(int, char*, char[]) == 3);

T… denotes a type tuple, which supports array-like access. To get to the tail of the list, D uses array slicing, where T[1..$] denotes the slice of the array starting from index 1 up to the length of the array (denoted by the dollar sign). I’ll explain the important differences between C++ pack and D tuple (including pack expansion) in the next installment.

Conclusion

When looked upon from the functional perspective, template metaprogramming doesn’t look as intimidating as it it seems at first. Knowing this interpretation makes you wonder if there isn’t a better syntax or even a better paradigm for metaprogramming.

I’ll discuss more interesting parts of template metaprogramming in the next installment (this one is getting too big already). In particular, I’ll show examples of higher order meta-functions like Filter or Not and some interesting tricks with type lists.