Modern Template Metaprogramming: A Compendium, Part I - Walter E. Brown

What is template metaprogramming

• Template metaprogramming is a specialized form of metaprogramming that leverages templates to perform compile-time computations, essentially allowing programs to manipulate other programs or themselves.
• Template metaprogramming is not just about leveraging templates for the sake of metaprogramming, but rather about exploiting template instantiation to perform compile-time evaluations, ultimately enhancing code efficiency and performance.

Definition of Metaprogramming:

• Writing computer programs that can write or manipulate other programs or themselves as data.
• Performing tasks during compile-time that would typically be done at runtime.

Essence of Template Metaprogramming:

• Utilizes templates to facilitate compile-time evaluation.
• Heavily relies on the process of template instantiation at compile time.

Template Instantiation Explained:

• Occurs when a template is used in a program, expecting a type, function, or variable, but a template is specified instead.
• The compiler then instantiates, or creates, the appropriate entity from the named template.

Key Machinery in Template Metaprogramming:

• Regardless of the type of template (function, variable, class), instantiation is the core mechanism.
• Template metaprogramming aims to improve source code flexibility and runtime performance by shifting work from runtime to compile time.
• While this approach may lengthen compile times, it reduces the workload at runtime.

How to shift works to compile-time?

Considerations for Practicing Metaprogramming:

• Understand that "runtime" in the context of metaprogramming actually refers to compile-time.
• Embrace constraints such as no mutability, no virtual functions, and no runtime type identification (RTTI), which necessitate a constant-based, non-runtime dispatch approach.
• Recognize that the challenge in template metaprogramming often lies in its unfamiliarity rather than inherent difficulty.

Purpose of Compile-time Calculations:

• Effective when values are known ahead of compile time.
• Not suitable for values determined at runtime.

A C++11 constexpr function can be useful but

Absolute Value Metafunction Example:

template <int N>  // template param used as the metafctn param
struct abs {
  static_assert(N != INT_MIN);
  static constexpr int value = (N < 0) ? -N : N;  // "return"
}

int const n =..; // could instead declare as constexpr
abs<n>::value - // instantiation yields a compile-time constant

• Uses a template parameter N as the function parameter.
• Implements a static assertion to prevent usage with the most negative integer, addressing limitations with two's complement integer representation.
• Calculates the absolute value of N using a conditional operator, effectively serving as the function's "return" value.
• Emphasizes initialization over assignment to ensure compile-time evaluation.
• Uses static constexpr for the computed value to underline its constant nature.

Key Insights:

• Assignment operations are avoided to maintain the computations within compile-time constraints.
• The metafunction is defined within a struct, leveraging C++ templates for compile-time execution.
• The use of static_assert ensures type safety and prevents invalid operations at compile time.

Calling the Metafunction:

• The metafunction is "called" by instantiating the template with a specific value (n) and accessing its value member, demonstrating how template metaprogramming simulates function calls.

• This approach is consistent across various C++ standards, with syntax evolving from C++98 through to proposed features in C++17.

• Relationship between constexpr functions and metafunctions:

  • Constexpr Functions:
    • Useful for performing computations at compile time.
    • Had they been available a decade or 15 years ago, metaprogramming today might look significantly different.
    • Offer a familiar call syntax, avoiding the awkward ::value syntax used in metaprogramming.
    • Function as real functions that are invoked at compile time.
  • Metafunctions:
    • structs that provide additional tools for metaprogramming.
    • Allow for public declarations inside a struct, which is not possible with functions.
    • Enable the use of public member type declarations, public member data declarations (static and either const or constexpr), and public member function declarations.
    • Useful for template metaprogramming, offering features like public member templates and static asserts.

• Comparison and Utility:

  • Metafunctions offer a broader set of tools compared to constexpr functions, such as the ability to make certain declarations public and to utilize static and constexpr members.
  • Despite the utility of constexpr functions, metafunctions provide a structured approach to metaprogramming with their ability to include a variety of declarations and assertions.

