Discussion :

[Jean-Marc.Bourguet]

Mais, supposons qu'on manipule des expressions arborescentes.

Je réalise un optimiseur (si je fais un compilateur), ou bien je fais des transformations en calcul formel (substitution d'une expression par une autre).

Pour faire ça, la manière la plus simple c'est de faire une égalité structurelle.

1/ Les optimisations se font par transformation d'arbre (ou de DAG d'ailleurs), pas par comparaison. La génération de code peut s'effectuer par recouvrement d'arbres partiel -- mais on est dans quelque chose de bien plus compliqué d'une égalité structurelle telle que tu l'envisages.

2/ Dans un système de calcul formel, on va plutôt chercher si les expressions sont équivalentes, s'évaluent toujours -- ou sous condition (il faut bien profiter que l'overflow des entiers c'est un comportement indéfini par exemple!) -- à la même valeur. On a à nouveau quelque chose de bien plus compliqué que l'égalité structurelle.

3/ On peut aussi chercher un isomorphisme entre les arbres -- par exemple pour unifier des paramètres. On a à nouveau quelque chose de plus compliqué que l'égalité structurelle et on va avoir un résultat aussi plus conséquent d'un simple booléen.

Dans tout les cas -- optimisation ou calcul formel -- on n'a pas une relation d'égalité de valeur: parce qu'on ne va vraisemblablement pas pouvoir substituer une expression par l'autre dans tous les contextes -- si on veut que les informations de debug ou les messages d'erreur aient un sens par exemple, il faut aussi garder trace de la position des expressions dans le fichier d'entrée. Je n'utiliserais donc certainement pas l'opérateur == pour ces opérations (qui sont d'ailleurs différentes, je vais essayer de leur donner des noms plus explicites).

[HanLee]

Certes, mais ces arbres ont quand même bien une sémantique de valeur, on les manipule très primitivement.

Et l'opérateur == a évidemment un sens.

Je sais pas, regarde std::set|vector|list, l'opérateur '==' est bien défini, il a un sens, pourtant je ne m'en suis encore jamais servi de mémoire (sauf pour les std::string).

[Jean-Marc.Bourguet]

Certes, mais ces arbres ont quand même bien une sémantique de valeur, on les manipule très primitivement.

Chaque fois que je manipule des arbres, je me retrouve à annoter les noeuds et les arcs. Et le simple fait qu'on puisse envisager de les annoter montre bien que ce sont des entités. Et les constituants d'un arbre sont des entités, celui-ci ne peut évidemment être une valeur.

Je sais pas, regarde std::set|vector|list, l'opérateur '==' est bien défini, il a un sens, pourtant je ne m'en suis encore jamais servi de mémoire (sauf pour les std::string).

Les conteneurs sont intéressants. J'ai pas le sentiment que ceux de la SL sont particulièrement bien conçu mais j'ai pas le temps d'expliquer mon point de vue. Réfléchir en quoi std::string est une classe batarde est un bon point de départ (mon point d'arrivée est que std::string devrait avoir une sémantique de valeur et n'est pas un conteneur, les conteneurs devraient avoir une sémantique d'entité). Un test pour savoir si quelque chose a une sémantique de valeur ou d'entité, c'est de voir si conceptuellement (parfois ce n'est pas trop pratique) n'avoir que l'assignation comme membre non const a du sens.

[Médinoc]

Euh, les conteneurs de la STL n'ont-ils pas tous une sémantique de valeur?
Contrairement aux collections de Java et .Net, qui ont une sémantique d'entité et une hiérarchie d'héritage.

Les strings, par contre, ont une sémantique de valeur même en .Net, ce qui est facilité par leur immuabilité.

[Jean-Marc.Bourguet]

Euh, les conteneurs de la STL n'ont-ils pas tous une sémantique de valeur?

Les conteneurs de la SL ont unifié (ou confondu? la chose est la même, sa désirabilité et son aspect volontaire diffèrent) l'entité et le type valeur décrivant l'état de l'entité. Un conteneur n'en est pas un si on ne sait pas accéder et modifier individuellement ses éléments -- donc ce n'est pas pour moi un type valeur. Quand j'utilise push_back, j'ai l'impression de modifier une entité, pas de remplacer une valeur par une autre comme quand je fais += sur des int.

[méphistopheles]

Le multidispatch n'est souvent pas necessaire, dans la matrice des resultats, tout ce qui n'est pas sur la diagonale est faux.

heu....quelle diagonale ? pourrais tu expliciter s'il te plait ?

[Médinoc]

Traduction: Deux objets qui ne sont pas du même type sont différents, point. Pas besoin d'appeler un comparateur pour ça, donc on n'a que N comparateurs à écrire (et appeler), plutôt que N².

[Jean-Marc.Bourguet]

Tu as un resultat qui depend de deux types dynamiques; quand les deux types ne sont pas egaux, le resultat de la comparaison est, sauf cas particulier, faux. La matrice en question est celle que tu aurais en mettant en ligne et en colonne les types que tu traiterais.

[HanLee]

2/ Dans un système de calcul formel, on va plutôt chercher si les expressions sont équivalentes, s'évaluent toujours -- ou sous condition (il faut bien profiter que l'overflow des entiers c'est un comportement indéfini par exemple!) -- à la même valeur. On a à nouveau quelque chose de bien plus compliqué que l'égalité structurelle.

+ (...)

Ca doit être une question de point de vue.
J'ai plus l'impression que tu es dans l'optique industrialisation grande échelle.
C'est un peu comme, pour des petits ordres de grandeur, un algorithme O(n²) n'est pas plus critiquable qu'un algorithme O(n log(n)).
std::vector<> est plus performant que std::set<> pour des petites tailles.

Sinon, quand je parlais de calcul formel, j'avais en tête des manipulations genre développer, substituer, factoriser, un truc qui se commande à la main.

Et en Caml par exemple, les arbres que l'on manipule sont bien des valeurs (en même temps, ces arbres ont une définition purement mathématique, et on est dans un langage fonctionnel).

Pour des exercices ou petites applications à usage personnel, voire académique, je pense que ça se justifie parfaitement de manipuler des arbres de cette façon.

[Médinoc]

C'est un peu comme, pour des petits ordres de grandeur, un algorithme O(n²) n'est pas plus critiquable qu'un algorithme O(n log(n)).

En anglais: Everything Is Fast For Small n.

[HanLee]

En anglais: Everything Is Fast For Small n.

?
L'article met en garde contre des présuppositions foireuses.

Si je sais que dans mon problème donné, la taille des données est bornée, l'article ne s'applique pas!

[Médinoc]

En effet, tu as raison. Quand on sait que n ne sera jamais grand, il n'y a pas de problème.

[Jean-Marc.Bourguet]

J'ai plus l'impression que tu es dans l'optique industrialisation grande échelle.

Et ce serait le cas? C'est vrai que j'ai plus l'habitude de travailler dans des programmes qui font plusieurs millions de lignes, qui tournent des semaines et ont besoin de plus de 4 GB de memoire pour contenir les donnees que sur des TP d'etudiants qui ne sont jamais execute que par leur auteur -- peut-etre une fois par le prof... Mais je ne m'attendais pas a ce que ce me soit reproche sur un forum qui se veut celui des professionnels -- meme si je n'ai jamais considere que c'etait le cas.

C'est un peu comme, pour des petits ordres de grandeur, un algorithme O(n²) n'est pas plus critiquable qu'un algorithme O(n log(n)).
std::vector<> est plus performant que std::set<> pour des petites tailles.

Nous ne sommes pas reellement en train de parler d'algorithme et de complexite, mais d'architecture. Et un des aspects de l'architecture est qu'on cherche a se rendre independant des algorithmes pour permettre ce genre de compromis -- on peut meme par exemple envisager de passer d'un algo en N carre en un en N log N en fonction de la taille, parce que les constantes multiplicatives et les termes negliges font que c'est plus performant. Mais ce n'est pas le sujet ici.

Sinon, quand je parlais de calcul formel, j'avais en tête des manipulations genre développer, substituer, factoriser, un truc qui se commande à la main.

Je lis plus une description d'entite qu'on modifie que de valeur sur lesquelles on fait des calculs.

Et en Caml par exemple, les arbres que l'on manipule sont bien des valeurs (en même temps, ces arbres ont une définition purement mathématique, et on est dans un langage fonctionnel).

Mon experience avec les langages fonctionnels est principalement en Lisp. Chaque fois que j'ai essaye de programmer de maniere "fonctionnellement pure", j'ai le probleme qu'il me semble qu'on duplique les donnees pour en jeter l'original a la premiere occasion et ensuite faire a nouveau une copie. J'aime bien la possibilite de faire des raisonnements en utilisant que des choses non mutables -- mais j'ai du mal a voir comment ca passe a l'echelle pour ce sur quoi je travaille (et la je suis bien dans une optique industrielle). Et si tu utilises la mutabilite autorisee par Caml. tu es vraisemblablement aussi dans une optique d'entite.

Pour des exercices ou petites applications à usage personnel, voire académique, je pense que ça se justifie parfaitement de manipuler des arbres de cette façon.

A part des TP, j'en suis pas sur du tout. A mon avis tu arriveras plus ou moins vite aux limitations de l'approche.

[Médinoc]

J'ai du mal à assimiler le problème de "l'entité qu'on modifie", car même avec les types valeurs de .Net, on peut faire ça. Il suffit qu'un type valeur ne soit pas immuable...

Mais à ce moment-là, on peut se dire qu'il n'y a plus de sémantique de valeur "pure". Ce qui signifierait que les seuls types pouvant avoir une sémantique de valeur "pure" sont les types immuables (mais assignables)...

[Jean-Marc.Bourguet]

Mais à ce moment-là, on peut se dire qu'il n'y a plus de sémantique de valeur "pure". Ce qui signifierait que les seuls types pouvant avoir une sémantique de valeur "pure" sont les types immuables (mais assignables)...

C'est bien cela. A part que je suis dans le conceptuel, plus que dans l'implementation.

Avoir un += ne me gene pas du tout.

Avoir une struct ou un conteneur fournissant ==, ne me gene pas tellement -- on est bien a la frontiere entre l'unification et confusion de deux concepts, si l'unification est volontaire et consciente, ca passe avec moi.

Ce qui ne passe pas, c'est si a == b qu'apres c = a; utilisation de c mais pas de a; avoir a != b. On peut se batir un type d'arbre qui ne fonctionne pas comme cela -- c'est ce qu'on va faire dans un langage fonctionnel pur -- mais ce n'est pas naturel. Ce n'est pas nécessairement performant (pour un arbre, on peut elaguer les copies, pour un graphe -- j'en manipule plus que des arbres --, je ne vois pas comment eviter de dupliquer). Ce peut etre utile (par exemple pour avoir une systeme transactionnel -- cet aspect et le raisonnement plus facile sont peut-etre ce qui va rendre le fonctionnel pur viable).

[HanLee]

Mon experience avec les langages fonctionnels est principalement en Lisp. Chaque fois que j'ai essaye de programmer de maniere "fonctionnellement pure", j'ai le probleme qu'il me semble qu'on duplique les donnees pour en jeter l'original a la premiere occasion et ensuite faire a nouveau une copie. J'aime bien la possibilite de faire des raisonnements en utilisant que des choses non mutables -- mais j'ai du mal a voir comment ca passe a l'echelle pour ce sur quoi je travaille (et la je suis bien dans une optique industrielle). Et si tu utilises la mutabilite autorisee par Caml. tu es vraisemblablement aussi dans une optique d'entite.

Ben je sais pas en Lisp, mais en OCaml, je sais que les copies qu'on a l'impression de faire sont la plupart du temps très bien optimisées, dans des problèmes récursifs comme ça.
Pour OCaml qui repose sur le lambda-calcul, et tous les gros machins de théorie derrière, il se débrouille bien sur ce genre de problème.
En C++ oui les copies il les ferait très certainement souvent, et je ne code pas comme en OCaml.

J'utilise rarement la mutabilité en OCaml, sauf pour les gros tableaux de données.

Pour l'industrie, t'as toujours le fait que tu ne contrôles pas tout, et là évidemment je douterais. On a pas autant de déterminisme qu'en C++, à l'inverse, c'est plus confortable.

