Down cast et calcul formel.

Version imprimable

22/02/2014, 20h49
BaygonV

Down cast et calcul formel.
Bonjour à tous et toutes,
je suis en train de réfléchir a la programmation d'un petit langage utilisant du calcul formel pour mes besoins personnels.
Idéalement, j'aimerais que l'utilisateur (moi :) ) puisse coder quelque chose du genre :

Code:

fun f(x) = x^2+3x-2

ou

Code:

fun g(x)=sin(x)

(fun est le mot clef imaginaire menant a la définition d'une fonction)

dans les deux cas, mon parser me fabrique un objet instance de la classe :
Code:

1 2 3 4 5 class fonction { private : ArbreExpr A; //Voir texte public : bool ispolynome();};
Ou ArbreExpr est un arbre dont les nœuds sont composés des opérateurs arithmétiques de bases ainsi que d’éventuelles fonctions (cf sin dans g) et les feuilles sont soient des doubles soient la variable x.
Il me semble assez facile (dans certains cas...) pour un objet de la classe fonction de se rendre compte qu'il est un polynôme.
De plus, il semble naturel que la classe polynôme dérive de la classe fonction. Du coup, ce que j aimerais c est que lors de la construction d'un objet de la classe fonction, celui ci s auto promeuve en polynome quand il est en mesure de comprendre qu il en a l intérêt.

Je suis mathématicien de formation (s'il vous plait évitez de me faire remarquer que dans mon mécanisme précédent j'ai fait des raccourcis mathématiques en pensant m'apprendre quelque chose de ce point de vu) je m'adresse a vous car je ne suis pas du tout informaticien et je me demande si ce down casting est nécessaire ? maladroit ? normal ? réalisable ?

Une autre solution serait d'implémenter cette promotion dans mon parser : par exemple, au moment de l entrée d'un pointeur d'objet fonction dans la table de symboles, un appel a la fonction membre ispolynome() par puis un appel à un constructeur de la classe polynome prenant une fonction comme argument en cas de réponse positive... cette méthode me semble moins sexy mais peut être est ce la méthode à employer ?

Si vous avez d'autres idées, je suis preneur !
22/02/2014, 22h22
oodini

Citation:

Envoyé par BaygonV

De plus, il semble naturel que la classe polynôme dérive de la classe fonction.

Si tu penses à l'héritage public, c'est un mauvais postulat.
Un polynôme n'est pas une fonction. Cette dernière comporte deux membres, alors qu'un polynôme n'en comporte qu'un...
Disons plutôt qu'une fonction peut être composée d'un polynôme.
23/02/2014, 01h41
Iradrille

Citation:

Envoyé par BaygonV

De plus, il semble naturel que la classe polynôme dérive de la classe fonction.

Hello,

Je vais réagir la dessus aussi, et je rejoins @oodini.

Bien que mathématiquement un polynome "soit une" (= héritage) fonction, ici ta classe "fonction" sert de conteneur et la véritable fonction est stockée dans l'arbre d'expressions.

Je verrais plutôt un élément "polynome" (avec ses paramètres) à insérer dans ton arbre.

edit : dans ton exemple c'est comme sinus, tu n'as pas de classe "Sinus" qui hérite de "fonction", mais bien un élément "sinus" que tu insère dans ton arbre. :)
23/02/2014, 02h05
BaygonV

Je fais confiance à votre réponse mais je suis loin de la comprendre.
En effet, ce que j'ai compris de la notion d'héritage c est qu il est naturel de faire qu une classe B hérite de la classe A si on peut dire que B est un A. Du coup l'héritage que j envisage me parait naturel.

Ce que je comprends de vos réponses me fait dire qu il est plus naturel que mon polynôme dérive d'ArbreExpr finalement ?

Pourtant pour moi, la classe fonction ne fait qu'encapsuler l ArbreExpr, le polynôme lui peut avoir a choisir une autre façon de se représenter.... ( vecteur sur une base bien choisie etc...), de plus le membre surnuméraire ispolynome() ne fera que répondre (stupidement) oui si on pose la question à un polynôme...

Je n arrive pas a comprendre clairement ou est mon erreur de raisonnement dans ce que je viens de dire bien que je suis a peu près sur d en faire une informatiquement parlant.

En fait pour moi une instance d ArbrExpr est une représentation d'une des caractéristiques d'une fonction, pas vraiment une fonction.
Par exemple, dans la classe fonction (que je n ai représentée que très schématiquement pour ne pas alourdir la question) je pourrais avoir envie de définir un membre représentant le domaine de définition de la fonction que je ne peux pas vraiment déduire de l'ArbrExpr (j imagine que je peux déduire d'ArbreExpr un domaine de définition maximal mais certainement pas un domaine de définition imposé par l'utilisateur). Et pour répondre à ton edit iradrille, si si, j'ai bien prévu de dériver de la classe fonction une classe représentant la fonction sinus...
23/02/2014, 02h53
oodini

Citation:

Envoyé par Iradrille

Bien que mathématiquement un polynome "soit une" (= héritage) fonction

Ah bon ?
N'y aurait-il pas confusion entre polynôme et fonction polynomiale ?

Citation:

Envoyé par BaygonV

Et pour répondre à ton edit iradrille, si si, j'ai bien prévu de dériver de la classe fonction une classe représentant la fonction sinus...

Vu la classe Fonction actuellement, ça me dérange ce genre de chose.
Il y a 2 concepts qui me semble mélangés.

Si tu supprimes l'arbre de la classe "fonction", ça peut améliorer les choses.

Ca aurait peut être plus de sens avec une hiérarchie du type
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 class AbstractFunction { public: virtual double operator()(double) = 0; virtual ~AbstractFunction() { } }; class Sin : public AbstractFunction { public: virtual double operator()(double x) { return std::sin(x); } }; class Polynome : public AbstractFunction { std::vector<double> m_coeff; public: Polynome(const std::vector<double>& coeff): m_coeff(coeff) { } virtual double operator()(double x) { // ... } }; class Function : AbstractFunction { ExprTree m_tree; public: Function(...) { ... } virtual double operator()(double x) { // ... } };
Avec ExprTree un arbre d'expression similaire à ce que tu possède, dont les noeuds peuvent être des "AbstractFunction", "x", ou une valeur.

@oodini: surement oui, j'ai assumé qu'on parlait de fonctions polynomiales, la question de l'héritage ne se pose pas sinon.

23/02/2014, 03h35
BaygonV

Citation:

Vu la classe Fonction actuellement, ça me dérange ce genre de chose.
Il y a 2 concepts qui me semble mélangés.

Quels sont les deux concepts que je mélange selon toi ? (je n ai pas pu comprendre ce qu ils étaient avec la suite de ta réponse)

Je comprends ce que tu dis dans la suite, mais mon arbre vient du fait que je peux comme ça définir la somme (produit, quotient) de n importe quelles fonctions (en gérant en plus les domaines). En y réfléchissant un peu mieux, la fonction sinus n est pas dérivée de la classe fonction, mais en est une instance avec un arbrExpr composé d un seul noeud (sin) et d une seule feuille (x). Bref

La classe fonction est censée représenter l ensemble de toutes les fonctions, et les classes dérivées des sous ensembles (fonctions polynomiales, fonctions rationnelles, etc...) l arbrExpr évidemment représente l expression de la fonction dans son cas le plus général, encore une fois les polynômes ou fonctions rationnelles pourraient choisir d avoir une représentation complémentaire...

En cherchant à dériver la classe sinus de la classe fonction tout a l heure je faisais de sinus une sorte de sous ensemble de l ensemble des fonctions ce qui ne peut avoir qu un sens très réduit ( ensemble singleton constitué de la fonction sinus...) et c est peut-être de ce le mélange dont tu parlais :)

Citation:

Envoyé par BaygonV

Quels sont les deux concepts que je mélange selon toi ? (je n ai pas pu comprendre ce qu ils étaient avec la suite de ta réponse)

il y à une confusion entre fonctions ( f(x) = y ), et fonctions (sin(x), ou autre, nommé sous fonctions dans le post pour éviter les confusions).
Pour moi il doit y avoir une différence entre les deux, et seule la fonction f(x) = y doit avoir un arbre d'expression.
(Je ne sais pas trop comment expliquer ça clairement, si ce n'est pas clair, n'hésite pas à le dire, j'essayerais de reformuler).

Citation:

Envoyé par BaygonV

Je comprends ce que tu dis dans la suite, mais mon arbre vient du fait que je peux comme ça définir la somme (produit, quotient) de n importe quelles fonctions (en gérant en plus les domaines). En y réfléchissant un peu mieux, la fonction sinus n est pas dérivée de la classe fonction, mais en est une instance avec un arbrExpr composé d un seul noeud (sin) et d une seule feuille (x). Bref

Tu as à priori déja fait la différence entre ces deux types de fonctions : le noeud (sin) est le 2eme type de fonction (sous fonction). Les fonctions polynomiales sont comme un sinus : rien d'autre qu'un noeud dans l'arbre d'expression.

Les "sous fonctions" ne doivent pas partager le même type que les "fonctions"
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 class Function { AbstractNode& m_root; public: Function(AbstractNode& root) : m_root(root) { } double operator()(double x) { return m_root(x); } }; // un noeud / feuille de l'arbre class AbstractNode { public: virtual ~AbstractNode() { } virtual double operator()(double) = 0; }; // feuilles class XNode : public AbstractNode { public: virtual operator()(double x) { return x; } }; class ConstNode : public AbstractNode { double m_value; public: ConstNode(double value) : m_value(value){ } virtual double operator()(double) {return m_value; } }; // noeud unaire (+, -, sin ...) class UnaryNode : public AbstractNode { AbstractNode& m_child; public: UnaryNode(AbstractNode& child) : m_child(child) { } virtual ~UnaryNode() { } virtual double operator()(double x) { return internalFct(m_child(x)); } protected: virtual double internalFct(double) = 0; }; // noeud binaire (*, /, %, ...) class BinaryNode : public AbstractNode { AbstractNode& m_leftChild; AbstractNode& m_rightChild; public: BinaryNode(AbstractNode& leftChild, AbstractNode& rightChild) : m_leftChild(leftChild), m_rightChild(rightChild) { } virtual ~BinaryNode() { } virtual double operator()(double x) { return internalFct(m_leftChild(x), m_rightChild(x)); } protected: virtual double internalFct(double, double) = 0; }; class MultiplyNode : public BinaryNode { public: MultiplyNode(AbstractNode& leftChild, AbstractNode& rightChild) : BinaryNode(leftChild, rightChild) { } protected: virtual double internalFct(double left, double right) { return left * right; } }; class SinusNode : public UnaryNode { public: SinusNode(AbstractNode& child) : UnaryNode(child) { } protected: virtual double internalFct(double x) { return std::sin(x); } }; class PolyNode : public UnaryNode { std::vector<double> m_coeff; public: PolyNode(AbstractNode& child, const std::vector<double>& coeff) : Node(child), m_coeff(coeff) { } protected: virtual double internalFct(double x) { double ret = 0.0; for(int i=0; i<m_coeff.size(); ++i) { ret += pow(x, i) * m_coeff[i]; } return ret; } };
Quelques exemples de représentation
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 // f(x) = sin(2x) se représente : ConstNode two(2.0); XNode x; MultiplyNode mul(x, two); SinusNode sin(mul); Function f(sin); // g(x) = 4x^2 + 3x + 5 auto coeff = { 5.0, 3.0, 4.0 }; XNode x; PolyNode poly(x, std::vector<double>(coeff, coeff+3)); Function g(poly);

23/02/2014, 07h18
koala01
Salut,

Citation:

Envoyé par BaygonV

Je fais confiance à votre réponse mais je suis loin de la comprendre.
En effet, ce que j'ai compris de la notion d'héritage c est qu il est naturel de faire qu une classe B hérite de la classe A si on peut dire que B est un A. Du coup l'héritage que j envisage me parait naturel.

Attention! On dit effectivement souvent que l'héritage public est une relation "EST-UN" qui existe entre la classe dérivée et la classe de base. Mais cette affirmation doit être prise au sens du LSP (Liskov Substitution Principle ou, si tu préfères, du Principe de Substitution de Liskov).

Ce principe nous dit, en gros, que l'on peut envisager de transmettre n'importe quel objet de type dérivé à une fonction qui s'attend à recevoir un objet du type de base comme paramètre. Pour être précis, il est énoncé sous la forme de

Citation:

Si q(x) est une propriété démontrable pour tout objet x de type T, alors, q(y) est vraie pour tout objet y de type S tel que S est un sous type de T

En gros, la grosse question que soulève ce principe est "qu'est ce qu'une propriété démontrable pour un objet de type T :question:" La réponse tient, pour faire simple à toute l'interface publique du type T.

Avant d'accepter de créer une relation d'héritage, il faut donc au minimum que toutes les fonctions membres publiques et toutes les valeur publiquement accessibles au travers du type de base soient également accessible au travers du type dérivé.

Le propre d'une fonction est... de pouvoir être exécutée. Si tu essaye de modéliser une fonction, tu ne pourras pas t'en sortir sans lui donner une fonction membre proche de execute() (ou compute ou tout ce que tu veux de similaire) . Une telle fonction n'a absolument aucun sens pour un polynome : un polynome ne s'exécute simplement pas : il s'évalue à une valeur spécifique.

En outre, pour que l'héritage public puisse être envisagé, il faut que les règles de la programmation par contrat soient respectées. On peut résumer les choses en trois points:
- Les préconditions ne peuvent pas être renforcées dans la classe dérivée.
- Les postconditions ne peuvent pas être affaiblies dans la classe dérivée
- Les invariants de la classe de base doivent être respecté dans la classe dérivée
C'est à cause de ces trois points que l'on ne peut pas plus envisager de faire dériver ListeTriee de Liste (non triée) que Carré de Rectangle, et ce, malgré le fait que l'on ai tous appris dés notre plus jeune age qu'un carré est un rectangle disposant de quatre coté égaux.

En effet, la précondition pour avoir une liste triée est... qu'elle soit déjà trié avant d'essayer de rajouter un élément. C'est une précondition plus forte que celle qui existe pour une liste simple, vu que la liste simple n''a pas besoin de l'être.

Quant au carré, on rajoute un invariant majeur : hauteur == largeur. Quelle que soit la modification que l'on appliquera à notre carré, cette égalité devra être respectée en permanence, aussi bien avant de modifier notre carré (autrement, ce n'est pas un carré à la base ) qu'après l'avoir modifié (autrement, ce n'est plus un carré une fois modifié).

Enfin, tout cela a pour but de te dire qu'il faut être très prudent avec le sens que l'on donne à la phrase "l'héritage correspond à une relation EST-UN". C'est une phrase commune qui n'est pas tout à fait fausse, mais qu'il s'agit de prendre avec des pincettes car l'héritage public est en réalité beaucoup plus que cela ;)
23/02/2014, 09h42
BaygonV
Bonjour, j ai des réponses a apporter mais avant tout je crois que si l'on veut sortir mentalement vivants de cette conversation, il faut que l'on fasse une distinction entre les différents sens du mot fonction que l'on peut utiliser, où en tout cas ceux que je distingue pour l'instant... possible qu'il y en ait d'autres, n'hésitez pas à rajouter des définitions :)
1. Sens faible : une fonction est une expression avec des x.\\
  
  Pour moi, je mets ce type de fonction dans mon arbre.
2. Sens fort : une fonction au sens fort est une fonction au sens faible munie d'un domaine de d\'efinition.
  Pour moi, ce type de fonction est une instance de ma classe fonction.
3. Sens informatique : un bout de code avec des arguments que l'on peut faire exécuter. Je crois que certains appellent ca une sous-routine.
  Pour l'instant je n'ai jamais utilisé cette sémantique dans la question qui nous occupe pour l'instant.
Autre prérequis pour la clarté du la discussion, je ne sais pas vous citer comme vous le faites (avec une référence au pseudo ainsi qu un lien vers le texte cité), pouvez vous me dire comment mieux me servir de la balise quote ?

Edit : Je viens de voir le bouton "répondre avec citation" j'imagine que c est de cela qu'il s'agit :)
23/02/2014, 11h12
BaygonV

Sans (et de très loin) rejeter la totalité de ta réponse, la tu as tort :

Citation:

Envoyé par koala01

Le propre d'une fonction est... de pouvoir être exécutée. Si tu essaye de modéliser une fonction, tu ne pourras pas t'en sortir sans lui donner une fonction membre proche de execute() (ou compute ou tout ce que tu veux de similaire) . Une telle fonction n'a absolument aucun sens pour un polynome : un polynome ne s'exécute simplement pas : il s'évalue à une valeur spécifique.

En effet mes fonctions ne s’exécutent pas mais s’évaluent (même si ces expressions ont finalement plus ou moins le même sens via un isomorphisme propre à embrouiller la terre entière...)

Je suis très étonné de ce que tu dis la :

Citation:

Envoyé par koala01

C'est à cause de ces trois points que l'on ne peut pas plus envisager de faire dériver ListeTriee de Liste (non triée) que Carré de Rectangle, et ce, malgré le fait que l'on ai tous appris dés notre plus jeune age qu'un carré est un rectangle disposant de quatre coté égaux.

Car dans la façon dont j'ai compris les choses il me semble absolument évident qu'une classe Carrés devrait hériter de la classe rectangle.
Peut être serait-il intéressant de continuer dans ma logique (fausse apparemment) de dériver Carrés de Rectangles et de voir ou ça coince exactement (tu sembles le dire, mais j ai tellement l impression qu il y a toujours un moyen de s en sortir que je me dis que : 1) Soit ce n est qu une impression... 2) Soit c'est vrai mais de manière tellement limite que la solution est a écarter pour des raisons X ou Y...
Autant dans le cas 1) je pense que je vais m en apercevoir, autant dans le cas 2) j aurai besoin de votre aide pour me dire ou sont les limites du bon gout...
23/02/2014, 14h04
BaygonV

Citation:

Envoyé par Iradrille

(Je ne sais pas trop comment expliquer ça clairement, si ce n'est pas clair, n'hésite pas à le dire, j'essayerais de reformuler).

Effectivement, je ne comprends pas :)
23/02/2014, 17h35
koala01
Citation:

Envoyé par BaygonV

Car dans la façon dont j'ai compris les choses il me semble absolument évident qu'une classe Carrés devrait hériter de la classe rectangle.

ET pourtant non!

Le point de vue informatique de la chose est qu'un carré n'est -- grosso modo -- qu'un état particulier du rectangle: un rectangle est (ou n'est pas) un carré en fonction de la vérification qui peut (ou ne peut pas) être faite longueur == largeur. Si cette affirmation est vraie, alors notre rectangle présente bel et bien un état particulier qui est d'avoir la forme d'un carré. Si cette affirmation est fausse, alors le rectangle ne présente pas cet état particulier : il est un rectangle et on en reste là pour le moment :D