• Hypothetical Impact on the Standard Library:

  • The design of type traits and possibly other components of the standard library might have been different with the earlier availability of constexpr functions.
  • Nonetheless, the current state of metaprogramming and the standard library incorporates both approaches effectively.

Compile-time recursion with specialization as base

template <unsigned M, unsigned N>
struct gcd {
  static int const value = gcd<N, M % N>::value;  // Recursive call per Euclid's algorithm
};

template <unsigned M>
struct gcd<M, 0> {
  static_assert(M != 0, "gcd of 0 and 0 is undefined");  // Base case specialization
  static int const value = M;  // Returns M when the second argument is 0
};

• Introduction to Compile-Time Recursion:

  • The technique involves metafunctions that can recursively call themselves, allowing computations to occur at compile time.
  • The Euclidean algorithm is highlighted as an example, noted for its utility in some standard library algorithms.

• Euclidean Algorithm for GCD:

  • Presented as a metafunction, the Euclidean algorithm calculates the GCD of two unsigned integer values at compile time.
  • The algorithm showcases compile-time recursion, with the metafunction calling itself until reaching a base case.

• Template Specialization as Pattern Matching:

  • The base case for the recursive algorithm is defined using template specialization, likened to pattern matching.
  • This specialization handles the case where the second argument is zero, essentially stopping the recursion and returning the first argument as the GCD.

• Sidenotes: considerations for constexpr:

  • The absence of constexpr in the example is acknowledged, attributed to its creation before the widespread adoption of constexpr.
  • Although constexpr might be preferred for modern implementations, the existing const approach remains valid, especially for compatibility with older compilers.

A metafunction can take a type as a parameter/argument

// Example: obtain the (compile-time) rank of an array type:
// primary template handles scalar (non-array) types as base case:
template <class T>
struct rank {
  static size_t const value = Ou;
};

// partial specialization recognizes any array type:
template <class U, size_t N>
struct rank<U[N]> {
  static size_t const value = 1u + rank<U>::value;
};

// · Usage:
using array_t = int[10][20][30];
rank<array_t>::value  // yields 3u (at compile-time)

• This technique demonstrates the powerful capability of metafunctions to operate on types rather than values, a feature not achievable with constexpr functions. Here's a detailed breakdown:

• Metafunction for Array Rank:

  • The primary template acts as a base case for scalar (non-array) types, assigning them a rank of zero.
  • A partial specialization handles array types by recursively calculating the rank, incrementing it by one for each array dimension encountered.

• Key Points:

  • Type-based Metafunctions: Unlike constexpr functions that operate on values, metafunctions can take types as parameters.
  • This is similar to the sizeof operator in C++, which can also operate on types, demonstrating a longstanding precedence for type-based operations in the language.
  • Template Metaprogramming: The example employs template metaprogramming techniques to perform compile-time computations, illustrating how recursion can be effectively used in specializations rather than in the primary template.

A metafunction can also produce a type as its result

• Type Functions in Metaprogramming:

  • Metafunctions can take one or more types as inputs and return a type as output.
  • This functionality extends the versatility of template metaprogramming by allowing developers to perform type transformations and manipulations at compile time.

• remove_const Metafunction:

  • Primary Template: Acts as an identity, returning the input type unchanged when it is not const-qualified.
  • Partial Specialization: Targets types with a top-level const qualifier, stripping it away and returning the underlying type without the const modifier.

• Syntax and Usage:

  • Classic Call Syntax: remove_const<T>::type is used to obtain the transformed type, where T is the input type.
  • C++14 Simplification: The introduction of alias templates in C++14, such as remove_const_t<T>, simplifies the syntax by eliminating the need to explicitly refer to ::type.

• Corrected and Extended Code Example:

template <class T>
struct remove_const {
  using type = T;
};  // Handles types without `const` qualifier

template <class U>
struct remove_const<U const> {
  using type = U;  // Removes top-level `const` qualifier
};

