Understanding C++ template metaprogramming

Question

In my quest to better understand templates and meta-programming in C++ I'm reading this article, but my understanding of the code snippets quickly diminishes, e.g.:

template<class A, template<class...> class B> struct mp_rename_impl;

template<template<class...> class A, class... T, template<class...> class B>
    struct mp_rename_impl<A<T...>, B>
{
    using type = B<T...>;
};

template<class A, template<class...> class B>
    using mp_rename = typename mp_rename_impl<A, B>::type;

The code is used like:

mp_rename<std::pair<int, float>, std::tuple>        // -> std::tuple<int, float>
mp_rename<mp_list<int, float>, std::pair>           // -> std::pair<int, float>
mp_rename<std::shared_ptr<int>, std::unique_ptr>    // -> std::unique_ptr<int>

Can someone please explain the code like I'm five? I do have a general and basic understanding of non-templated C++.

What I don't get is:

Why is mp_rename_impl forward declared with two type parameters (class A, template<class...> class B), then it's defined and specialized at the same time[*] with three (template<class...> class A, class... T, template<class...> class B) and respectively two(A<T...>, B) type parameters?

I understand that it aliases (using type = B<T...>;) the type to be B<T...> instead of A<T...>, but I don't really get how it is done.

Also why is A a template template parameter only in the specialization?

[*] most certainly I got something wrong here

Answer 1

Why is mp_rename_impl forward declared with two type parameters (class A, template<class...> class B), then it's defined and specialized at the same time[*] with three (template<class...> class A, class... T, template<class...> class B) and respectively two(A<T...>, B) type parameters?

The forward declaration establishes the number of parameters needed to instantiate mp_rename_impl, and that the former should be an actual type, the latter a template.

Then when there's an actual instantiation, it tries to match the specialisation struct mp_rename_impl<A<T...>, B>, and in doing so it can consider any combination of values for the specialisation's A, T... and B matching the specialisation's expectations: namely template<class...> class A, class... T, template<class...> class B. Note that the A parameter in the specialisation shares a name with the A in the declaration, but is not the same - the former being a template and the latter a type. Effectively, to match the specialisation a template instantiation must have been passed as the declaration's A parameter, and that template's parameters are captured at T.... It imposes no new restrictions on what can be passed as B (though the using statement does - B<T...> needs to be valid or you'll get a compilation error - too late for SFINAE to kick in).

Also why is A a template template parameter only in the specialization?

The specialisation calls that parameter A, but it's not conceptually the same as A in the declaration. Rather, the former's A<T...> corresponds to the latter A. Perhaps the specialisation should have called it "TA" or something else to indicate it's the template from which an actual A can be formed in combination with the T... parameters. The specialisation is then of A<T...>, B, so the compiler works backwards from whatever instantiation is actually attempted to find valid substitutions for A, T... and B, guided by the restrictions on their form specified in template<template<class...> class A, class... T, template<class...> class B>.

What this achieves it to make sure the specialisation is only matched when the two parameters are a template already given some set of parameters types, and a template able to take a list of parameter types. The matching process effectively isolates the T type list so it can be reused with B.

Answer 2

My first attempt wasn’t what you were looking for, so let me briefly try to go back and explain like you’re six.

It’s not forward-declared in the sense that a function has a prototype and a definition. There’s an implementation for any A, and that compiles to an empty struct (which is a unique type to the compiler, but doesn’t require any actual storage or run-time code). Then, there’s a second implementation, only for template classes A.

There are really two templates in the second definition. What’s going on is that the second definition it takes the two parameters A and ... T and turns them into a type A<T>, which becomes the first parameter of mp_rename_impl<A<T...>,B>. So it applies to any A that’s a template class. But that’s a more specific kind of A! So it’s a specialization that needs to declare a struct with a type definition in its scope. Finally, the third variant is not a specialization of the template at all. It’s declaring the templated mp_rename as an alias for the more complicated type stored within the scope of every struct in the second declaration, which as you see is the identifier type in the scope mp_rename_impl<A, B>. Believe it or not, this makes his template code a lot more readable.

