Page 1 of 1

Introduction to C++ Metaprogramming: Basics Rate Topic: -----

#1 Anthony`  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 2
  • View blog
  • Posts: 10
  • Joined: 30-December 15

Posted 31 December 2015 - 12:17 PM

This article will discuss metaprogramming in C++11 using templates, otherwise known as template metaprogramming. These examples were compiled using the latest clang C++ compiler.

What is metaprogramming?

Metaprogramming isn't specific to C++ only, as a matter of fact, C++'s metaprogramming facilities came as a result of a mistake due to templates being Turing-complete. Putting it simply: a language is Turing-complete if any algorithm that can be expressed as a computer program can be written in that language; C++'s templates are such a language.

A metaprogram is a program that operates on other programs, including itself. In the context of C++, template metaprograms generally operate on types and compile-time expressions. Template metaprograms share some important features of purely functional programming:
  • Call-by-need, otherwise known as lazy evaluation. Templates are instantiated when they need to be by the compiler.
  • No side-effects. Applying functions don't produce side-effects.
  • Variable bindings are immutable.

Let's write a metaprogram.

Computing factorials

A major advantage of template metaprogramming is the fact that your metaprograms will be executed during compile-time as opposed to run-time. Essentially, your compiler is executing the metaprogram and embedding its values in the source code then compiling the rest of the program. An immediate advantage is that less code execution is taking place at run-time, but as a cost of such a feature this means it takes longer for the compiler to compile the program as a whole.

A pretty common implementation for a program that computes a factorial looks like:
#include <iostream>

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

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

As you might expect, running the program outputs 120.

Notice that I implemented the factorial function as a recursive one, other than being easier to write, it is also how we are going to write our factorial metafunction, since it's also easier to write ion this way.

A template metafunction is a class template that returns a type or compile-time expression. This isn't a strict definition, but I find Boost's implementations of metafunctions to be quite well-defined and concise. A template metafunction is called as such: `metafunction<args...>::type`. For now, we will be defining a numeric metafunction that doesn't exactly conform to this convention.
template <unsigned int n>
struct factorial {
  static constexpr unsigned int value = n * factorial<n - 1>::value;
};

First, it's worth noting that this is a regular class-template except I'm using a struct here. You could just as easily use a class but recall that in C++ structs only differ from classes in visibility; by default its struct members are public, so we can avoid an extra line by using structs as our template-classes.

Since metafunctions are executed at compile-time, the compiler needs to know that the `value` member is a compile-time expression. C++11 introduced the `constexpr` type-qualifier, but `const` could also be used (see here for differences). Also, we use the `static` qualifier so the compiler can store its value in the data segment of the program (this means we don't need to instantiate a class in order to get access to its value -- a run-time operation).

However, there is one more thing we need to deal with: the base case. The base case for our recursive factorial metafunction is the same for its non-metafunction: when N = 1, the function should return 1. Using template specialization, this is simple:
template <>
struct factorial<0> {
  static constexpr unsigned int value = 1;
};

Thus, our complete factorial metaprogram looks like:
#include <iostream>

template <unsigned int n>
struct factorial {
  static constexpr unsigned int value = n * factorial<n - 1>::value;
};

template <>
struct factorial<0> {
  static constexpr unsigned int value = 1;
};

int main() {
  std::cout << factorial<5>::value << std::endl; // 120
  return 0;
}


Integral constant wrappers

Since our metafunction will be returning a type in our next example, we need some way of encapsulating the properties of a compile-time expression such as: type, value, next/previous values, and itself. It turns out this isn't very difficult to do using `typedef`s or C++11's new `using` keyword:
template <int N>
struct _int {
  using type = _int<N>;
  using value_type = int;
  static constexpr int value = N;
  using next = _int<N + 1>;
  using prev = _int<N - 1>;
};

If you look closely you will notice `_int<N>` in the code, which means it must instantiate itself... right? Right!? Actually, no. :)/>/> This is one of the features of template metaprogramming; `_int<5>` isn't instantiated until we need it, so the compiler doesn't instantiate it at all! Recall this is known as call-by-need or lazy evaluation.

You can also spend some time implementing basic mathematical operations on integral constants like so:
template <typename T, typename N>
struct plus : _int<T::value + N::value> {};

template <typename T, typename N>
struct minus : _int<T::value - N::value> {};

Use as:
plus<_int<1>, _int<1>>::value // 2 

We didn't need to re-implement all of `_int`'s fields since we are forwarding them via instantiation. Another way to look at it is as if we are inheriting `_int`'s properties into its child classes (`plus` and `minus`). This technique is known as template metafunction forwarding.

Computing binary to decimal

This example will look at computing a metafunction that converts a binary string to its base-10 value. In this example, we will also follow Boost's convention of a metafunction.

Following the previous section on integral constant wrappers and taking advantage of metafunction forwarding, our metaprogram looks like:
#include <iostream>

template <unsigned int N>
struct _uint {
  using type = _uint<N>;
  using value_type = unsigned int;
  static constexpr unsigned int value = N;
  using next = _uint<N + 1>;
  using prev = _uint<N - 1>;
};

template <>
struct _uint<0> {
  using type = _uint<0>;
  using value_type = unsigned int;
  static constexpr unsigned int value = 0;
  using next = _uint<1>;
  using prev = _uint<0>;
};

template <unsigned int N>
struct binary : _uint<binary<N / 10>::type::value * 2 + (N % 10)> {};

template <>
struct binary<0> : _uint<0> {};

int main() {
  std::cout << binary<101>::type::value << std::endl; // 5
  return 0;
}


Is This A Good Question/Topic? 0
  • +

Page 1 of 1