C++: Template Meta-Programming 2.0

• Download source - 15.4 KB

I was amazed after I had converted only the first few portions of the TypeList from the C++98 implementation to Modern C++. I have decided to convert my Alchemy API to use Modern C++ in order to truly learn the nuances by application of acquired knowledge. The code of these meta-programs is very elegant and completely readable. This really does feel like a new language, and an entirely new version of meta-programming.

The elegance enabled by the new constructs will allow me to present a complete TypeList implementation for Modern C++ in this entry.

Compare and Contrast

My primary goal is to compare the differences between template meta-programming with C++98 and Modern C++ (C++11 and beyond). While the concepts remain similar, the newer language has been expanded in a way that makes this a more natural way to compose functional programming logic with C++.

To be clear, I want to explicitly state that meta-programming has its places, and generally it will not be in core-application logic. Libraries and utilities that will be developed and tested, but are less likely to require maintenance work are good candidates for these types of solutions. Application programmers can take advantage of these complex machinations, yet the caller may never even realize what magic exists behind the curtain. A great example would the C++ Standard Library itself.

Frame of Reference

Andrei Alexandrescu made the concept of meta-programming accessible to the masses in his book Modern C++ Design, published in 2001. He demonstrates and develops many useful components for meta-programming that he created as part of his library, Loki.

This is the style of meta-programming that I first learned, and the type of structure that, Alchemy, is built around. I have altered the implementation and interfaces for my meta-constructs to suit my needs, compared to what is presented in the book. The next few sections demonstrate how the same tasks are accomplished in both versions of the language.

Then

The most important of these constructs is the TypeList. The TypeList is a work-horse construct that can be in a variety of unique ways, yet does not contain any internal data or run-time code. structs become the natural type to act as a functional container, which performs all of its compile-time, or static, operations on types, and stores values in static const values or enums.

To simplify expressions, I made liberal use of typedefs. This helped me avoid the repetition of verbose template expressions and at the same time give a label to the purpose of that template. Sometimes, there are no ways to simplify expressions other than turning to the pre-processor. I prefer to avoid the pre-processor at all costs in my application logic. However, I have grown accustomed to leaning on the pre-processor to generate code for me for repetitive definitions that appear in a class or at the global scope.

Here is an example of how Alchemy's TypeList is constructed. Internally, a TypeNode provides the declarations for the head and tail types.

C++

// A trait class to assist with tag-dispatching.
struct container_trait{ };
// Represents the end of a type list.
struct empty{};
 
template< typename H,
          typename T
        >
struct TypeNode
{
  typedef H head;
  typedef T tail;
};

Now the definition of the TypeList to show the organization of the structure:

C++

template< class T0, class T1, class T2, class T3,
          class T4, class T5, class T6, class T7,
          class T8, class T9, class T10,class T11,
        >
struct TypeList
  : container_trait
{  
  typedef
    TypeNode<T1,  TypeNode<T2,  TypeNode<T3,
    TypeNode<T4,  TypeNode<T5,  TypeNode<T6,  
    TypeNode<T7,  TypeNode<T8,  TypeNode<T9,  
    TypeNode<T10, TypeNode<T11, TypeNode<T12, MT>
    > > > > > > > > > > >                type;
    // Alchemy continues on to 32
};

Composing a structure should be much simpler than this nested definition. Therefore, I decided to wrap the inner declaration with a simpler outer definition. Unfortunately, there are only a few facilities available to customize template declarations. The best option in my particular situation was template specialization.

I wanted to provide a natural interaction with my TypeList object, and still allow support for a variable number of parameters. Thirty-two was my initial number of parameters that I would support. I can live with writing thirty-two specializations once. However, I had many operations that I would also implement, and each of those would require specialized implementations as well. So, I resorted to the preprocessor to generate the code for me.

Here is the definition of the MACRO, and how it was used. It generates the code in the block from above:

C++

#define tmp_ALCHEMY_TYPELIST_DEF(S) \
template<TMP_ARRAY_##S(typename T)> \
struct TypeList<TMP_ARRAY_##S(T)> \
  : container_trait \
{ \
typedef TMP_ARRAY_##S(TypeNode<T), empty TMP_REPEAT_##S(>)  type; \ 
}
 
// Define specializations of this array from 1 to 31 elements
tmp_ALCHEMY_TYPELIST_DEF(1);
tmp_ALCHEMY_TYPELIST_DEF(2);
tmp_ALCHEMY_TYPELIST_DEF(3);

