TMP related notes from book

• Code

1.1 Metafunction and type_traits

1.1.1 Introduction to Metafunctions

• Metafunctions are called and executed at compile time. During the compilation phase, the compiler can only construct constants as intermediate results, unable to construct and maintain variables that can record the state of the system and change it hereafter, so functions (which are metafunctions) used at compile time can only be functions without side effects.

• Nature of C++ Metaprogramming:

  • Functions in C++ metaprogramming are akin to mathematical functions with no side effects.
  • Metafunctions must produce the same output for the same input regardless of how many times they are called.

• Characteristics of Functions with Side Effects:

  • Functions with side effects produce different outputs with the same input if there are changes in the system state.
  • This behavior contrasts with metafunctions, which are called at compile time and cannot maintain or alter system state.

• Example of a Metafunction:

  • constexpr int fun(int a) { return a + 1; }
  • This function is defined with constexpr, indicating it can be evaluated at compile time without side effects.

• Contrast with Non-Metafunction:

  • Example of erroneous code:

    static int call_count = 3;
    constexpr int fun2(int a) { return a + (call_count++); }

  • fun2 attempts to use a mutating global variable (call_count), leading to a compilation error because it violates the no side effects rule.

1.1.2 Type Metafunction

• Mathematical Function Representation:

  • Mathematical functions are usually expressed as y = f(x), involving input (x), output (y), and a mapping (f).

• Function Input and Output Variability:

  • While typically numeric, inputs and outputs of functions can vary, such as mapping events to probabilities in probability theory.

• Metaprogramming and Metafunctions:

  • Core elements of metaprogramming are metafunctions, where both input and output can be various types, not limited to numeric values.

• Example of Type Metafunction in C++:

  • Metafunction mapping integer types to corresponding unsigned types:

    template <typename T>
    struct Fun_ {
      using type = T;
    };
    
    template <>
    struct Fun_<int> {
      using type = unsigned int;
    };
    
    template <>
    struct Fun_<long> {
      using type = unsigned long;
    };
    
    Fun_<int>::type h = 3;

• Understanding Metafunction Definition:

  • Metafunctions, like Fun_, do not resemble regular C++ functions visually but fulfill the criteria of a metafunction:
    • Input is a type T.
    • Output is an internal type from the template, Fun_<T>::type.
    • Mapping is executed through template specialization.

• Is Fun a metafunction?

  • As defined in the book C++ Template Metaprogramming, it is not at least a "standard metafunction" because it does not have an inline type declaration.
  • However, according to the discussion at the beginning of this chapter, it is a metafunction because it has input (T), output (Fun<T>::type), and clearly defines the mapping rules. So, we consider it a metafunction.

• Broader Definitions and Examples of Metafunctions:

  • Metafunctions are not restricted to functions with constexpr or templates with type declarations.
  • Inputs and outputs can extend beyond types to include numeric values or templates, enhancing flexibility and decreasing coding limitations.

1.1.3 Various Metafunctions

• Flexibility and Evolution of Metafunctions in C++:

  • Metafunctions are not originally part of the C++ language design; they evolved to support operations with "no side effects" and compile-time execution.
  • There are no strict rules on the structure of metafunctions, allowing for diverse forms and functionalities.

• Examples of Metafunctions:

  • Simple template metafunction:

    template <typename T>
    struct Fun {};

  • Parameterless metafunctions:

    • Returns type int:

      struct Fun {
        using type = int;
      };

    • Returns value 10 using constexpr:

      constexpr int fun() { return 10; }

• Extended Use of constexpr in Metafunctions:

  • C++14 enhances the ability to define metafunctions using constexpr for simpler and more direct expressions:

    template <int a>
    constexpr int fun = a + 1;

  • This defines a variable template rather than a traditional function but serves as a metafunction with compile-time evaluation.

• Metafunctions with Multiple Return Types:

  • The ability to output multiple types from a single input exemplifies advanced metafunction capabilities:

    template <>
    struct Fun<int> {
      using reference_type = int&;
      using const_reference_type = const int&;
      using value_type = int;
    };

  • Despite the complexity, such designs are valid and can be beneficial in specific programming scenarios.

1.1.4 type_traits

• Introduction to type_traits Library:

  • Originated from Boost and incorporated into C++11.
  • Accessible via the header file <type_traits>.
  • Provides a suite of functionalities for type transformation, comparison, and judgment.

