C ++ metaprogramming

from Wikipedia, the free encyclopedia

C ++ - meta-programming is the technique of meta-programming in the programming language C ++ , so a technique in C ++ code to be generated from other program code. Templates are mainly used (in this case one also speaks of template metaprogramming), but also metaprogramming with the help of constant expressions and so-called preprocessor macros .

functionality

Template meta programming makes use of the fact that templates are evaluated during compilation . So you can write code that is evaluated at compile time so that the actual code is only then generated. Although this increases the compilation time, the method has the advantage that it can shorten the runtime .

Template meta programming is a programming technique that has been intensively researched for C ++ and implemented in practice. For example, there is an implementation of a Lisp derivative or, with Spirit, a parser generator implemented with the help of C ++ templates . Krzysztof Czarnecki and Ulrich W. Eisenecker are considered to be the masterminds of this type of programming. Outstanding work on C ++ metaprogramming comes from Andrei Alexandrescu , whom he made particularly well-known with his book Modernes C ++ Design - Generic Programming and Design Patterns Applied .

Template metaprogramming in C ++ is Turing-complete , which means that any algorithm can be implemented through template metaprogramming. At the same time, it follows that there cannot be a correct C ++ compiler that translates every C ++ program, or that it is no longer generally possible to decide whether a C ++ program is correct.

There are no changeable variables in template metaprogramming; H. Elements once initialized with a certain value retain their value forever. Interestingly, one consequence of this is that C ++ template metaprograms generally - unlike C ++ runtime programs - represent a form of purely functional programming . The control flow in template meta programs is therefore carried out with the help of recursion .

Examples

Power calculation with the help of templates

The following example calculates the power for positive exponents: 

template<int B, unsigned int E>
struct potenz {
    enum { value = B * potenz<B, E - 1>::value };
};

template<int B>
struct potenz<B, 0> {
    enum { value = 1 };
};

const int P = potenz<10, 3>::value;

Explanation: The template potent instantiates itself recursively , whereby the exponent is reduced by 1 with each recursion step. The template has a so-called specialization for the case that the exponent is 0 and returns the result 1 in this case. This specialization takes on the role of the termination condition of the recursion.

So the structure of the code can be described as pseudocode 

P(B, E) := B * P(B, E-1)
P(B, 0) := 1

describe.

Power calculation using constant expressions

The following example also calculates the power, in this case using generalized constant expressions:

constexpr int potenz(int basis, unsigned int exp) {
    return (exp == 0) ? 1 : basis * potenz(basis, exp - 1);
}

const int P = potenz(10, 3);

Explanation: Calls to simple functions can be made at compile time and used in constant expressions . The function to be called must be provided with constexpr . This is a new feature introduced in C ++ 11 , the 2011 revision of the C ++ international ISO standard.

Constructs used

In C ++ template metaprogramming, class templates take on the role of functions at runtime.

They can take types and constant values, including references to functions, as parameters so that they take on the role of a return type. Specializations of templates correspond to branches and in this way enable the control of the program flow.

Based on this, complex functions and data structures can be implemented that are evaluated at compile time. These can be used to create class structures, for example, and thus to simplify the implementation of certain design patterns , or to synthesize functions.

Libraries like Boost or Loki implement certain basic constructs that facilitate such metaprogramming, such as if or fold- like constructs at compile time or data structures.

Type lists

So-called type lists represent a simple example of a data structure defined by templates at compilation time. A typical implementation looks as follows: 

struct NullType;

template<typename H, class T>
struct TypeList {
    typedef H Head;
    typedef T Tail;
};

typedef TypeList<Type1, TypeList<Type2, TypeList<Type3, NullType>>> MyList;

Type lists can be processed using templates, but the end must be marked with a "null type".

It is very time-consuming to develop functionality based on type lists. However, elegant use is possible with the appropriate basic functions. The problem with the use arises from the fact that the possibilities for metaprogramming were only discovered afterwards and no specially designed language constructs exist for them.

Processing of type lists

In C ++ there is no easy way to access the elements of type lists. If a type list is to be processed, each iteration must be processed in a separate function call (with Tail as template parameter) or via the instantiation of a class template for each iteration. The processing is typically terminated by a specialization for the null type.

