La meta-programmation en C++

Date de publication : 24/11/2004 , Date de mise a jour : 01/09/2005

Par Laurent Gomila (Autres articles)
 

Dans cet article, nous allons explorer une partie peu connnue mais pourtant extrêmement puissante du C++ : la meta-programmation.

1. La base de la meta-programmation : les templates

2. Mais... Qu'est-ce donc que la meta-programmation ?

template <class T>
const T& Max(const T& x, const T& y)
{
    return x > y ? x : y;
}

int i = Max(5, 9);
double d = Max(1.5, 8.6);
std::string s = Max(std::string("bonjour"), std::string("hello"));

const int& Max(const int& x, const int& y)
{
    return x > y ? x : y;
}

const double& Max(const double& x, const double& y)
{
    return x > y ? x : y;
}

const std::string& Max(const std::string& x, const std::string& y)
{
    return x > y ? x : y;
}

• On peut faire faire tout un tas de calculs mathématiques à notre compilateur : sinus, exponentielle, factorielle, ... et booster les performances de ce genre de calculs généralement lents.
• On peut réécrire des programmes habituellement pauvres en performances et leur donner un second souffle, par exemple le tri-bulle (bubble sort).
• On peut procéder à des optimisations intéressantes et certainement insoupçonnées sur nos calculs, notamment le calcul matriciel avec les expression templates.
• On peut générer automatiquement du code, notamment pour implanter des design patterns tels que les fabriques ou le visiteur sans effort et en gardant un typage fort.
• On peut écrire des outils puissants tels que des analyseurs syntaxiques.

3. Calcul et optimisation mathématique

template<unsigned int N> struct Fact
{
    enum {Value = N * Fact<N - 1>::Value};
};
template<> struct Fact<0>
{
    enum {Value = 1};
};

// Ici, x vaudra 24 avant même que vous ne lanciez votre programme - coût à l'execution : 0 sesterce
unsigned int x = Fact<4>::Value;

3.1. Quelques règles de meta-programmation

Exemple de fonction évaluée à la compilation
// Une fonction totalement inutile : elle renvoit son paramètre
int Identite(int N)
{
    return N;
}
unsigned int x = Identite(5); // x ne sera connu que lorsque le programme sera executé

// La même en meta-programme
template<int N> struct Identite
{
    enum {Value = N;}
};
unsigned int x = Identite<5>::Value; // la valeur de x est connue de notre compilateur

Exemple de fonction inline
inline int Add(int X, int Y)
{
    return Y == 0 ? X : Add(X, Y - 1) + 1;
}

int Somme = Add(5, 3);

Exemple de conditionnelle
template<bool Condition> struct Test {};

template<> struct Test<true>
{
    static void Do()
    {
        DoSomething();
    }
};

template<> struct Test<false>
{
    static void Do()
    {
        DoSomethingElse();
    }
};

// Code habituel
if (Condition)
    DoSomething();
else
    DoSomethingElse();

// Avec notre structure Test
Test<Condition>::Do();

Exemple de conditionnelles bis
template <int I> struct NumericTests
{
    enum
    {
        IsPair = (I % 2 ? false : true),
        IsZero = (I == 0 ? true : false)
    };
};

bool b1 = NumericTests<45>::IsPair; // 0 (false)
bool b2 = NumericTests<0>::IsZero; // 1 (true)

Exemple de boucles
template <int Begin, int End> struct Boucle
{
    static void Do()
    {
        DoSomething();
        Boucle<Begin + 1, End>::Do();
    }
};

template <int N> struct Boucle<N, N>
{
    static void Do() {}
};

// Méthode habituelle
for (int i = 5; i < 15; ++i)
    DoSomething();

// Avec notre structure Boucle
Boucle<5, 15>::Do();

Exemple de variables temporaires
template <int X, int Y> struct SomeVeryComplicatedComputations
{
    enum
    {
        Temp1 = X + 2 * Y,
        Temp2 = Y + 2 * X,
        Temp3 = X < Y ? 0 : 1,

        Value = Temp3 ? Temp1 : Temp2
    };
};

3.2. Réecriture des fonctions mathématiques

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

template <int I> inline double Factorielle()
{
    return I * Factorielle<I - 1>();
}
template <> inline double Factorielle<0>()
{
    return 1.0;
}

template <int N> inline double Puissance(double x)
{
    return x * Puissance<N - 1>(x);
}
template <> inline double Puissance<0>(double x)
{
    return 1.0;
}

// Ici N représente l'ordre, autrement dit la précision du calcul

template <int I> inline double Exp_(double x)
{
    return Exp_<I - 1>(x) + Puissance<I>(x) / Factorielle<I>();
}
template <> inline double Exp_<0>(double x)
{
    return 0.0;
}

template <int N> inline double Exponentielle(double x)
{
    return x < 0.0 ? 1.0 / Exp_<N>(-x) : Exp_<N>(x);
}