• Usage of Metafunctions in type_traits:

  • Example demonstrating type transformation:

    std::remove_reference<int&>::type h1 = 3;  // Transforms `int&` to `int`
    std::remove_reference_t<int&> h2 = 3;      // Simplified form using alias template

  • std::remove_reference and std::remove_reference_t are metafunctions for type manipulation, where the latter is a simplified alias introduced for easier use.

• Role of type_traits in Generic Programming:

  • Essential for writing generic code that requires type transformations.
  • Frequently utilized in frameworks, including deep learning frameworks, to handle type-specific logic.

1.1.5 Metafunctions and Macros

• Macros as Metafunctions:

  • While macros can technically be considered metafunctions due to their function-like behavior, they are generally not included in discussions about C++ metafunctions.
  • This exclusion is due to macros being processed by the preprocessor, not the compiler, limiting their integration with compile-time features.

• Limitations of Macros:

  • Macros lack namespace support, posing risks of name conflicts with other parts of the code.
  • Unlike constexpr functions and templates, macros do not support the advanced features available to compiler-processed metafunctions.

• Use of Macros in Specific Contexts:

  • Despite their limitations, macros can be advantageous in certain scenarios, such as in the construction of deep learning frameworks.
  • Macros can serve as supplements to template metafunctions, offering utility where templates may not suffice.

• Guidelines for Using Macros in Frameworks:

  • It is recommended to restrict end-user access to macros within the framework to avoid potential misuse.
  • Macros should be undefined after their purpose is fulfilled to clean up the namespace and prevent unintended effects.

1.1.6 The Nominating Method of Metafunctions in This Book

In this book, metafunctions are named differently depending on the form of return values for metafunctions:

• if the return value of a metafunction is represented by a dependent name, the function will be named the form of xxx_ (an underscore as the suffix);
• if the return value of a metafunction is represented directly with a non-dependent name, the name of the metafunction will not contain a suffix in the form of an underscore.

template <int a, int b>
struct Add_ {
  constexpr static int value = a + b;
};

template <int a, int b>
constexpr int Add = a + b;

constexpr int x1 = Add_<2, 3>::value;
constexpr int x2 = Add<2, 3>;

1.2 Template Template Parameters and Container Templates

• Metafunctions handle three categories of "metadata":
  • Numeric values
  • Types
  • Templates
• The term "metadata" is used to distinguish these elements from "data" manipulated during runtime.

1.2.1 Templates as the Input of Metafunctions

template <template <typename> class T1, typename T2>
struct Fun_ {
  using type = typename T1<T2>::type;
};

template <template <typename> class T1, typename T2>
using Fun = typename Fun_<T1, T2>::type;

Fun<std::remove_reference, int&> h = 3;

• The Fun metafunction is defined to take two parameters: a template (T1) and a type (T2).
• It uses the template T1 with T2 as an argument, and outputs the result of this application.
• Code implementation:
  • Fun_ struct applies T1<T2> and stores the result as a type.
  • Alias Fun simplifies access to this type result.
• Usage example:
  • Fun<std::remove_reference, int&> results in the type int.
  • Variable h is declared as an int and initialized with the value 3.
• In functional programming terms:
  • Fun is a higher-order function because it takes a function (T1, a template) as an input.
  • Mathematically represented as Fun(T1, t2) = T1(T2), where T1 is a function and t2 is a value.

1.2.2 Templates as the Output of Metafunctions

• Templates can also be used as the output of metafunctions in addition to the input of metafunctions

template <bool AddOrRemoveRef>
struct Fun_;

template <>
struct Fun<true> {
  template <typename T>
  using type = std::add_lvalue_reference<T>;
};

template <>
struct Fun<false> {
  template <typename T>
  using type = std::remove_reference<T>;
};

template <typename T>
using Res_ = Fun_<false>::template type<T>;
Res<int&>::type h = 3;

• The Fun_ metafunction is designed to manipulate template types based on a boolean parameter, showing versatility in handling C++ templates:
  • For the true case, it outputs a template that adds an lvalue reference (std::add_lvalue_reference).
  • For the false case, it outputs a template that removes references (std::remove_reference).
• Implementation and usage:
  • Template specializations for true and false provide different behaviors based on the boolean input.
  • Res_ uses Fun_<false> to apply the std::remove_reference template to int&, resulting in int.
  • Res<int&>::type h = 3; initializes h as an integer with the value 3.
• Mathematical representation:
  • Fun(addOrRemove) = T where addOrRemove is a boolean, and T is the output template from Fun_, which itself acts as a metafunction.

1.2.3 "Containers" in Metaprogramming

• Containers in Metaprogramming:

  • Containers, rather than arrays, are essential for holding elements (numeric values, types, templates).
  • Containers in metaprogramming typically hold only one category of operands due to simplicity and common requirements.

