December 2002/STL & Generic Programming

C/C++ Contributing Editors

STL & Generic Programming: Typelists

Thomas Becker

Variable-length template argument lists are a cinch with this fundamental metaprogramming technique.

Introduction

A friend of mine recently sent me an email in which he told me about an upcoming film festival that is devoted entirely to local filmmakers. He expressed his excitement by saying, “I love filmmakers. Without them, films would only be made by accident.” I thought that was funny. If I as a software engineer were to say, “I love creators of programming languages. Without them, programming languages would only be created by accident,” then that would not really be funny. The programming language that I learned most recently and am really excited about was created entirely by accident. I am of course talking about C++ template metaprogramming, or MetaC++, as I have christened it for easier reference in this column. In my last two columns, I showed you how certain C++ template constructs can be used to write functions that are executed at compile time and whose output is injected in the source code that is then compiled into the actual machine code. These MetaC++ functions typically operate on types and ints (more precisely, on anything that can be passed as a template argument). They receive their arguments via template parameters, and they return their values via typedefs and enums. The basic language constructs in MetaC++ are if branching and looping.

If you did not read my last two columns or have forgotten all about them, and this sounds mysterious to you, please read on. You will shortly see some simple MetaC++ functions at work, and I’ll explain again briefly how it all works. This month’s column can in fact be viewed as a third installment in a sequence on C++ template metaprogramming.

I mentioned before that the presence of if branching and looping makes MetaC++ as full-fledged a programming language as can possibly be: MetaC++ is Turing-complete, as the theoretical computer scientist would say. Of course, no designer of programming languages would seriously ask you to program with nothing but if branching and looping, or with any other minimal set of constructs, for that matter. But there is no designer behind MetaC++, so we have no one to complain to. And yet, it turns out that there is one more language construct available in MetaC++, and a very powerful one to boot, namely, lists of types. In this column, I’ll show you what typelists are and how they can be used in conjunction with the MetaC++ techniques that we already know about.

Good introductions to typelists can be found in Chapter 3 of Andrei Alexandrescu’s book [1], in his online article [2], and in Section 10.10.5 of Czarnecki and Eisenecker’s book [3]. Andrei Alexandrescu’s book [1] again tops the list for interesting applications. Other places you can look for applications are [4], [5], and [6], among others.

As with most code that involves template metaprogramming, the examples in this column will compile only if partial template specialization is supported. In particular, Microsoft’s Visual C++ will not compile any of this. However, as I have mentioned in my recent columns, Microsoft has made a commitment to rectify this situation in the near future.

Typelists

You are certainly familiar with the way lists are typically implemented in languages such as C and C++ (or Pascal, Modula, etc., for that matter): in these languages, a list is usually a set of nodes that is chained together by next pointers. The last node of the list can be identified by the fact that its next pointer is a null pointer. The list can be traversed by following the next pointers until the last node is reached. Conceptually, typelists in MetaC++ are very much like that: they are collections of types, not necessarily all different, which can be traversed in a well-defined order until the last element of the list is reached. Technically, this list structure is realized very differently in MetaC++ than in C or C++. Typelists very much resemble lists in good old Lisp, which I suppose only a minority of you are familiar with. In Lisp, lists are implemented using a nested structure. The empty list is a special object, usually called nil. A non-empty list is a pair. The first entry in the pair is the first element of the list, and the second entry in the pair is another list consisting of the remaining list elements. Here’s an example: if we use the notation (x, y) for a pair, then the list of integers whose elements are 42, 43, 42, and 41 (in that order) looks like this:
(42, (43, (42, (41, nil))))
Make sure you understand that you are looking at a pair whose first entry is the first list element — the integer 42 in this case — and whose second entry is again a pair of the form (element, list).

The two entries of a non-empty, Lisp-style list are often called head and tail, first and rest, or, in most Lisp dialects, car and cdr (and you thought C++ nomenclature was unintuitive). Traversing such a list is a recursive affair: look at the head, and then traverse the tail. Stop when you encounter nil.

