Pousser plus à fond la métaprogrammation

Ce qui suit donne quelques pistes de métaprogrammation avec C++. Notez que depuis C++ 11, qui standardise plusieurs pratiques que nous faisions auparavant de manière « manuelle », il est bien plus simple de faire plusieurs des manoeuvres décrites ici que ce ne l'était auparavant. Si votre compilateur le permet, privilégiez les approches C++ 11 et n'utilisez celles de C++ 03 que pour comprendre comment on arrivait à faire de même (ou à obtenir des résultats similaires) par le passé... ou encore, si votre compilateur n'est pas à jour.

L'un des sujets les plus passionnants en programmation contemporaine est la métaprogrammation, qui est utile en Java et en C# avec les generics de chacun de ces langages mais qui atteint véritablement ses lettres de noblesse avec les templates de C++.

Certains individus, en particulier (sans donner une liste exhaustive) Andrei Alexandrescu, concepteur de la bibliothèque Loki; Todd Veldhuizen, concepteur de la bibliothèque Blitz++, et Jaakko Järvi, John Maddock de même que David Abrahams et Aleksey Gurtovoy, ces derniers concepteurs de la bibliothèque MPL et tous trois faisant partie de l'équipe de concepteurs derrière Boost, ont poussé l'idée de la métaprogrammation beaucoup plus loin.

L'idée originale derrière la métaprogrammation à l'aide de templates en C++ est en général attribuée à Erwin Unruh, qui a écrit en 1994 un programme qui avait la particularité de ne pas compiler sans erreur mais de générer dans ses messages d'erreur la liste des nombres premiers jusqu'à un certain seuil et a présenté ce programme devant le comité de standardisation ISO du langage C++.

Le constat d'Unruh saisit les gens présents ce jour-là : le métalangage des templates en C++ est un langage complet au sens de Turing. Implication de ce constat : tout programme susceptible d'être exprimé en C++ à l'exécution l'est aussi, théoriquement, dans son métalangage et donc d'être évalué à la compilation.

Todd Veldhuizen, inspiré de cette trouvaille, a par la suite développé plusieurs techniques autour de l'idée de base et a transformé ce chic truc de métaprogrammation en une discipline de programmation à part entière, le tout dans l'optique d'écrire une bibliothèque en C++ (Blitz++) capable de battre en terme de puissance de calcul des programmes Fortran optimisés à fins de calculs numériques.