// Ici aussi, N resprésente l'ordre de développement

template <int N> inline double Cosinus(double x)
{
    return Cosinus<N - 1>(x) + (N % 2 ? -1 : 1) * Puissance<2 * N>(x) / Factorielle<2 * N>();
}
template <> inline double Cosinus<0>(double x)
{
    return 1.0;
}

template <int I> inline double Atanh(double x)
{
    return Atanh<I - 1>(x) + Puissance<2 * I + 1>(x) / (2 * I + 1);
}
template <> inline double Atanh<1>(double x)
{
    return x;
}
template <> inline double Atanh<0>(double x)
{
    return 0.0;
}

3.3. Les "expression templates", ou comment booster vos calculs matriciels

Vector V1, V2, V3, V4;

V4 = (V1 / 2.5) - (V2 + V3) * 5;

1. V2 + V3 sera d'abord évalué, un vecteur temporaire Temp1 sera généré après appel à l'opérateur + surchargé.
2. V1 / 2.5 sera ensuite évalué, un nouveau vecteur temporaire Temp2 sera créé après appel à l'opérateur /.
3. Temp1 * 5 sera calculé, et créera un résultat Temp3 après appel à l'opérateur *.
4. Temp2 - Temp3 sera le dernier calcul effectué, produisant une nouvelle variable temporaire Temp4 après passage par l'opérateur -.
5. V4 = Temp4 sera finalement évalué, affectant les valeurs de Temp4 à V4 via l'opérateur =.

Vector V1, V2, V3, V4;

// operator +(const Vector&, const Vector&)
Vector Temp1;
for (int i = 0; i < 3; ++i)
    Temp1[i] = V2[i] + V3[i];

// operator /(const Vector&, double)
Vector Temp2;
for (int i = 0; i < 3; ++i)
    Temp2[i] = V1[i] / 2.5;

// operator *(const Vector&, double)
Vector Temp3;
for (int i = 0; i < 3; ++i)
    Temp3[i] = Temp1[i] * 5;

// operator -(const Vector&, const Vector&)
Vector Temp4;
for (int i = 0; i < 3; ++i)
    Temp4[i] = Temp2[i] - Temp3[i];

// Vector::operator =(const Vector&)
for (int i = 0; i < 3; ++i)
    V4[i] = Temp4[i];

Vector V1, V2, V3, V4;

// Vector::operator =(???)
for (int i = 0; i < 3; ++i)
    V4[i] = (V1[i] / 2.5) - (V2[i] + V3[i]) * 5;

struct Vector
{
    // Définition des types iterateurs
    typedef double* iterator;
    typedef const double* const_iterator;

    // Fonctions de récupération des itérateurs de début et de fin
    iterator begin() {return Elements;}
    iterator end()   {return Elements + 3;}
    const_iterator begin() const {return Elements;}
    const_iterator end()   const {return Elements + 3;}

    // Et enfin les données
    double Elements[3];
};

Nos opérateurs
enum Operators
{
    Add,   // addition
    Sub,   // soustraction
    Mult,  // multiplication
    Div,   // division
    Plus,  // + unaire
    Minus, // - unaire
    Const  // Constante
};

Quelques opérateurs unaires
// Modèle de classe pour nos opérateurs unaires
template <class T, int Op> struct UnaryOp {};

// Classe de base pour nos opérateurs unaires
template <class T> struct UnaryOpBase
{
    UnaryOpBase(T t) : It(t) {}
    inline void operator ++() {++It;}

    T It;
};

// Spécialisation pour le moins unaire - nous devrons spécialiser nos classes pour chaque opérateur
template <class T> struct UnaryOp<T, Minus> : public UnaryOpBase<T>
{
    UnaryOp(T t) : UnaryOpBase<T>(t) {}
    inline double operator *() {return -(*It);}
};

// Spécialisation pour les constantes
template <class T> struct UnaryOp<T, Const> : public UnaryOpBase<T>
{
    UnaryOp(T t) : UnaryOpBase<T>(t) {}
    inline void operator ++() {}
    inline double operator *() {return It;}
};

Quelques opérateurs binaires
// Modèle de classe pour nos opérateurs binaires
template <class T, class U, int Op> struct BinaryOp {};

// Classe de base pour nos opérateurs binaires
template <class T, class U> struct BinaryOpBase
{
    BinaryOpBase(T I1, U I2) : It1(I1), It2(I2) {}
    inline void operator ++() {++It1; ++It2;}

    T It1;
    U It2;
};

// Spécialisation pour l'addition
template <class T, class U> struct BinaryOp<T, U, Add> : public BinaryOpBase<T, U>
{
    BinaryOp(T I1, U I2) : BinaryOpBase<T, U>(I1, I2) {}
    inline double operator *() {return *It1 + *It2;}
};

