Metaprogrammation avec des patrons

La métaprogrammation avec des patrons est une technique de programmation dans laquelle les patrons sont utilisés de sorte que le compilateur, lors de la compilation du code, exécute un programme. Ces programmes peuvent générer des constantes ou des structures de données. Cette technique est utilisée principalement dans le langage de programmation C++.

Calcul de constantes

L'exemple simple de calcul de factorielle avec récursion illustre bien ce qu'est la "programmation lors de la compilation".

En C++, une fonction factorielle peut être écrite récursivement comme suit:

int factorielle(unsigned int n) 
{
   if (n == 0)
     return 1;
   return n * factorielle(n - 1);
}
 
// factorielle(4) == (4 * 3 * 2 * 1) == 24
// factorielle(0) == 0! == 1

En utilisant la métaprogrammation avec des patrons, on peut écrire:

template <unsigned int N>
struct Factorielle 
{
   enum { valeur = N * Factorielle<N - 1>::valeur };
};
 
template <>
struct Factorielle<0> 
{
   enum { valeur = 1 };
};
 
// Factorielle<4>::valeur == 24
// Factorielle<0>::valeur == 1

La solution de la métaprogrammation avec des patrons utilise la spécialisation de patron pour terminer la récursion. Bien que ces deux solutions soient similaires, dans le deuxième cas, Factorielle<4>::valeur est calculé lors de la compilation. Cela implique que Factorielle<x>::valeur ne peut être utilisé que si x est connu lors de la compilation, c'est-à-dire si x est une constante ou le résultat d'un appel à sizeof().

En D, le patron factorielle ressemblerait à:

template Factorielle(unsigned int n)
{
    static if (n == 1)
        const Factorielle = 1;
    else
        const Factorielle = n * Factorielle!(n-1);
}
// Factorielle!(4) == 24

La métaprogrammation avec des patrons a des utilisations pratiques malgré son apparence maladroite. Elle peut être utilisée pour créer des classes vecteur à n dimensions quand n est connu à la compilation. L'avantage par rapport à un vecteur à n dimensions traditionnel est que les boucles peuvent être déroulées, ce qui produit un code très optimisé.

Considérons cet exemple de l'opérateur d'addition. Une addition pour un vecteur à n dimensions pourrait être écrite ainsi:

template<int dimension>
Vector<dimension>& Vector<dimension>::operator+=(const Vector<dimension>& rhs) 
{
   for (int i = 0; i < dimension; i++)
     value[i] += rhs.value[i];
   return *this;
}

Quand le compilateur instancie la fonction patron définie ci-dessus, le code suivant est produit:

template<>
Vector<2>& Vector<2>::operator+=(const Vector<2>& rhs) 
{
   value[0] += rhs.value[0];
   value[1] += rhs.value[1];
   return *this;
}

L'optimiseur du compilateur est capable de dérouler la boucle for car le paramètre dimension du patron est une constante connue à la compilation. Pour une véritable implémentation de cette technique, voir (en) [1].

En C++, la métaprogrammation avec des patrons est Turing-complète, ce qui signifie que n'importe quel calcul exprimable par un programme peut être calculé par un métaprogramme à base de patrons.

Les métaprogrammes à base de patrons n'ont pas de variables mutables, c'est-à-dire qu'aucune variable ne peut changer de valeur une fois qu'elle a été initialisée. Cela a pour conséquence que contrairement au C++ à l'exécution, la métaprogrammation à base de patrons est une forme de programmation fonctionnelle. Pour cette raison, l'analyse de flot dans les métaprogrammes est faite par le moyen de la récursion, comme vu plus haut

Initialisation de données

En C++, la métaprogrammation avec des patrons permet d'initialiser une donnée comme un tableau ou une structure de données complexe. L'exemple suivant illustre le remplissage d'un tableau dont les 32 premières valeurs sont le carré de l'index, et les valeurs suivantes sont l'index.

Le template est utilisé pour faire calculer la valeur d'un élément du tableau:

template <int N>
struct ValeurTab
{
    enum { valeur = N > 32 ? N : N * N };
};

Comme dans l'exemple de factorielle, pour récupérer la 10ème valeur, il suffit d'écrire ValeurTab<10>::valeur Ainsi le remplissage d'un tableau se ferait ainsi:

 
    int tab[] = { 
                    ValeurTab<0>::valeur, 
                    ValeurTab<1>::valeur, 
                    ValeurTab<2>::valeur /* ... */ 
                }

