Type Lists

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 Typelists. 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 Typelists together with the tail. Here is an example of more complex Typelist definition:

// Typelist with an 8, 16, 32, and 64 bit integer defined.
typedef 
  Typelist< char , 
  Typelist< short, 
  Typelist< int, long int > > > integral_t;

When I first saw this, I thought of two things:

1. How can this be useful, there is no data
2. 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;
// Or format like a C struct definition:
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
{
  // TBD ...
};

Here is the outer definition for a specialization with two items:

template < typename T0, typename T1 >
struct Typelist< T0, T1 >
{
  // TBD ...
};

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;
};
// Typelist primary template definition.
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 3^rd 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 Typenodes 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.

// Calls the meta-function Length
// to get the number of items in integral_t.
size_t count = Length< integral_t >::value;

// count now equals 4

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.