Down cast et calcul formel.

Version imprimable

Voir 40 message(s) de cette discussion en une page

23/02/2014, 23h40
JolyLoic
Pour revenir au sujet fonction/polynôme, je pense qu'il faut un peu préciser ton besoin initial. La question que je me pose est pourquoi ressens-tu le besoin d'avoir une classe polynôme différente de la classe fonction. Je peux voir 3 raisons différentes, qui demandent toutes trois des solutions informatiques différentes :
1. Parce que, en tant que mathématicien, tu as l'habitude de nommer différemment ces cas, mais en fait, tu ne vas rien en faire de particulier
2. Parce qu'il y a des opérations que tu vas implémenter de manière particulière pour les polynômes (par exemple la dérivation, ou encore l'évaluation par schéma de Horner)
3. Parce qu'il y a des opérations qui n'ont du sens que pour les polynômes (par exemple déterminer si un polynôme est premier)
Dans le cas 1, tu n'as même pas besoin d'une classe polynôme. La classe fonction suffit.

Dans le cas 2, avoir une classe polynôme qui dérive de la classe fonction me semble une bonne option, qui respecte le principe de Liskov (contrairement à d'autres dans ce fil, je ne vois pas de violations de ce principe dans ce cas, la seule violation qui ait été citée (évaluation / exécution) me semblant fausse, fonction comme polynômes peuvent s'évaluer un un point, mais pas s'exécuter). Je partirais donc probablement vers une classe enrobante Fonction, t'évitant de manipuler des pointeurs partout, une classe de base expression (une fonction possédant une expression racine) une classe dérivée polynôme, et d'autres classes dérivées pour les autres éléments de l'arbre décrivant la fonction.
Le seul point me posant problème dans ce cas est que l'on va devoir à un moment où à un autre tester si une fonction est un polynôme (par exemple, l'addition de deux polynômes peut donner soit une expression addition, soit une expression polynôme, le second cas étant préférable, alors que dans le cas général, l'addition ne peut donner qu'une expression addition). Je ne pense pas qu'il s'agisse là d'une violation du principe de Liskov, puisque c'est totalement transparent pour l'utilisateur, mais ça introduit une dépendance entre l'opération d'addition de fonctions et les polynômes. Mais je ne vois pas comment m'en passer sans renoncer aux optimisations que peuvent apporter ces derniers.

Dans le cas 3, on peut partir comme dans le cas 2, mais l'utilisateur va être au courant de différences entre la classe de base et des classes dérivées. Je pense encore que le principe de substitution de Liskov n'est pas violé, mais si l'utilisateur veut bénéficier des différences, un downcast sera nécessaire pour lui. Je suis assez mal à l'aise dans ce genre de situations. Si certains ont des solutions meilleures à proposer, je suis ouvert, mais en l'état, je partirais probablement vers une solution comme le point 2.
24/02/2014, 01h05
koala01

Citation:

Envoyé par BaygonV

Puisque tu es modérateur j'en profite pour te demander si je peux continuer à utiliser ce fil pour tenter d appliquer ce que tu m'as expliqué dans mon cas ?
Histoire de penser tout haut ici sous le 'contrôle' des utilisateurs du forum ?
Ça va continuer a avoir un rapport avec le thème du fil puisque pour l'instant bien qu'aillant compris l'idée de ce que tu m'as expliqué sur la "programmation par contrat" je suis très loin de l'avoir digéré et de pouvoir "l'énoncer simplement" dans les situations qui me préoccupent en ce moment.
De toutes façons, je ne pourrai m'y remettre sérieusement que vers jeudi prochain.

Ne t'en fais pas trop pour cela: "on" (la modération) ne te taperas pas trop sur les doigts si la discussion digresse trop ;)

Dans le pire des cas, si on se rend compte que l'on aborde vraiment un sujet qui mérite une discussion à lui tout seul, on scindera les messages, et tout le monde sera content :D
28/02/2014, 18h51
BaygonV

