Joel F Real men use unique_ptr | Voila, apres le premier post sur la MPT, je récidive avec cette fois quelque chose de plus burné : Les Expressions Templates.
Tout d'abord je tiens à signaler que ce post est une tentative d'adaptation des articles de Todd Veldhuizen, ze Boss en MPT, créateur de la librairie Blitz++ en autre.
Note : Cette explication fait partie de mes travaux de DEA 
1. Principes
Considérons une fonction qui cacule l'intégrale d'une fonction mathématique.
Un moyen "classique" de l'implementer est d'utiliser un pointeur de fonction :
Code :
- double integrate( double (*f)(double), double inf, double sup )
- {
- double r=0;
- static const double dx = 0.001
- for( double i=inf;i<sup;i+=dx;) r += dx*f(i);
- return r;
- }
|
Simple, efficace, pas de problème. SAUF que si cette fonction est une part critique de votre application, le déréférencement de pointeur va peut etre commencer à devenir tres tres handicapant.
Il serait agréable de pouvoir ecrire quelque chose comme :
Code :
- Data<double> x;
- double r = integrate( 1+1/x,0,10);
|
et de voir se dérouler le code de l'intégration :
Code :
- double r = 0;
- for( double i=inf;i<sup;i+=dx;) r += dx*(1+1/i);
|
Comment faire ?
2. Une Solution Elégante : Les Expressions templates
Lorsque l'on manipule ce genre d'expression, on peut considérer qu'elles sont l'application d'une grammaire restreinte, contenant juste des valeurs, des opérateurs et des expressions. A partir de la on peut reconstruire un ensemble de classe pour réécrir ces expressions :
Il nous faut d'abord une classe pour représenté les variables et les constantes
Code :
- class Variable
- {
- public :
- Variable() {}
- double eval( double x ) const { return x; }
- };
- class Constante
- {
- public :
- Constante( const double& v) : val(v){}
- double eval( double ) { return val; }
- private :
- double val;
- };
|
Ensuite, il nous font pouvoir coder les divers opérateurs d'une expression
arithmétique. Cantonnons nous au opérateurs bianires de bases : +,-,/,*.
Qu'est-ce qu'un operateur binaire : c'est une opération ET un noeud d'una rbre de syntaxe abstraite ayant deux fils. Ces deux aspects de l'opérateurs se retrouvent dans deux familles de classes :
Code :
- // classe représentant la caractére binaire d'un opérateur
- template<class L,class R,class OP>
- class BinaryNode
- {
- public :
- BinaryNode( const L& l, const R& r ) : left(l), right(r) {}
- double eval( double x ) { return OP::eval( left.eval(x), right.eval(x));}
- private:
- L left;
- R right;
- };
- // classes représentant les opérations des opérateurs
- struct func_plus
- {
- static double eval( double x, double y) { return x+y; }
- };
- struct func_moins
- {
- static double eval( double x, double y) { return x-y; }
- };
- struct func_fois
- {
- static double eval( double x, double y) { return x*y; }
- };
- struct func_divise
- {
- static double eval( double x, double y) { return x/y; }
- };
|
Il nous reste à coder une classe pour encapsuler une expression quelconque :
Code :
- template<class E>
- class Expression
- {
- public :
- Expression( const E& expr) : xpr(expr) {}
- double eval( double x) { return xpr.eval(x); }
- private :
- E xpr;
- };
|
Voila, nous avaons toute nos briques. Comment alors reconstruire à partir de ces classes une expression arithmétique et l'évaluez en ligne ?
Trés simplement, nous allons redéfinir les opérateurs +,-,*,/ sur les types Variable, Constante et Expression et reconstruire au sein de ces opérateurs l'arbre de syntaxe de l'expression :
Code :
- // var+var
- inline Expression<BinaryNode<Variable,Variable,func_plus> >
- operator+( const Variable& v1, const Variable& v2 )
- {
- typedef BinaryNode<Variable,Variable,func_plus> expr_t;
- return Expression<expr_t>( expr_t(v1,v2) );
- }
- // (expr)+var
- template<class E>
- inline Expression<BinaryNode<Expression<E>,Variable,func_plus> >
- operator+( const Expression<E>& e, const Variable& v )
- {
- typedef BinaryNode<Expression<E>,Variable,func_plus> expr_t;
- return Expression<expr_t>( expr_t(e,v) );
- }
- // var+(expr)
- template<class E>
- inline Expression<BinaryNode<Variable,Expression<E>,func_plus> >
- operator+( const Variable& v ,const Expression<E>& e)
- {
- typedef BinaryNode<Variable,Expression<E>,func_plus> expr_t;
- return Expression<expr_t>( expr_t(v,e) );
- }
- // expr+expr
- template<class E1,class E2>
- inline Expression<BinaryNode<Expression<E1>,Expression<E2>,func_plus> >
- operator+( const Expression<E>& e1 ,const Expression<E>& e2)
- {
- typedef BinaryNode<Expression<E1>,Expression<E2>,func_plus> expr_t;
- return Expression<expr_t>( expr_t(e1,e2) );
- }
|
Voila, rajoutez a cela les opérateurs -,*,/, la surcharge pour gérer les constantes numériques :
Code :
- // const+expr
- // les autres versions sont nécéssaire evidemment
- template<class E>
- inline Expression<BinaryNode<Constante,Expression<E>,func_fois> >
- operator*( const double& c, const Expression<E>& e)
- {
- typedef BinaryNode<Constante,Expression<E>,func_fois> expr_t;
- return Expression<expr_t>( expr_t(Constante(c),e) );
- }
|
En écrivant du code comme :
Code :
- template<class E>
- double integrate( Expression<E> e, double inf, double sup)
- {
- double r=0;
- static const double dx = 0.001;
- for( double i=inf;i<sup;i+=dx;) r += dx*e.eval(i);
- }
|
Nous générons par instanciation récursives des templates le code suivant :
Code :
- template<class E>
- double integrate( Expression<E> e, double inf, double sup)
- {
- double r=0;
- static const double dx = 0.001;
- for( double i=inf;i<sup;i+=dx;) r += dx*(1+1/i);
- }
|
C'est gaagné
cette technique permet aussi via quelques modifications mineurs de
générer du code arithmétique vectoriel ou matriciel inline trés performant, éliminant toutes recopies d'objets temporaires et augmentant les performances d'un facteurs 3 ou 4, faisant du C++ un langage aussi rapide que le C.
On peut aussi ecrire des classes pour générer du code inline de parser/lexer à la YACC, des filtres de flux, du TI rapide (oops la c'est mon job  ) bref, des infinités d'applications.
EDIt : typo/ortho
Message édité par Joel F le 29-07-2003 à 10:19:30
|