// Usage examples:
// Classic syntax pre-C++14
remove_const<const int>::type a; // `a` is of type int

// Simplified syntax with C++14
using remove_const_t = typename remove_const<T>::type; // Alias template
remove_const_t<const int> b; // `b` is of type int, equivalent to `int b;`

• Conceptual Insights:

  • The remove_const metafunction demonstrates the capacity of template metaprogramming to conduct compile-time type analysis and transformations, providing a mechanism for cleaner and more expressive type manipulations.
  • By leveraging these metafunctions, developers can write more generic, flexible, and type-safe code, enhancing the overall robustness and maintainability of C++ applications.

• Conclusion:

  • Type functions like remove_const exemplify the advanced capabilities of C++ template metaprogramming, facilitating sophisticated compile-time type operations. These operations enrich the language's type system, allowing for more precise and intentional type handling in a variety of programming scenarios.

C++11 library metafunction convention #1

• metafunctions can return a type as a result, rather than a value.
• This concept is exemplified through the remove_const metafunction

template <class T>
struct remove_const {
  using type = T;
};  // Handles types without `const` qualifier

template <class U>
struct remove_const<U const> {
  using type = U;  // Removes top-level `const` qualifier
};

// Usage examples:
// Classic syntax pre-C++14
remove_const<const int>::type a; // `a` is of type int

// Simplified syntax with C++14
using remove_const_t = typename remove_const<T>::type; // Alias template
remove_const_t<const int> b; // `b` is of type int, equivalent to `int b;`

• Type Functions in Metaprogramming:

  • Metafunctions can take one or more types as inputs and return a type as output.
  • This functionality extends the versatility of template metaprogramming by allowing developers to perform type transformations and manipulations at compile time.

• remove_const Metafunction:

  • Primary Template: Acts as an identity, returning the input type unchanged when it is not const-qualified.
  • Partial Specialization: Targets types with a top-level const qualifier, stripping it away and returning the underlying type without the const modifier.

• Conceptual Insights:

  • The remove_const metafunction demonstrates the capacity of template metaprogramming to conduct compile-time type analysis and transformations, providing a mechanism for cleaner and more expressive type manipulations.
  • By leveraging these metafunctions, developers can write more generic, flexible, and type-safe code, enhancing the overall robustness and maintainability of C++ applications.

• Metafunction Conventions:

  • Type Result Convention: For metafunctions that yield a type as a result, the convention is to alias the result using the name type. This practice promotes consistency and readability in template metaprogramming.
  • Historical Inconsistencies: The standard library contains exceptions to this convention, largely due to historical developments predating the establishment of these norms. An example cited is iterator_traits, which provides multiple results like value_type and iterator_category without adhering to the type naming convention.

Compile-time decision-making

Identity Metafunction:

template <class T>
struct type_is {
  using type = T;
};

template <class T>
struct remove_volatile : type_is<T> {};  // Inherits from `type_is` for non-volatile types

template <class U>
struct remove_volatile<U volatile> : type_is<U> {};  // Inherits from `type_is` for volatile-qualified types, removing `volatile`

• Introduced as a utility metafunction named type_is, serving as a straightforward identity function that simply returns the type passed to it.

• Demonstrates the utility of simple, foundational metafunctions in facilitating more complex type manipulations.

• Usage Through Inheritance:

  • The type_is metafunction is leveraged through inheritance to implement other metafunctions, such as remove_volatile, showcasing a pattern of reusing metafunction conventions to ensure consistency and prevent errors like misspelling.

• remove_volatile Metafunction: Illustrates the application of the type_is convention to create a metafunction that removes the volatile qualifier from a type. The primary template handles types without the volatile qualifier by default, while a partial specialization handles and removes volatile from volatile-qualified types.

Compile-time decision-making between two types based on a predicate

• A hypothetical metafunction named IF or IF_t

• This innovative approach allows for dynamic type selection and self-configuring code structures that adjust according to compile-time conditions.

