C++ Core Guidelines: Rules for Template Metaprogramming

Contents[Show]

Yes, you read it correctly. Today, I write about template metaprogramming which is programming with types and not values. 

dinosaur 966869 1280

The introduction to template metaprogramming in the guidelines ends uniquely: "The syntax and techniques needed are pretty horrendous.". In accordance, the rules are mostly about don' ts and provide not much content:

Honestly, I don't think template metaprogramming is so horrendous but the syntax has still a lot of potentials.

Let me try to demystify template metaprogramming and write about programming at compile time in general. During this introduction to programming at compile time, I explicitly write about type-traits (T.124: Prefer to use standard-library TMP facilities) and constexpr functions (T.123: Use constexpr functions to compute values at compile time) and implicitly refer to the other rules. Here is my plan:

I give an introduction to template metaprogramming, show how the type-traits library allows you the use template metaprogramming in a well structured and a portable way, and how you can use constexpr functions to replace template metaprogramming magic with ordinary functions.

Template Metaprogramming

OverviewTemplateMetaprogramming

How it all started

1994 presented Erwin Unruh at a C++ committee meeting a program which didn't compile. Here is probably the most famous program that never compiled.

// Prime number computation by Erwin Unruh
template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
    enum { prim = (p%i) && is_prime<(i > 2 ? p : 0), i -1> :: prim };
    };

template < int i > struct Prime_print {
    Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    void f() { D<i> d = prim; }
    };

struct is_prime<0,0> { enum {prim=1}; };
struct is_prime<0,1> { enum {prim=1}; };
struct Prime_print<2> { enum {prim = 1}; void f() { D<2> d = prim; } };
#ifndef LAST
#define LAST 10
#endif
main () {
    Prime_print<LAST> a;
    } 

 

Erwin Unruh used the Metaware Compilers, but the program is not valid for C++ anymore. A newer variant from the author is here. Okay, why is this program so famous? Let's have a look at the error messages.

 prim

I highlighted the important parts in red. I think, you see the pattern. The program calculates at compile time the first 30 prime numbers. This means template instantiation can be used to do math at compile time. It is even better. Template metaprogramming is Turing-complete, and can, therefore, be used to solve any computational problem. (Of course, Turing-completeness holds only in theory for template metaprogramming because the recursion depth (at least 1024 with C++11) and the length of the names which are generated during template instantiation provide some limitations.)

How does the magic work?

Let me start traditional.

Calculating at Compile Time

Calculating the factorial of a number is the "Hello World" of template metaprogramming.

// factorial.cpp

#include <iostream>

template <int N>                                                                 // (2)
struct Factorial{
    static int const value = N * Factorial<N-1>::value;
};

template <>                                                                      // (3)
struct Factorial<1>{
    static int const value = 1;
};

int main(){
    
    std::cout << std::endl;
    
    std::cout << "Factorial<5>::value: " << Factorial<5>::value << std::endl;    // (1)
    std::cout << "Factorial<10>::value: " << Factorial<10>::value << std::endl;
    
    std::cout << std::endl;

}

 

The call factorial<5>::value in line (1) causes the instantiation of the primary or general template in line (2). During this instantiation, Factorial<4>::value will be instantiated. This recursion will end if the fully specialised class template Factorial<1> kicks in in line (3).  Maybe, you like it more pictorial.

factorial5

Here is the output of the program:

factorial

Damn, I almost forgot to prove that the values were calculated at compile time. Here we are with the Compiler Explorer. For simplicity reasons, I only provide a screenshot of the main program and the corresponding assembler instructions.

 goldboltSource

goldboltAssem

 

The first yellow line and the first purple line shows it. The factorials of 5 and 10 are just constants and were calculated during compile time. 

Honestly, the factorial program is a nice program but is not idiomatic for template metaprogramming.

Manipulating Types at Compile Time

Manipulating types at compile time is typically for template metaprogramming. If you don't believe me, study std::move. Here is, what std::move is conceptionally doing:

static_cast<std::remove_reference<decltype(arg)>::type&&>(arg);

 

Okay. std::move takes an argument arg, deduces the type (decltype(arg)) from it, removes the reference (remove_reverence), and casts it to a rvalue reference (static_cast<...>::type&&>). In essence, this means that std::move returns always a rvalue reference type and, therefore, move semantic can kick it.

How does std::remove_reference from the type-traits library work? Here is a code snippet removing constness from its argument.

 

template<typename T > 
struct removeConst{ 
    typedef T type;               // (1)
};

template<typename T > 
struct removeConst<const T> { 
    typedef T type;               // (1)
};


int main(){
    
    std::is_same<int, removeConst<int>::type>::value;        // true
    std::is_same<int, removeConst<const int>::type>::value;  // true
  
}

 

I implemented removeConst the way std::remove_const is probably implemented in the type-traits library. std::is_same from the type-traits library helps me to decide at compile-time if both types are the same. In case of removeConst<int> the first or general class template kicks in; in case of removeConst<const int>, the partial specialisation for const T applies. The key observation is that both class templates return the underlying type in line (1) and, therefore, the constness is removed.

What's next?

In the next post, I continue my introduction to programming at compile time. This means in particular that I'm going to compare functions and metafunctions before I come to the type-traits library.

 

 

Thanks a lot to my Patreon Supporters: Eric Pederson, Paul Baxter,  Meeting C++, Matt Braun, Avi Lachmish, Roman Postanciuc, Venkata Ramesh Gudpati, Tobias Zindl, Dilettant, Marko, Ramesh Jangama, and Emyr Williams.

 

Thanks in particular to:  TakeUpCode 450 60

 

Get your e-book at Leanpub:

The C++ Standard Library

 

Concurrency With Modern C++

 

Get Both as one Bundle

cover   ConcurrencyCoverFrame   bundle
With C++11, C++14, and C++17 we got a lot of new C++ libraries. In addition, the existing ones are greatly improved. The key idea of my book is to give you the necessary information to the current C++ libraries in about 200 pages.  

C++11 is the first C++ standard that deals with concurrency. The story goes on with C++17 and will continue with C++20.

I'll give you a detailed insight in the current and the upcoming concurrency in C++. This insight includes the theory and a lot of practice with more the 100 source files.

 

Get my books "The C++ Standard Library" (including C++17) and "Concurrency with Modern C++" in a bundle.

In sum, you get more than 600 pages full of modern C++ and more than 100 source files presenting concurrency in practice.

 

Get your interactive course

 

Modern C++ Concurrency in Practice

C++ Standard Library including C++14 & C++17

educative CLibrary

Based on my book "Concurrency with Modern C++" educative.io created an interactive course.

What's Inside?

  • 140 lessons
  • 110 code playgrounds => Runs in the browser
  • 78 code snippets
  • 55 illustrations

Based on my book "The C++ Standard Library" educative.io created an interactive course.

What's Inside?

  • 149 lessons
  • 111 code playgrounds => Runs in the browser
  • 164 code snippets
  • 25 illustrations

Add comment


Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 890

All 2180691

Currently are 126 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments