Best Introduction to C++ Template Metaprogramming

Best introduction to C++ template metaprogramming?

[Answering my own question]

The best introductions I've found so far are chapter 10, "Static Metaprogramming in C++" from Generative Programming, Methods, Tools, and Applications by Krzysztof Czarnecki and Ulrich W. Eisenecker, ISBN-13: 9780201309775; and chapter 17, "Metaprograms" of C++ Templates: The Complete Guide by David Vandevoorder and Nicolai M. Josuttis, ISBN-13: 9780201734843.

Todd Veldhuizen has an excellent tutorial here.

A good resource for C++ programming in general is Modern C++ Design by Andrei Alexandrescu, ISBN-13: 9780201704310. This book mixes a bit of metaprogramming with other template techniques. For metaprogramming in particular, see sections 2.1 "Compile-Time Assertions", 2.4 "Mapping Integral Constants to Types", 2.6 "Type Selection", 2.7 "Detecting Convertibility and Inheritance at Compile Time", 2.9 "NullType and EmptyType" and 2.10 "Type Traits".

The best intermediate/advanced resource I've found is C++ Template Metaprogramming by David Abrahams and Aleksey Gurtovoy, ISBN-13: 9780321227256

If you'd prefer just one book, get C++ Templates: The Complete Guide since it is also the definitive reference for templates in general.

Understanding C++ template metaprogramming

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.

is c++ Template Metaprogramming a form of functional programming

is c++ Template Metaprogramming a form of functional programming?

Yep! Template expansion has no side effects, so it is pure-functional.

If it is, do some pitfalls like stackoverflow for non-tail recursion relevant for c++ Template Metaprogramming?

Absolutely. Factorial isn't a good demonstration of this, since the result will overflow long before your stack does, but long recursions can definitely cause the compiler to error out. Interestingly, however, compilers tend to implement templates in such a way that you get automatic memoization. For instance, a naively written implementation of the Fibonacci series will tend to compile in O(n) time rather than O(2^n).

C++ Template Metaprogramming- not sure I quite get the fuss?

Have you read the zillions of articles out there that thoroughly discuss TM? For example:

• http://www.codeproject.com/Articles/3743/A-gentle-introduction-to-Template-Metaprogramming
• http://aszt.inf.elte.hu/~gsd/halado_cpp/ch06s04.html
• http://blog.lorentey.hu/2010/04/21/cpp-template-metaprogramming/
• etc, etc.

A simple way of looking at (one kind) of template metaprogramming is as "strong" memoization. A common example is the following:

Lets say your program needs the compute a factorial for some number. With TM you can compute the factorial in compile-time, which increases compile time (and binary size) but decreases runtime. The example code is from the 2nd site above; if you were doing it the "naive" way, you'd have code that looks like:

int factorial( int n) {
    return (n==0) ? 1 : n*factorial(n-1)l
}

int main() {
    cout << factorial(5) << endl;
    return 0;
}

With TM we can compute the factorial at compile-time:

// factorial.cpp

#include <iostream>

template <int N>
struct Factorial {
    enum { value = N * Factorial<N-1>::value };
};

template <>
struct Factorial<1> {
    enum { value = 1 };
};

// example use
int main() {
    const int fact5 = Factorial<15>::value;
    std::cout << fact5 << endl;
    return 0;
}

Here Factorial<15>::value is essentially a compile-time constant. As always, simplistic examples aren't particularly useful, but hopefully you get the gist of it.

Template Metaprogramming - I still don't get it :(

Just as factorial is not a realistic example of recursion in non-functional languages, neither is it a realistic example of template metaprogramming. It's just the standard example people reach for when they want to show you recursion.

In writing templates for realistic purposes, such as in everyday libraries, often the template has to adapt what it does depending on the type parameters it is instantiated with. This can get quite complex, as the template effectively chooses what code to generate, conditionally. This is what template metaprogramming is; if the template has to loop (via recursion) and choose between alternatives, it is effectively like a small program that executes during compilation to generate the right code.

Here's a really nice tutorial from the boost documentation pages (actually excerpted from a brilliant book, well worth reading).

http://www.boost.org/doc/libs/1_39_0/libs/mpl/doc/tutorial/representing-dimensions.html

Tutorials and Introductions to C++ Expression Templates

You should get a copy of C++ Templates: The Complete Guide.

The code example to which you link doesn't have the accompanying text, which is quite helpful (the chapter on expression templates is 22 pages long). Without the text, all you have is code without any comments or explanation as to what it does and how and why it does it.

Non-C++ languages for generative programming?

The alternative to template style meta-programming is Macro-style that you see in various Lisp implementations. I would suggest downloading Paul Graham's On Lisp and also taking a look at Clojure if you're interested in a Lisp with macros that runs on the JVM.

Macros in Lisp are much more powerful than C/C++ style and constitute a language in their own right -- they are meant for meta-programming.

Can this be accomplished with templates in C++?

This can be done fairly easily using a std::tuple to specify your list of types. All we need to do is declare the primary template to take two parameters, then create a partial specialization where those type parameters are tuples. In the partial specialization, we can use the argument deduction to capture the template parameters of the tuple and re-use them for our purposes. We could create a new template for the purposes of specifying the list of types (i.e. Types<int,double>), but a tuple is especially nice in this case because you need to have a way to access the the individual rows anyway, and a std::tuple provides a built-in way to do this through std::get<i>. Using the tuple for the template parameters may make it more obvious that you use std::get to access the rows.

Here's a complete example:

#include <string>
#include <tuple>
#include <vector>

// primary template
template <typename RowTuple,typename RowInfoTuple> struct Rows;

// variadic partial specialization 
template <typename... RowTypes,typename... RowInfoTypes>
struct Rows<std::tuple<RowTypes...>,std::tuple<RowInfoTypes...>>
{
  // use variadic expansion to make a tuple of vectors
  std::tuple<std::vector<RowTypes>...> rows;
  std::tuple<RowInfoTypes...> rowinfos;
};

struct rss_feed { };

int main(int,char**)
{
  Rows<
    std::tuple<double,int>,
    std::tuple<std::string,rss_feed>
  > data;

  std::get<0>(data.rows).push_back(1.5);
  std::get<1>(data.rows).push_back(2);
  std::get<0>(data.rowinfos) = "info";
  std::get<1>(data.rowinfos) = rss_feed();
  return 0;
}

---

Related Topics