Citation:

Peut être serait-il intéressant de continuer dans ma logique (fausse apparemment) de dériver Carrés de Rectangles et de voir ou ça coince exactement (tu sembles le dire, mais j ai tellement l impression qu il y a toujours un moyen de s en sortir que je me dis que : 1) Soit ce n est qu une impression... 2) Soit c'est vrai mais de manière tellement limite que la solution est a écarter pour des raisons X ou Y...
Autant dans le cas 1) je pense que je vais m en apercevoir, autant dans le cas 2) j aurai besoin de votre aide pour me dire ou sont les limites du bon gout...

Je sais que c'est contre intuitif au possible, mais l'idée de la programmation par contrat est de pouvoir te garantir que tu obtiendras un résultat cohérent si tu fournis quelque chose de cohérent à la base. Autrement dit

Citation:

Donnes moi ce que je veux, tu auras ce à quoi tu t'attends.

Pour pouvoir te donner ces garanties, on dispose de trois concepts particuliers:
- Les préconditions. Ce sont des conditions qui doivent être vérifiées (comprends : vraies) au plus tard au moment où l'on commence à manipuler l'objet.
- Les postcondition. Ce sont des conditions qui doivent être vérifiées (comprends : vraies) au plus tard une fois que le traitement est terminé.
- Les invariants. C'est tout ce qui doit être vrai en permanence: on peut s'en servir comme d'une précondition, ou comme d'une postcondition, mais cela doit aussi être vrai entre le début et la fin du traitement.
La classe carré, si elle existait, imposerait un invariant très fort : longueur == largeur. Et ca, ca devrait être vrai en permanence parce que c'est une caractéristique essentielle de la forme géométrique que nous appelons carré.