• Purpose and Design of IF/IF_t:

  • Designed to make compile-time decisions between two types based on a boolean predicate.
  • The predicate's result, known at compile time, determines which of the two given types is selected.

• Applications of IF/IF_t:

  • Enables writing self-configuring code that adapts based on compile-time conditions.
  • Facilitates conditional type selection for variables, function object instantiation and calls, and inheritance, depending on the value of a compile-time constant.

• Implementation Sketch:

// Compile-time decision-making
// Imagine a metafunction, IF/IF_t, to select one of two types:

template <bool p, class T, class F>
struct IF : type_is<...> {};  // p? T: F

// Such a facility would let us write self-configuring code:

// Assume: int const q = -; // user's configuration parameter

IF_t<(q < 0), int, unsigned> k;
// k declared to have 1 of these 2 integer types

IF_t<(q < 0), F, G>{}(...);
// instantiate and call 1 of these 2 function objects

class D : public IF_t<(q < 0), B1, B2> {
  //...
};
// inherit from 1 of these 2 base classes

• Usage Examples:

  • Variable Type Selection: Based on the condition q < 0, k is declared as either int or unsigned.
  • Function Object Selection: Decides between instantiating and calling one of two function objects, F or G, based on q.
  • Inheritance Decision: Chooses one of two base classes, B1 or B2, for class D to inherit from, based on q.

• Demonstrates the power and flexibility of compile-time metaprogramming in C++, allowing developers to create highly configurable and type-safe code structures.

• The IF/IF_t concept underscores the capability of template metaprogramming to implement complex logic and conditional type decisions without runtime overhead, enhancing both performance and code maintainability.

Behind the scene of IF

template <bool, class T, class>  // Bool is assumed true, F is unnamed
struct IF : type_is<T> {};

template <class T, class F>
struct IF<false, T, F> : type_is<F> {};

• Implementation Details:

  • Primary Template: Assumes the boolean condition is true. It only requires the name for the type T that is to be selected if the condition is true, leaving the third parameter (the false case type) unnamed due to its irrelevance in this scenario.
  • Partial Specialization for false: When the boolean condition is false, this specialization selects the type F, demonstrating the simplicity and elegance of template specialization in handling compile-time conditional logic.

• Standard Library Correlation:

  • The IF metafunction is conceptually equivalent to std::conditional in C++11, showcasing how standard library features encapsulate common metaprogramming patterns.
  • With C++14, the introduction of conditional_t simplifies the syntax further by providing a more convenient alias to std::conditional's ::type member, aligning with the convention of adding _t suffixes to type traits for easier access to their resulting types.

• Reflection on Design Choices:

  • The choice to default to true for the primary template and only specialize for the false case underscores a common strategy in template metaprogramming: optimize for the common case or a default assumption, and explicitly handle exceptions or alternatives through specialization.

• Augmentation in C++14:

  • C++14's augmentation of standard type traits, including conditional_t, exemplifies the evolution of C++ towards more user-friendly and concise metaprogramming, facilitating type manipulations without verbose syntax.

A single-type variation on conditional

• enable_if Concept:

// "If true, use the given type; if false, use no type at all":

// primary template assumes the bool value is true:
template <bool, class T = void>  // default is useful, not essential
struct enable_if : type_is<T> {};

// partial specialization recognizes a false value, computing nothing:
template <class T>
struct enable_if<false, T> {};  // no member named type!

SFINAE applies during implicit template instantiation

// During template instantiation, the compiler will:
// 1. Obtain (or figure out) the template arguments:
//    Taken verbatim if explicitly supplied at template's point of use.
//    Else deduced from function arguments at point of call.
//    Else taken from the declaration's default template arguments.
// 2. Replace each template parameter, throughout the template, by its
//    corresponding template argument.
//    If these steps produce well-formed code, the instantiation succeeds, but
//    If the resulting code is ill-formed, it is considered not viable
//    (due to substitution failure) and is silently discarded.