Pour faciliter le remplissage d'un grand tableau, on peut utiliser des macros classiques:

#define REMPLIR_TAB1(I) ValeurTab<(I)>::valeur
#define REMPLIR_TAB2(I) REMPLIR_TAB1((I)), REMPLIR_TAB1(I + 1)
#define REMPLIR_TAB4(I) REMPLIR_TAB2(I), REMPLIR_TAB2(I + 2)
#define REMPLIR_TAB8(I) REMPLIR_TAB4(I), REMPLIR_TAB4(I + 4)
#define REMPLIR_TAB16(I) REMPLIR_TAB8(I), REMPLIR_TAB8(I + 8)
#define REMPLIR_TAB32(I) REMPLIR_TAB16(I), REMPLIR_TAB16(I + 16)
#define REMPLIR_TAB64(I) REMPLIR_TAB32(I), REMPLIR_TAB32(I + 32)
#define REMPLIR_TAB128(I) REMPLIR_TAB64(I), REMPLIR_TAB64(I + 64)
//...

Ainsi pour remplir un tableau de 100 éléments en respectant l'algorithme du patron de classe, il suffit d'écrire:

    int tab[] = { REMPLIR_TAB64(0),REMPLIR_TAB32(64),REMPLIR_TAB4(64 + 32) };

Contrôle sur la compilation

D'abord, quelques classes:

 class UneClasseA 
 {
 public:
     UneClasseA() {}
     virtual ~UneClasseA() {}
 };
 
 class UneClasseB : public UneClasseA
 {
 public:
     UneClasseB() {}
     virtual ~UneClasseB() {}
 };
 
 class UneClasseC : public UneClasseA
 {
 public:
     UneClasseC() {}
     virtual ~UneClasseC() {}
 };
 
 class UneNouvelleClasseD : public UneClasseA
 {
 public:
     UneNouvelleClasseD() {}
     virtual ~UneNouvelleClasseD() {}
 };

Il se peut que, dans un programme, un objet de classe UneClasseC soit manipulé, lors de divers appels de fonctions (ou méthodes), comme un objet de classe UneClasseA afin de profiter des avantages du polymorphisme. Cependant, il se peut que l'ont ait un traitement spécifique selon la classe réelle de l'objet. Par exemple, Ceci arrive fréquemment pour l'affichage graphique d'un objet lorsque le programme est découpé selon le concept MVC. Cette technique est un motif de conception appelé visiteur. Classiquement, en C++, cela se fait par une cœrcition descendante (Downcasting en anglais). Il suffit alors de faire les tests:

 UneClasseB* pConvB = 0;
 UneClasseC* pConvC = 0;
 
 if (pConvB = dynamic_cast<UneClasseB*>(pObjetA))
 {
     // Traitement spécifique à uneClasseB
 }
 else if (pConvC = dynamic_cast<UneClasseC*>(pObjetA))
 {
     // Traitement spécifique à uneClasseC
 }
 else
 {
     // Erreur, type inconnu
 }

Un problème peut se poser lors de la programmation d'un nouvel objet (UneNouvelleClasseD). En effet, il faut penser à modifier toutes les parties de codes qui font ce genre de traitement. L'erreur ne sera visible que lors de l'exécution du programme, et il faut que cette exécution passe dans cette portion de code pour observer l'erreur.

Ici, la métaprogrammation permet de rendre le programme impossible à compiler si l'on rajoute un type qui n'est traité nulle part.

Pour cela, il faut établir une liste de types qui permettra de vérifier si tous les traitements de chaque type ont été programmés.

template <class H, class SousListe> struct ListeType {};
 
struct ListeFin {};

une liste de types se présentera sous une forme récursive : une liste contient un type et une sous-liste. La liste se termine par le type ListeFin. Par exemple:

ListeType<UneClasseB, ListeType<UneClasseC, ListeFin> >

Il suffit alors de créer une classe abstraite qui sera spécialisée avec cette liste de types. Cette classe sera rendu non abstraite en implémentant une méthode virtuelle pure pour chaque type (une méthodes par traitement spécifique). Ainsi, l'oubli de l'implémentation de la méthode d'un type de la liste, génèrera une classe abstraite. Une classe abstraite ne pouvant pas être instanciée, le compilateur retournera en erreur lors de la création de l'objet Visiteur. Il suffira alors d'ajouter l'implémentation de la méthode de traitement du nouveau type, pour enlever le comportement abstrait de la classe et permettre une instanciation. Ainsi, le compilateur peut alors compiler le programme et aucune méthode d'implémentation ne sera oubliée.