Depuis lors, la métaprogrammation s'est développée à la fois en art et en catégorie de design à part entière. L'essentiel de cette section sera inspiré (ou carrément emprunté) des efforts des pionniers de ce champ fabuleux (du moins à mon avis; tout cela m'amuse beaucoup!) qui s'offre à nous.

Introduction aux calculs statiques

template <int N>
   struct Factorielle {
      enum { value = N * Factorielle<N-1>::value };
   };

template <>
  struct Factorielle<0> {
     enum { value = 1 };
};

#include <iostream>
// ...
int main() {
   using namespace std;
   // affiche 720
   cout << Factorielle<6>::value << endl;
}

Cette stratégie n'offre pas la souplesse de bien d'autres (on ne peut pas l'utiliser pour trouver la factorielle d'un entier N arbitraire choisi à l'exécution) mais elle nous indique, par son ouverture sur les calculs récursifs à la compilation, qu'il est possible d'examiner certains types d'opération sous un angle tout neuf.

Détail technique : la version ci-dessus utilise des constantes entières, ce qui est limitatif pour évaluer une factorielle (avec la capacité d'un int, présumant qu'il s'agisse d'un type entier signé sur 32 bits, la plus grosse factorielle évaluable est $12!$ ).

template <int N>
   inline double Facto() {
      return N * Facto<N - 1>();
   }
template <>
   inline double Facto<0>() {
      return 1.0;
   }
#include <iostream>
int main() {
   using namespace std;
   cout << Facto<50>() << endl;
}

Une version correcte utilisant un double pour cumuler la factorielle à la compilation serait celle proposée ci-dessous, avec la fonction Facto().

Traits et optimisation

Supposions que nous souhaitions réaliser une copie brute de données dans n tableau de bytes :

#include <cassert>
#include <algorithm>
template <class T>
   char* copie_brute(char *dest, std::size_t capacite, const T &val) {
      using std::copy;
      assert(sizeof(T)<=capacite);
      auto p = reinterpret_cast<const char*>(&val);
      copy(p, p + sizeof(T), dest);
      return dest + sizeof(T);
   }

Ici, notre fonction copie les bytes de val un à un dans dest (présumant que la capacité de dest, dénotée ici par le paramètre capacite, soit suffisante). On serait tentés, du fait que nous copions les bytes un à un de manière brute et sans discrimination, de passer par une fonction de plus bas niveau telle que memcpy(). Ceci nous donnerait :

#include <cassert>
#include <cstdlib>
template <class T>
   char* copie_brute(char *dest, std::size_t capacite, const T &val) {
      using std::memcpy;
      assert(sizeof(T)<=capacite);
      memcpy(dest, p, sizeof(T));
      return dest + sizeof(T);
   }

Toutefois, avant de recourir à des fonctions plus primitives (ce qui peut obscurcir le code), mieux vaut valider qu'il y ait bel et bien un avantage à le faire. Ici, si vous faites le test avec un compilateur contemporain, il est possible que vous constatiez... en fait, qu'il n'y a aucun gain de vitesse, donc que les deux livrent la même marchandise.

Comment cela est-il possible? Après tout, std::copy() s'exprime (naïvement) comme suit :

// ...
namespace std {
   // ...
   template <class InIt, class OutIt>
      void copy(ItIt debutSrc, InIt finSrc, OutIt debutDest) {
         for(; debutSrc != finSrc; ++debutSrc, ++debutDest)
            *debutDest = *debutSrc;
      }
   // ...
}

Il se trouve toutefois que le comportement observable auquel l'algorithme est tenu serait respecté si copy() passait par memcpy() dans le cas où :

• Les séquences source et destination sont définies par des itérateurs de catégorie Random Access, et
• Le type des éléments pointés par chacun est un byte (dans les autres cas, il pourrait y avoir des constructeurs ou des opérateurs d'affectation plus appropriés)

Il y a peut-être d'autres règles à respecter si nous voulons être rigoureux; de même, il y a peut-être d'autres cas d'optimisation possibles auxquels je n'ai pas pensé en rédigeant ceci. La beauté de la démarche est qu'il est probable que les gens en charge de votre version de la bibliothèque standard, eux, y aient réfléchi et vous évitent, au passage, des erreurs bêtes et des « optimisations » qui seraient en fait des pessimisations.

Supposons ces deux petites règles, qui sont une simplification du cas réel. On peut imaginer que std::copy() soit exprimé comme suit (exemple complet sur https://wandbox.org/permlink/oBSgKWjhwrHCfCtU) :

// ...
#include <type_traits>
#include <cstring>
#include <iterator>
namespace std { // note : n'ajoutez pas d'éléments à std:: dans du vrai code!
   // ...
   class raw_copying{};
   class per_element_copying{};
   template <class T>
      using iter_categ_t = typename std::iterator_traits<T>::iterator_category;
   template <class T>
      using iter_value_t = typename std::iterator_traits<T>::value_type;
   template <class T>
      using remove_const_t = typename std::remove_const<T>::type;
   template <class InIt, class OutIt>
      void copy(InIt debutSrc, InIt finSrc, OutIt debutDest, raw_copying) {
         using std::memcpy;
         using std::distance;
         memcpy(reinterpret_cast<char*>(debutDest),
                reinterpret_cast<const char*>(debutSrc),
                distance(debutSrc,finSrc)); // dans ce cas, distance() est O(1)
      }
   template <class InIt, class OutIt>
      void copy(InIt debutSrc, InIt finSrc, OutIt debutDest, per_element_copying) {
         for(; debutSrc != finSrc; ++debutSrc, ++debutDest)
            *debutDest = *debutSrc;
      }
   template <class InIt, class OutIt>
      void copy(InIt debutSrc, InIt finSrc, OutIt debutDest) {
         using std::conditional_t;
         using std::is_same_v;
         using std::random_access_iterator_tag;
         using std::remove_const_t;
         copy(debutSrc, finSrc, debutDest, conditional_t<
            is_same_v<iter_categ_t<InIt>, random_access_iterator_tag> &&
            is_same_v<iter_categ_t<OutIt>, random_access_iterator_tag> &&
            is_same_v<remove_const_t<iter_value_t<InIt>>, char> &&
            is_same_v<remove_const_t<iter_value_t<OutIt>>, char>,
            raw_copying, per_element_copying
         >{});
      }
   // ...
}

C'est pas simple (et probablement pessimiste), mais ce type de manoeuvre, où une fonction délègue le travail à une autre dès la compilation, sur la base des caractéristiques des types impliqués, est un cas type de métaprogrammation pour fin d'optimisation. C'est le rôle de fonctions comme std::copy() de faire les tests appropriés (pas plus, pas moins) et de réaliser des optimisations de manière sous-jacente à coût zéro. Conséquemment, à moins que vous n'ayez mesuré (à partir de binaires compilés à pleine optimisation!) et constaté un véritable problème, préférez les algorithmes standards aux optimisations maison. Et si vous constatez un véritable problème, signalez-le aux gens en charge de votre version de la bibliothèque standard!

Pratiques de nommage

Brève parenthèse sur les pratiques de nommage en métaprogrammation avec C++. La convention est :

• De faire en sorte que le type interne d'un trait se nomme type. Par exemple, ajouter_const<T>::type est le type correspondant à T, mais auquel la qualification const aurait été ajoutée (si elle n'y était pas déjà), et
• De faire en sorte que la valeur (constante) interne se nomme value. Par exemple, possede_constructeur_defaut<T>::value sera true seulement si T expose un constructeur par défaut

Règle générale, il est bien vu d'avoir des traits simple, ne contenant qu'un minimum de types ou de valeurs (idéalement, une de l'une ou de l'autre), plutôt que des traits complexes regroupant un agrégat de types et de constantes (comme dans l'exemple traits_types<T>, plus bas). Suivant les saines pratiques générales de programmation, on préférera une entité, une vocation.

template<class T>
   void f(T & val) {
      using type_sans_const = typename std::remove_const<T>::type;
      // ...
   }

template<class T>
   void f(T & val) {
      using type_sans_const = std::remove_const_t<T>;
      // ...
   }

template<class T>
   void f(T &val) {
      if (is_const<T>::value)
         // ...
   }

template<class T>
   void f(T &val) {
      if (is_const_v<T>)
         // ...
   }

Mise en situation – Portabilité sans macros

Imaginons du code se voulant portable à plusieurs plateformes (Macintosh, Linux sur plusieurs plateformes matérielles, Windows 32 bits comme 64 bits, etc.). Il est possible que certains éléments de programmes reposent sur l'utilisation de types précis, comme par exemple sur des entiers signés encodés sur 32 bits.

Il est possible de définir par une macro-instruction un nom qui soit utilisable dans le programme et qui corresponde au type désiré, à l'aide de définitions conditionnelles et du préprocesseur. L'exemple suivant en est une illustration :

// ...
// présumons que SGI expose des short sur 32 bits et des int sur 64 bits
#if defined(__sgi)
typedef short entier32;
// un alias parmi plusieurs possibles. On pourrait utiliser les alias définis
// dans les bibliothèques de Windows aussi
#elif defined (WIN32)
typedef int entier32;
// sous Windows 64 bits, les int sont 32 bits mais les pointeurs sont 64 bits...
#elif defined (WIN64)
typedef int entier32;
// etc.
#endif

Plusieurs structures sont possibles (par exemple l'utilisation de macros avec #define plutôt que des alias avec typedef ou, pour du code plus contemporain, avec using) et je ne prétends pas que l'exemple ci-dessus soit correct. Il est simplement illustratif et montre la forme typique de ce genre de manoeuvre.

Par expérience, préparer son code ainsi est pénible et complexe, pour plusieurs raisons d'ailleurs :

• Les macros sont dangereuses et on cherche à les éviter le plus possible, du fait qu'une erreur à l'invocation du compilateur peut transformer le code source de manière silencieuse (ce qui peut nuire énormément au cycle de développement)
• Les cas à examiner sont multiples et varient selon le compilateur, selon la plateforme et selon les bibliothèques. Mis à part quelques macros standardisées (__cplusplus, par exemple), rien ne dit que les macros disponibles sur un compilateur donné et en incluant une bibliothèque donnée (p. ex. : la macro WORD définie dans windows.h) existera pour un autre compilateur ou avec une autre bibliothèque – ou pire, rien ne dit que deux macros de même nom sur deux plateformes distinctes auront le même sens, ainsi
• Le nombre de cas à couvrir explose rapidement et de manière potentiellement exponentielle. Ceci augmente les risques d'erreur humaine, et résulte en du code dont l'évolutivité est extrêmement pénible à gérer

Une meilleure solution serait d'identifier le bon type pour le compilateur en fonction duquel le code est généré mais à partir de code pur C++, indépendant du compilateur, des bibliothèques et du système d'exploitation.

Voici une stratégie simple montrant comment on pourrait y arriver. Disons, pour simplifier le propos (et pour ouvrir la porte à des exercices de raffinement), que nous présumons que sur toute plateforme en fonction de laquelle nous sommes susceptibles de générer notre code, le type short sera encodé sur 32 bits ou le type int sera encodé sur 32 bits.

Nous voudrons définir le type int_32::type de manière à ce qu'il soit équivalent à short si le type short est encodé sur 32 bits et de manière à ce qu'il soit équivalent à int dans le cas contraire. Nous ne voulons pas avoir recours à une macro pour y arriver.

Alternatives statiques

Au fond, ce que nous voulons, c'est une alternative (un if...else) évaluée à la compilation. Une alternative statique, généralisation du cas de la sélection statique de types.

template <bool, class, class>
   struct static_if_else;
template <class SiVrai, class SiFaux>
   struct static_if_else <true, SiVrai, SiFaux> {
      using type = SiVrai;
   };
template <class SiVrai, class SiFaux>
   struct static_if_else <false, SiVrai, SiFaux> {
      using type = SiFaux;
   };
template <bool conde, class SiVrai, class SiFaux>
   using static_if_else_t = typename static_if_else<cond,siVrai,SiFaux>::type;

Le code, en soi, est très simple :

• La spécialisation de static_if_else pour un booléen vrai définit un type interne et public type correspondant au type à utiliser si la condition est vraie, et
• La spécialisation de static_if_else pour un booléen faux définit un type interne et public type correspondant au type à utiliser si la condition est fausse

Cette stratégie est belle à plusieurs égards :

• Elle est entièrement indépendante de la plateforme, étant écrite en C++ standard et n'impliquant aucune macro portable ou non
• Elle a un coût nul à l'exécution, étant pleinement évaluée à la compilation du programme et n'impliquant que des types, aucune donnée (donc aucun espace supplémentaire en mémoire), et bien entendu
• Expose comme résultat un type tout à fait légal et pleinement utilisable pour un programme C++ conforme au standard

using int_32 = conditional_t <
   sizeof(short)==4,
   short,
   int
>;
// ou encore, de manière équivalente
struct entier_32 {
   using type = conditional_t <
      sizeof(short)==4,
      short,
      int
   >;
};
using int_32 = entier_32::type;

Présumant que notre critère de sélection soit correct, alors le type à utiliser dans nos programmes serait int_32. On aurait aussi pu utiliser la version définissant int_32 à partir du type interne type d'un struct tel qu'entier_32, comme le montre la version alternative (plus haut).

On privilégiera habituellement la version avec struct et type interne dans le code de production, et ce pour des raisons pratiques : il est alors plus facile de regrouper sous un même chapiteau des données de diverses natures sur un entier 32 bits s'il existe un type enregistrement à cet effet.

Une solution générale au problème d'identifier un entier d'une taille donnée serait :

#include <type_traits>
class Illegal;
// si votre compilateur définit std::conditional_t, alors supprimez la définition suivante
template <bool C, class SiVrai, class SiFaux>
   using conditional_t = typename std::conditional<C,SiVrai,SiFaux>::type;
template <int N> // N == nb. bytes
   struct entier {
      using type = conditional_t<
         sizeof(char)==N, char,
         conditional_t<
            sizeof(short)==N, short,
            conditional_t<
               sizeof(int)==N, int,
               conditional_t<
                  sizeof(long)==N, long,
                  conditional_t<
                     sizeof(long long)==N, long long,
                     Illegal
                  >
               >
            >
         >
      >
   };
using int_16 = entier<2>::type;
using int_32 = entier<4>::type;

Métafonctions

La bibliothèque standard de C++ regorge de métafonctions, c'est-à-dire de petits traits qui réalisent un « traitement » statique sur un type ou sur une constante et qui « produisent » en retour un type ou une constante.

L'usage courant de métafonctions est de réduire leur portée : une bonne métafonction nous donnera un seul type ou une seule constante (parfois les deux). Par le passé, il arrivait fréquemment que des métafonctions ayant plusieurs « résultats » soient utilisées (pensons à std::numeric_limits ou à std::iterator_traits, qui livrent tous deux plusieurs informations sur un même type; si nous le réécrivions aujourd'hui, nous les séparerions sans doute en plusieurs métafonctions de portée plus limitée).

Ce qui suit présente deux exemples de métafonctions, l'une produisant une constante et l'autre produisant un type. Ces exemples visent à expliquer des techniques et pratiques de métaprogrammation typiques, et ne se veulent pas exhaustifs.

Vérifier la constance d'un type donné (et tests semblables)^[1]

Imaginons qu'un algorithme générique applicable à un type T donné doive prendre des dispositions particulières si T est qualifié const ou s'il ne l'est pas. Cela peut jouer un rôle dans certaines manoeuvres d'optimisation.

Évidemment, nous visons ici, comme toujours, une technique à coût zéro, en temps d'exécution comme en taille dans le programme.

Comme dans le cas de plusieurs techniques de métaprogrammation, nous définirons le cas général : pour un type T quelconque, nous dirons que la valeur de est_const sera fausse.

template <class T>
   struct est_const {
      enum { value = false };
   };
template <class T>
   struct est_const<const T> {
      enum { value = true };
   };
template <class T>
   struct est_const<const T*> {
      enum { value = true };
   };
template <class T>
   struct est_const<const T&> {
      enum { value = true };
   };

Tests sur les types et C++ 11

Avec C++ 11, une partie importante des techniques décrites ici est intégrée à même le standard, dans l'en-tête <type_traits>. Ainsi, par exemple, là où nous montrons dans cette section comment écrire est_const<T>::value, le standard implémente maintenant is_const<T>::value.

Si votre compilateur offre cet en-tête, privilégiez-le : bien que la plupart des traits de <type_traits> puissent être implémentés par programmation, certains d'entre eux seraient fastidieux, voire impossibles à implémenter manuellement et sont à la portée du compilateur (pensez à is_pod<T>::value, qui permet de savoir si T est un Plain Old Datatype). Évidemment, au besoin, vous pouvez appliquer les techniques décrites ici.

Pratiques en ce qui a trait aux traits prédicats

Pour est_const et plusieurs autres « traits prédicats », dont le principal rôle est de donner accès à une constante statique booléenne, l'usage consacré depuis les travaux de Dave Abrahams et Aleksey Gurtovoy (et mis en application dans le standard) est d'y aller par étapes. Tout ce qui suit existe et est rendu disponible dans l'espace nommé std par <type_traits> (ne le réécrivez pas; utilisez-le!).

template <class T, T val>
   struct integral_constant {
      using type = T;
      static constexpr const T = val;
   };

struct true_type : integral_constant<bool, true> {
};
struct false_type : integral_constant<bool, false> {
};

template <class T>
   struct est_const : false_type {
   };
template <class T>
   struct est_const<const T> : true_type {
   };
template <class T>
   struct est_const<const T*> : true_type {
   };
template <class T>
   struct est_const<const T&> : true_type {
   };

Supprimer la constance d'un type donné (et actions semblables)

Et s'il était important, pour un type T, de connaître la version non const de ce type? Évidemment, on souhaitera ici une solution homogène, telle que supprimer la constance de const int* et supprimer la constance de int* donne dans chaque cas le type int*, de manière à pouvoir définir des algorithmes pouvant tirer profit de cet outil sans être obligés de se préoccuper de cas particuliers.

Nous nommerons supprimer_const l'algorithme métaprogrammé nous permettant de connaître la version sans qualification const d'un type donné. Comprenons toutefois que ce que nous faisons ici est définir un type équivalent au type d'origine mais sans qualification const; nous ne modifions pas la qualification d'origine en tant que telle.

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

Suppression de qualifications sur un type avec C++ 11

Avec C++ 11, une partie importante des techniques décrites ici est intégrée à même le standard, dans l'en-tête <type_traits>. Ainsi, par exemple, là où nous montrons dans cette section comment écrire supprimer_const<T>::type, le standard implémente maintenant remove_const<T>::type ou mieux, avec un compilateur récent : remove_const_t<T>.

Application – Vérifier la primitivité d'un type donné^[2]

Comme la grande majorité des langages, C++ offre une gamme de types primitifs (int, float, char, etc.), tout en offrant (contrairement à beaucoup d'autres langages, incluant Java et C#) un support très homogène pour les types, génériques ou non, conçus à l'aide du langage (classes, enregistrements, unions, énumérations), que je nommerai ici types maison.

Une particularité des types primitifs est que lorsqu'on passe une instance d'un tel type en paramètre à un sous-programme qui n'aura pas à le modifier, il est préférable de le passer par valeur alors que la majorité des types maison sont, dans de telles situations, avantageusement passés par référence-vers-const dû au coût potentiellement élevé de la construction et de la destruction implicites résultant de la copie dans le cas d'un passage par valeur.

Cela dit, si un algorithme générique souhaite utiliser la convention la plus efficace possible dans tous les cas lorsqu'il passe un objet en paramètre à un autre sous-programme générique, comment peut-il déterminer ce que signifie la meilleure convention de passage de paramètre possible?

Une stratégie serait d'exprimer le problème sous cet angle : si le type est un type primitif, alors passe-le par valeur, sinon passe-le par référence-vers-const. Mais pour être en mesure de déterminer si un type est primitif ou non, il nous faudra travailler un peu.

Listes de types

Nous allons exprimer la question « T est-il un type primitif? » sous une autre forme, soit « T est-il dans la liste des types primitifs? » Et pour répondre à cette question, nous allons définir le sens à donner à « liste de types » et le sens à donner à la question « T est-il dans la liste des types primitifs? ».

Une liste de types, si on la prend de haut niveau, sera une liste au sens classique du terme, soit une tête suivi d'une queue. Placés dans une situation de métaprogrammation, manipulant non pas des objets mais leurs types, nous définirons l'idée de liste de types sous forme d'un type générique, puis nous définirons quelques algorithmes génériques métaprogrammés sur ce type (incluant, pour nos fins, un algorithme de recherche d'un type dans la liste) et nous définirons (entre autres) la liste des types primitifs.

Notez que nous n'instancierons aucun objet. Tout au long de notre travail, nous concevrons des types par multiprogrammation de telle sorte que les gains de qualité de code seront bien réels et que le coût à l'exécution sera zéro.

Idée de liste de types

template <class ...>
   struct type_list {
   };

Examinons quelques exemples. Notez que la liste des types utilisée est incomplète à la lueur du standard C++ 11, qui standardise entre autres de nouveaux types de caractères.

using types_caracteres = type_list <char, unsigned char, signed char, wchar_t>;
using types_entiers_numeriques =
   type_list <short, unsigned short, int, unsigned int, long, unsigned long, long long, unsigned long long>;
using types_virgule_flottante = type_list <float, double, long double>;

Quelques listes typiques :

• La liste de tous les types servant à encoder des caractères en C++
• La liste de tous les types entiers numériques (donc principalement voués à permettre des calculs)
• La liste des singletons d'un programme
• La liste de tous ceux qui, parmi les types primitifs, ont une représentation à virgule flottante, etc.

Opérations sur une liste de types

Nous savons donc comment définir l'idée de liste de types et nous sommes en mesure de l'utiliser pour définir d'autres types. évidemment, on ne peut s'arrêter là. Comme tout type, même métaprogrammé, cette structure de données n'est pertinente que si nous définissons des opérations s'y appliquant.

Calculer la longueur d'une liste de types

L'algorithme classique sur une liste est celui en calculant la longueur (au sens du nombre d'éléments de cette liste). Évidemment, cet algorithme s'exprime aisément : la longueur d'une liste vide est zéro, alors que la longueur d'une liste en général est un de plus que la longueur de sa queue.

Procédant par métaprogrammation, nous devrons exprimer cette idée récursivement et à l'aide de types et de constantes connues à la compilation seulement. Heureusement, cet algorithme s'exprime aussi aisément en code que verbalement.

template <class TList>
   struct static_length;
template <>
   struct static_length<type_list<>> : std::integral_constant<int, 0> {
   };
template <class T, class ... Q>
   struct static_length<type_list<T, Q...>> : std::integral_constant<int, 1 + sizeof...(Q)> {
   };

Ainsi :

• Si Q est Vide, alors il existe une spécialisation (le cas static_length<type_list<>>) pour la prendre en charge
• Si Q... a la forme de type_list<T,Q...>, alors il existe aussi une spécialisation (la version récursive) s'y appliquant
• Enfin, dans tous les autres cas, la forme à laquelle on cherche à appliquer static_length est illégale (on a peut-être cherché à utiliser static_length<int> alors que int n'est ni une liste de types, ni type_list<>) et le programme ne devrait pas compiler. C'est ce à quoi sert le tout premier cas : à stopper la compilation des cas pour lesquels il n'existe pas de spécialisation

En prenant l'exemple de la liste de types nommée types_caracteres, plus haut, l'expression static_length<types_caracteres>::value devrait être équivalente à la constante 4.

template <class>
   struct static_length;
template <class ... Ts>
   struct static_length<type_list<Ts...>> : std::integral_constant<int, sizeof...(Ts)> {
   };

Obtenir un type par son indice dans une liste de types

On voudra ensuite retrouver un type par son indice dans une liste de types. Nous procéderons selon la notation usuelle avec C et C++ pour les tableaux, notation semi ouverte débutant à 0. Nous ferons en sorte que les expressions illégales (comme chercher un float dans une liste d'entiers) ne compilent tout simplement pas.

Cette opération prendra en paramètre un entier (non signé) et révélera le type se situant à l'indice correspondant à cet entier dans la liste.

template <unsigned int, class TList>
   struct type_par_indice;

template <unsigned int i, class TL>
   using type_par_indice_t = typename type_par_indice<i, TL>::type;

template <class T, class ... Q>
   struct type_par_indice<0, type_list<T, Q...>> {
      using type = T;
   };
template <unsigned int i, class T, class ... Q>
   struct type_par_indice<i, type_list<T, Q...>> {
      static_assert(i <= sizeof...(Q), "i <= sizeof...(Q)");
      using type = type_par_indice_t<i - 1, type_list<Q...>>;
   };

En prenant l'exemple de la liste de types nommée types_caracteres, plus haut, l'expression type_par_indice<types_caracteres,2>::type, pour « type à l'indice 2 », sera équivalente à signed char.

Cet algorithme montre comment il est possible d'orchestrer un algorithme de recherche récursif à la compilation dans une liste de types. Voyons maintenant comment procéder de manière semblable pour obtenir des algorithmes encore plus utiles.

Obtenir l'indice d'un type dans une liste de types

Voyons maintenant comment retrouver l'indice de la première occurrence d'un type dans une liste de types. Nous procéderons selon la notation C et C++ usuelle pour les tableaux, notation à demi-ouverte débutant à 0, ce qui nous permettra entre autres d'exprimer l'absence d'un type dans une liste (avec l'indice -1, disons).

Cette opération prendra en paramètre le type dont on souhaite connaître l'indice dans la liste et son résultat sera un entier représentant l'indice de ce type dans la liste (ou -1 si le type recherché n'y apparaît pas).

template <class T, class TList>
   struct indice_par_type : std::integral_constant<int, -1> {
   };
template <class T, class ...Q>
   struct indice_par_type<T, type_list<T, Q...>> : std::integral_constant<int, 0> {
   };
template <class U, class T, class ...Q>
   struct indice_par_type<U, type_list<T, Q...>> {
   private: // type privé, une sorte de temporaire
      enum {
         RechercheDansQueue = indice_par_type<U, type_list<Q...>>::value
      };
   public: // l'indice en tant que tel
      enum {
         value = RechercheDansQueue == -1 ? -1 : 1 + RechercheDansQueue
      };
   };

La réponse à notre question

Nous sommes maintenant capables de résoudre notre problème initial, soit celui de vérifier si T est un type primitif.

En effet, présumant l'existence d'une liste de types nommée types_primitifs et listant tous les types primitifs, l'algorithme recherché sera tel que proposé ci-dessous.

template <class T>
  struct est_primitif : std::integral_constant<bool, indice_par_type<T, types_primitifs>::value != -1>   {
  };

Joli, n'est-ce pas? Un algorithme récursif à coût zéro qui identifie la primitivité ou non d'un type T et permet de manière générique de choisir la convention d'appel optimale pour un paramètre de ce type.

Fusionner des listes de types

template <class TL0, class TL1>
   struct static_merge;
template <class ... TL0, class ... TL1>
   struct static_merge<type_list<TL0...>, type_list<TL1...>> {
      using type = type_list<TL0..., TL1 ...>;
   };
template <class T, class ... TL>
   struct static_merge<T, type_list<TL...>> {
      using type = type_list<T, TL ...>;
   };
template <class T, class ... TL>
   struct static_merge<type_list<TL...>, T> {
      using type = type_list<TL ..., T>;
   };

template <class TL0, class TL1>
   using static_merge_t = typename static_merge<TL0, TL1>::type;

Supprimer un type d'une liste de types

template <template <class> class Pred, class TList>
   struct static_remove_if;

template <template <class> class Pred, class TList>
   using static_remove_if_t = typename static_remove_if<Pred, TList>::type;

template <template <class> class Pred, class T, class ... Q>
   struct static_remove_if<Pred, type_list<T, Q...>> {
      using type = std::conditional_t<
         Pred<T>::value,
         static_remove_if_t<Pred, type_list<Q...>>,
         static_merge_t<T, static_remove_if_t<Pred, type_list<Q...>>>
      >;
   };
template <template <class> class Pred, class T>
   struct static_remove_if<Pred, type_list<T>> {
      using type = std::conditional_t<
         Pred<T>::value, type_list<>, type_list<T>
      >;
   };


template <class T>
   struct is_ {
      template <class U>
         struct type : std::integral_constant<bool, std::is_same<T, U>::value>
         {
         };
   };

template <class T, class TList>
   struct static_remove {
      using type = static_remove_if_t<typename is_<T>::type, TList>;
   };

template <class T, class TList>
   using static_remove_t = typename static_remove<T, TList>::type;

Exemple – identifier le signe des types char et wchar_t

Question qui se pose sur toutes les plateformes : les types char et wchar_t sont-ils des types signés ou non signés?

using char_signe = std::conditional_t<
   static_cast<char>(-1)<0,
   char,
   type_list<>
>;
using char_non_signe = std::conditional<
   static_cast<char>(-1)>=0,
   char,
   type_list<>
>::type;

L'expression des types désirés est simple : type_list<> si la condition n'est pas rencontrée, et le type voulu dans le cas où la condition s'avère.

using types_entiers_signes_base = type_list<signed char, type_list <short, int, long, long long>;

using types_entiers_signes = static_merge_t <
   types_entiers_signes_base,
   static_merge_t <type_list<char_signe>, type_list<wchar_t_signe>>
>;

Ainsi, la liste des types entiers signés sera telle que proposé ci-dessus, peu importe la plateforme. Le même modèle s'appliquera à la liste des entiers non signés.

Concaténer deux listes

using types_signes = static_merge_t <
   types_entiers_signes, types_virgule_flottante
>;

Définir la liste des types primitifs

Présumant que définir la liste de types types_entiers contenant tous les types entiers (incluant bool et les types caractères) soit maintenant évidente à vos yeux, comment pourrait-on définir la liste des types primitifs, c'est-à-dire la concaténation de la liste des types entiers, de la liste des types à virgule flottante et du type void?

using types_primitifs = static_merge_t <
   types_entiers, static_merge_t<
      types_virgule_flottante, void
   >
>;

Définir des traits par type

Nous avons mis en place plusieurs outils pour nous guider dans nos travaux. Reste à voir comment en tirer vraiment profit, comme par exemple en permettant de déduire à la compilation la meilleure convention de passage de paramètres possible pour un type T donné.

template <class T>
   struct traits_types {
      enum {
         est_const = ::est_const<T>::value,
         est_volatile = ::est_volatile<T>::value,
         est_reference = ::est_reference<T>::value,
         est_primitif = ::est_primitif<T>::value,
         est_entier = ::est_entier<T>::value,
         est_virgule_flottante = ::est_virgule_flottante<T>::value,
         est_signe = ::est_signe<T>::value,
         est_non_signe = ::est_non_signe<T>::value,
         // ... 

// ...
   private:
      template <class U>
         struct traits_pointeur : std::false_type {
            using type_pointe = Vide;
         };
      template <class U>
         struct traits_pointeur<U*> : std::true_type {
            using type_pointe = U;
         };
      template <class>
         struct traits_pointeur_methode : std::false_type {
         };
      template <class U, class V>
         struct traits_pointeur_methode<U,V::*> : std::true_type {
         };
// ...

// ... 
   public:
      enum {
         est_pointeur = traits_pointeur<T>::value,
         est_pointeur_methode = traits_pointeur_methode<T>::value
      };
      using type_sans_const = typename supprimer_const<T>::type;
      using type_sans_reference = typename supprimer_reference<T>::type;
      using type_pointe = typename traits_pointeur<T>::type_pointe;
      using meilleur_type_parametre = std::conditional_t<
         est_pointeur || est_pointeur_methode || est_primitif,
         T,
         std::conditional_t<
            !est_reference,
            const type_sans_reference&,
            type_sans_reference&
         >
      >;
  };

Encore une fois, cette masse d'information sur un type T quelconque et sur le meilleur comportement à adopter avec un T dans un programme a été obtenue à la compilation, et n'entraîne pas le moindre coût à l'exécution d'un programme.

Complément – Énumérations ou constantes statiques?

Vous remarquerez qu'on utilise souvent en pratique des constantes énumérées (définies à partir de divers enum) plutôt que des static const pour définir des constantes entières. La raison est que, bien que certains compilateurs supportent cette écriture :

struct X {
   static const int value_I = 3;
   static const bool value_B = true;
};

... il se trouve qu'elle n'est pas permise par le standard C++ 98 (mais est légale avec C++ 03) ce qui limite la portabilité du code résultant, alors que cette écriture :

struct X {
   enum {
      value_I = 3, value_B = true
   };
};

... est légale sur tous les compilateurs.

Reliquats du passé

La métaprogrammation avec C++ n'a pas débuté avec C++ 11, bien au contraire. Depuis les années '90, les programmeuses et les programmeurs ont redoublé de créativité pour exploiter ce filon qu'est le métalangage des templates dans le but de tirer le maximum du langage et du compilateur (certains diront même que l'on parle ici d'abus, mais bon, quand on s'amuse...).

Ce qui suit dénote quelques-unes de ces manoeuvres auxquelles nous avions recours auparavant pour arriver à nos fins; à moins que les compilateurs auxquels vous avez accès ne soient pas à jour (ce qui rendrait ces tours de passe-passe pertinents pour vous), donc, ce qui suit n'a qu'un intérêt historique.

Listes de types avec avec C++ 03

Notez que nous n'instancierons aucun objet. Tout au long de notre travail, nous concevrons des types par multiprogrammation de telle sorte que les gains de qualité de code seront bien réels et que le coût à l'exécution sera zéro.

Idée de vide

Le premier pas dans la détermination d'une liste de types est de définir ce que signifie une liste vide, du fait qu'un algorithme permettant de parcourir une liste (pour ne donner qu'un exemple) doit s'arrêter éventuellement et que le meilleur moment pour s'arrêter est lorsque la queue de la liste est vide. Étant donné que le type void est primitif, nous ne souhaitons pas lui attribuer ce rôle particulier.

Comment représenter efficacement le vide? Mais par une classe (ou un struct) vide, voyons!

class Vide {}; // oui, tout simplement

La taille d'une instance de Vide ne sera pas 0 puisqu'en C++, hormis le cas particulier du Empty Base Class Optimization, tout objet occupe un espace d'au moins un byte (exprimé autrement,$\forall T(sizeof(T)>0)$). Cela ne nous préoccupera pas puisque Vide ne nous servira qu'à titre de concept. Nous n'instancierons jamais ce type, qui ne nous servira qu'à titre de type.

Idée de liste de types

template <class T, class U>
   struct type_list {
      using tete = T;
      using queue = U;
   };

template <class, class>
   struct type_list {
   };

Cette définition, à la fois simple, puissante et récursive, s'exprime aisément sous la forme proposée ci-dessous. Notez que la liste des types utilisée est incomplète à la lueur du standard C++ 11, qui standardise entre autres de nouveaux types de caractères, mais je n'ai pas encore entre les mains un compilateur me permettant de valider une éventuelle mise à jour. Cela viendra.

using types_caracteres = type_list <
   char, type_list <
      unsigned char, type_list <
         signed char, type_list <
            wchar_t, Vide
         >
      >
   >
>;

using types_entiers_numeriques = type_list <
   short, type_list <
      unsigned short, type_list <
         int, type_list <
            unsigned int, type_list <
               long, type_list <
                  unsigned long, type_list<
                     long long, type_list<
                        unsigned long long, Vide
                     >
                  >
               >
            >
         >
      >
   >
> 

using types_virgule_flottante = type_list <
   float, type_list <
      double, type_list <
         long double, Vide
      >
   >
>;

Quelques listes typiques :

• La liste de tous les types servant à encoder des caractères en C++
• La liste de tous les types entiers numériques (donc principalement voués à permettre des calculs)
• La liste des singletons d'un programme
• La liste de tous ceux qui, parmi les types primitifs, ont une représentation à virgule flottante, etc.

Remarquez que chacune des définitions de listes de types se termine par l'élément Vide, qui ne sert clairement qu'en tant que type et n'est jamais instancié (tel qu'annoncé). Pour simplifier la notation de listes comme celles-ci, la bibliothèque Loki a recours à des macros. Sous C++ 11, des templates variadiques allègent cette tâche.

Opérations sur une liste de types

Nous savons donc comment définir l'idée de liste de types et nous sommes en mesure de l'utiliser pour définir d'autres types. évidemment, on ne peut s'arrêter là. Comme tout type, même métaprogrammé, cette structure de données n'est pertinente que si nous définissons des opérations s'y appliquant.

Calculer la longueur d'une liste de types

L'algorithme classique sur une liste est celui en calculant la longueur (au sens du nombre d'éléments de cette liste). Évidemment, cet algorithme s'exprime aisément : la longueur d'une liste vide est zéro, alors que la longueur d'une liste en général est un de plus que la longueur de sa queue.

Procédant par métaprogrammation, nous devrons exprimer cette idée récursivement et à l'aide de types et de constantes connues à la compilation seulement. Heureusement, cet algorithme s'exprime aussi aisément en code que verbalement.

template <class>
   struct static_length;
template <>
   struct static_length<Vide> : std::integral_constant<int, 0> {
   };
template <class T, class Q>
   struct static_length<type_list<T, Q>> : std::integral_constant<int, 1 + static_length<Q>::value> {
   };

Ainsi :

• Si Q est Vide, alors il existe une spécialisation (le cas static_length<Vide>) pour la prendre en charge
• Si Q a la forme de type_list<T,Q>, alors il existe aussi une spécialisation (la version récursive) s'y appliquant
• Enfin, dans tous les autres cas, la forme à laquelle on cherche à appliquer static_length est illégale (on a peut-être cherché à utiliser static_length<int> alors que int n'est ni une liste de types, ni Vide) et le programme ne devrait pas compiler. C'est ce à quoi sert le tout premier cas : à stopper la compilation des cas pour lesquels il n'existe pas de spécialisation

En prenant l'exemple de la liste de types nommée types_caracteres, plus haut, l'expression static_length<types_caracteres>::value devrait être équivalente à la constante 4.

Obtenir un type par son indice dans une liste de types

On voudra ensuite retrouver un type par son indice dans une liste de types. Nous procéderons selon la notation usuelle avec C et C++ pour les tableaux, notation semi ouverte débutant à 0. Nous ferons en sorte que les expressions illégales (comme chercher un float dans une liste d'entiers) ne compilent tout simplement pas.

Cette opération prendra en paramètre un entier (non signé) et révélera le type se situant à l'indice correspondant à cet entier dans la liste.

template <class TList, unsigned int i>
   struct type_par_indice;
template <class T, class Q>
   struct type_par_indice<type_list<T,Q>,0> {
      using type = T;
   };
template <class T, class Q, unsigned int i>
   struct type_par_indice<type_list<T,Q>,i> {
      using type = typename type_par_indice<Q,i-1>::type;
   };

En prenant l'exemple de la liste de types nommée types_caracteres, plus haut, l'expression type_par_indice<types_caracteres,2>::type, pour « type à l'indice 2 », sera équivalente à signed char.

Cet algorithme montre comment il est possible d'orchestrer un algorithme de recherche récursif à la compilation dans une liste de types. Voyons maintenant comment procéder de manière semblable pour obtenir des algorithmes encore plus utiles.

Obtenir l'indice d'un type dans une liste de types

Voyons maintenant comment retrouver l'indice de la première occurrence d'un type dans une liste de types. Nous procéderons selon la notation C et C++ usuelle pour les tableaux, notation à demi-ouverte débutant à 0, ce qui nous permettra entre autres d'exprimer l'absence d'un type dans une liste (avec l'indice -1, disons).

Cette opération prendra en paramètre le type dont on souhaite connaître l'indice dans la liste et son résultat sera un entier représentant l'indice de ce type dans la liste (ou -1 si le type recherché n'y apparaît pas).

template <class TList, class T>
   struct indice_par_type;
template <class T>
   struct indice_par_type<Vide, T> : std::integral_constant<int, -1> {
   };
template <class T, class Q>
   struct indice_par_type<type_list<T, Q>, T> : std::integral_constant<int, 0> {
   };
template <class T, class Q, class U>
   struct indice_par_type <type_list<T, Q>, U> {
   private: // constante privée, une sorte de temporaire
      enum {
         pos_dans_queue = indice_par_type<Q, U>::value
      };
   public: // l'indice en tant que tel
      enum {
         value = pos_dans_queue == -1? -1 : 1 + pos_dans_queue
      };
   };

La réponse à notre question

Nous sommes maintenant capables de résoudre notre problème initial, soit celui de vérifier si T est un type primitif.

En effet, présumant l'existence d'une liste de types nommée types_primitifs et listant tous les types primitifs, l'algorithme recherché sera tel que proposé ci-dessous.

template <class T>
  struct est_primitif : std::integral_constant<bool, indice_par_type<types_primitifs, T>::value != -1> {
  };

Joli, n'est-ce pas? Un algorithme récursif à coût zéro qui identifie la primitivité ou non d'un type T et permet de manière générique de choisir la convention d'appel optimale pour un paramètre de ce type.

Insérer un type dans une liste de types

Le code ci-dessous est une mise à jour de celui provenant d'une version antérieure du présent article. Merci à Sébastien Lévy qui m'a signalé une erreur dans une version antérieure.

//
// cas général
//
template <class, class>
   struct static_insert;
//
// une liste et autre chose: on concatène la tête de la 1re liste avec
// la concaténation de la queue de la 1re liste et le reste, tiens
//
template <class T, class Q, TList>
   struct static_insert<type_list<T, Q>, TList> {
      using type = type_list<
         T, typename static_insert<Q, TList>::type
      >;
   };
//
// quand on a épuisé la 1re liste...
//
template <class T, class Q>
   struct static_insert<Vide,type_list<T,Q> > {
      using type = type_list<
         T, typename static_insert<Vide, Q>::type
      >;
   };
//
// ...et quand il ne reste plus rien...
//
template <>
   struct static_insert<Vide,Vide> {
      using type = Vide;
   };

Supprimer un type d'une liste de types

template <class TList, class T>
   struct static_remove;
template <class T>
   struct static_remove<Vide, T> {
      using type = Vide;
   };
template <class T, class Q>
   struct static_remove<type_list<T, Q>, T> {
      using type = Q ;
   };
template <class T, class Q, class U>
   struct static_remove<type_list<T, Q>, U> {
      using type = type_list<
         T, typename static_remove<Q, U>::type
      >;
   };

Exemple – identifier le signe des types char et wchar_t

Question qui se pose sur toutes les plateformes : les types char et wchar_t sont-ils des types signés ou non signés?

using char_signe = typename
   std::conditional<
      (static_cast<char>(-1)<0),
      char,
      Vide
   >::type;
using char_non_signe = typename
   std::conditional<
      (static_cast<char>(-1)>=0),
      char,
      Vide
   >::type;

L'expression des types désirés est simple : Vide si la condition n'est pas rencontrée, et le type voulu dans le cas où la condition s'avère.

using types_entiers_signes_base = type_list <
   signed char, type_list <
      short , type_list <
         int, type_list <
            long, type_list <
               long long, Vide
            >
         >
      >
   >
>;

using types_entiers_signes = typename
   static_insert <
      types_entiers_signes_base,
      static_insert <
         type_list <
           char_signe, Vide
         >,
         type_list <
           wchar_t_signe, Vide
         >
      >::type
   >::type;

Ainsi, la liste des types entiers signés sera telle que proposé ci-dessus, peu importe la plateforme. Le même modèle s'appliquera à la liste des entiers non signés.

Concaténer deux listes

using types_signes = typename
   static_insert <
      types_entiers_signes, types_virgule_flottante
   >::type;

Définir la liste des types primitifs

Présumant que définir la liste de types types_entiers contenant tous les types entiers (incluant bool et les types caractères) soit maintenant évidente à vos yeux, comment pourrait-on définir la liste des types primitifs, c'est-à-dire la concaténation de la liste des types entiers, de la liste des types à virgule flottante et du type void?

using types_primitifs = typename
   static_insert <
      types_entiers, typename
         static_insert <
            types_virgule_flottante,
            type_list<void, Vide>
         >::type
   >::type;

Lectures complémentaires

Wikis sur le sujet :

• Un qui ne se limite pas à la métaprogrammation en C++ : http://en.wikipedia.org/wiki/Metaprogramming
• Un plus spécifiquement sur la métaprogrammation avec C++ : http://en.wikipedia.org/wiki/Template_metaprogramming

Les métafonctions :

• http://www.boost.org/doc/libs/1_57_0/libs/mpl/doc/refmanual/metafunction.html
• Expliquées par David Abrahams et Aleksey Gurtovoy en 2004 : http://www.artima.com/cppsource/metafunctions.html

Réflexivité par métaprogrammation :

• Article de Giuseppe Attardi et Antonio Cisternino en 2000 (du moins, c'est l'impression que j'en tire de par la bibliographie) : http://lcgapp.cern.ch/project/architecture/ReflectionPaper.pdf
• Présentation de Daveed Vandevoorde en 2003 : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1471.pdf

Un chapitre du livre de Nicolai Josuttis et Daveed Vandevoorde sur la métaprogrammation en C++, en 2003 : http://www.informit.com/articles/article.aspx?p=30667

La bibliothèque MPL, de Boost : http://www.boost.org/doc/libs/1_57_0/libs/mpl/doc/index.html

Métaprogrammation avec constexpr, par Sumant Tambe en 2011 : http://cpptruths.blogspot.ca/2011/07/want-speed-use-constexpr-meta.html

Introduction à la métaprogrammation, par Nicolás Brailovsky en 2014 : https://monoinfinito.wordpress.com/series/introduction-to-c-template-metaprogramming/

La métaprogrammation avec C++ 11 bénéficie de plusieurs améliorations, décrites en partie par Andrzej Krzemieński dans ce texte de 2012 : http://akrzemi1.wordpress.com/2012/03/19/meta-functions-in-c11/

Texte de Paul Fultz II en 2015 à propos des types dépendants, mais avec une approche alternative à celles qui nous amènent à utiliser typename pour expliciter notre intention : http://pfultz2.com/blog/2015/01/24/dependent-typing/

Une petite bibliothèque de métaprogrammation proposée par Eric Niebler en 2014 : http://ericniebler.com/2014/11/13/tiny-metaprogramming-library/

Métaprogrammation et théorie des nombres, par Zeeshan Amjad en 2007 : http://www.codeguru.com/cpp/cpp/algorithms/math/article.php/c14087/Template-Meta-Programming-and-Number-Theory.htm

Série d'articles d'introduction à la métaprogrammation en C++, bien écrits d'ailleurs, par Manu Sánchez :

• Introduction, texte de 2014 : http://blog.biicode.com/template-metaprogramming-with-modern-cpp-introduction/
• Les templates plus en profondeur, texte de 2014 : http://blog.biicode.com/template-metaprogramming-cpp-ii/
• La métaphore d'Haskell, texte de 2014 : http://blog.biicode.com/template-metaprogramming-modern-cpp-haskell-metaphor/
• Une petite bibliothèque de métaprogrammation :
  • l'idée et les grands principes, texte de 2014 : http://blog.biicode.com/tiny-metaprogramming-library/
  • métafonctions, texte de 2015 : http://blog.biicode.com/a-tiny-metaprogramming-lib-metafunctions/
  • Boxing, texte de 2015 : http://blog.biicode.com/tiny-metaprogramming-library-boxing-1/

Techniques pour raffiner l'écriture de programmes métaprogrammés, et accélérerant la compilation ou en améliorant la syntaxe :

• En 2013, Justin Berger discute de l'accélération de la compilation de programmes utilisant applyTuple(f,tup) : http://www.metaxcompile.com/blog/2013/03/30/Faster-template-compilation.html
• Métaprogrammation inspirée de Factor, texte de 2012 : https://pubby8.wordpress.com/2012/10/15/stack-based-template-metaprogramming-in-c-11/
• Métaprogrammation sans douleur, par le brillant Louis Dionne en 2014 : http://ldionne.github.io/mpl11-cppnow-2014/

Des handles qui soient Type-Safe, sur la base de types utilisés en lieu de constantes, par Emil Ernerfeldt en 2014 : http://www.ilikebigbits.com/blog/2014/5/6/type-safe-identifiers-in-c

Le λ-calcul à la compilation, texte de 2014 : http://kukuruku.co/hub/cpp/interpreting-when-compiling-or-an-alternative-understanding-of-lambdas-in-c-11

Le Pigeonhole Principle par métaprogrammation, un texte de Sumant Tambe en 2014 : http://cpptruths.blogspot.ca/2014/05/the-pigeonhole-principle-in-c.html

Exemples d'applications de la métaprogrammation, parfois brillantes, parfois discutables (mais intéressantes) :

• Un jeu de la vie, par Matt Bierner en 2014 : http://blog.mattbierner.com/stupid-template-tricks-the-life-comonadic/
• Un Snake, par Matt Bierner en 2014 : http://blog.mattbierner.com/stupid-template-tricks-snake-part-2-interactive-nibbler/
• Un générateur de nombres pseudoaléatoires, par Matt Bierner en 2014 : http://blog.mattbierner.com/stupid-template-tricks-compile-time-pseudo-random-number-generator/
• Un processeur de langages, par Matt Bierner en 2015 : http://blog.mattbierner.com/stupid-template-tricks-pride-and-parser-combinators-part-one/
• Un programme générant FizzBuzz à l'aide d'erreurs de compilation, par Adam Tornhill en 2007 : http://www.adamtornhill.com/articles/fizzbuzz.htm
• Quelques exemples proposés par Andrey Budnik : https://github.com/abudnik/tcalc
• Abuser du compilateur en profitant du fait que les templates sont Turing-Complete, texte de Miklós Homolya en 2014 : https://mysticalprogramming.wordpress.com/2014/03/19/how-to-abuse-a-cpp-compiler/
• Métaprogrammer une machine virtuelle, texte de 2013 par Guillaume Sanchez : http://vermeille.fr/dotclear2/index.php/post/23-Metaprogramming-a-full-Virtual-Machine
• Un shell pour métaprogrammer interactivement (oui, oui!) avec C++, par Abel Sinkovics et Andras Kucsma : http://abel.web.elte.hu/shell/
• Pour une variante sur static_if_else, utilisant le Currying bien connu des aficionados de programmation fonctionnelle, voir ce texte de 2015 : https://constexpr.wordpress.com/2015/02/23/c11-template-currying/
• Un Tetris métaprogrammé (oui, sans blagues), par Matt Bierner en 2015 : http://blog.mattbierner.com/stupid-template-tricks-super-template-tetris/

Métaprogrammation en C++ avec inspiration provenant de Haskell, par Manu Sánchez en 2015 : http://manu343726.github.io/c++/haskellizing-tmp/

#include <iostream>
using namespace std;
template <int ... Ns>
   struct ints {
   };
template <int N, int ... Ns>
   struct int_seq : int_seq <N - 1, N, Ns...> {
   };
template <int ... Ns>
   struct int_seq <0, Ns...> {
      using type = ints<0, Ns...>;
   };
template <int N>
   using int_seq_t = typename int_seq<N>::type;
template <int ... Ns>
   void afficher(ints<Ns...> &&) {
      for (auto val : { Ns ... })
         cout << val << ' ';
      cout << endl;
   }
int main() {
   afficher(int_seq_t<5>{}); // 0 1 2 3 4 5
}

Truc de Nicolas Brailo en 2015 pour remplacer des séquences d'alternatives par un mécanisme de métaprogrammation : https://monoinfinito.wordpress.com/2015/05/05/c-a-jump-table-with-a-template-device/

Paul Watt explique, dans ce texte de 2015, comment il a modernisé son code métaprogrammé avec des templates variadiques : http://codeofthedamned.com/index.php/c-meta-template-programming-2

Petite présentation de métaprogrammation contemporaine par Peter Dimov en 2015 :

• http://pdimov.com/cpp2/simple_cxx11_metaprogramming.html
• http://pdimov.com/cpp2/simple_cxx11_metaprogramming_2.html

La bibliothèque Boost.Hana, de Louis Dionne, qui met de l'avant plusieurs techniques de métaprogrammation particulièrement fécondes :

• http://ldionne.com/hana/
• http://ldionne.com/hana/index.html#tutorial-quickstart

Série d'articles sur la métaprogrammation en C++, par Niels Deppe en 2017 :

• http://nilsdeppe.com/posts/tmpl-part1
• http://nilsdeppe.com/posts/tmpl-part2
• http://nilsdeppe.com/posts/tmpl-part3
• http://nilsdeppe.com/posts/tmpl-part4

Exercices

EX00 – Référez-vous à la présentation de static_if_else dans la section Portabilité sans macros. L'exemple proposé définissait entier_32::type comme étant équivalent à short si le type short était encodé sur 32 bits et comme étant équivalent à int dans le cas contraire. Il se trouve que cette stratégie est incomplète :

• Certaines plateformes peuvent offrir des types short et int tous deux de 16 bits et offrir un long sur 32 bits, de même
• Certaines plateformes peuvent offrir des types short, int et long tous encodés sur 64 bits, et il faudrait dans un tel cas empêcher la compilation du programme pour permettre aux informaticien(ne)s de revoir certaines stratégies de design

L'exercice est donc de raffiner la définition du type entier_32 pour qu'y soient considérés équivalents entier_32::type et le premier type entier signé encodé sur 32 bits parmi short, int et long. Faites en sorte que le programme ne compile tout simplement pas si aucun de ces trois types n'est encodé sur 32 bits.

Plusieurs stratégies sont possibles pour réaliser cet exercice. Vous avez toute la latitude désirée dans la mesure où vous n'utilisez pas de macros. Expliquez comment vous avez testé votre version de entier_32.

EX01 – Référez-vous à la présentation de est_const, et définissez est_volatile.

EX02 – Référez-vous à la présentation de est_const, et définissez est_reference. Quelles sont les différences entre les solutions de EX01 et de EX02.

EX03 – Référez-vous à la présentation de supprimer_const et définissez supprimer_volatile.

EX04 – Référez-vous à la présentation de supprimer_const, et définissez supprimer_reference. Y a-t-il des différences de fond entre les solutions à EX03 et à EX04? Si oui, lesquelles? Sinon, pourquoi?

EX05 – Référez-vous à la présentation de static_insert. Est-il possible d'exprimer l'insertion en début de liste plutôt qu'en fin de liste comme le propose notre exemple? Si oui, indiquez comment. Sinon, expliquez pourquoi.

EX06 – Référez-vous à la présentation de static_remove, plus haut, et exprimez l'algorithme supprimer_tous qui supprime toutes les occurrences d'un type T dans une liste de types.

EX07 – Exprimez l'algorithme supprimer_doublons qui supprime tous les doublons d'un type T dans une liste de types de telle sorte que la liste résultante ne comprenne plus qu'une seule occurrence de ce type, et soit tel que la liste résultante ne contienne aucune occurrence de ce type si elle n'en contenait aucune au préalable.

EX08 – Exprimez l'algorithme remplacer_un qui remplace la première occurrence d'un type T par un type U dans une liste de types.

EX09 – Exprimez l'algorithme remplacer_tous qui remplace chaque occurrence d'un type T par une occurrence d'un type U dans une liste de types.

EX10 – Dans la section Idée de vide, plus haut, nous mentionnons qu'il est possible d'exprimer une assertion statique de manière à ce que l'erreur à la compilation provoquée par une condition fausse soit due à la déclaration d'un tableau de char de taille 0. Sans que ce soit la meilleure technique à appliquer en pratique, exprimez votre propre template AssertionStatique de cette manière. Discutez du pour et du contre de cette approche en comparaison avec celle exprimée ici.

^[1] La technique décrite dans cette section (et ses multiples cousines) est si utile en programmation générique qu'elle sera intégrée au standard C++ 11. En attendant, vous saurez comment le faire par vous-mêmes!

^[2] Cette section est très, très fortement inspirée des travaux de Andrei Alexandrescu sur la bibliothèque Loki. Les explications sont de moi mais l'idée est de lui. Pour en savoir plus, voir son très intéressant livre Modern C++ Design.