{"id":6244,"date":"2021-10-26T11:47:09","date_gmt":"2021-10-26T11:47:09","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/template-metaprogramming-a-introduction\/"},"modified":"2023-06-26T09:23:51","modified_gmt":"2023-06-26T09:23:51","slug":"template-metaprogramming-a-introduction","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/template-metaprogramming-a-introduction\/","title":{"rendered":"Template Metaprogramming – How it All Started"},"content":{"rendered":"

Metaprogramming is programming on programs. C++ applies metaprogramming at compile time. It started in C++98 with template metaprogramming, was formalized in C++11 with the type-traits library, and since C++11 has steadily improved. The main driving force is constant expressions. In this post, I want to write about its roots.<\/p>\n

<\/p>\n

 \"TemplateMetaprogramming\"<\/p>\n

In writing about template metaprogramming, I want to demystify its techniques. This demystification helps you to understand better the functions of the type-traits library<\/a> and, in particular, appreciate constexpr<\/code>. Most of the bad reputation of template metaprogramming is that you may get error messages of epic length. Template metaprogramming was not designed; it started with an accident.<\/p>\n

The Accident<\/h2>\n

In 1994, Erwin Unruh<\/a> from Siemens presented at a C++ committee meeting a program that didn’t compile. Here is probably the most famous program that never compiled successfully.<\/p>\n

\n
\/\/ Prime number computation by Erwin Unruh<\/span>\r\ntemplate<\/span> <<\/span>int<\/span> i><\/span> struct<\/span> D { D(void<\/span>*<\/span>); operator<\/span> int<\/span>(); };\r\n\r\ntemplate<\/span> <<\/span>int<\/span> p, int<\/span> i><\/span> struct<\/span> is_prime {\r\n    enum<\/span> { prim =<\/span> (p%<\/span>i) &&<\/span> is_prime<<\/span>(i ><\/span> 2<\/span> ?<\/span> p :<\/span> 0<\/span>), i -<\/span>1<\/span>><\/span> ::<\/span> prim };\r\n    };\r\n\r\ntemplate<\/span> <<\/span> int<\/span> i ><\/span> struct<\/span> Prime_print {\r\n    Prime_print<<\/span>i-<\/span>1<\/span>><\/span> a;\r\n    enum<\/span> { prim =<\/span> is_prime<<\/span>i, i-<\/span>1<\/span>>::<\/span>prim };\r\n    void<\/span> f<\/span>() { D<<\/span>i><\/span> d =<\/span> prim; }\r\n    };\r\n\r\nstruct<\/span> is_prime<<\/span>0<\/span>,0<\/span>><\/span> { enum<\/span> {prim=<\/span>1<\/span>}; };\r\nstruct<\/span> is_prime<<\/span>0<\/span>,1<\/span>><\/span> { enum<\/span> {prim=<\/span>1<\/span>}; };\r\nstruct<\/span> Prime_print<<\/span>2<\/span>><\/span> { enum<\/span> {prim =<\/span> 1<\/span>}; void<\/span> f<\/span>() { D<<\/span>2<\/span>><\/span> d =<\/span> prim; } };\r\n#ifndef LAST<\/span>\r\n#define LAST 10<\/span>\r\n#endif<\/span>\r\nmain () {\r\n    Prime_print<<\/span>LAST><\/span> a;\r\n    } \r\n<\/pre>\n<\/div>\n
 <\/p>\n
Erwin Unruh used the Metaware Compilers, but the program is not valid for C++ anymore. A newer variant from the author is here<\/a>. Okay, why is this program so famous? Let’s look at the original error messages that wrote type as txpe.<\/p>\n
 \"prim\"<\/p>\n
I highlighted the important parts in red. I think you see the pattern. The program calculates at compile time the first prime numbers until 30. This means template instantiation can be used to do math at compile time. It is even better. Template metaprogramming is Turing-complete<\/a>, and can, therefore, be used to solve any computational problem. (Of course, Turing completeness holds only in theory for template metaprogramming because the recursion instantiation depth (at least 1024 with C++11) and the length of the names generated during template instantiation provide some limitations.)<\/p>\n<\/p>\n
How does the magic work?<\/h3>\n
Let me decompose what is going on step by step.<\/p>\n
Calculating at Compile Time<\/h4>\n
Calculating the factorial of a number is the “Hello World” of template metaprogramming.<\/p>\n
\n
\/\/ factorial.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n\r\ntemplate<\/span> <<\/span>int<\/span> N><\/span>                                                                 \/\/ (2)<\/span>\r\nstruct<\/span> Factorial{\r\n    static<\/span> int<\/span> const<\/span> value =<\/span> N *<\/span> Factorial<<\/span>N-<\/span>1<\/span>>::<\/span>value;\r\n};\r\n\r\ntemplate<\/span> <><\/span>                                                                      \/\/ (3)<\/span>\r\nstruct<\/span> Factorial<<\/span>1<\/span>><\/span>{\r\n    static<\/span> int<\/span> const<\/span> value =<\/span> 1<\/span>;\r\n};\r\n\r\nint<\/span> main<\/span>(){\r\n    \r\n    std::<\/span>cout <<<\/span> '\\n';\r\n    \r\n    std::<\/span>cout <<<\/span> \"Factorial<5>::value: \"<\/span> <<<\/span> Factorial<<\/span>5<\/span>>::<\/span>value <<<\/span> '\\n'<\/span>;    \/\/ (1)<\/span>\r\n    std::<\/span>cout <<<\/span> \"Factorial<10>::value: \"<\/span> <<<\/span> Factorial<<\/span>10<\/span>>::<\/span>value <<<\/span> '\\n'<\/span>;  \/\/ (4)<\/span><\/em>\r\n    \r\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n\r\n}\r\n<\/pre>\n<\/div>\n
 <\/p>\n
The call factorial<5>::value<\/code> in line (1) causes the instantiation of the primary or general template in line (2). During this instantiation, Factorial<4>::value<\/code> will be instantiated. This recursion will end if the fully specialized class template Factorial<1> <\/code>kicks in in line (3).  Maybe, you like it more pictorial.<\/p>\n
\"factorial5\"<\/p>\n
Here is the output of the program:<\/p>\n
\"factorial\"<\/p>\n
Let me start with C++ Insights:<\/p>\n
C++ Insights<\/h4>\n
The call Factorial<5>::value<\/code> (line 1) causes the instantiation of the class template for the numbers 5 to 2. The full specialization for 1 is already available. The call Factorial<10>::value<\/code> (line 2) causes the instantiation of the function template for the numbers 10 – 6 because all other fully specialized function templates are already available. The following output shows the instantiation for the numbers 5 to 2.<\/p>\n
\"CppInsightsRecursiveInstantiaion\"<\/p>\n
 <\/p>\n
<\/span><\/span><\/p>\n
Now, my analysis continues with the Compiler Explorer<\/a>.<\/p>\n
Compiler Explorer<\/h4>\n
For simplicity reasons, I only provide a screenshot of the main program and the corresponding assembler instructions.<\/p>\n
The Compiler Explorer allows you to visualize this compile-time calculation.<\/p>\n
 \"goldboltSource\"<\/p>\n
\"goldboltAssem\"<\/p>\n
The output shows it. The factorials of 5 and 10 are just constants and were calculated during compile time. You can see the result directly in the first line and last line of the assembler instructions.<\/p>\n
CppCon 2021<\/h2>\n
I was quite happy this week that I could use a previous post as a starting point for this post. I gave this week four talks at the CppCon<\/a> and honestly, this was too much. Here are my talks that are published on Youtube’s CppCon channel<\/a>. The pdfs are already available.<\/p>\n
Thanks to C++ Insights<\/a> and Compiler Explorer<\/a>, you can and should analyze the program further. This should help to build your intuition about template instantiation and template metaprogramming.<\/p>\n