Meta-functions in C++11

Function and class templates in C++03, along with the ability to specialize them (and to partially specialize the latter), enabled the creation of powerful tools. Perhaps the most prominent one is Boost.MPL library. Not everyone needs to know or needs to use meta-programming techniques to be a good programmer, and it might look like a bit too academic tool. But there are domains where meta-programming are useful: for instance, type traits or compiler-checked dimensional analysis.

However, the employment of such techniques often comes with reservations because these techniques are very difficult to use by ordinary programmers. This is mostly because the design of C++03 did not focus on meta-programming support, and it was only discovered and perhaps overused the template mechanism a bit. The code that employs meta-programming is not easy to write or use. On the other hand, it does offer an amazing capability: performing computations and using their results at compile-time.

C++11 offers some tools that make meta-programming easier. More programmers can use these techniques without investing many nights on picking up the details of template mechanics and analyzing mysterious compiler error messages. Dave Abrahams will be giving a talk “Metaprogramming in C++11” in C++ Now! 2012, in May. This will surely cover all the interesting aspects of the new meta-programming tools. Until that time, you can read about two of the new techniques here. You can also consider it a short introduction into basic concepts of meta-programming in general.

What is a meta function?

So what does “meta” mean in our context. My definition is, that it is a piece of code that can be executed and its result used while the program is compiling. Unlike normal run-time functions, meta-functions can compute two things: values or types.

Computing values

The computation of values at compile-time in C++03 is based on the unique behavior of templates, that, apart from types, they can also be parametrized with some integral values. For instance:

template <int i>;
struct IntArray 
  int value [i];

template <int i, int j>;
struct Multiply
    static const int value = i * j;

Struct IntArray shows us what non-type template parameters were really added for to C++03. Struct Multiply shows us a simple meta-function example: given two values of type int, we can compute a new one (at compile-time):

int array[ Multiply<3, 4>::value ]; // 12-element array

Text Multiply<3, 4>::value hardly looks like a function call, but logically it is one: you give input values, you obtain a result.

And this is where the interesting question arises. Do you mind that such meta-function is declared as an artificial class, and that it is evaluated by instantiating a class template and accessing a static member? If you have worked with meta-functions for a while and you are used to such constructs you may not even realize anymore that this is a problem. If you think this example is acceptable, lets look at a bit more complicated example. Let’s compute a factorial. I do not believe that anyone would ever need to evaluate a factorial function during the compilation, but it is the smallest example that I can think of that shows the basic concepts of functional programming: recursion, terminal conditions of the recursion, and error handling.

template <int i> struct Factorial
  static const int value = i * Factorial<i - 1>::value;

template <> struct Factorial<0>
  static const int value = 1;

The first definition introduces the recursion. The value of value of the ‘current’ instantiation is determined based on the corresponding value from another instantiation. The second definitions determines the terminal condition of the recursion, for i equal to 0.

One other thing to demonstrate is checking for the precondition, and signalling an error. In the case of factorial we would like to eliminate the possibility of providing negative arguments. Of course, we could have used type unsigned int to avoid the problem, but the goal of this exercise is to show how precondition checking could be implemented, in general. This requires to build more meta-functions atop the above, unsafe, Factorial.

template <int i, bool c>
  struct NegativeArgument
  static const int value = Factorial<i>::value;

template <int i>
  struct NegativeArgument<i, false>; // not defined

template <int i>
  struct SafeFactorial
  static const int value = NegativeArgument<i, (i >= 0)>::value;

Let’s take the example from the end. Meta-function SafeFactorial forwards the argument to another meta-function: NegativeArgument; but it also passes the precondition (i >= 0). The name of the latter function appears non-intuitive at this point, but it will turn very appropriate when it comes to generating a compile-time error message. The main trick is embedded in meta-function NegativeArgument. The specialization for bool = false is deliberately declared (to intercept violated preconditions) but left undefined to make sure the code that picks this specialization fails to compile. If it fails to compile we will get an error message saying something along the lines “use of undefined type ‘NegativeArgument<i,c>.’” It is not a perfect message, but hopefully sufficient to give a hint to the user what she did wrong.

The two parameter version of NegativeArgument will silently forward the argument to our good meta-function Factorial.

The point I am trying to make here is that defining meta-functions like this is a bit complicated, or arcane. How does C++11 help us with this? By extending the concept of constant expressions. You have probably already heard about constexpr and what it allows you to do. If you haven’t, see this post.

In short, in C++11 our unsafe and safe versions of compile-time factorial can be defined as:

constexpr int factorial( int i )
  return (i == 0) ?            // terminal condition
         1 :                   // and terminal value
         i * factorial(i - 1); // recursive definition

constexpr int safe_factorial( int i )
  return (i < 0) ?            // error condition
         throw exception() :  // error reporting (at compile-time!)
         factorial(i);        // real computation

The meaning of this code is described in the aforementioned post. A ‘constexpr function’ is almost like a normal function, but we have to use a conditional operator rather than if-statement. With this tool, we can declare an array of 24 elements like this:

int array[ factorial(4) ];

Again, I chose the factorial example, because it is very simple to define and therefore fits into this post. You probably wouldn’t need a compile-time factorial ever in your life. But one might need, for instance, a function for computing the greatest common divisor, if one needs to implement a compile-time rational number library.

Computing types

Another type of meta-functions is one where we pass one type as argument and get another one in return. For instance, let’s try to implement function remove_pointer (like the one in the Standard) that for types U = T* returns T and for any other type returns that type unchanged. That is, the meta-function removes the top-level pointer wherever it is possible to remove it.

This is implementable due to partial template specialization:

template <typename U>         // in general case
struct remove_pointer
  typedef U type;

template <typename T>         // for U = T*
struct remove_pointer<T*>
  typedef T type;

This does not appear that bad, but in order to use our meta-function in a function template you have to use a somewhat clumsy syntax:

template <typename T>
typename remove_pointer<T>::type fun(T val);

The necessity to use the inconvenient typename is a consequence of the rules for partial class template specialization rules. The compiler needs to be prepared for nasty specializations like the following:

template <typename U>         // 'master' template
struct MyClass
  typedef U type;             // define a type

template <typename T>         // specialization
struct MyClass<const T>
  static int type = 0;        // define an object

You could argue that compiler should be required to be smart enough to somehow make everything work without the hint from the programmer (in the form of helper typename) but it is not easily implementable in general case and… this is simply how C++ works. In the end, the perspective of having to write stuff like typename remove_pointer<T>::type is hardly attractive, and makes the code difficult to read, especially for your colleagues that do not wish to be troubled with such stuff.

This is C++03. Fortunately, C++11 offers a certain convenience: alias templates. Type aliases is a new feature for defining types; similar to typedefs, but with a slightly improved syntax:

using Integer = int;
// same as: typedef int Integer;

using FunPtr = int* (*)(int*);
// same as: typedef int*(*FunPtr)(int*);

Alias templates add functionality that was missing for a long time in C++03:

template <typename T>
using StackVector = std::vector<T, StackAllocator<T>>;

StackVector<int> v;

With alias templates we can write our pointer-removing meta-function as follows:

template <typename U>         // in general case
struct remove_pointer
  using type = U; 

template <typename T>         // for U = T*
struct remove_pointer<T*>
  using type = T;

template <typename W>
using RemovePointer = typename remove_pointer<W>::type;

We did not make our meta-function definition any smaller. And we still needed to use the infamous typename. However, the way the meta-function is used has improved significantly:

template <typename T>
RemovePointer<T> fun(T val);

This technique for denoting meta-functions and type traits has been employed in report “A Concept Design for the STL,” as well as in Origin libraries.

Try it yourself

There are more features that make meta-programming easier in C++11, static assertions being one of them. Some enhancements come from simply improving compiler implementations (e.g., better support for recursive template instantiations). I only listed the two that I found most interesting. Generalized constant expressions (constexpr) are currently implemented — according to my knowlege — in GCC 4.6. Alias templates are implemented in GCC 4.7 and Clang 3.0.

This entry was posted in programming and tagged , . Bookmark the permalink.

16 Responses to Meta-functions in C++11

  1. C++ meta-programming is really cool. We’ve been using it quite a bit in our lab to accomplish some pretty amazing things.

  2. Jesse says:

    `Function and class templates in C++03, along with the ability to partially and fully specialize them, enabled the creation of powerful tools.`
    I’m sure you know this, but the above sounds like partial specialization of function templates is allowed.

  3. L. says:

    Nice post! One small typo I’ve spotted: “SatckVector” -> “StackVector”🙂.

  4. Grout says:

    Why didn’t C++11 implement all the type traits as alias templates? A lot of needless ::type typing appears in C++11 code as a result.

  5. Hi Grout. If I were to guess, I would say that the C++ Standards Committee prefers to standardize things that are already in use and have proved to be useful for a long period of time (this was the case with type traits in the current form) than requiring something of all the implementers that appears good, but is not guaranteed to prove good in practice (this was the case, for instance, with exported templates). Alias templates appear useful, and if it turns out in practice that they are better for type traits in many applications, they will surely get standardized in the future – unless something even more attractive and simple is devised.

  6. Graham says:

    The first example in computing types uses the aliase keyword, surely this should be using typedefs?

  7. Will says:

    Typo in constexpr int factorial( int i ):
    return (i = 0) ? // terminal condition
    should be
    return (i == 0) ? // terminal condition
    (ah, C’s syntax…)
    (Worth noting that a change of the parameter from “int i” to “const int i” (or “int const i”) would helpfully prevent the erroneous code from compiling…)

  8. Template metaprograms have no mutable variables — that is, no variable can change value once it has been initialized, therefore template metaprogramming can be seen as a form of functional programming . In fact many template implementations implement flow control only through recursion, as seen in the example below.

  9. Pingback: c++14 新特性 : variable templates | dengos

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s