dinosaur 966869 1280

C++ Core Guidelines: Rules for Template Metaprogramming

Yes, you read it correctly. Today, I write about template metaprogramming, 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 primarily about dont’s and do not provide much content:

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

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:

 

Rainer D 6 P2 500x500Modernes C++ Mentoring

Be part of my mentoring programs:

  • "Fundamentals for C++ Professionals" (open)
  • "Design Patterns and Architectural Patterns with C++" (open)
  • "C++20: Get the Details" (open)
  • "Concurrency with Modern C++" (starts March 2024)
  • Do you want to stay informed: Subscribe.

     

    I introduce template metaprogramming, show how the type-traits library allows you to use template metaprogramming in a well-structured and 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 that didn’t compile. Here is probably the most famous program that was 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 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 show it. The factorials of 5 and 10 are just constants and were calculated during compile time. 

    The factorial program is friendly but 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 the case of removeConst<int>, the first or general class template kicks in; in the case of removeConst<const int>, the partial specialization for const T applies. The critical observation is that both class templates return the underlying type in line (1), and the constness is removed.

    What’s next?

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

     

     

     

     

    Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, moon, Philipp Lenk, Hobsbawm, and Charles-Jianye Chen.

    Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.

    My special thanks to Embarcadero
    My special thanks to PVS-Studio
    My special thanks to Tipi.build 
    My special thanks to Take Up Code
    My special thanks to SHAVEDYAKS

    Seminars

    I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

    Standard Seminars (English/German)

    Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

    • C++ – The Core Language
    • C++ – The Standard Library
    • C++ – Compact
    • C++11 and C++14
    • Concurrency with Modern C++
    • Design Pattern and Architectural Pattern with C++
    • Embedded Programming with Modern C++
    • Generic Programming (Templates) with C++
    • Clean Code with Modern C++
    • C++20

    Online Seminars (German)

    Contact Me

    Modernes C++ Mentoring,

     

     

    0 replies

    Leave a Reply

    Want to join the discussion?
    Feel free to contribute!

    Leave a Reply

    Your email address will not be published. Required fields are marked *