• It's a metafunction that allows conditional enabling or disabling of template specializations based on a compile-time boolean expression. If the condition is true, enable_if provides a type; if false, it provides no type, effectively removing the template from consideration due to substitution failure.

• The primary template of enable_if assumes the condition is true and provides a default type, typically void, unless specified otherwise.

• A partial specialization for false condition intentionally does not define a type, causing a substitution failure if this specialization is instantiated, leveraging SFINAE.

• SFINAE (Substitution Failure Is Not An Error):

  • SFINAE is a principle in C++ template metaprogramming that allows a program to compile even if there is a substitution failure in template instantiation. This principle is crucial for creating flexible and robust template-based APIs that can adapt based on the types passed to them.

• Practical Use Cases:

  • enable_if and SFINAE are used for function overloading, template specialization, and controlling template instantiation. These techniques enable writing more generic, adaptable code that can handle different types and conditions at compile time.

SFINAE in use

• Example Usage of enable_if:
  • To differentiate function templates based on type traits, such as distinguishing between integral and floating-point types. This is done by placing enable_if in the return type or as a template parameter, selectively enabling a function template based on the trait's value.

// Example: want one algorithm f taking integral types T, and
// overload it with a second f taking floating-point types T.
// For a given type T, want at most one of the two algorithms
// to be instantiated:

template <class T>
typename enable_if<is_integral<T>::value, maxint_t>::type f(T val) {
  // Implementation for integral types
}

template <class T>
typename enable_if<is_floating_point<T>::value, long double>::type f(T val) {
  // Implementation for floating-point types
}

// What if neither overload were viable?
// Calling f with, say, a string argument produces an ill-formed
// program, since both candidates will be SFINAE'd away.

• Understanding enable_if and SFINAE:
  • The mechanism of enable_if and the principle of SFINAE highlight the depth and flexibility of C++'s type system and template metaprogramming. They allow developers to write code that adapts based on type characteristics determined at compile time, contributing to the language's power in generic programming and type-safe interfaces.

A taste of the future: Concept

• Concepts has a very solid mathematical foundation. And that means it is a solid, well-baked idea.

// Concepts Lite seems likely to be published (as a TS) in 2015,
// and thence perhaps to be integrated with C++17:
// Its "constraints" metaprogramming feature seems likely
// to reduce or obviate many current uses for SFINAE, etc.
// Based on decades of concepts work by A. Stepanov, inspired
// by the founder of abstract algebra, Emmy Noether (1882-1935).
// Revisiting part of our SFINAE example:
template <class T>
enable_if_t<is_integral<T>::value, maxint_t>  // SFINAE
f(T val){...};

template <Integral T>   // constrained template (short form) 'Integral' is a
maxint_t f(T val){...}; // concept constraining 'T' to integral types

C++11 library metafunction convention #2

// A metafunction with a value result has:
// - A static constexpr member, value, giving its result, and ...
// A few convenience member types and constexpr functions.
// · Canonical C++11 value-returning metafunction:
template <class T, T v>
struct integral_constant {
  static constexpr T value = v;
  constexpr operator T() const noexcept { return value; }
  constexpr T operator()() const noexcept { return value; }
  // remaining members are only occasionally useful
};

// Inheriting from integral_constant provides more options
// for meta-call syntax (details in just a moment).

// Revised rank metafunction
// Example: obtain the (compile-time) rank of an array type:
// primary template handles scalar (non-array) types as base case:
template <class T>
struct rank : integral_constant<size_t, Ou> {};
// partial specialization recognizes bounded array types:
template <class U, size_t N>
struct rank<U[N]> : integral_constant<size_t, 1u + rank<U>::value> {};
// partial specialization recognizes unbounded array types:
template <class U>
struct rank<U[]> : integral_constant<size_t, 1u + rank<U>::value> {};

• Value-Returning Metafunctions:

  • These metafunctions are characterized by having a static constexpr member named value that holds the result of the metafunction.
  • Additional convenience features include member types and constexpr functions to facilitate the use of the metafunction's result.

