Previously, I had discussed the tuple data type. The tuple is a general purpose container that can be comprised of any sequence of types. Both the types and the values can be accessed by index or traversing similar to a linked list.
The TypeList
is a category of types that are very similar to the tuple, except no data is stored within the type list. Whether the final implementation is constructed in the form of a linked list, an array, or even a tree, they are all typically referred to as Typelist
s. I believe that the Typelist
construct is credited to Andrei Alexandrescu. He first published an article in the C/C++ Users Journal, but a more thorough description can be found in his book, Modern C++ Design.
There is No Spoon
What happens when you instantiate a Typelist
?
Nothing.
Besides, that's not the point of creating a Typelist
container. The overall purpose is to collect, manage, and traverse type information programmatically. Originating with generic programming methods in C++, type lists are implemented with templates. Type lists are extremely simple, and yet can be used to solve a number of problems that would require enormous amounts of hand-written code to solve. I will use the Typelist
in my solution for Alchemy.
Let's start by defining a Typelist
:
template < typename T, typename U >
struct Typelist
{
typedef T head_t;
typedef U tail_t;
};
There are no data or functions defined in a Typelist
, only type definitions. We only need these two elements, because as we saw with the Tuple, more complex sets of types can be created by chaining Typelist
s together with the tail. Here is an example of more complex Typelist
definition:
typedef
Typelist< char ,
Typelist< short,
Typelist< int, long int > > > integral_t;
When I first saw this, I thought of two things:
- How can this be useful, there is no data
- The syntax is extremely verbose, I wouldn't want to use that
Remember in The Matrix when Neo goes to meet The Oracle, and he is waiting with the other "potentials"?! While he waits, he watches a young prodigy bending a spoon with his mind. He urges Neo to try, and offers some advice:
Spoon boy: Do not try and bend the spoon. That's impossible. Instead... only try to realize the truth.
Neo: What truth?
Spoon boy: There is no spoon.
Neo: There is no spoon?
Spoon boy: Then you'll see, that it is not the spoon that bends, it is only yourself.
Hmmm, maybe that's a bit too abstract, but, that's pretty much what it's like working with a Typelist
. There is no data. Now take your red pill and let's move on.
Simplify the Definition
Let's make the definition simpler to work with. Working with a single Typelist
definition of variable length seems much simpler to me than having to enter this repeated nesting of Typelist
structures. Something like this:
typedef Typelist< char, short, int, long int > integral_t;
typedef Typelist
<
char,
short,
int,
long int
> integral_t;
This could be usable, and it is easily achieved with template specialization or variadic templates. The solution based on template specialization is much more verbose, however, it is also more portable. I have also seen comments on compiler limits placed on the number of fields supported by variadic templates, but I do not have any personal experience with hitting limits myself. This is something I will probably explore in the future. For now, I will start the implementation with a template specialization solution.
Specialization
For this type of solution, we must select a maximum number of elements that we want or expect to be used. This is one of the drawbacks of specialization compared to the variadic approach. The forward declaration of the full Typelist
would look like this:
template < typename T0, typename T1, ..., typename Tn >
struct Typelist;
We cannot go much further until we resolve the next missing concept.
The Terminator
Similar to a linked-list, we will need some sort of indicator to mark the end of the Typelist
. This terminator will also be used in the specialized definitions of Typelist
to give us a consistent way to define the large number of definitions that will be created. With meta-programming, we do not have variables, only types and constants. Since a Typelist
is constructed entirely from types, we should use a type to define the terminator:
struct empty {};
With a defined terminator, here is what the outer definition for a 10-node Typelist
:
template < typename T0, typename T1 = empty,
typename T2 = empty, typename T3 = empty,
typename T4 = empty, typename T5 = empty,
typename T6 = empty, typename T7 = empty,
typename T8 = empty, typename T9 = empty >
struct Typelist
{
};
Here is the outer definition for a specialization with two items:
template < typename T0, typename T1 >
struct Typelist< T0, T1 >
{
};
Implementation
Believe it or not, we have already seen the implementation that goes inside of the template definitions shown above. The only exception is we will rename what we previously called a Typelist
to a Typenode
. Otherwise, the implementation becomes the typedef
that we created. By convention, we will name the typedef
, type
. For reference, constant values are called, value
, in template meta-programming. This consistency provides a very generic and compatible way for separate objects that were not designed together, to still inter-operate.
template < typename T, typename U >
struct Typenode
{
typedef T head_t;
typedef U tail_t;
};
template < typename T0, typename T1 = empty,
typename T2 = empty, typename T3 = empty,
typename T4 = empty, typename T5 = empty,
typename T6 = empty, typename T7 = empty,
typename T8 = empty, typename T9 = empty >
struct Typelist
{
typedef Typenode< T0,
Typenode< T1,
Typenode< T2,
Typenode< T3,
Typenode< T4,
Typenode< T5,
Typenode< T6,
Typenode< T7,
Typenode< T8,
Typenode< T9 > > > > > > > > > > type;
};
Here is the implementation for the two node specialization:
template < typename T0, typename T1 >
struct Typelist < T0, T1 >
{
typedef Typenode< T0,
Typenode< T1> > type;
};
Simple? Yes. Verbose? Yes. Is it worth it? I believe it will be. Besides, since this definition will be hidden away from users, I would feel comfortable defining some code-generating MACROs to take care of the verbose and repetitive internal definitions. However, I will demonstrate that another time.
Using a Typelist
We have simplified the interface required of the user to define a Typelist
, however, interacting with one at this point is still cumbersome. For example, consider the definition of the integral_t Typelist
defined above. If we wanted to create a variable using the type in the 3rd slot (index 2
, int
), this syntax would be required:
integral_t::type::tail_t::tail_t::head_t third_type = 0;
These are the stories that grown-up C programmers tell little C++ programmers growing up to prevent the use of some of the most effective aspects of the language. The next few entries will be focused on extracting data out of the Typelist
in a clean and simple way. However, let's tackle one solution right now.
How Many Elements?
Length
is a common piece of information that is desired from containers. This is no different for type-containers. How can we determine the number of elements in the integral_t
we have been using in this entry? We will write a meta-function. Unfortunately, I have not yet demonstrated many of the techniques in meta-function development. This means we will need to develop a Length
function that matches the signature for every specialization that was created for the Typelist
definition itself. Otherwise, we could create a meta-function that actively traverses the Typenode
s searching for a terminator. We will revisit and solve this problem with a more elegant solution.
The solution will be very simple, and very verbose, but still, very simple. Since we must define a Length
implementation for each Typelist
specialization that we created, we know in each specialization how many parameters types were defined. We can take advantage of that information to create our simple solution:
template < typename ContainerT >
struct Length;
template <>
struct Length < empty >
{
enum { value = 0 };
}
template < typename T0 >
struct Length < Typelist < T0 > >
{
enum { value = 1; }
}
template < typename T0, typename T1 >
struct Length < Typelist < T0, T1 > >
{
enum { value = 2; }
}
Again, with some preprocessor MACROS, generating all of the variations could be greatly simplified. For now, I would like to get enough infrastructure in place to determine how effective this entire approach will be at solving the goals of Alchemy. Here is a sample that demonstrates querying the number of elements in the integral_t
type.
size_t count = Length< integral_t >::value;
Summary
I have now introduced the Typelist
meta-programming construct. This is a simple type-only type declaration, which contains quite a bit of untapped potential for us. However, without a basic set of meta-programming constructs to build upon, our only option for implementing the Length
meta-function is to resort to one function implementation for the total number of elements that can be held in the Typelist
. This is not a very maintainable solution, but it won't be this way for long. I will be introducing a few simple constructs to make decisions based on type at compile-time, in order to create a more elegant and maintainable implementation of Length
. From there, I will continue forward and show how to query the type of parameter at a specified index, get the size of that type and many other meta-functions we can use to inspect our new data structure.