• Variadic Templates for Containers:

// 1. container that can hold int
template <int... Vals>
struct IntContainer;

// 2. container that can hold bool
template <bool... Vals>
struct BoolContainer;

// 3. container that can hold types
template <typename... Types>
struct TypeContainer;

// 4. hold templates as its element and each template element can receive one
// type as a parameter
template <template <typename> class... T>
struct TemplateCont;

// 5. take templates as its element, but each template can hold zero or more
// type parameters.
template <template <typename...> class... T>
struct TemplateCont2;

// Note, all 5 above don't have definition. The declaration already contains all
// the information that the compiler needs.

• Metaprogramming Idioms:
  • Metaprogramming often uses declarations without definitions unless necessary, reducing complexity and compile-time overhead.
  • This approach is illustrated with the declaration of containers without definitions, as they provide sufficient information for the compiler.

1.3.1 Executed in Sequence Order

template <typename T>
struct RemoveReferenceConst_ {
 private:
  using inter_type = typename std::remove_reference<T>::type;

 public:
  using type = typename std::remove_const<inter_type>::type;
};

template <typename T>
using RemoveReferenceConst = typename RemoveReferenceConst_<T>::type;

RemoveReferenceConst<const int&> h = 3;

• Overview of RemoveReferenceConst_ Metafunction:

  • The metafunction RemoveReferenceConst_ performs two sequential transformations on the type T to remove both reference and const qualifiers.