Yes, I definitely left out many of the gory details for the definitions of the MACROs. But why would you want them? We're moving forward into the future; but you can still access them from Alchemy on GitHub.

The direct usage of the TypeList was then much more accessible to the user. Also, there was no need for them to use any MACROs to define a new TypeList:

C++

typedef TypeList
        <
          int,
          long,
          float,
          char
        > types;

Now

There are two primary additions to Modern C++ that make template programming in general a pleasure to use, and that is to not even mention meta-programming itself:

Similar to variadic function parameters, this feature allows a variable number of arguments to be used in a template definition.

This allows the using keyword to be used in situations similar to typedef. However, unlike typedef, using can be defined as a template. Therefore, it is compatible with partially-specialized templates.

1. Variadic templates
2. Template aliases

Here are the definitions that I required when I ported my code to Modern C++ (don't worry, I will explain the syntax afterwards):

C++

// Forward Declarations
struct empty { };
struct container_trait { };
 
template< typename... T >
struct type_node;
 
template< typename... NodesT >
struct type_list;

And an implementation for these types:

C++

// An empty terminating node.
template< typename... T >
struct type_node<>
{ 
    using head = empty;
    using tail = empty;
};

// Recursive parameter pack node
template< typename    H,
			 typename... T 
			 >
struct type_node<H, T...>
			  : type_node<T...>
{ 
    using head = H;
    using tail = type_node<T...>;
};

template< typename... NodesT >
struct type_list
: container_trait
{
    using nodes = type_node<NodesT...>
};

No, really! That's it! We get the exact same usage as the code from above, and I'm not even sure that I need to explain this last chunk of code.

I admit, I had a few false-starts trying to get a grasp on the parameter pack. No, not to reach this point, neither of the code samples above are good for anything except defining a list of types. My first challenge appeared when I tried to create a meta-function to give me the type of parameter at a specific index in the list.

Let me introduce the new constructs, then I will demonstrate some of the elegant solutions that barely scratch the surface of their capabilities.

The Parameter Pack...

The variable defined within a variadic template is called the parameter pack.

The parameter pack is essentially a list of types delimited by commas. To define one as a parameterized type in a template definition, use the ellipsis between the typename or class declaration and the name that you assign your type. There can be whitespace before and after the ellipsis if you desire...or not. However, the general style that you are likely to see places the ellipsis attached to the type-declaration and a space before the type-name.

C++

// Most common style
template<typename... T> struct common;
 
// These are all legal too.
template<typename ...T>  struct spaces_before;
template<typename ... T> struct spaces_both;
template<typename...T>   struct spaces_none;
 
// Template parameter packs are legal for
// use with template functions as well.
template<typename... T>
T function(T... params);

You may have noticed in my type_list implementation and the declaration of the template function that I placed the ellipsis after the declared name. This is how you invoke the parameter pack in your logic.

Invoke the Parameter Pack

What does it mean to invoke the parameter pack?

Nothing really. You're setting it where you want to apply it, and the compiler goes to work ripping apart the parameter pack and generating your code. However, the compiler does need a little bit of help. You will need two things if you are generating code from the parameter pack:

This is a definition that will be implicitly called by the compiler as many times as necessary until it reaches your terminating case. If you refer to the definition of the type_list, you will see that the parameter pack is applied in a context where another type is placed before it, separated with a common. This essentially peels one or more types away from the parameter pack at a time. In this sense, the template parameter pack is similar to the variadic MACRO usage.[/codespan]

A condition that will handle the case of an empty list, or at least terminate the recursion before the compiler attempts to go beyond the end of the parameter pack. It is not necessary for this to be an entirely different definition.

1. Recursive definition
2. Terminating condition

Size of a Parameter Pack

A convenient sizeof... operator has been provided to match the syntax of the parameter pack. This version of the operator is not related in anyway to the classic sizeof operator.

C++

template< typename... T >
struct length
  : std::integral_constant<std::size_t, sizeof...(T)>
{ };

The Parameter Pack Cannot Be A Variable

The parameter pack must be decomposed completely at compile-time. It cannot be the sole definition of a typedef or a using alias.

C++

template< typename... T >	
struct param_pack
			
{	
    using save_for_later = T...;
};

However, that does not mean that we are helpless. There is an idiom that exists with template programming that allows us to extract the type from a template parameter. I am not sure if it has a name.

Let me demonstrate it for you. This is the definition you are most likely to find on the Internet for a TypeList:

C++

template< typename... T > struct typelist { };

The previous code is completely legal because the parameter pack expansion is defined and terminated with this definition. With another template that is given the right specialization, we can extract the parameter pack from the original type definition.

To demonstrate this, let's create a length meta-function that will report the number of elements in the type_list that I defined above. We need to declare a default version of the length meta-function. This function does not necessarily need to be implemented.

C++

// Default declaration
// This does not require an implementation
template< typename... T > struct length;
 
// This specialization allows us to identify and access 
// the parameter pack defined within our type_list.
template< typename... T >
struct length <type_list<T...>>
  : std::integral_constant<std::size_t, sizeof...(T)>
{ };

We can use the parameter pack from the type_list because we specialized this template solely for the this type. The compiler does a best fit comparison when attempting to resolve types, and finds this version.

Template Aliases

Up until this point, we have had the typedef, which has served us well. However, it does have its shortcomings. I believe the most notable is that partial template specialization is not supported by a typedef. The template alias does provide this support.

C++

// I want to provide a simple type to create
// a map of strings to another type.
template< typename T >
using StringMap = std::map<std::string, T>;
 
// Can now be used as:
StringMap<int>     named_ints;

Here's a more complex example:

C++

// I want to map names to lists of things. template< typename T > using NamedListMap = std::map<std::string, std::list<T>; NamedListMap<unsigned int> lotto_picks_by_state;

Improves Readability of Templates

There is one other feature of template aliases that I did not fully appreciate until I started to use them. Most code examples do not get complex enough to allow you to fully appreciate the second feature. Let me demonstrate, then I will get into the gory details.

This is an example of an additional declaration that was added to C++14, but is possible in C++11. I am not sure if this technique wasn't discovered until after C++11, or they left it out to keep it from becoming C++12.

C++

// The C++ Standard Library contains useful
// meta-functions to manipulate types.
// This one converts type T into T*
template< class T >
struct add_pointer;
 
// This is used like this:
typedef typename std::add_pointer<void>::type   void_ptr;
// eww! ^^^^^^^^                         ^^^^

// Or directly...
typename std::add_pointer<void>::type   p_void = 0;
// I think I just threw up in my mouth...
// No wonder templates have a bad reputation.

These definitions appear in C++14, but you can use this technique in C++11.

C++

// Template alias for std::add_pointer
template< class T >
using add_pointer_t = typename std::add_pointer<void>::type;
 
// New usage:
typedef add_pointer_t<void>   void_ptr;

// And directly...
add_pointer_t<void>   p_void = nullptr;

Detailed Explanation

typedefs are a common way to reduce clutter in code. Primarily with templates because the use of template type declarations require you to qualify the type with typename if you are using a dependent-type.

What is a dependent-type?

That is a very good question. To help with the explanation, dependent type is a shortened version of the name template parameter dependent type. I'm surprised the C++ community hasn't just adopted TPDT, but I digress. A dependent type is a sub-type declared within a template class or struct.

typename is required when referencing sub-items in a template. I say sub-items because other things can be defined within a struct, that are accessed in the same manner as a dependent type, like a static variable. typename is a clue to the compiler that you want it to be interpreted as a type.

The capabilities of the template alias allow us to clearly specify beforehand that we mean a type. Therefore both the typename qualifier and sub-type required to access the dependent name are managed by the alias. This greatly simplifies code when there are many template types to deal with. Template meta-programming is a prime example.

One Last Tip

In the fall of 2014, N4115 Parameter Pack Searching[^] was proposed with some additions to the utility library. This would add a common form of the idiom that I described above to gain access to a parameter pack. The name proposed for the type is packer.

I was trying to modify an existing parameter pack, and I just couldn't put the pieces together. So that is when I searched and found N4115 when I found N4144 Searching and Manipulation of Parameter Packs[^], by Bill Seymour and Stephan T. Lavavej. This is an amended version of the first document and it adds manipulation utilities. One in particular is add_to.

I already demonstrated the concepts of packer, however, in my code I refer to it as param_pack. Here is how add_to is implemented. Multiple specializations are declared to handle the possibility of adding a parameter pack to a parameter pack.

C++

template<class T, class U> struct add_to;
// Add to the front of the list
template<typename T, typename... ArgsU>
struct add_to<T, param_pack<ArgsU...>>
{
  using type = param_pack<T, ArgsU...>;
};
 
// Add to the back of the list
template<typename... ArgsT, typename U>
struct add_to<param_pack<ArgsT...>, U>
{
  using type = param_pack<ArgsT..., U>;
};
 
// Combine two lists
template<class... ArgsT, class... ArgsU>
struct add_to<param_pack<ArgsT...>, param_pack<ArgsU...>>
{
  using type = param_pack<ArgsU..., ArgsT...>;
};
 
// And the template alias
template<typename T, typename U>
using add_to_t = typename add_to<T,U>::type;

You will see a demonstration of the usage in the next section.

A Modern C++ TypeList

I searched the Internet, albeit briefly, and I did not find any Modern C++ implementations of a TypeList that did not expand beyond this definition:

C++

template< typename... T > struct typelist { };

I found the fundamentals to convert the code that I already have into modern form. I want to convert and get it integrated first. If there are better practices, I can adjust the implementation in a working test harness.

I have already shown the definition of the basic type_list structure that I use as well as a demonstration of the length and param_pack, and the implementation for add_to. In the code below, I have omitted the forward declarations and template aliases that I define in the type list header file.

I am going to blast through the different operations that I have built so I do not take up too much more of your time. If something is not clear, please drop a comment and I can further explain or even add more detail to the description.

I have posted a link to the single header file that contains all of these definitions at the bottom.

make_type_list

I wanted to be able to make a type_list from an existing set of internal type_nodes, and then later, a param_pack.

C++

template< typename... T>
struct make_type_list< type_node<T...>>
  : container_trait
{
   using type  = type_list<T...>;
};
 
template< typename... T>
struct make_type_list< param_pack<T...>>
  : container_trait
{
   using type  = type_list<T...>;
};
type_at

Query the type of element at a specified index in the type_list. This item required a helper template that I called type_of_node.

C++

template< typename... T>
struct make_type_list< type_node<T...>>
  : container_trait
{
   using type  = type_list<T...>;
};
 
template< typename... T>
struct make_type_list< param_pack<T...>>
  : container_trait
{
   using type  = type_list<T...>;
};
type_at

Query the type of element at a specified index in the type_list. This item required a helper template that I called type_of_node.

C++

template< std::size_t    IdxT,
          typename  NodesT
        >
struct type_of_node
{
  using type =
    typename type_of_node<IdxT-1, typename NodesT::tail>::type;
};
 

// Terminating specialization
template< typename  NodesT >
struct type_of_node<0, NodesT>
{
  using type = typename NodesT::head;
};

Now for the actual implementation of type_at.

C++

template< std::size_t IdxT,
          typename    T  
        >
struct type_at
{
  using nodes = typename T::nodes;
  using type  = typename type_of_node<IdxT, nodes>::type;
  using rest  = typename make_type_list<typename nodes::tail>::type;
};

I added the declaration of nodes to simplify the declaration for type. This wasn't strictly necessary. I added rest for convenience in other solutions. rest returns a type_list of the elements remaining after the specified index.

For example, if there were 10 elements in a type list and index 6 was specified. A type list with elements [7,8,9] would be returned.

Stop me if I go too fast for the rest of these.

front

C++

template< typename T >
struct front
{
  /// Type of the first element in the list.
  using type = type_at_t<0, T>;
  using rest = typename type_at<0, T>::rest;
};

back

C++

template< typename T >
struct back
{
  /// Type of the last element in the list.
  using type = type_at_t<length<T>::value-1, T>;
};

pop_front

C++

template< typename T >
struct pop_front
{
  using type = typename front<T>::rest;
};

push_front

C++

template< typename F, typename L >
struct push_front
{
private:
   using params = typename to_param_pack<typename L::nodes>::type;
   using sum    = typename add_to<F, params>::type;

public:
   using type   = typename make_type_list<sum>::type;
};

push_back

C++

template<typename L, typename B>
struct push_back
{
private:
   using params = typename to_param_pack<typename L::nodes>::type;
   using sum    = typename add_to<params, B>::type;

public:
   using type   = typename make_type_list<sum>::type;
};

Summary

Again, I am pleased at how much simpler my code has become with these new additions. It's still C++. It's like C++ with the Hemi. Statements can be expressed more tersely, which actually increases the readability of the code as opposed to the lose meaning. Repetitive typing and redundant code can also be reduced.

If you frequently program with templates, or are even a big fan of the C++ Standard Library, you owe it to yourself to become familiar with these two features.

As promised, here is a link to the full type list implementation:

• Download type_list.h - 15.4 KB

Original post written by Paul M. Watt Code of the Damned.