This being said, we’re ready to look at typelists in MetaC++. The empty typelist is a specially named class that has no members and serves no other purpose than to be the empty typelist:
class Nil {};
To get non-empty typelists, we need the following class template:
template<typename H, typename T>
class TypeList
{
public:
  typedef H Head;
  typedef T Tail;
};
We can of course instantiate TypeList with any old value for the template parameters H and T, but the intended use is for T to be either Nil or another instance of TypeList. And that leads us to the formal definition of a typelist in MetaC++:

Nil is the empty typelist.

A non-empty typelist is an instantiation of the class template TypeList, where the second template argument is again a typelist, possibly the empty one.

That way, we get the same nested structure as in a Lisp-style list. Here are three examples:
TypeList<int, Nil>
TypeList<char*, TypeList<int, Nil> >
TypeList<int, TypeList<char*, TypeList<int, Nil> > >
If you compare these to the Lisp-style lists that we discussed earlier, in a purely formal way, then you see that you can view each of these as a list of types. The third one, for example, can be viewed as a list containing the types int, char*, and int.

Notice that so far, we’re just playing. The three things above are instantiations of a class template. Therefore, we could declare objects of any one of these types, as in:
TypeList<int, TypeList<char*, TypeList<int, Nil> > >
  someSillyObject;
But that hardly makes any sense: neither the class Nil nor the class template TypeList have any member functions or member variables, and therefore, an object such as someSillyObject above is just dumb and empty. What else could we possibly do with a class template instantiation? Let’s try using it in a typedef:
typedef
  TypeList<int, TypeList<char*, TypeList<int, Nil> > >
    MyFirstTypeList;
Next, we could retrieve from MyFirstTypeList the three types that make up the typelist, using them, for example, to declare objects of the respective types:
MyFirstTypeList::Head thisIsAnInt;
MyFirstTypeList::Tail::Head thisIsACharStar;
MyFirstTypeList::Tail::Tail::Head thisIsAnotherInt;
What we have achieved by building a typelist from the three types int, char*, and int is this: we have taken three types and encoded them into one new type, in such a way that the three original types can be retrieved from the new type. Clearly, we can do this for any number of types. And all of this is happening at compile time. This is certainly rather intriguing. In fact, we’re almost at a point where I can demonstrate to you the enormous programming power of typelists. Bear with me for one more ingredient in the mix.

MetaC++ Functions That Operate on Typelists

It is clear that an implementation of the list concept can only be useful if it comes with a certain minimal set of functions that do things such as getting the length of the list, retrieving the nth element, concatenating two lists, and so on. It turns out that everything our hearts desire along those lines can be written in MetaC++ for typelists. You can find a comprehensive treatment of this subject in Section 10.10.5 of Czarnecki and Eisenecker’s book [3], or in Chapter 3 of Andrei Alexandrescu’s book [1]. As examples, I will show you the length function and the nth-element function.

For the length, we need a MetaC++ function that implements the following pseudocode:
int Length(typelist TL)
{
  if( TL == Nil )
    return 0;
  return Length(TL::Tail) + 1;
}
Here is how it’s done [8]:
template<typename TL>
class MetaLength
{
public:
  enum{
    Ret = MetaLength<typename TL::Tail>::Ret + 1
  };
};

template<>
class MetaLength<Nil>
{
public:
  enum{ Ret = 0 };
};
Notice that MetaLength is your typical MetaC++ function. The function is implemented as a class template. Its argument is a type, which must be a typelist in this special case. The argument is passed to the function as a template parameter. The function “returns” an integer by defining a public enum value named Ret, which can be retrieved at compile time. The if construct of the pseudocode is implemented using explicit template specialization. If you want to convince yourself that MetaC++ functions are executed entirely at compile time, put the lines:
std::cout
  << MetaLength<MyFirstTypeList>::Ret
  << std::flush;