@ JolyLoic : Deux classes différentes pour fonctions et polynômes car je vois à la fois des opérations communes aux fonctions et aux polynômes qui s implémenteraient de manière plus simple pour un polynôme, ne serait ce que la représentation "de travail" de ce dernier. Et aussi car il y a des opérations que l'on peut faire sur un polynôme et que l'on ne peut pas, a priori, faire sur une fonction. C'est donc un mélange de 2 et 3.
La solution qui me semblait la bonne était de faire dériver polynôme de fonction et que l'objet de classe fonction, lors de sa construction puisse faire un test et s'auto promouvoir polynôme (pour moi c est la qu'est le downcast).
Le problème d'évaluation me semble aussi être un faux problème, d'autant plus que évaluation et exécution sont de mon point de vue des mots qui désignent la même chose dans deux jargons différents.

@ Koala01 : Ok merci :)

Je vais enfin pouvoir m'y remettre.

En fait, la solution la plus classique consiste à se dire que si tu as une fonction mathématique

Code:

f(x) = ...

f(x) est la fonction, mais les points de suspension représente une expression.

L'expression peut prendre plusieurs formes: Ce peut être une expression littérale (ex: 3.1415926) ou une combinaison de une ou deux "sous expression(s)" et d'un opérateur:
non(a) est la combinaision d'un opérateur (non) et d'une expression (a)
a*b ou a+b sont les combinaison de deux expression (a et b) et d'un opérateur ( * ou +)
(a² +b²) est la combinaison d'une expression (a+b, qui est elle meme la combinaison de deux expressions et d'un opérateur) et d'un opérateur (les parenthèses).

En partant de là, on peut arriver à créer ce que l'on appelle un AST (Abstract Syntax Tree). Pour l'expression (a² + b²) il prendrait un forme ressemblant à
Code:

1 2 3 4 5 6 7 8 operateur() | operateur + / \ operateur exposant operateur exposant / \ / \ littéral a littéral 2 litéral b littéral 2
En parcourant correctement cet arbre, tu deviens véritablement susceptible d'évaluer n'importe quelle expression, aussi complexe puisse-t-elle être, car littéral a exposant littéral 2, ca te donne bel et bien a², littéral b exposant littéral 2 te donne bel et bien b² l'expression "a²" que l'on vient d'évaluer + l'expression "b²" que l'on vient d'évaluer donne bel et bien l'expression "a²+b²" et, si on met cette expression dans l'opérateur parenthèse, on obtient bel et bien (a²+b²) qui est, elle meme une expression qui pourrait intervenir dans une expression encore plus complexe ;)

Au final, tu n'as donc pas besoin de grand chose : deux classes de base (Expression et Operateur), qui exposent chacune une fonction virtuelle pure "evaluate()" dont le comportement sera défini dans les classes dérivées.

Pour ce qui est de la classe Expression, tu as trois classes dérivées:

LitteralExpression qui permet de représenter des valeurs comme 'a' ou comme 3.1415926
SingleExprAndOperator, qui sert de classe de base à toutes les expressions composées d'une seule sous expression et d'un opérateur ( non(expression), parenthèse(expression) etc)
DoubleExprAndOperator qui sert de classe de base à toutes les expressions composées de deux sous expression et d'un opérateur ( exposant(gauche droite), addition(gauche,droite), soustraction(gauche droite) etc)

Chacune de ces classes peut servir de classe de base à plusieurs classes concrètes, permettant

pour la première de faire la distinction entre les différentes valeur possible (une chaine de caractère, un double, un entier ou un autre type primitif)
pour la deuxième de faire la distinction entre les expression utilisant les différents opérateurs "unaires" (comprends: n'utilisant qu'un seul opérande) : non(expression) parenthèse(expression) et autres
pour la troisième permettant de faire la distinction entre les expressions utilisant les différents opérateurs "binaires" (comprends: utilisant deux opérandes) : addition, soustraction, multiplication, exposant, division, modulo,...

Et bien sur, ta classe Operator servira de base à tous les opérateurs possibles et imaginables: Parenthèse, Non, OperateurPlus, OperateurMoins, OperateurFois, OperateurDivise, OperateurExposant, OperateurModulo, et tous les autres.

Une fois que tu as cela, "YAPUKA", même si c'est peut etre le plus difficile, "parser" l'expression qui correspond à ta fonction pour créer l'AST correspondant ;)

Mais ca, c'est un problème qui mérite encore plus d'explications. Je vais le laisser en suspend pour l'instant ;)

