Version 0.1
Author: prototype
Copyright (C) 2004 prototype
Permission is granted to copy and redistribute this article provided that its contents (including the title, author information, and this copyright claim) are kept intact in its original form.
This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
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)