Variadic templates

In C ++ 11 have variadic templates , so templates with any number of parameters, collection maintained. Such a functionality can already be implemented with type lists, such as in Loki and Boost , but the support of variadic templates integrated in the programming language offers the advantage of significantly shorter compilation times, since the processing of type lists is associated with a great deal of effort. Instead of the parameters, a single tuple parameter is chosen. The processing must also take place with variadic templates via recursive instantiation so that there is a strong structural similarity.

Tuple

An elementary example for the generation of data structures using metaprogramming are tuples. These can be implemented with variadic templates (or previously type lists). For this, you usually create a class template that accepts any number of types as parameters and contains a field of this type for each type. Again in C ++, this must be done in a recursive manner. For example, a tuple can inherit from a tuple with one less element . Operations such as index accesses that must take place during the translation can then be implemented, or operations such as comparisons and hashes can be synthesized that can be applied to the tuples at runtime.

Generation of static tables at compile time

The advantage of static tables is the replacement of "expensive" calculations with a simple array indexing (for examples see lookup table ). In C ++ there is more than one way to create a static table at compile time. The following example demonstrates the creation of a very simple table using recursive structures and variadic templates. The table is ten in size, and each value is simply the index multiplied by itself. 

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 10;

/**
 * Variadisches Template für die rekursive Hilfs-Struktur.
 */
template<int INDEX = 0, int ...D>
struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> { };

/**
 * Spezialisierung des Templates um bei einer Größe von TABLE_SIZE die Rekursion zu beenden.
 */
template<int ...D>
struct Helper<TABLE_SIZE, D...> {
  static constexpr std::array<int, TABLE_SIZE> table = { D... };
};

constexpr std::array<int, TABLE_SIZE> table = Helper<>::table;

enum  {
  FOUR = table[2] // Nutzung zur Kompilierungszeit
};

int main() {
  for(int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // Nutzung zur Laufzeit
  }
  std::cout << "FOUR: " << FOUR << std::endl;
}

The idea behind this is that the auxiliary structure recursively inherits from a structure with another template argument (in this example calculated as INDEX * INDEX) until the specialization of the template ends the recursion when the size of ten elements is ten. Finally, the specialization uses the variable argument list as the elements for the array. The compiler generates code similar to the following (excerpt from the output of Clang with the following call parameters -Xclang -ast-print -fsyntax-only). 

template <int INDEX = 0, int ...D> struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> {
};
template<> struct Helper<0, <>> : Helper<0 + 1, 0 * 0> {
};
template<> struct Helper<1, <0>> : Helper<1 + 1, 0, 1 * 1> {
};
template<> struct Helper<2, <0, 1>> : Helper<2 + 1, 0, 1, 2 * 2> {
};
template<> struct Helper<3, <0, 1, 4>> : Helper<3 + 1, 0, 1, 4, 3 * 3> {
};
template<> struct Helper<4, <0, 1, 4, 9>> : Helper<4 + 1, 0, 1, 4, 9, 4 * 4> {
};
template<> struct Helper<5, <0, 1, 4, 9, 16>> : Helper<5 + 1, 0, 1, 4, 9, 16, 5 * 5> {
};
template<> struct Helper<6, <0, 1, 4, 9, 16, 25>> : Helper<6 + 1, 0, 1, 4, 9, 16, 25, 6 * 6> {
};
template<> struct Helper<7, <0, 1, 4, 9, 16, 25, 36>> : Helper<7 + 1, 0, 1, 4, 9, 16, 25, 36, 7 * 7> {
};
template<> struct Helper<8, <0, 1, 4, 9, 16, 25, 36, 49>> : Helper<8 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 8 * 8> {
};
template<> struct Helper<9, <0, 1, 4, 9, 16, 25, 36, 49, 64>> : Helper<9 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 64, 9 * 9> {
};
template<> struct Helper<10, <0, 1, 4, 9, 16, 25, 36, 49, 64, 81>> {
  static constexpr std::array<int, TABLE_SIZE> table = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
};

