Abstract
Typelist and relevant concepts are introduced, together with a basic typelist implementation. An elegant, easy-to-use, and macro-free typelist generator is shown.


Introduction

Typelist, as its name suggests, refers to a (singly-) linked-list "data" structure, but the data or elements here are types. As the more familiar singly-linked list data structure, typelist consists of a number of nodes that are arranged in a logically-linear fashion; each node conprises two fields: one field, referred to as the "data field", stores the data (a type); the other field, referred to as the "pointer field", stores the information for finding the next node. The pointer field of the last node normally has a singular "value" indicating the end of the list. Typelist is as fundamental and important for C++ template metaprograming, which is becoming a crucial paradigm in moden C++ design and programming, as plain array for conventional programming. Examples of applications of typelist can be found in Andrei Alexandrescu's book: Modern C++ Design, and also in future installments of this C++ Metaprogramming series. Here I focus on a basic implementation of typelist and a solution to the interesting question: how to generate a typelist without C-type macros?

A basic implementation of typelist

Implementation of typelist can be extremely simple as long as one knows how to store a data and how to implement a pointer in C++ template metaprogramming. The solutions to the two problems turn out to be the same and trivial -- use typedef. Let us take a look at an example to see how it works.

typedef int  type;    // Stores `int' to `type'.
type i;               // `i' is of type `int'.

This simple little example illustrates that after the typedef, `type' is remembered by the compiler to stand for `int' and thereafter wherever `type' is used, it will work as if it was literally replaced by `int'. This effect is exactly what we want -- using a symbol to represent a data (the data here is a type). With this understood, storing a data in C++ template programming is straightforward; while the pointer used in typelist can be considered as an alias to the next node, therefore it can also be implemented using a typedef.

A basic implementation of typelist can be something like

template <typename T, typename SL>
struct typelist
{
   typedef T   type;
   typedef SL  sublist;
};

Obviously, with this implementation, we want to use `type' to store the data in this node and `sublist' to store the pointer to the next node. Let us see how we can use it construct a typelist. It would be something like

typedef typelist<int, typelist<bool, ?> >  tl2;

`tl2' here is a typelist with two nodes. In the first node, we store `int'; in the second node, `bool'. The `sublist' of the first node is `typelist<bool, ?>' -- the second node; but what about the `sublist' of the second node. I leave a `?' there, meaning to be defined.

Remember that as I mentioned above we need a "singular" value for the pointer of the last node. So the `?' should be replaced by a type that is not used except in marking the end of a typelist. This type is easy to obtain, for example:

class null_type;

so the above `tl2' can be defined as:

typedef typelist<int, typelist<bool, null_type> >  tl2;

This works. But it turns out the best value is actually `typelist<null_type, null_type>'. This value is much more convenient to use as will illustrated in future installments. Here I would like to rationalize it a little bit through an analogy to the singular value for a pointer in normal programs.

It is well known that 0 is used as the singular value for pointers in normal C++ programs. This value has two basic characteristics: first, it is a legal pointer value, which means it can be assigned to any pointer object; second, it semantically means “nowhere” in the memory. In analogy, what are needed for a singular value for the pointer in typelist are the following: first, it is a legal typelist value, which means that itself has to be a typelist; second, it semantically means there is no node after itself. Obviously, `typelist<null_type, null_type>' satisifies these two requirements much better than `null_type'.

(to be continued)