Il faut donc créer une classe abstraite visiteur avec une liste quelconque de types:

 template <class liste> class AbsVisiteur;
 
 // Spécialisation de AbsVisiteur pour le cas où c'est une liste de type ListeType
 // Hérite de AbsVisiteur de la sous-liste pour créer l'arbre d'héritage afin
 // de remonter au parent pour lancer la visite
 template <class H, class SousListe>
 class AbsVisiteur< ListeType<H, SousListe> > : public AbsVisiteur<SousListe>
 {
 public:
     // Méthode virtuelle pure qui rend la classe abstraite
     virtual void visite(H*) = 0;
 
     template <class Z> void lanceVisite(Z* pZ)
     {
         H* pConv = 0;
 
         if (pConv = dynamic_cast<H*>(pZ))
         {
             // Le type courant (dans la liste) est celui de la classe courante
             // (dans l'arbre d'héritage)
             visite(pConv);
         }
         else
         {
             // Le type courant (passé à la fonction) est différent de celui du
             // type courant (dans la liste et l'arbre héritage)
             // La sous-liste est testée avec la classe parente
             AbsVisiteur<SousListe>::lanceVisite(pZ);
         }
     }
 };
 
 // Spécialisation pour le type de fin de liste
 // C'est la super-classe
 class AbsVisiteur< ListeFin > 
 {
 public:
 
     template <class Z> void lanceVisite(Z* pZ)
     {
         // Cette classe est la classe mère de toutes les classes correspondant
         // au dernier type de la liste (type qui permet de terminer la liste).
         // Donc, ici, toute la liste a été testée, et aucune classe correspondante
         // au type de la fonction n'a été trouvée.
 
         // Donc ERREUR le type donné n'est pas dans la liste parcourue
         throw "Type introuvable";
     }
 };

Ensuite, il faut créer la liste de types spécifiques.

typedef ListeType<UneClasseB, ListeType<UneClasseC, ListeFin> > UneListeClasses;

Enfin, il faut créer la classe qui implémentera tous les traitements spécifiques:

 class Visiteur : public AbsVisiteur<UneListeClasses>
 {
 public:
     virtual void visite(UneClasseB * b)
     {
         // Traitement spécifique à uneClasseB
     }
     virtual void visite(UneClasseC * c)
     {
         // "Traitement spécifique à uneClasseC
     }
 
     // S'il manque l'implémentation d'une classe de la liste, la classe reste
     // abstraite car il reste une méthode virtuelle pure Visit() = 0
 };

Ainsi, pour ajouter un nouveau type, il faut l'ajouter dans la liste de types UneListeClasses, et pour que le programme compile, il faudra ajouter l'implémentation de la méthode visite pour le nouveau type.

Avantages et inconvénients de la métaprogrammation à base de patrons

• Compromis entre la compilation et l'exécution : comme tout le code sous forme de patron est traité, évalué et généré à la compilation, la compilation prendra plus de temps tandis que le code exécutable pourra être plus efficace. Bien que cet ajout soit généralement minime, pour des gros projets, ou pour des projets qui utilisent des patrons en grande quantité, cela peut être important.
• Programmation générique : la métaprogrammation à base de patrons permet au programmeur de se concentrer sur l'architecture et de déléguer au compilateur la génération de n'importe quelle implémentation requise par le code client. Ainsi, la métaprogrammation à base de patrons peut être accomplie via du code vraiment générique, facilitant la minimisation et la maintenabilité du code.
• Lisibilité : la syntaxe et les idiômes de la métaprogrammation à base de patrons sont ésotériques par rapport à du C++ conventionnel, et des métaprogrammes avancés peuvent être très difficiles à comprendre. Les métaprogrammes peuvent ainsi être difficiles à maintenir pour des programmeurs peu rompus à cette technique.
• Portabilité : à cause de différences dans les compilateurs, le code reposant fortement sur de la métaprogrammation à base de patrons (en particulier les nouvelles formes de métaprogrammation) peuvent avoir des soucis de portabilité.