Why does the more generic definition at the top expand to just an empty struct? When A is not a template class, the contents are trivial, but it does need some kind of type to its name so the compiler will consider it distinct from every other type. (It would have been more cool to write my example below to generate classes with the static constants as members, rather than functions. In fact, I just did.)

Updated as threatened to make my templates a bit more like his:

Okay, template metaprogramming is a kind of programming where, instead of having the program compute something when it runs, the compiler computes it ahead of time and stores the answer in the program. It does this by compiling templates. This can be a lot faster to run, sometimes! But there are limits on what you can do. Mainly, you can’t modify any of your parameters, and you’ve got to be sure the computation stops.

If you’re thinking, “You mean, just like functional programming?” you are one very smart five-year-old. What you normally end up doing is writing recursive templates with base cases that expand either to unrolled, streamlined code, or to constants. Here’s an example that might seem familiar from your Intro to Computer Science class when you were three or maybe four:

#include <iostream>

using std::cout;
using std::endl;

/* The recursive template to compute the ith fibonacci number.
 */
template < class T, unsigned i >
  struct tmp_fibo {
    static const T fibo = tmp_fibo<T,i-1>::fibo + tmp_fibo<T,i-2>::fibo;
  };

/* The base cases for i = 1 and i = 0.  Partial struct specialization
 * is allowed.
 */
template < class T >
  struct tmp_fibo<T,1U> {
    static const T fibo = (T)1;
  };

template < class T >
  struct tmp_fibo<T,0U> {
    static const T fibo = (T)0;
  };

int main(void) {
  cout << "fibo(50) = " << tmp_fibo<unsigned long long, 50>::fibo
       << ". fibo(10) = " << tmp_fibo<int, 10>::fibo << "."
       <<  endl;

  return 0;
}

Compile to assembly language, and we see what code the compiler generated for the line tmp_fibo<unsigned long long, 50>::fibo Here it is, in full:

movabsq $12586269025, %rsi

The templates generates an integral constant within each structure at compile-time. What those examples are doing, since you can declare type names within structs, is doing the same thing for types.

Answer 3

I will try to make it simple. Template metaprogramming is about computing types at compile-time (you can also compute values, but just let us focus on that).

So if you have this function:

int f(int a, int b);

You have a function that returns an int value given two int values.

You use it like this:

int val = f(5, 8);

Metafunctions operate on types, instead of on values. A metafunction looks like this:

//The template parameters of the metafunction are the
//equivalent of the parameters of the function
template <class T, class U>
struct meta_f {
    typedef /*something here*/ type;
};

Namely, a metafunction has a nested type inside, by convention the nested type is called type.

So you invoke a metafunction like this in non-generic contexts:

using my_new_type = meta_f<int, float>::type;

In generic contexts you must use typename:

using my_new_type = typename meta_f<T, U>::type;

This returns a type, not a run-time value, since we said metafunctions operate on types.

Examples of metafunctions in the standard library can be found in header type_traits, among others. You have add_pointer<T> or decay<T>. These metafunctions return new types given a type.

In C++14, in order to avoid pieces of code like this, which are verbose:

using my_computed_type = typename std::add_pointer<T>::type;

Some template aliases with a _t suffix, again by convention, were created that invoke the metafunction, directly, for you:

template <class T>
using add_pointer_t = typename std::add_pointer<T>::type;

And now you can write:

using my_computed_type = std::add_pointer_t<T>;

All in all, in a function, you have runtime values as parameters, in a metafunction, the parameters are types. In a function you invoke with the usual syntax and obtain a runtime value. In a metafunction you get the ::type nested type and get a new computed type.

//Function invocation, a, b, c are values of type A, B, C
auto ret = f(a, b, c);

//Meta function invocation. A, B, C are types
using ret_t = typename meta_f<A, B, C>::type;

//Typical shortcut, equivalent to metafunction invocation.
using ret_t = meta_f_t<A,B,C>;

So for the first function you get a value, for the others, you get a type, not a value.