in your main program, where MyFirstTypeList is the typedef given above for the three-element typelist. You will find that the machine code that your compiler generates from these lines is identical to the machine code generated from the line:
std::cout << 3 << std::flush;
The pseudocode for the nth-element function looks like this:
type NthType(typelist TL, int n)
{
  assert( n < Length(TL) );
  if( 0 == n )
    return TL::Head;
  return NthType(TL::Tail, n-1);
}
The MetaC++ code is:
template<typename TL, int n>
class MetaNthType
{
public:
  typedef MetaNthType<typename TL::Tail, n-1 >::Ret Ret;
};

template<typename TL>
class MetaNthType<TL, 0>
{
public:
  typedef typename TL::Head Ret;
};
This is an example of a MetaC++ function that takes two arguments, a type and an int. The function returns a type through the public typedef Ret. The if construct of the pseudocode is implemented via partial template specialization. Using the type MyFirstTemplateList defined earlier, the line:
MetaNthType<MyFirstTypeList, 1>::Ret aCharStar;
now declares a variable of type char*.

Typelists: Putting It All Together

What I have shown you so far is this: typelists provide us with a mechanism to encode any given ordered set of C++ types, basic or user-defined, not necessarily pair-wise different, into one new type, namely, a typelist. The typelist can be queried for its length, and the original types can be retrieved from the typelist by index. All this is happening at compile time using template metaprogramming. The significance of this for actual C++ programming lies in the fact that we can now encode several types into a typelist, pass that typelist to a class template as a single template argument, and then retrieve the elements of the typelist from the template argument. Here’s a silly example:
template<typename TL>
class SillyUseOfTypeLists
{
private:
  enum{ nTypeListLen =
    MetaLength<TL>::Ret
  };
  MetaNthType<TL, nTypeListLen-1>::Ret
    sillyDataMember;
};
This class template takes a non-empty typelist as its template argument and defines a member variable whose type is the last type on the list. Okay, that’s silly, but never mind. You’ll see a serious example in just a moment. But you can already see what we have achieved here: we have extended the C++ language so that it now supports variable-length template parameter lists! In ordinary C++, a class template must have a fixed number of template parameters. Since C++ template parameters can be given default values, you may be able to instantiate a class template by giving it fewer arguments than the fixed number of template parameters, but you can never give it more template arguments than that. Using typelists, we can write class templates that effectively take an arbitrary number of template parameters. To do this, we write the class template in such a way that it takes one template parameter, a typelist. We then ask the client who instantiates the class to please take the template argument list that she wishes to pass to us and encode it into a typelist. Inside our class template, we retrieve these intended template arguments using the MetaC++ functions MetaLength and MetaNthType.

A Dusting of Syntactic Sugar

There is just one little dash of syntactic sugar that I want to mention before moving on to a real example of using typelists. Let us look at our earlier example of a three-element typelist again:
typedef
  TypeList<int, TypeList<char*, TypeList<int, Nil> > >
    MyFirstTypeList;
As the number of types you put in a list increases, typing the nested construct of heads and tails becomes increasingly annoying. Even Lisp programmers, who are not known to be easily intimidated by nested parenthesized expressions, have recognized that. Lisp traditionally has a function called list, which takes an arbitrary number of arguments and returns a list whose elements are those arguments, in the order that they were passed to the function list. It would be nice to have the same thing in MetaC++. In other words, we would like to have a MetaC++ function that implements the following pseudocode:
typelist List(type T1,..., type Tn)
{
  // Zero arguments passed
  if( 0 == n )
    return Nil;
  
  return TypeList<T1, List(T2,..., Tn)>;
}
where T1,..., Tn indicates a variable-length parameter list. There is just one little problem with translating this pseudocode into valid MetaC++. It’s called the chicken-and-egg problem. The only way for us to implement variable-length parameter lists in MetaC++ is via typelists, and the sole purpose of the function List is to create typelists in the first place. Therefore, we’ll have to settle for something less than a full-fledged List function. I mentioned before that by using default values for template arguments, we can write class templates in C++ that allow the client to pass any number of arguments up to the maximum that is specified in the definition of the class template. Using this technique, we can write a List function in MetaC++ that works for up to n elements, where n is an arbitrary but fixed number. We can still use the pseudocode for List given above as guidance on how to write the MetaC++ code. For example, for lists of up to four elements:
template<
  typename T1=Nil,
  typename T2=Nil,
  typename T3=Nil,
  typename T4=Nil
  >