Le problème, c'est que la classe rectangle n'impose absolument pas cet invariant : tu peux très bien avoir un rectangle de longueur 4 et de largeur 3. Ce n'est pas un carré, mais c'est bel et bien un rectangle (enfin, si les angles font 90°, mais on va considérer que c'est le cas ;) ).
Tu te demandes peut être pourquoi c'est un problème :question: La raison est toute simple : tu doit pouvoir faire avec un objet de type dérivé (carré, en l'occurrence) strictement tout ce que tu peux faire avec un objet du type de base (rectangle en l'occurrence). Ainsi, il est plus que vraisemblable que tu aies une fonction redimentionne(type nouvelleLongueur, type nouvelleLargeur) dans ta classe rectangle. Cette fonction, tu la retrouverais forcément dans ta classe carré. Oui, mais, hé ho! STOP!

Je peux, effectivement invoquer monRectangle.redimentionne(15, 20). Cela fonctionne : j'ai toujours un rectangle dont les nouvelles dimensions sont quinze de long et 20 de large. Pas de problème. Mais, qu'est ce qui se passe si j'invoque monCarre.redimentionne(15,20) :question: L'invariant de mon carré ( longueur == largeur) n'est plus respecté du tout, vu que l'on ne peut décemment pas aller prétendre que 15 == 20 ! Tu te rends bien compte que je ne pourrai jamais invoquer cette fonction sur un carré. Oui, mais... Moi, si je fais hériter carre de rectangle, c'est pour pouvoir gérer tous les objets en les connaissant comme des rectangles, sans avoir à m'inquiéter de savoir si c'est un carré ou si c'est un rectangle, c'est le but même de la substituabilité. Et je risque donc de traiter tous mes rectangles -- ou plutôt, tous mes objets connus comme étant des rectangles-- "par lot", et, pourquoi pas, d'invoquer cette fonction redimentionne. Sans m'inquiéter de savoir si j'ai bel et bien affaire à un rectangle et non à un carré, vu que "j'ai été assez bête" pour perdre le type réel des différents objets. Je n'ai donc aucun moyen de savoir si je suis bel et bien occupé à manipuler un rectangle ou si je manipule en réalité un carré :aie: Et l'on vient de voir que je ne peux pas envisage d'invoquer cette fonction sur un carré au risque de ne pas respecter la règle qui fait d'un carré une forme géométrique tout à fait particulière.

Je présume qu'à la lecture de cette explication, tu commences tout doucement à comprendre où se situel le problème ;). J'aurais aussi pu faire valoir le fait que tu auras forcément deux fonctions distinctes sur un rectangle : une fonction qui permet de récupérer sa longueur et une autre qui permet de récupérer sa largeur. Mais la notion même de longueur et de largeur est totalement inconnue pour le carré : c'est un coté, qu'il soit horizontal ou vertical ne changera pas la manière dont on le nomme : coté. Les notions véhiculées par les fonctions longueur et largeur du rectangle non, tout simplement, pas lieu d'être pour le carré. Ce qui est quand même embêtant pour des fonctions don carré disposerait d'office parce qu'elles lui viennent de sa classe de base.

On se rendrait alors compte que le principe de substitution de Liskov ne serait pas respecté parce qu'il existe une propriété "expose la fonction longueur" et une propriété "expose la fonction largeur" qui seraient vérifiée pour la classe de base (rectangle) et qui ne le seraient pas pour la classe dérivée (carré).

Bref, tout t'incite à ne pas faire dériver carré de rectangle. Ou du moins, tout devrait t'inciter à ne pas le faire ;)
23/02/2014, 18h11
BaygonV

