Les templates (2/2)

Template Meta-Programming

Ce terme (TMP) est souvent utilisé pour désigner l'exécution de code à la compilation. Cela peut être vu comme un langage à part entière au sein du C++, où les classes sont des fonctions : leurs paramètres template sont les entrées, et leur contenu forment leur sortie.

template <int Tag>
struct tag_t {
    static constexpr int tag = Tag;
};

// Entrées
template <class A, class B>
struct sum_tags {
    // Sorties
    using type = tag_t<A::tag + B::tag>;
};

using arg1   = tag_t<2>;
using arg2   = tag_t<3>;
using f      = sum_tags<arg1, arg2>;
using result = f::type; // tag_t<5>

Ce langage possède beaucoup de propriétés des langages fonctionnels, notamment :

• Aucune variable ne peut être modifiée

• On ne dispose pas de boucles (on utilise la récursion)

• Les fonctions sont pures (elles retournent toujours la même chose avec les mêmes arguments)

• Cela implique qu'aucun effet de bord n'est possible

• Les branchements sont fait par pattern matching sur les types

• Certaines évaluations sont paresseuses (instanciées uniquement lorsqu'on a besoin d'elles)

Ces propriétés demandent de changer de paradigmes de programmation pour être à l'aise en TMP, et d'être très organisés dans le code pour ne pas se perdre étant donné la verbosité imposée par les templates.

La TMP est parfois comparée au langage fonctionnel Haskell, et la librairie Boost.Hana (qui est la librairie de TMP la plus récente et la plus complète) recopie les structures du Haskell et redirige vers la documentation Typeclassopedia (écrite pour le Haskell).

Substitution Failure Is Not An Error

Substitution Failure Is Not An Error (SFINAE) désigne le fait que des paramètres template déduits incorrects ne déclenchent pas une erreur de compilation, si une autre classe / type / valeur / fonction template correspond aux arguments (trouvée par pattern matching). Exemple :

// La substitution des types T::type1 et T::type2 peut échouer (si T ne définit
// pas ces types).
template <class T>
typename T::type1 use(T&&) { return {}; }
template <class T>
typename T::type2 use(T&&) { return {}; }

struct Both { using type1 = int; using type2 = float; };
struct T1   { using type1 = char; };

int main() {
    // Erreur : appel ambigu ('use' est déclaré deux fois).
    // use(Both{});
    
    // La seconde fonction 'use' est ignorée : par d'erreurs.
    use(T1{});
    
    // Aucune fonction 'use' valide n'est trouvée.
    // use(int{});
}

std::void_t est alors utilisé comme un alias de void pour pouvoir spécialiser une classe ou une valeur template, si des arguments template dépendant sont corrects :

std::declval<T>() est une fonction qui est utilisée dans des tests de types (souvent avec decltype). C'est une fonction qui n'a pas de définition.

template <class...>
using void_t = void;

template <class T>
std::add_rvalue_reference_t<T> declval() noexcept;

// Dans le cas général, T1 et T2 ne peuvent pas s'additionner.
template <class T1, class T2, class SFINAE = void>
constexpr bool can_be_added = false;

// La spécialisation est choisie par défaut (plus prioritaire).
// Cependant, elle et ignorée si l'expression 'T1 + T2' n'est pas valide.
template <class T1, class T2>
constexpr bool can_be_added<T1, T2, void_t<decltype(
    declval<T1 const&>() + declval<T2 const&>()
)>> = true;

static_assert(can_be_added<float, int>);
static_assert(!can_be_added<void, int>);

std::enable_if_t est un alias d'une classe donnée (void par défaut) qui est incorrect si son paramètre booléen template s'évalue à false. C'est utilisé pour supprimer des templates selon des conditions connues à la compilation :

template <bool Enabled, class T = void>
struct enable_if {};

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

// Ce type déduit sera valide uniquement si Enabled est évalué à true.
template <bool Enabled, class T = void>
using enable_if_t = typename enable_if<Enabled, T>::type;


// ici, enable_if_t alias le type de retour (void).

// Sérialisation de types dans le cas général.
// On requiert implicitement 'operator<<(std::ostream&, T const&)'.
template <class T>
enable_if_t<!std::is_trivially_copyable_v<T>>
serialize(std::ostream& os, T const& data) {
    os << data;
}

// Les types TriviallyCopyable peuvent être sérialisés automatiquement :
// on copie leur représentation en mémoire.
template <class T>
enable_if_t<std::is_trivially_copyable_v<T>>
serialize(std::ostream& os, T const& data) {
    auto src = reinterpret_cast<char const*>(&data);
    os.write(src, sizeof(T));
}