class MetaList
{
public:
  typedef typename
    TypeList<T1, typename MetaList
    <T2, T3, T4>::Ret> Ret;
};

// Kicks in for zero arguments passed or 
// any number of Nil’s passed.
template<>
class MetaList<Nil, Nil, Nil, Nil>
{
  public:
    typedef typename Nil Ret;
};
Our typelist MyFirstTypeList can now conveniently be generated as follows:
typedef MetaList<int, char*, 
  int>::Ret MyFirstTypeList;
A list with two elements can be generated just as easily:
typedef MetaList<int&, const char*>::Ret MySecondTypeList;
Notice that the limitation of MetaList to a fixed maximal number of arguments does not compromise our ability to use typelists of arbitrary length. First of all, any given version of MetaList can easily be extended to any larger number of arguments with full downward compatibility: it is easy to find the three places in the definition of MetaList above where you have to add a little something to increase the maximal number of arguments. Secondly, in a full-fledged MetaC++ environment, you’ll have the capability of concatenating any two typelists. Using that in conjunction with MetaList, you can build typelists of arbitrary length with relative ease. Finally, MetaList was only syntactic sugar to begin with. If all else fails, then you can always use the explicit nested form to generate your typelist.

A Simple Application of Typelists

If is often desirable to package objects of different, unrelated types into some sort of container. Think of the situation where you want to return a number of items from a function. Unfortunately, STL-style containers are homogeneous containers that hold objects of one and the same type. It is of course possible to work around that limitation using pointers and inheritance, but the extra effort, complexity, and overhead often make this an undesirable design choice. But what if you knew the number of elements that your container needs to hold and their types at compile time? This is almost like one of those interview questions where they test if you can still see the simplest things when surrounded by complex issues. A heterogeneous container whose size and element types are known at compile time is simply a struct whose member variables are the desired elements, possibly with get and set functions. Simple as this is, there is room for improvement here. Rather than having to define such a struct from scratch every time you need one, it would be nice to have a simple generic mechanism to generate the struct definition at compile time. All you’d have to do would be to specify the types of the elements that you want in your struct. This can actually be achieved in MetaC++ with typelists. The resulting objects are a little more complex than the plain structs that you would have written manually, but they behave in a very similar way.

Before I show you the basics of how all this can be done with MetaC++, let me point out that the whole idea has been implemented and brought to maturity by Jaakko Järvi. His tuple library is part of the Boost library [7], and he has explained his implementation in CUJ [4]. The objects that he works with are called tuples, because you access the elements in there by index and not by name, as you would with a plain old struct. Listing 1 shows you a primitive tuple implementation that uses typelists. The class template Tuple of Listing 1 has one template parameter TL, a typelist. The class has two data members. The type of the first one, m_elem, is the first type on the typelist TL. The type of the second one is another instance of Tuple, with the template parameter set to the tail of the typelist TL. To visualize this nested structure, suppose we have instantiated Tuple as follows:
typedef MetaList<int, char*, int>::Ret ATypeList;
Tuple<ATypeList> aTuple;
The object aTuple is much like a simple struct that has two ints and a char* as its members. Except aTuple has a nested structure: it contains an int member and another Tuple object, which in turn holds the char* and the second int, using the same nested structure. Think of a set of Russian dolls, where each doll contains a coin of some type and another doll.