Comment alors formaliser la relation indéniable qui existe entre carrés et rectangle ?
Dans la classe rectangle on peut tout a fait imaginer une fonction membre bool iscarre() non ?
Il faut que je fasse deux classes : class rectangle et class carre, sans relation d héritage, une fonction bool iscarre() dans ma classe rectangle puis un fonction de conversion rectangle -> carre ainsi qu une fonction de conversion carre -> rectangle par exemple ?
Mais alors, comment continuer a traiter ces deux choses de la même manière dans certains cas (il est indéniable qu il y a des situations ou on a besoin de voir ces formes sous le même point de vue).
Est ce que je dois chercher du coté programmation générique plutôt que d'essayer d élaborer une savante hiérarchie-bancale de classes ?
23/02/2014, 18h23
koala01

De deux choses l'une:
Ou bien tu as besoin d'une classe carré, et à ce moment là, ta classe carré est une classe soeur de ta classe rectangle (comprends: carre et rectangle ont toutes les deux d'une classe de base "forme géométrique"), mais il n'y a pas de relation effective entre la classe carré et la classe rectangle. Il ne sert même à rien de vouloir "convertir" un rectangle en carré. Cela ne fonctionnera pas : un carré reste un carré et un rectangle reste un rectangle, point barre. Et si un rectangle se retrouve à vérifier l'égalité longueur == largeur, hé bien, c'est un rectangle qui vérifie l'égalité, et c'est des choses qui arrivent :D