----

Sinon, je crois que ce qu'on appelle entité chacun désigne quelque chose de différent. Par exemple pour moi mutabilité n'implique pas entité pour moi ; tout ce qui se décrit formellement et se manipule comme en maths, je lui donne une sémantique de valeur.

Pour du lambda-calcul, l'égalité structurelle, je l'appellerais "==".
L'alpha-équivalence, ben je l'appellerais ainsi, et non pas avec "==".
Beta-equivalence, de même.

A part des TP, j'en suis pas sur du tout. A mon avis tu arriveras plus ou moins vite aux limitations de l'approche.

Pour le passage à l'échelle, faudrait tester quoi.
Mais à quelle échelle ?
Celle qui demande de passer à une gestion de pile explicite pour la récursion?

Parce que typiquement pour reprendre mon exemple, j'ai une grosse expression mathématique (grosse pour moi), à développer, et regrouper selon certains termes. J'ai donc un utilitaire perso pour vérifier mes calculs, parce que c'est pas mal pour m'aider, et que j'ai pas Maple (puis parce que je peux personnaliser l'impression).

Ben je sais que la taille des données sera toujours petite du point de vue de mon PC.

[méphistopheles]

Traduction: Deux objets qui ne sont pas du même type sont différents, point. Pas besoin d'appeler un comparateur pour ça, donc on n'a que N comparateurs à écrire (et appeler), plutôt que N².