std::enable_if peut également contenir une expression incorrecte, auquel cas on le même résultat qu'avec Enabled == false.

Un pattern est souvent utilisé pour tester la validité d'une expression, et sera implémenté avec std::is_detected_v en C++20 : il indique à la compilation si le type template est valide avec les arguments passés.

namespace detail {
     // Par défaut, le template général dit que l'expression n'est pas valide.
     template <template <class...> class Expression, class SFINAE, class...Ts>
     constexpr bool is_detected = false;
     
     // Si l'expression arrive à être instantiée avec les paramètres donnés, cette
     // spécialisation est choisie, qui dit alors que l'expression est valide.
     template <template <class...> class Expression, class...Ts>
     constexpr bool is_detected<
          Expression,
          std::void_t<Expression<Ts...>>,
          Ts...
     > = true;
}

// L'utilisation publique du template évite de passer 'void' à la main pour
// correspondre au paramètre testé avec SFINAE.
template <template <class...> class Expression, class...Ts>
constexpr bool is_detected = detail::is_detected<Expression, void, Ts...>;


template <class T1, class T2>
using addition_expression = decltype(
     std::declval<T1 const&>() + std::declval<T2 const&>()
);

static_assert(!is_detected<addition_expression, int, std::vector<int>>);
static_assert( is_detected<addition_expression, int, float>);

Le mécanisme SFINAE induit un surcoût lors de la compilation. En cas de ralentissement notable, on préfèrera donc si possible d'autres méthodes (comme le tag dispatch).

Fold expressions

Les variadic templates doivent normalement être traités avec de la récursion. Cependant, cela peut demander de la redondance dans le code, et les fonctions imbriquées peuvent gêner le debugging.

Depuis C++17, les fold expressions permettent d'appliquer une récursion de manière automatique, en utilisant un des opérateurs binaires autorisés (il peut s'agir d'une redéfinition d'opérateur).

Dans l'exemple suivant, on utilise std::index_sequence<Is...> pour passer les entiers de 0 à size(tuple) - 1, afin d'accéder aux éléments du tuple avec std::get<I>. std::make_index_sequence<N> est un alias pour std::index_sequence<0, 1, ..., N-1>.

namespace detail {
    // Affiche tous les éléments du tuple passé avec une fold expression.
    template <size_t...Is, class...Ts>
    void print_tuple(
        std::ostream& os,
        std::tuple<Ts...> const& tuple,
        std::index_sequence<Is...>)
    {
        // Fold expression (avec l'opérateur ',').
        (..., (os << ", " << std::get<Is + 1>(tuple)));
    }
}

template <class...Ts>
std::ostream& operator<<(
    std::ostream& os,
    std::tuple<Ts...> const& tuple)
{
    os << "{ ";
    if constexpr (sizeof...(Ts) > 0) {
        os << std::get<0>(tuple);
        // Construit 'std::index_sequence<0, 1, ..., sizeof...(Ts) - 2>'.
        // Utilisé par print_tuple pour déduire les arguments templates.
        constexpr auto seq = std::make_index_sequence<sizeof...(Ts) - 1>{};
        detail::print_tuple(os, tuple, seq);
    }
    return os << " }";
}

Pour aller plus loin

D'autres outils de la librairie standard peuvent être utiles pour simplifier la TMP, comme std::conditionnal_t<Bool, T1, T2> qui alias T1 ou T2 selon la valeur de Bool.

Apprendre un langage fonctionnel comme le Haskell permet de mieux comprendre certaines librairies et d'améliorer ses compétences en TMP.

Les expression template permettent d'optimiser des calculs en rendant leur évaluation paresseuse, et en évitant notamment la création d'objets temporaires.

C++20 (ou C++23) apportera la réflexion à la compilation, ce qui permettra d'analyser et de modifier des types durant la compilation. Cela permettra de simplifier beaucoup de tests effectués via SFINAE et apportera de nouvelles fonctionnalités utilisables à la compilation.

Challenges

(**) Implémenter les booléensis_iterator<T> et is_iterable<T>. Exemple :

static_assert(!is_iterator<int>);
static_assert( is_iterator<int*>);
static_assert(!is_iterable<int*>);
static_assert( is_iterable<std::list<int>>);

(*) Créer la fonction template nth_times qui exécute un function object N fois. Aucune boucle ne doit être utilisée : nth_times<200>(f) va donc copier coller l'appel à f 200 fois.

void execute();

int main() {
    nth_times<5>(execute);
    // Equivalent de :
    // execute();
    // execute();
    // execute();
    // execute();
    // execute();
}

Les compilateurs savent dérouler une boucle for classique quand ses paramètres sont connus à la compilation. nth_times sert donc ici uniquement d'exercice.