Ou bien, tu veux juste pouvoir déterminer si un rectangle respecte "toutes les conditions" pour être un carré. Le fait d'être un carré est alors "un état particulier" dans lequel un rectangle est susceptible de se trouver. Et dans ce cas, tu ajoutes juste une fonction isSquare (quitte à parler anglais, autant le faire complètement :D, à moins que tu ne préfère estCarre ;) ) qui renvoie vrai si longueur == largeur.

Tu ne fais à ce moment là aucune différence explicite entre les deux et tu gère tous les éléments comme étant des rectangles. De toutes manières, les règles de calcul (de superficies et de périmètres) utilisées pour le rectangle peuvent parfaitement être utilisée pour le carré ;). A priori, cela ne devrait donc pas te poser de problème de considérer que le carré n'est qu'un état particulier dans lequel un rectangle est susceptible de se trouver... ou non ;).
23/02/2014, 18h48
BaygonV

Ok j crois comprendre, cela étant dit, mon problème n est pas vraiment entre carré et rectangle mais entre fonction et fonction polynomiale.
Par contre après ce choc rectangle/carré je risque de souvent tourner en rond avant de décider de faire dériver A de B. Grrr j aime pas du tout ce que tu viens de m expliquer.
Et je parle moitié anglais moitié francais si je veux non mais :)
23/02/2014, 19h21
koala01