ha... c'est dommage, j'aurais justement besoin d'avoir A==B qui renvoie vrai si A==(A)B...

[Jean-Marc.Bourguet]

ha... c'est dommage, j'aurais justement besoin d'avoir A==B qui renvoie vrai si A==(A)B...

Tu dois trouver l'ancetre commun le plus proche? Il faut faire des
dynamic_cast et en cas de non succes passer la main au parent qui fera de
meme.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
class B {
public:
   bool operator==(B const& other) {
      return equalHelper(other);
   }
protected:
   virtual bool equalHelper(B const& other) {
      // verifie l'equalite de l'etat observable
   }
};
 
class D: public B {
protected:
   bool equalHelper(B const& otherBase) {
      if (B::equalHelper(otherBase) {
         if (D const& other = dynamic_cast<D const&>(otherBase)) {
            // verifie l'etat propre a D et retourne false
         } else {
            return true;
         }
      } else {
         return false;
      }
   }
};

[Jean-Marc.Bourguet]

Ben je sais pas en Lisp, mais en OCaml, je sais que les copies qu'on a l'impression de faire sont la plupart du temps très bien optimisées, dans des problèmes récursifs comme ça.

Tu peux m'indiquer comment il y a maniere de faire mieux que de ne pas copier les parties qui ne sont pas accessible a partir des noeuds modifies. Dans le cas des arbres, ca revient a elaguer des branches, dans le cas de graphes -- qui m'interesse plus que les arbres -- c'est deja beaucoup plus difficile a determiner, et ca se reduit a rien dans les cas qui m'interessent le plus en pratique, tous les noeuds etant accessible de tous les autres.

Pour OCaml qui repose sur le lambda-calcul, et tous les gros machins de théorie derrière, il se débrouille bien sur ce genre de problème.

Je connais un peu la theorie derriere et je ne vois pas en quoi elle modifie mon point de vue. Je serais enchante qu'on m'indique une structure de donnee adequate -- mais il me semble qu'il y a une impossibilite reelle, j'ai jamais rien trouve qui m'indique le contraire et j'attends encore les references de la part de ceux qui m'ont dit qu'il y en avait.

En C++ oui les copies il les ferait très certainement souvent, et je ne code pas comme en OCaml.

J'ai du mal a voir en quoi la difference de style entre C++ et OCaml est importante ici (le GC?). Si c'est possible pour OCaml, ce doit l'etre en C++ quite a se tapper un GC a la main -- ce qui ne m'effraie pas outre mesure.

Sinon, je crois que ce qu'on appelle entité chacun désigne quelque chose de différent.

Voir le troisieme cas dans ma reponse a Medinoc. Semantique de valeur: on a deux variables egales, on fait une copie d'une que l'on modifie de sorte qu'elle ne se compare plus egale a la premiere variable; si les deux variables initiales sont toujours egales, c'est une semantique de valeur, si l'etat de la deuxieme variable et celui de la copie sont egaux, c'est une semantique de reference (et on ne parlera de preference pas d'egalite)

Par exemple pour moi mutabilité n'implique pas entité pour moi ; tout ce qui se décrit formellement et se manipule comme en maths, je lui donne une sémantique de valeur.

Cela fait longtemps que je suis sorti, mais en math je n'ai jamais eu que des valeurs non modifiables.

[méphistopheles]

Tu dois trouver l'ancetre commun le plus proche? Il faut faire des
dynamic_cast et en cas de non succes passer la main au parent qui fera de
meme.

Le problème est que A peut être n'importe quoi.... je ne peut donc le modifier.... tous ce que je sait est que A a un opérateur ==... si je peut affecter un opérateur operateur==( A &...) dans B, je ne peut faire le réciproque dans A....


auriez vous une idée ?