@koala01, solution intéressante, quelque chose m'échappe par contre : comment faire des traitement particulier pour les polynomes.

Je suppose qu'un polynome serait un litéral, et que les fonctions evaluate seraient définies comme ça ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct Literal {
    virtual ~Literal() { }
    virtual double evaluate(double x) const;
};
 
struct Polynome : Literal { ... };
 
struct Operateur {
     virtual ~Operateur() { }
     virtual Literal *evaluate() const;
}
 
struct DoubleExprAndOperator : Operator {
    const Literal *left;
    const Literal *right;
    virtual ~DoubleExprAndOperator() { }
    DoubleExprAndOperator(const Literal *left, const Literal *right) : left(left), right(right) { }
};
 
struct Plus : DoubleExprAndOperator {
    virtual ~Plus() { }
    Plus(const Literal *left, const Literal *right) : DoubleExprAndOperator(left, right) { }
    virtual Literal *evaluate() const {
         if(dynamic_cast<const Polynome*>(left) && dynamic_cast<const Polynome*>(right)) {
              return new Polynome(...);
         }
         return new UnAutreLiteral(...);
    }
};

Le double dispatch peut (comme d'hab) supprimer ces vilains casts.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Literal *freeOpAddLeft(const Literal *left, const Literal *right) { return right->opAddRight(left); }
Literal *freeOpAddLeft(const Polynome *left, const Literal *right) { return right->opAddRight(left); }
 
Literal *freeOpAddRight(const Literal *left, const Literal *right) { return new Literal(...); }
Literal *freeOpAddRight(const Literal *left, const Polynome *right) { return new Literal(...); }
Literal *freeOpAddRight(const Polynome *left, const Literal *right) { return new Literal(...); }
Literal *freeOpAddRight(const Polynome *left, const Polynome *right) { return new Polynome(...); }
 
struct Literal {
    virtual ~Literal() { }
    virtual double evaluate(double x) const;
 
    virtual const Literal *opAddLeft(const Literal *right) const;
 
    virtual const Literal *opAddRight(const Literal *left) const;
};
 
struct Polynome : Literal {
    virtual ~Polynome() { }
    virtual double evaluate(double x) const { ... }
 
    virtual const Polynome *opAddLeft(const Literal *right) const { return freeOpAddLeft(this, right); }
 
    virtual const Polynome *opAddRight(const Literal *left) const { return freeOpAddRight(left, this); }
    virtual const Polynome *opAddRight(const Polynome *left) const { return freeOpAddRight(left, this); }
 
};
 
struct Plus : DoubleExprAndOperator {
    virtual ~Plus() { }
    Plus(const Literal *left, const Literal *right) : DoubleExprAndOperator(left, right) { }
    virtual Literal *evaluate() const { return left->opAddLeft(right); }
};

Mais ce code me semble sacrément bordélique (on va devoir créer 20 millions de fonctions), y-a-t'il mieux ?

01/03/2014, 17h47
koala01

Mais un polynome n'est jamais qu'une expression dont chaque partie peut être évaluée indépendamment ;)

Ainsi, si tu as un polynome qui représente l'expression (a² + b²) *(a² -2ab +b²)+3a, tu peux créer un AST qui recrée cette expression en n'utilisant jamais que les opérateurs "classique" +, -, *, exposant, et parenthèse ;)

La seule question qui reste en suspend est "quelle valeur donner à a et à b :question:" Mais ca, tu le détermine lorsque tu appelle, justement, la fonciton correspondante f(3,19) ;)

En outre, tu n'as pas forcément besoin de définir une fonction qui reprend chaque type d'expression possible dans chaque classe d'expression.

A partir du moment où tu as une classe
Code:

1 2 3 4 5 6 7 8 class UnaryExpr{ public: SingleExpr(Expression * expr, Operator * op):expr_(expr),op_(op){} Expression const & expr() const{return *expr_;} private: Expression * expr_; Operator * op_; };
Tu as largement assez pour n'avoir plus qu'à définir le comportement de evaluate() pour chaque expression "unaire" (comprends: chaque expression composée d'un opérateur et d'une seule expression ) ;)
Il en va de meme avec un classe
Code:

1 2 3 4 5 6 7 8 9 10 class BinaryExpr{ public: BinaryExpr(Expression *left, Expression * right Operator * op):left_(left), right_(right)op_(op){} Expression const & left() const{return *left_;} Expression const & right() const{return *right_;} private: Expression * left_; Expression * right_; Operator * op_; };
La construction en elle même, ca se passe au niveau d'une fabrique et d'un système qui permet de déterminer quel type d'expression doit être créé en fonction de l'opérateur rencontré ;)

02/03/2014, 03h11
JolyLoic

Citation:

Envoyé par koala01

Mais un polynome n'est jamais qu'une expression dont chaque partie peut être évaluée indépendamment ;)

Ainsi, si tu as un polynome qui représente l'expression (a² + b²) *(a² -2ab +b²)+3a, tu peux créer un AST qui recrée cette expression en n'utilisant jamais que les opérateurs "classique" +, -, *, exposant, et parenthèse ;)

Le problème est qu'en faisant ainsi, tu auras certes une modélisation des polynômes fonctionnelle, mais une modélisation très peu efficace (elle correspond au cas 1 de mon post précédent). C'est pourquoi, si tu pressens que les polynômes vont être très présents dans tes cas d'utilisation, et que les performances comptent, il vaut mieux modéliser ceux-ci différemment. Un polynôme serait un nœud terminal (sans enfants), comme peut l'être un littéral, mais sans en être un (à la limite, on peut dire qu'un littéral est un polynôme de degré 0 ou -inf (pour le polynôme nul), mais je ne suis pas certain de la pertinence de ce choix).
02/03/2014, 03h40
koala01

Citation:

Envoyé par JolyLoic

Le problème est qu'en faisant ainsi, tu auras certes une modélisation des polynômes fonctionnelle, mais une modélisation très peu efficace (elle correspond au cas 1 de mon post précédent). C'est pourquoi, si tu pressens que les polynômes vont être très présents dans tes cas d'utilisation, et que les performances comptent, il vaut mieux modéliser ceux-ci différemment. Un polynôme serait un nœud terminal (sans enfants), comme peut l'être un littéral, mais sans en être un (à la limite, on peut dire qu'un littéral est un polynôme de degré 0 ou -inf (pour le polynôme nul), mais je ne suis pas certain de la pertinence de ce choix).

En effet, je vois ce que tu veux dire.

Ceci dit, j'ai présenté les base, rien n'empêche de "broder" un peu autour de cela. Car il y a malgré tout une chose immuable : un polynome est bel et bien une expression! (ou du moins : on peut beaucoup plus facilement le considérer comme tel que comme une fonction :D )

A partir de là, on fait strictement ce que l'on veut. Rien n'empêche d'envisager de créer une classe spécifique (que je verrais bien template et sans doute variadic en sus, histoire d'éviter de se répéter vraiment trop souvent pour ce qui reste commun ;)) Polynome, qui hérite de Litteral (si c'est ce que tu penses etre le plus efficace :D) et qui adapte comportement d'évaluation en fonction d'un certain nombre de politiques.

Je ne sais pas trop comment on pourrait l'organiser (je n'ai surtout pas encore vraiment réfléchi à la question), Mais il n'y a pas grand chose qui t'empêche, si une formule est connue, de simplement avoir un comportement qui évalue a², b², 2ab et 3a sur base d'une valeur connue pour a et pour b afin de rendre, effectivement, l'évaluation de (a²+b²)*(a²-2ab+b²)+3a plus rapide ;).

Et encore : il faut voir quel est le but final du programme que BaygonV veut développer. Car, je t'accorde volontiers que, dans le domaine de la recherche, la possibilité que je présentais à la base sera peut être "trop suboptimale" pour une utilisation poussée.

Mais, s'il s'agit "juste" (on se comprend sur le terme, hein :D) de donner "suffisamment d'intelligence" à un programme d'exercice que pour lui permettre de valider la réponse d'un étudiant ou de créer une application qui ferait office de calculatrice scientifique, si même il arrive à un résultat une demi seconde plus lentement (et je ne crois pas que l'on en arriverait à ce point :D), je ne crois sincèrement pas que cela puisse réellement poser problème ;)

Voir 40 message(s) de cette discussion en une page