• Detailed Breakdown of Operations:

  • The metafunction RemoveReferenceConst_ performs two sequential transformations on the type T to remove both reference and const qualifiers.
  1. Calculate inter_type: Removes the reference from T using std::remove_reference<T>::type.
  2. Calculate type: Removes the const qualifier from inter_type using `std::remove_const

1.3.2 Codes Executed in Branches

Branching at compile time involves creating decision paths based on compile-time conditions, which can dictate the behavior of both compile-time and runtime code.

1.3.2.1 Implementing Branches Using std::conditional and std::conditional_t

namespace std {

template <bool B, typename T, typename F>
struct conditional {
  using type = T;
};

template <typename T, typename F>
struct conditional<false, T, F> {
  using type = F;
};

template <bool B, typename T, typename F>
using conditional_t = typename conditional<B, T, F>::type;
}  // namespace std


// Its logic is that if B is true, the function returns T, otherwise F is
// returned. It is typically used in the following way:
std::conditional<true, int, float> :: type x = 3;
std::conditional t<false, int, float> y =1.0f;

• The advantage of conditional and conditional_t is that they are relatively simple to use, but
• the disadvantage is that they are not very expressive—it can only implement binary branches (true and false branches) and it behaves more like a conditional operator expression at runtime: x = B? T:F;
• Support for multiple branches (a feature similar to switch) is more difficult.
• Accordingly, the use of conditional and conditional_t is relatively narrow. Thus, these two metafunctions are not recommended unless there are particularly simple cases of branches.

1.3.2.2 Implementing Branches with (Partial) Specialization

• Branch Implementation Using Specialization:
  • Specialization in templates allows for introducing specific behaviors based on the type. It's a natural and common method to implement branching logic in C++.

struct A;
struct B;

template <typename T>
struct Fun_ {
  constexpr static size_t value = 0;
};

template <>
struct Fun_<A> {
  constexpr static size_t value = 1;
};

template <>
struct Fun_<B> {
  constexpr static size_t value = 2;
};

constexpr size_t h = Fun_<B>::value; // assign h with 2 as T is B

• Legal Constraints on Specialization:

template <typename TW>
struct Wrapper {
  template <typename T>
  struct Fun_ {
    constexpr static size t value = 0;
  };

  template <>
  struct Fun_<int> {
    constexpr static size t value = 1;
  };
};

• It's illegal to fully specialize a template within a non-fully specialized class template, as shown in the initial Wrapper code snippet, where the full specialization of Fun<int> inside Wrapper causes a compilation error.

• Solution Using Partial Specialization:

  • Introduce a dummy template parameter (TDummy) to convert full specialization into partial specialization:
    • This allows for specialization inside templated classes without breaking C++ standards.
    • The default value of TDummy is void, allowing the specialized metafunction to be called as Fun_<int> without additional parameters.

template <typename TW>
struct Wrapper {
  template <typename T, typename TDummy = void>
  struct Fun_ {
    constexpr static size_t value = 0;
  };

  template <typename TDummy>
  struct Fun _<int, TDummy> {
    constexpr static size_t value = 1;
  };
};

1.3.2.3 Implementing Branches Using std::enable_if and std::enable_if_t

• Overview of std::enable_if and std::enable_if_t:

  • enable_if is a template structure used in C++ to conditionally enable or disable certain template specializations based on a boolean condition B.
  • When B is true, enable_if specializes to enable the type T; otherwise, it does not provide a type, effectively disabling the template.

• Code Functionality Using enable_if:

  • This technique leverages SFINAE (Substitution Failure Is Not An Error), a feature in C++ that allows template specialization to fail without generating a compile-time error.
  • By using enable_if, developers can conditionally compile code depending on the truth of the template argument.

• Example with Function Overloading:

namespace std {

template <bool B, typename T = void>
struct enable_if {};

template <class T>
struct enable_if<true, T> {
  using type = T;
};

template <bool B, class T = void>
using enable_if_t = typename enable_if<B, T>::type;

}  // namespace std

template <bool IsFeedbackOut, typename T,
          std::enable_if_t<IsFeedbackOut>* = nullptr>
auto FeedbackOut(T&&) { /* ... */
}

template <bool IsFeedbackOut, typename T,
          std::enable_if_t<!IsFeedbackOut>* = nullptr>
auto FeedbackOut_(T&&) { /* ... */
}

• Two overloads of FeedbackOut function are defined:

  • The first overload is enabled only if IsFeedbackOut is true.
  • The second overload is enabled only if IsFeedbackOut is false.

• std::enable_if_t is used as a non-type template parameter defaulted to nullptr to control which overload is active based on the IsFeedbackOut condition.

• Practical Usage and Implications:

  • enable_if and enable_if_t are crucial for creating overloads that cannot be distinguished by parameter types alone, thus solving some overload resolution issues in template-heavy code.
  • They can be used in various contexts where SFINAE is supported, not limited to template parameters, thus offering flexibility in template function design.

• Readability and Understanding:

  • While powerful, the usage of enable_if and enable_if_t can make the code less intuitive and harder to read compared to direct template specialization.
  • The complexity introduced by SFINAE might require a deeper understanding of template mechanics, which may not be as straightforward as other methods like template specialization.

1.3.2.4 Compile-time Branches with Different Return Types

• Runtime Return Type Limitations:

auto wrap1(bool Check) {
  if (Check)
    return (int)0;
  else
    return (double)0;
}

• In the provided runtime code snippet, there's an attempt to use conditional logic to return different types (int or double). However, in C++14, a function without an explicitly declared return type must return the same type from all return statements. The code snippet will fail to compile because it violates this requirement.

• Compile-Time Type Flexibility:

  • The limitation of having a single return type in functions is overcome using template metaprogramming and std::enable_if.
  • By templating the function fun on a boolean Check and using std::enable_if_t, different implementations of fun can be enabled based on the value of Check.

template <bool Check, std::enable_if_t<Check>* = nullptr>
auto fun() {
  return (int)0;
}

template <bool Check, std::enable_if_t<!Check>* = nullptr>
auto fun() {
  return (double)0;
}

template <bool Check>
auto wrap2() {
  return fun<Check>();
}

int main() { std::cerr << wrap2<true>() << std::endl; }

• Two template specializations of fun are defined:

  • The first specialization returns an int when Check is true.
  • The second returns a double when Check is false.

• Use of wrap2 Function:

  • wrap2 wraps around fun, forwarding its template argument Check. The return type of wrap2 is determined by the type returned by the called fun specialization, effectively enabling wrap2 to also return different types based on the compile-time boolean.

• Practical Implications and Advantages:

  • This method showcases the flexibility of C++ templates to implement functions that can change return types based on compile-time conditions. It is particularly useful in scenarios where different types must be handled based on compile-time conditions.
  • This approach enhances metaprogramming capabilities, making it a powerful feature for developing complex, type-safe algorithms and libraries.

• C++17 if constexpr:

  • The introduction of if constexpr in C++17 further simplifies compile-time conditional logic by allowing a more straightforward and readable way to implement compile-time branches within the same function body, without the need for separate template specializations.
  • if constexpr executes conditionally at compile-time, effectively allowing different code branches to be compiled based on the condition, similar to the separate template specializations but within a single function body.

1.3.2.5 Simplify Codes with if constexpr

• Introduction to if constexpr:

  • if constexpr is a C++17 feature that allows conditional compilation within function bodies based on compile-time constants. It enables the compiler to conditionally include or exclude code blocks during compilation, enhancing optimization and code simplicity.

• Functionality of if constexpr:

  • The compiler evaluates the condition provided to if constexpr at compile time. If the condition is true, it compiles the code within the corresponding block; otherwise, it ignores that block.
  • This behavior allows a single function to return different types based on the compile-time condition, simplifying template specialization and reducing code duplication.

template <bool Check>
auto fun() {
  if constexpr (Check)
    return (int)0;
  else
    return (double)0;
}

int main() { std::cerr << fun<true>() << std::endl; }

• Advantages of if constexpr:

  • Reduces the number of function instances the compiler needs to generate compared to separate template specializations or function overloads. This can lead to smaller binary sizes and faster compilation times.
  • Simplifies code by avoiding multiple template specializations for each condition, making the code more readable and maintainable.

• Drawbacks and Limitations:

  • Compile-time vs. Runtime: If the constexpr condition is omitted or not met, the branching logic might inadvertently shift from compile-time to runtime, which reduces the effectiveness of if constexpr and may lead to performance penalties.
  • Narrow Usage Scope: if constexpr is primarily useful within functions to direct compile-time logic and cannot be used to vary class templates or other metafunctions that require different types based on compile-time conditions. Its use is limited to situations where the function logic diverges based on compile-time known conditions.

1.3.3 Codes Executed in Loops

• Traditional loops (while, for) are not used because they require variable operations, incompatible with compile-time operations which focus on constants, types, and templates.
• Recursion is utilized instead of looping constructs to manipulate metadata at compile time.

template <size_t Input>
constexpr size_t OnesCount = (Input % 2) + OnesCount<(Input / 2)>;

template <>
constexpr size_t OnesCount<0> = 0;

constexpr size_t res = OnesCount<45>;

template <size_t ... Inputs>
constexpr size_t Accumulate = 0;

template <size_t CurInput, size_t ... Inputs>
constexpr size_t Accumulate<CurInput, Inputs ... >
= CurInput + Accumulate<Inputs ... >;

constexpr size_t res = Accumulate<1, 2, 3, 4, 5>;

template <size_t... values>
constexpr size t fun() {
  constexpr size t res = fun<1, 2, 3, 4, 5>();
  return (0 + ... + values);
}

• Fold Expressions in C++:
• Simplified method for writing loops that operate at compile-time.
• Used primarily for operations on parameter packs in template metaprogramming.
• Offers a concise syntax but has specific limitations and use cases.

1.3.4 Caution: Instantiation Explosion and Compilation Crash

1.3.5 Branch Selection and Short Circuit Logic

template <size_t N>
constexpr bool is_odd = ((N % 2) == 1);

template <size_t N>
struct AllOdd_ {
  constexpr static bool is_cur_odd = is_odd<N>;
  constexpr static bool is_pre_odd = AllOdd_<N - 1>::value;
  constexpr static bool value = is_cur_odd && is_pre_odd;
};

template <>
struct AllOdd_<0> {
  constexpr static bool value = is_odd<0>;
};

• Metafunction is_odd:

  • Determines if a number N is odd.
  • Defined using a simple modulus operation: constexpr bool is_odd = ((N % 2) == 1);.

• Recursive Template AllOdd_:

  • Recursively evaluates if all numbers from 0 to N are odd.
  • Uses is_odd to check if the current number N is odd.
  • Recursively checks if all previous numbers are odd using AllOdd_<N - 1>.
  • Implements logical AND to combine results: constexpr static bool value = is_cur_odd && is_pre_odd;.

• Specialization for Base Case:

  • Base case for the sequence when N is 0, using AllOdd_<0> to start the recursion.
  • Ensures that the sequence includes the evaluation of 0 being odd or not.

• Compiler Instantiations:

  • Each recursive call results in a new instantiation of the AllOdd_ template for each decrement of N until reaching 0.
  • This process results in N + 1 instantiations total, one for each number in the sequence from 0 to N.

• Lack of Short Circuiting:

  • Despite the logical AND operation, template metaprogramming does not utilize short circuit logic effectively.
  • The recursive instantiation proceeds regardless of intermediate results, potentially leading to unnecessary computations if any number in the sequence is not odd.

• The following is an improved version of the program (only the modified sections are listed here):

template <bool cur, typename TNext>
constexpr static bool AndValue = false;

template <typename TNext>
constexpr static bool AndValue<true, TNext> = TNext::value;

template <size t N>
struct Allodd_ {
  constexpr static bool is_cur_odd = is_odd<N>;
  constexpr static bool value = AndValue<is_cur_odd, Allodd_<N - 1>>;
};