// Spécialisation pour la multiplication
template <class T, class U> struct BinaryOp<T, U, Mult> : public BinaryOpBase<T, U>
{
    BinaryOp(T I1, U I2) : BinaryOpBase<T, U>(I1, I2) {}
    inline double operator *() {return *It1 * *It2;}
};

BinaryOp<
    BinaryOp<
        Vector::const_iterator,
        UnaryOp<
            double,
            Const>,
        Div>,
    BinaryOp<
        BinaryOp<
            Vector::const_iterator,
            Vector::const_iterator,
            Add>,
        UnaryOp<
            double,
            Const>,
        Mult>,
    Minus>

template <class T, class U> inline BinaryOp<T, U, Add> MakeAdd(const T& t, const U& u)
{
    return BinaryOp<T, U, Add>(t, u);
}
template <class T, class U> inline BinaryOp<T, U, Mult> MakeMult(const T& t, const U& u)
{
    return BinaryOp<T, U, Mult>(t, u);
}
template <class T> inline UnaryOp<T, Minus> MakeMinus(const T& t)
{
    return UnaryOp<T, Minus>(t);
}
template <class T> inline UnaryOp<T, Const> MakeConst(const T& t)
{
    return UnaryOp<T, Const>(t);
}

Surcharges de l'opérateur +
template <class T, class U> BinaryOp<T, U, Add> operator +(const T& v1, const U& v2)
{
    return MakeAdd(v1, v2);
}
template <class T> BinaryOp<Vector::const_iterator, T, Add> operator +(const Vector& v1, const T& v2)
{
    return MakeAdd(v1.begin(), v2);
}
template <class T> BinaryOp<T, Vector::const_iterator, Add> operator +(const T& v1, const Vector& v2)
{
    return MakeAdd(v1, v2.begin());
}
BinaryOp<Vector::const_iterator, Vector::const_iterator, Add> operator +(const Vector& v1, const Vector& v2)
{
    return MakeAdd(v1.begin(), v2.begin());
}

Surcharges de l'opérateur *
template <class T>BinaryOp<T, UnaryOp<double, Const>, Mult> operator *(const T& v1, double d)
{
    return MakeMult(v1, MakeConst(d));
}
BinaryOp<Vector::const_iterator, UnaryOp<double, Const>, Mult> operator *(const Vector& v1, double d)
{
    return MakeMult(v1.begin(), MakeConst(d));
}

Surcharges de l'opérateur -
template <class T> UnaryOp<T, Minus> operator -(const T& v1)
{
    return MakeMinus(v1);
}
UnaryOp<Vector::const_iterator, Minus> operator -(const Vector& v1)
{
    return MakeMinus(v1.begin());
}

Surcharge de l'opérateur d'affectation
template <class T> const Vector& Vector::operator =(T Expr)
{
    for (iterator i = begin(); i != end(); ++i, ++Expr)
        *i = *Expr;

    return *this;
}

4. Génération automatique de code

4.1. Les typelists

Implémentation des typelists
template <class T1, class T2>
struct TypeList
{
    typedef T1 Head;
    typedef T2 Tail;
};

struct NullType {};

typedef TypeList<double, TypeList<float, TypeList<int, NullType> > > MyList;

#define TYPELIST_1(t1)                         TypeList<t1, NullType>
#define TYPELIST_2(t1, t2)                     TypeList<t1, TYPELIST_1(t2) >
#define TYPELIST_3(t1, t2, t3)                 TypeList<t1, TYPELIST_2(t2, t3) >
#define TYPELIST_4(t1, t2, t3, t4)             TypeList<t1, TYPELIST_3(t2, t3, t4) >
#define TYPELIST_5(t1, t2, t3, t4, t5)         TypeList<t1, TYPELIST_4(t2, t3, t4, t5) >
#define TYPELIST_6(t1, t2, t3, t4, t5, t6)     TypeList<t1, TYPELIST_5(t2, t3, t4, t5, t6) >
#define TYPELIST_7(t1, t2, t3, t4, t5, t6, t7) TypeList<t1, TYPELIST_6(t2, t3, t4, t5, t6, t7) >
...

// Notre liste devient alors
typedef TYPELIST_3(double, float, int) MyList;

4.2. Les hiérarchies automatiques

template <class TList, template <class> class Handler> class CScatteredHierarchy;

// Notre liste n'est pas vide : on hérite de Handler<T1> et on continue
// le processus par récurrence, avec T2 qui est la suite de notre liste.
template
<
    class T1,
    class T2,
    template <class> class Handler
>
class CScatteredHierarchy<TypeList<T1, T2>, Handler> : public Handler<T1>,
                                                       public CScatteredHierarchy<T2, Handler>
{
};

// Cas d'arrêt : on a épuisé tous les types de notre liste
template
<
    class T,
    template <class> class Handler
>
class CScatteredHierarchy<TypeList<T, NullType>, Handler> : public Handler<T>
{
};

4.3. Quelques exemples concrets

5. Conclusion

Une version PDF de cet article est disponible : Télécharger (144 Ko)