Since C ++ 17 this can be written much more readable: 

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 10;

constexpr std::array<int, TABLE_SIZE> table = [] { // Oder: constexpr auto table
  std::array<int, TABLE_SIZE> A = {};
  for (unsigned i = 0; i < TABLE_SIZE; i++) {
    A[i] = i * i;
  }
  return A;
}();

enum  {
  FOUR = table[2] // Nutzung zur Kompilierungszeit
};

int main() {
  for(int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // Nutzung zur Laufzeit
  }
  std::cout << "FOUR: " << FOUR << std::endl;
}

To show a more sophisticated example, the following code has been extended to include a helper for value calculation (as preparation for significantly more complicated calculations), a table-specific offset and a template argument for the type of table values ​​(e.g. uint8_t, uint16_t ...) . 

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 20;
constexpr int OFFSET = 12;

/**
 * Helfer für die Berechnung der einzelnen Tabellenelemente.
 */
template <typename VALUETYPE, VALUETYPE OFFSET, VALUETYPE INDEX>
struct ValueHelper {
  static constexpr VALUETYPE value = OFFSET + INDEX * INDEX;
};

/**
 * Variadisches Template für die rekursive Hilfs-Struktur.
 */
template<typename VALUETYPE, VALUETYPE OFFSET, int N = 0, VALUETYPE ...D>
struct Helper : Helper<VALUETYPE, OFFSET, N+1, D..., ValueHelper<VALUETYPE, OFFSET, N>::value> { };

/**
 * Spezialisierung des Templates um bei einer Größe von TABLE_SIZE die Rekursion zu beenden.
 */
template<typename VALUETYPE, VALUETYPE OFFSET, VALUETYPE ...D>
struct Helper<VALUETYPE, OFFSET, TABLE_SIZE, D...> {
  static constexpr std::array<VALUETYPE, TABLE_SIZE> table = { D... };
};

constexpr std::array<uint16_t, TABLE_SIZE> table = Helper<uint16_t, OFFSET>::table;

int main() {
  for(int i = 0; i < TABLE_SIZE; i++) {
    std::cout << table[i] << std::endl;
  }
}

This example can also be written much more readable since C ++ 17: 

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 20;
constexpr int OFFSET = 12;

template<typename VALUETYPE, VALUETYPE OFFSET>
constexpr std::array<VALUETYPE, TABLE_SIZE> table = [] { // Oder: constexpr auto table
  std::array<VALUETYPE, TABLE_SIZE> A = {};
  for (unsigned i = 0; i < TABLE_SIZE; i++) {
    A[i] = OFFSET + i * i;
  }
  return A;
}();

int main() {
  for(int i = 0; i < TABLE_SIZE; i++) {
    std::cout << table<uint16_t, OFFSET>[i] << std::endl;
  }
}

Advantages and disadvantages of template meta programming

  • Weighing up between translation time and execution time : Since the entire template source text is processed, evaluated and used during translation, the translation takes longer overall, while the executable code can become more efficient as a result. Although this additional effort is generally very small, it can have a major impact on the duration of the translation in large projects or projects in which templates are used intensively.
  • Generic programming : Template meta programming enables a higher level of abstraction. Therefore, template metaprogramming can lead to shorter source code and better maintainability.
  • Readability : Compared to conventional C ++ programming, the syntax and spelling of the template meta programming seem strange at first. Therefore, advanced or even most of the non-trivial template metaprogramming can be difficult to understand. As a result, metaprograms can be difficult to maintain for programmers who are inexperienced in template metaprogramming; in particular, the purely functional structure does not correspond to the usual structure of C ++. The latter, however, also depends on how the template metaprogramming was implemented in the specific case.
  • Bad support from development tools : In the existing development tools it is not possible to follow the metageneration step by step. Due to the lack of language resources, it has also been difficult to date to generate meaningful error messages for metaprogramming. Most compilers issue error messages that make it difficult to determine the actual error.

literature

Web links

Individual evidence

  1. ↑ Metalisp ( Memento of 4 February 2003 at the Internet Archive )
  2. ↑ Boost Spirit