Template Metaprogramming: Shifting Down a Gear

Template metaprogramming (MP) in C++ is a powerful technique but the syntax used can be obscure and difficult to understand. Here I propose an alternative approach in which a subset of the standard C++ language is used to write template metaprograms in a natural and familiar style.

This article assumes either an understanding of template metaprogramming or a pretty good ability to absorb new ideas. If you want to read up on the topic before reading this article: see [Veldhuizen1995] online for Todd Veldhuizen's historical paper and some useful links; and [Walker2001] for a recent Overload article on the subject.

There are a number of forms of MP but in this document we use only the general-purpose one presented in Andrei Alexandrescu's Modern C++ Design [Alexandrescu2001]; I will refer to this form of MP as AMP.

C++ template-metaprogramming uses standard features of the language to achieve computation in the type-domain, at compilation time.

This means that computation is done on types rather than on values. This may sound bizarre but in practice it can aid both in design abstraction and in time/space efficiency. Applications of MP include high-performance numerical computing [Blitz], matrix computation [GMCL], reflection [Attardi-], dimensional analysis [Barton-] and static configuration [Breymann-].

However, despite the power of the technique it isn't really used in the mainstream, and it's been 8 years since Erwin Unruh wrote the first MP program [Unruh1994].

This may be due in part to a lack of suitable C++ compilers in the past but another reason must be that MP is not a designed part of the language: it's really an accident resulting from the interaction of several language features. And - as so often happens when something is used for other than its intended purpose - MP code can be obscure and difficult to understand.

Let's start by implementing the factorial function as a template metaprogram.

Here is a standard implementation of the factorial function:

int factorial(int n) {
  if (n==1) {
    return 1;
  }
  else {
    return n*factorial(n-1);
  }
}
...
// example call
int x = factorial(5);

The two branches of the conditional statement return the two possible outcomes:

Here is an MP implementation of the factorial function^[1]:

// definition
template<int n>
struct factorial {
  enum {RET = n*factorial<n-1>::RET};
};
// partial specialization
template<>
struct factorial<1> {
  enum {RET = 1};
};
...
// example call
enum {x = factorial<5>::RET};

The definition and partial specialization of the factorial class template here give the two possible outcomes:

Compare the possible outcomes of the function with those of the class. Although the factorial class looks very different from the factorial function they have the same logical structure :-

The big difference between the two implementations is that the template computation happens at compile-time instead of when the program is run. Integer results of template computations are available as compile time constants, for example, in the expression factorial<5>::RET. This means that, for example, you could declare an array like this:

int buffer[factorial<5>::RET];

Types can be manipulated at compile time too, using typedef to name intermediate and final results in the same way that enum (or const int) is used to name integer values. There's an example which uses types later in the article.

If you want to know what happens - in general - when you run a program in a given language you need to know its execution model: a specification of what happens when a program written in the language is run on a conforming implementation.

My first acquaintance with the idea of an execution model for MP was a talk by Gabriel Dos Reis at ACCU 2001 [Reis2001] in which he showed how C++ template metaprograms could be modelled in the Scheme language. Scheme is a good model for MP because both languages' execution models are essentially those of functional programming languages.

Dos Reis talked about M-values (M stands for meta) being the MP equivalent to values in most programming languages. An M-value is a type or anything else that can be manipulated at compile time.

AMP M-values:

This information is summarized in Table 1.

template<typename T>
struct Setup { /* code for general case */ };
template<>
struct Setup<Null> { /* code for T==Null */ };
// OR
template<int N>
struct Factorial{ /* code for general case */ };
template<>
struct Factorial<0> { /* code for N==0 */ };

enum {N=Length<T::Tail>+1};

enum {value=N};

typedef Next<T>::value NextType;

typedef Next<T>::value value;

If you look back to the MP implementation of the factorial function you will see that it uses features 1, 2 and 3 with these pieces of code:

Using these language features sophisticated programs can be written (even a Lisp interpreter [Czarnecki-]) but it's not easy: the syntax is unhelpful and the programs can't be effectively debugged (you can't single-step through a compilation ...).

The C++ MP code in the factorial example and in Listings 1 and 2 can be difficult to follow but the abstract execution model is very simple. It has single assignment (variables are initialised on declaration and cannot be modified thereafter), conditional selection (choice, as in switch or if), but no iteration (no for, while or do loops - recursion is used instead).

Given the simplicity of the execution model we can consider writing programs in a source language with a more suitable syntax than C++ MP code. Programs written in this source language could be automatically translated to the correct C++ MP code.

But which language? A functional language such as Scheme or Haskell would have the right sort of execution model, but would not be taken up by many C++ programmers.

Instead I propose that we actually use a subset of C++ itself as the source language, which I've called typeshift. This will by definition be familiar to C++ programmers and there are other advantages, as we shall see.

Here's the factorial example in typeshift :-

int factorial(int n) {
  switch(n) {
    case 1:
      return 1;
    default:
      return n*factorial(n-1);
  }
}

It is, of course, the same code as the standard factorial function we gave earlier (which should be no surprise). This code is similar but not identical to the factorial function we gave earlier. It uses switch instead of if because typeshift will not initially support if.

The point of typeshift is this: you write a program in the typeshift language and then use a translator to convert it to C++ MP code. The translator would convert the above factorial program to this MP program (again, this code is identical to that of the earlier example):

// definition
template<int n>
struct factorial {
  enum {RET = n*factorial<n-1>::RET};
};
// partial specialization
template<>
struct factorial<1> {
  enum {RET = 1};
};

So now you can write a program in something resembling everyday C++ and have it converted to a template metaprogram.

Now this is just a tutorial example: a MP factorial program isn't very practical because it has to be recompiled every time you want to compute a different factorial. An MP program is only useful if you can make use of the results of the compile-time computation when the program is run. Later on we'll look at an admittedly abstract but genuinely useful example of template metaprogramming.

typeshift is a small subset of C++. We take only those features which are required to support the AMP execution model:

We do, of course, need to be able to represent types so that we can support template type-parameters. You might think that this is where it gets complicated, but in fact it doesn't - in "real" C++ types are very different from values but in typeshift they are quite similar: everything is just an M-value.

typeshift uses distinguished identifiers like type, fixed_type and template_type to declare variables (and subclasses) which to represent types and such variables behave as they do in MP.

This execution model of AMP as supported by typeshift is shown in Table 2 [next page] which you will want to compare with Table 1. Remember that this is only the first version of typeshift: over time its syntax and semantics will be extended to make it even easier to write template metaprograms.

I have not yet looked into mapping other forms of MP into typeshift but I hope that we will only need to add a few more features of C++ to the language for it to be able to model any current use of MP.

Here's an example of MP which uses types. Listings 1 and 2 are an implementation of the typelist data-structure from Alexandrescu [Alexandrescu2001] (not actually his implementation). They demonstrate how AMP can be used to implement a simple type-data- structure (a linked list of types) and a type-function which finds the length of such a list.

// typelists - standard approach. This
// particular approach even works on MSVC 6.0.

namespace typelists {
  // a list of types, each element has a head
  // and a tail - the head is one of the types
  // in the list, the tail is either another
  // list of types or Null
  template<typename HeadT, typename TailT>
  struct List {
    typedef HeadT Head;
    typedef TailT Tail;
  };

  // terminates type lists
  struct Null {};

  // - find the length of a type list -
  // ... the general case - the length is 1
  // more than the length of the tail
  template<typename T>
  struct Length {
    enum{RET=Length<typename T::Tail>::RET+1};
  };
  // ... the case of Null - the length is zero
  template<>
  struct Length<Null> {
    enum {RET = 0};
  };
};

// try out typelists - standard approach
#include <iostream>
#include "tm1.h"
using namespace typelists;

int main() {
  // declare a type list
  typedef List<int, List<double,
              List<char, Null> > > basictypes;
  // compute the length of the type list. the
  // whole right-hand side below is evaluated
  // at compile time (the result is 3)
  int n = Length<basictypes>::RET;
  std::cout << "n = " << n << std::endl;
  return 0;
}

Listings 3 and 4 [next page] implement the same program, but in typeshift.

// typelists - typeshift approach
#include <ts_runtime.h>

namespace typeshift {
  namespace meta {
    namespace _typelist {

// a list of types, each element has a head
// and a tail - the head is one of the types in
// the list, the tail is either another list of
// types or fixed_type::null
struct List {
  // constructor
  List(const type& HeadT, const type& TailT)
    : Head(HeadT), Tail(TailT) {}
  // members
  const type& Head;
  const type& Tail;
};

// - find the length of a type list -
int Length(const type& T) {
  switch (T) {
  // the case of fixed_type::null - the length
  // is zero
  case fixed_type::null:
    return 0;
  // the general case - the length is 1 more
  // than the length of the tail
  default:
    return Length(dynamic_cast<const
                            List&>(T).Tail)+1;
  }
}
}}};

// typelists - try out typeshift approach

#include <iostream>
#include "tm2.h"
using namespace typeshift::meta_::typelist;

int main() {
  typedef List<int, List<double,
           List<char, fixed_type::null> > >
           basictypes;
  int n = Length<basictypes>::RET;
        // the generated code still uses RET
  std::cout << "n = " << n << std::endl;
  return 0;
}

The .h file in Listing 3 is very different from the .h file in Listing 1 but if you read them while referring to Tables 1 and 2 you should be able to follow how the two sets of code correspond.

switch(T) {
  case Null: // code for T==Null
  default: // code for general case
};
// OR
switch(N) {
  case 0: // code for N==0
  default: // code for general case
}

int N=Length(T.Tail)+1;

return N;

type NextType=Next(T);

return NextType;

One important difference between the two sets of code is the namespace: it was typelist in the original C++ MP but is metatypeshift::meta::_typelist in the typeshift code. This is because we propose to signal the presence of typeshift code by enclosing it in a distinguished namespace whose name begins with typeshift::meta, or in a namespace derived from this. An enhanced C++ compiler or external tool can use this to pick out the typeshift code from the "normal" C++ code.

The .cpp file in Listing 4 is practically identical to the .cpp file in Listing 2 - only the namespace identifier and the name for the null list-terminator are different. This is because I don't propose changing the syntax of references to the names in the generated C++ MP code (at least, not yet) because that is going to be rather more difficult to handle than just transforming the definition.

In [Reis2001] Gabriel Dos Reis gives an example from Abelson & Sussman [Abelson-1985] of a coin-counting program, first of all in Scheme and then in C++ MP code. Given an amount of money (in pennies) the program returns the number of ways in which change can be given using British coins.

Dos Reis's C++ MP code along with a test rig is given in Listings 5 and 6.

I translated it into typeshift and this (again, with a test rig) is given in Listings 7 and 8.

// coins - C++ MP approach
// This code is reprinted by permission from
// Gabriel Dos Reis' ACCU 2001 talk [Reis2001]

template<int coin_kind>
struct coin_value { };
template<>
struct coin_value<1> { enum {value = 1}; };
template<>
struct coin_value<2> { enum {value = 5}; };
template<>
struct coin_value<3> { enum {value = 10}; };
template<>
struct coin_value<4> { enum {value = 25}; };
template<>
struct coin_value<5> { enum {value = 50}; };

template<int amount, int coin_kinds, bool stop>
struct count_change_helper {
  enum {remaining_coins = coin_kinds - 1};
  enum {remaining_amount = amount
        - coin_value<coin_kinds>::value};
  enum {value = 
         (count_change_helper<
            remaining_amount, coin_kinds,
            (remaining_amount <= 0 ||
            coin_kinds == 0)>::value
          +
          count_change_helper<
            amount, coin_kinds - 1,
            (amount <= 0 ||
            remaining_coins == 0)>::value)
  };
};

template<int amount, int coin_kind>
struct count_change_helper<amount,
                           coin_kind, true> {
  enum {value = (amount == 0) ? 1 : 0};
};

template<int amount>
struct count_change {
  enum {value = count_change_helper<amount, 5,
        (amount <= 0 || 5 == 0)>::value };
};

// coins - try C++ MP approach
#include "coinsct.h"
#include <iostream>
int main() {
const int amount = 23;
std::cout << "ways for " << amount << ": "
<< count_change<amount>::value << std::endl;
return 0;
};

template<int amount, int coin_kind>
struct count_change_helper<amount,
                           coin_kind, true> {
  enum {value = (amount == 0) ? 1 : 0};
};

template<int amount>
struct count_change {
  enum {value = count_change_helper<amount, 5,
        (amount <= 0 || 5 == 0)>::value };
};

// coins - typeshift approach
#include <ts_runtime.h>
namespace typeshift {
namespace meta {
namespace coins {
int coin_value(int coin_index) {
switch (coin_index) {
case 1: return 1;
case 2: return 5;
case 3: return 10;
case 4: return 25;
case 5: return 50;
}
}
int count_change_helper(int amount,
int coin_kinds, bool stop) {
switch (stop) {
case true:
return (amount==0)?1:0;
case false: {
int remaining_coins = coin_kinds - 1;
int remaining_amount =
amount - coin_value(coin_kinds);
int value = count_change_helper(
remaining_amount, coin_kinds,
remaining_amount <= 0 ||
coin_kinds == 0)
+
count_change_helper(amount,
coin_kinds - 1, amount <= 0 ||
remaining_coins == 0);
return value;
}
}
}
int count_change(int amount) {
int value = count_change_helper(amount, 5,
amount <= 0 || 5 == 0);
return value;
}
}}}

// coins - try typeshift approach
#include "coinsrt.h"
#include <iostream>
#include <sstream>
int main() {
const int amount = 23;
std::cout << "ways for " << amount << ": "
<< typeshift::meta::coins::count_change(amount)
<< std::endl;
return 0;
}
template<int amount, int coin_kind>
struct count_change_helper<amount,
                           coin_kind, true> {
  enum {value = (amount == 0) ? 1 : 0};
};

template<int amount>
struct count_change {
  enum {value = count_change_helper<amount, 5,
        (amount <= 0 || 5 == 0)>::value };
};

If you compare the two sets of listings I think you will agree that the typeshift version is clearer. But there's more - typeshift is a subset of C++ so we can actually compile and run a typeshift program without translating it to C++ MP code.

Both programs can be built^[2] with gcc 2.91.66. When compiling the C++ MP code pass -ftemplate-depth-99 to g++ to maximise the size of the problem that can be handled.

When run with the same input the programs give identical results so they are in some sense operationally equivalent. However, the C++ MP code computes the answer at compile-time but the typeshift code computes the answer at run-time.

This operational equivalence means that metaprograms can be written in typeshift and tested and debugged in the value-domain. Only then need the program be transformed to C++ MP code for execution at compilation time.

Even typeshift programs that use types can be compiled, run and debugged in this way using the typeshift 'type' class library.

There are two ways of implementing typeshift:

A C++ compiler essentially already has the mechanism to compile typeshift because syntactically and semantically it is a true subset of C++. Two changes would be needed:

There should be no impact on compilation outside the typeshift::meta_xxx namespace because from the point of view of code outside the namespace the names defined inside the namespace are from the transformed C++ code. It is not possible for code outside the namespace to "have any knowledge of" the original typeshift code.

A proof-of-concept typeshift pre-processor is currently under development, and should be available from http://www.typeshift.org when this article is published. It will be downloadable in the form of source code for a C++ program released under the GPL (GNU General Public License [GPL]).

Template metaprogramming has traditionally been viewed as an esoteric and obscure area of C++, but using typeshift metaprograms can now be written (and even debugged) in a familiar language. Hopefully this will lead to metaprogramming being used much more widely in C++.

Many thanks to Gabriel Dos Reis for his advice and encouragement, and also for his permission to quote the example program from [Reis2001].

Thanks too to Mark Radford for his invaluable comments and suggestions, which have certainly made the article easier to understand.