• Canonical Value-Returning Metafunction:

  • The integral_constant template serves as the foundational building block for value-returning metafunctions.
  • It provides a static constexpr member value, along with constexpr conversion and call operators for easier access to the value.

• Usage of integral_constant:

  • By inheriting from integral_constant, metafunctions gain a standardized way to return values, enhancing consistency and usability.
  • This inheritance approach allows for more flexible meta-call syntax and integrates well with the overall C++ type system and template metaprogramming paradigms.

• Revised Rank Metafunction Example:

// Inheriting from integral_constant provides more options
// for meta-call syntax (details in just a moment).

// Revised rank metafunction
// Example: obtain the (compile-time) rank of an array type:
// primary template handles scalar (non-array) types as base case:
template <class T>
struct rank : integral_constant<size_t, Ou> {};
// partial specialization recognizes bounded array types:
template <class U, size_t N>
struct rank<U[N]> : integral_constant<size_t, 1u + rank<U>::value> {};
// partial specialization recognizes unbounded array types:
template <class U>
struct rank<U[]> : integral_constant<size_t, 1u + rank<U>::value> {};

• Demonstrates applying the value-returning convention through the rank metafunction, which computes the compile-time rank of array types.

• The primary template handles scalar (non-array) types by inheriting from integral_constant with a value of zero, indicating a rank of zero for non-array types.

• Specializations for bounded and unbounded array types recursively calculate the array's rank, demonstrating the utility and adaptability of inheriting from integral_constant.

• Key Points:

  • Consistency and Stability: The conventions for metafunctions underscore the importance of stability and consistency in the C++ Standard Library and among C++ practitioners. The decision not to replace these conventions with newer features like constexpr functions reflects the committee's commitment to backward compatibility and stability.
  • Metaprogramming Tools: integral_constant and its pattern of usage exemplify the tools provided to metaprogrammers for creating robust, reusable, and expressive template-based utilities. These tools allow for compile-time computations and type manipulations that are central to effective C++ template metaprogramming.

Some integral_constant conveniences

template <bool b>
using bool_constant = integral_constant<bool, b>;

// Some useful C++11 convenience aliases:
using true_type = bool_constant<true>;
using false_type = bool_constant<false>;

// Value-returning metafunction calls have evolved:
is_void<T>::value   // since Technical Report 1
bool(is_void<T>{})  // instantiate/cast; since C++11
is_void<T>{}()      // instantiate/call; since C++14
is_void_v<T>        // a C++14 variable template; planned for C++17 standard
                    // library

• Convenience Aliases:

  • bool_constant: A template alias for integral_constant specialized for boolean values, simplifying the creation of boolean metafunctions.
  • true_type and false_type: Specific instances of bool_constant representing true and false values, respectively, to further ease the definition and use of compile-time boolean constants.

• Evolution of Metafunction Call Syntax:

  • The syntax for invoking value-returning metafunctions has evolved over time, providing multiple ways to access the computed value:
    • Pre-C++11: Accessing the value directly via ::value.
    • C++11 Enhancements:
      • The introduction of an implicit cast operator (operator T()) in integral_constant, allowing the metafunction to be cast to its value type (bool in this context) implicitly.
      • This enables a more concise syntax for obtaining the metafunction's value without explicitly referencing ::value.
    • C++14 Additions:
      • An operator() was added to integral_constant, permitting the instantiation and direct invocation of the metafunction to retrieve its value, offering an alternative syntactic form (is_void<T>{}()).
    • Planned for C++17:
      • The introduction of variable templates for type traits (is_void_v<T>), simplifying the syntax further by eliminating the need to instantiate the metafunction or access ::value directly.

• Significance of Variable Templates (C++14 Feature):

  • The introduction of variable templates in C++14 paves the way for *_v variable template aliases for value-returning metafunctions, streamlining the way values are accessed from metafunctions.
  • This advancement highlights the continuous improvement and simplification of template metaprogramming in C++, making it more accessible and reducing the verbosity of common metaprogramming tasks.