Citation:

Envoyé par BaygonV

Ok j crois comprendre, cela étant dit, mon problème n est pas vraiment entre carré et rectangle mais entre fonction et fonction polynomiale.
Par contre après ce choc rectangle/carré je risque de souvent tourner en rond avant de décider de faire dériver A de B. Grrr j aime pas du tout ce que tu viens de m expliquer.

Il n'y a malheureusement pas à aimer ou non ce que je viens d'expliquer. Il y a des règles à applliquer scrupuleusement pour être sur de prendre la bonne décision face à laquelle tu es seul et au sujet de laquelle tu ne peux attendre aucune aide ni de la part du langage ni de la part du compilateur pour t'assurer qu'elle est cohérente.

Mais ne t'en fais pas, une fois le principe compris, on s'habitue très vite à le mettre correctement en oeuvre ;) Et, avec un peu d'expérience, on apprend aussi très vite à trouver les solutions "les plus adaptées" à un problème donné ;)

Citation:

Et je parle moitié anglais moitié francais si je veux non mais :)

Oui, mais bon. L'idéal est toujours de quand meme choisir sa langue et de s'y tenir, pour que le code soit un minimum cohérent sur l'ensemble du projet ;). Et, d'une certaine manière, le fait que l'anglais n'utilise absolument pas les caractères accentués en fait la langue de prédilection, car cela évite les mauvaises compréhension entre "tourne" et "tourné" :D
23/02/2014, 19h37
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.
23/02/2014, 20h02
Davidbrcz

A moins qu'il y ait un but pédagogique derrière pour faire ca à la main, il faut passer par un framework qui gere tout ca à ta place. Surtout si tu n'es informaticien de base et que le parsing d'expression mathématique, c'est quand même un sujet relativement couvert.

Giac (bien que un peu bordelique), marche plutôt bien ou sinon y'a Ginac ou encore SymbolicC++.
23/02/2014, 21h38
BaygonV

J ai bien un but pédagogique et il est vrai qu a terme, j utiliserai surement une de ces bibliothèques. Dans un premier temps, j essaie d en faire un morceau a la main pour 'comprendre'...
23/02/2014, 22h40
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, 00h05
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, 17h51
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, 16h47
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, 02h11
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, 02h40
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 ;)