The Get function deserves some attention. Let us first look at how it is used. The following lines of code get and set the value of the second one of the three elements of our tuple object aTuple:
char* p = aTuple.Get<1>();
char c = ’x’;
aTuple.Get<1>() = &c;
You can see that the index of the element that is to be accessed is passed to the Get function as a template argument. Accordingly, the function Tuple::Get in Listing 1 is a function template with an integer template parameter. Don’t look at the result type of this function for now. The function body does nothing but forward to a corresponding helper called Tuple::UglyGet. The forwarding call adds an argument, namely a tag object of type NthElem<m>, where m is the index of the element that we want to get or set. NthElem is an empty class template with a template parameter of type int. The only purpose of this class is to provide tags that have different types for different integer values. The helper Tuple::UglyGet is overloaded on the type of the tag argument. If m is 0, it gets the element of the this object. If m is greater than 0, it forwards the get request to the nested tuple object, with the index m decremented by 1.

Conceptually, Tuple::UglyGet is a helper that ought to be private. The reason why it is not is that in the nested structure of tuples, the inner tuple m_rest is of a completely different, unrelated type than its containing tuple. Therefore, the call:
m_rest.UglyGet(NthElem<m-1>())
inside Tuple::UglyGet is not a recursive call. It is a call to a member of an object of an unrelated type. If UglyGet were a private member of the Tuple class template, this would not compile. The only way to fix it would be to establish an appropriate friend relationship. This, however, is notoriously difficult to achieve in the presence of templates. Therefore, UglyGet is a public member of the Tuple class template. That’s not exactly pretty, but it is not a disaster either. UglyGet exposes no more and no less to the outside world than Get itself.

The other thing about the Get function that we need to look at is its result type. For someone who is not familiar with C++ template metaprogramming, the declaration:
template<int m>
typename boost::add_reference<
  typename MetaNthType<TL, m>::Ret
  >::type
Get();
must look quite intimidating. With a good understanding of MetaC++, figuring this out is a cinch. The function Get must return a reference to the mth tuple element. The type of this element is the mth type on the tuple’s typelist TL. Therefore, the Get function’s desired result type is obtained by first calling the MetaC++ function MetaNthType with the typelist TL and the integer m as its arguments. The return value of this call is then passed to a MetaC++ function that adds a reference in a way that does not cause a reference-to-reference situation. The appropriate choice for this function is Boost’s add_reference.

Let me stress again that the tuple class in Listing 1 is only meant as a very simple example for the use of typelists. Jaakko Järvi’s library implementation (see [4] and [7]) is much more mature. In particular, you won’t find any explicit use of typelists in his implementation. The reason for this is that the nested structure of tuples parallels the nested structure of lists. It is therefore possible to incorporate the typelist structure into the tuple class itself. Listing 2 shows the essence of such a tuple class.

References

[1] Andrei Alexandrescu. Modern C++ Design (Addison-Wesley, 2001).

[2] Andrei Alexandrescu. “Generic <Programming>: Typelists and Applications,” C/C++ Users Journal C++ Experts Forum, February 2002, <www.cuj.com/experts/2002/alexandr.htm>.

[3] Krzystof Czarnecki and Ulrich W. Eisenecker. Generative Programming, Methods, Tools, and Applications (Addision Wesley, 2000).

[4] Jaakko Järvi. “Tuple Types and Multiple Return Values,” C/C++ Users Journal, August 2001.

[5] Ulrich W. Eisenecker, Frank Blinn, and Krzystof Czarnecki. “A Solution to the Constructor Problem of Mixin-Based Programming in C++,” <www.oonumerics.org/tmpw00/>.

[6] Emily Winch. “Heterogeneous Lists of Named Objects,” <www.oonumerics.org/tmpw01/>.

[7] <www.boost.org/libs/tuple/doc/tuple_users_guide.html>

[8] If you have read my previous columns, you’ll notice that I have changed my notational convention for MetaC++ functions. I used to write them in all upper case letters, alluding to the dank and musty old world of preprocessor macros. I have decided that is ugly. Why not just prefix the names of MetaC++ functions with “Meta”?

Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, Lake Tahoe. He can be reached at thomas@styleadvisor.com.