[Conception] Polymorphisme paramétrique ou d'inclusion ? Cas litigieux…

Version imprimable

01/09/2009, 12h47
Florian Goo

[Conception] Polymorphisme paramétrique ou d'inclusion ? Cas litigieux…
Bonne rentrée, les C++iens !

Je me remets sur mon projet et je suis face à un problème de conception. J'ai hésité à poster dans le forum conception général, mais tout ceci est je trouve assez propre au C++.

Voilà le problème.
Je souhaite modéliser les entités sémantiques du C++ : les namespaces, les classes, les fonctions et tout et tout. Restons-en à ces trois types d'entités.
Je suis partagé entre deux solutions :
1. mettre en place un pattern composite transparent (une interface scope que les classes namespace_, class_ et function vont implémenter d'une part et agréger d'autre part), en utilisant le polymorphisme d'inclusion ;
2. ou faire une totale distinction entre ces trois classes, en utilisant le polymorphisme paramétrique.
Le problème avec la solution 1, c'est qu'elle n'est pas type-safe. Si j'écris une interface scope contenant une fonction permettant d'ajouter un namespace, cela n'aura pas de sens pour les objets de type class_ et function.
Après, avec un pattern Visitor, on peut toujours s'en sortir.

Le problème avec la solution 2, c'est la nécessité d'émuler le polymorphisme d'inclusion à plusieurs endroits du code (grâce à des outils du style boost::variant), tels que :
- la liste (présente dans chaque objet des trois classes) des nœuds enfants dans l'arborescence des scopes ;
- le type de retour de certaines fonctions (qui peuvent renvoyer un objet d'un des trois types).
Cette nécessité m'apparait comme symptomatique d'un mauvais choix de type de polymorphisme, mais ce n'est rien de plus qu'une sensation.

Chacune des deux solutions ne fait que me pousser vers l'autre. Le choix est tellement cornélien que je préfère me tourner vers ceux d'entre vous qui ont plus d'expérience en conception. Que faites-vous dans ce genre de situation ? (Peut-être une solution 1,5 ?)

Merci à vous !
01/09/2009, 13h58
Jean-Marc.Bourguet

Citation:

Envoyé par Florian Goo

Le problème avec la solution 1, c'est qu'elle n'est pas type-safe. Si j'écris une interface scope contenant une fonction permettant d'ajouter un namespace, cela n'aura pas de sens pour les objets de type class_ et function.

Ce genre de restrictions est plus accidentelle qu'essentielle. Je ne les enforcerais pas dans le systeme de type.

En passant, ceci peut t'interesser.
01/09/2009, 14h48
Florian Goo

Solution 1 sans hésitation, alors ?
01/09/2009, 15h35
Alp

Oui, a priori. Tu peux enforcer les règles de scoping dans ton mécanisme de dispatch, ce que tu peux aussi faire avec du polymorphisme paramétrique mais qui lui te pousse à utiliser boost::variant alors que le polymorphisme d'inclusion semble adapté quoi.
01/09/2009, 17h14
loufoque

Personnellement, je ne vois pas en quoi la solution 1 est pertinente, puisqu'il faudra downcaster ou visiter.
L'utilisation d'un variant a plus de sens, mais peut être plus lourde syntaxiquement.
02/09/2009, 00h33
Florian Goo

Si vous-même êtes en désaccord sur ce point, ça me rassure sur mon propre niveau ;).
Mais ça ne fait que me tirailler encore plus entre les deux possibilités…

Si cela pouvait donner lieu à un débat, ce serait formidable.
Mais à défaut (ou même en complément), auriez-vous de la littérature pertinente sur le sujet ?
02/09/2009, 00h38
metagoto
Citation:
Envoyé par Florian Goo

Le problème avec la solution 2, c'est la nécessité d'émuler le polymorphisme d'inclusion à plusieurs endroits du code (grâce à des outils du style boost::variant), tels que :

la liste (présente dans chaque objet des trois classes) des nœuds enfants dans l'arborescence des scopes ;
le type de retour de certaines fonctions (qui peuvent renvoyer un objet d'un des trois types).
En me basant sur ces seuls points, j'ai l'impression qu'un boost variant recursif pourrait faire l'affaire. J'ose même espérer que cela soit plus simple qu'une solution dynamique au regard des inconvénients qui ont été énumérés.
Dans le doute, autant privilégier une solution statique.
(après, je dis ça, je dis rien... :oops:)
02/09/2009, 08h55
Jean-Marc.Bourguet

Citation:

Envoyé par Florian Goo

Solution 1 sans hésitation, alors ?

Non, je n'ai pas reflechi au probleme assez pour avoir une preference entre les solutions que tu indiques ou pour une alternative que je te proposerais -- pour bien concevoir il faut savoir non seulement ce qui est modele mais aussi le contexte d'utilisation. Ca demande du temps que je n'ai pas.

Simplement la raison que tu donnes contre elle ne me semble pas particulierement pertinente.

Personnellement je définirais le meta-schéma de manière à ce qu'il soit type-safe. Donc une variation du modèle composite où n'importe quoi ne peut pas être inclu dans n'importe quoi ;) Style:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Namable { string name; list<Namable&> getChildren() = 0; // Pas d'attribut liste, délégué aux enfants }; class Method : public Namable { Class& parent; }; class Class : public Namable { list<Method&> methods; }; class Function: public Namable { }; class NameSpace : public Namable { list<Class&> classes; list<Functions&> functions; };
Si tu veux éviter d'avoir plusieurs listes par classe, tu peux toujours faire des interfaces de marquage (genre INameSpaceable = je peux le mettre dans un name space) mais je crois qu'un typage fort te donnera une meilleure sémantique (par exemple en offrant une méthode NameSpace::getClasses()).

02/09/2009, 11h55
Florian Goo

Merci pour vos réponses, je fais rentrer tout ça dans la machine à mouliner ;).

Finalement ça débouche peut-être sur une question plus simple : quand utiliser le pattern Visitor et quand utiliser boost::variant (ou autre) ?

Salut,

Pourquoi ne pas passer par des type traits :question:

Tu aurais une classe de base scope proche de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Scope
{
    public:
        Scope(Scope const *, std::string const &);
        std::string const & name()const;
        std::string const entiereScopeName() const;
        virtual void addNamespace(Scope const &) = 0;
        virtual void addClass(Scope const &) = 0;
        virtual void addFunction(Scope const &) = 0;
    private:
        Scope * parent_;
        std::string name_;
        std::list<Scope&> children_;
};

et des traits de politique proche de

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
struct AllowedNamespace
{
    static void check(){/* just does nothing while there are  allowed */}
};
struct ForbiddenNamespace
{
    static void check(){throw NameSpaceForbidden();}
};
struct AllowedClass
{
    static void check(){/* just does nothing while there are  allowed */}
};
struct ForbiddenClass
{
    static void check(){throw ClassForbidden();}
};
struct AllowedFunction
{
    static void check(){/* just does nothing while there are  allowed */}
};
struct ForbiddenFunction
{
    static void check(){throw FunctionForbidden();}
};
/* il y en a peut etre d'autres*/

et une définition de ta classe concrète proche de

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
template <class NameSpacePolicy,
              class ClassPolicy,
              class FunctionPolicy
              /*, et toutes les autres  */
        >
class TConcreteScope : public Scope
{
 
        virtual void addNamespace(Scope const& s)
        {
            NamespacePolicy::check();
            children_.push_back(s);
        }
        virtual void addClass(Scope const &)
        {
            ClassPolicy::check();
            children_.push_back(s);
        }
        virtual void addFunction(Scope const &)
        {
            FunctionPolicy::check();
            children_.push_back(s);
        }
};

Après, tu n'a plus qu'à définir les alias de types qui vont bien:

Code:

1
2
3
typedef TConcreteScope<AllowedNamespace,
                       AllowedClass,
                       AllowedFunction> MyNameSpace;

De cette manière, tu profite tout à la fois du polymorphisme dynamique et de la souplesse de définition des différents scopes réels ;)

Nota: tu pourrais remplacer le lancement d'une exception par le simple fait de ne pas déclarer la fonction check dans les ForbiddenXX... ainsi, la vérification se ferait à la compilation :D

Ceci dit, c'est peut être justement ce que propose boost::any :aie:

03/09/2009, 19h37
Florian Goo
Bon, concentrons-nous sur un cas d'utilisation en particulier, histoire d'ajouter les contraintes une à une. (Après, quel que soit la solution sur ce point, cela ne veut pas dire que je ne doive jouer qu'avec un seul type de polymorphisme, comme le suggère koala.)

Je vais avoir des fonctions de recherche qui vont implémenter le name-lookup.

Par exemple, il y a une fonction find_unqualified_name() à qui on donne un nom et un scope et qui nous renvoie l'entité associée à ce nom. Ça peut être une variable, une classe, un type en général, une fonction, un namespace… tout et n'importe quoi, inconnu à la compilation.

Cette fonction devra donc renvoyer au choix :
1. un named_entity* (où named_entity est une interface qui sera implémentée par les classes namespace_, class_, function, variable et toutes les autres) ;
2. un boost::variant<namespace_, class_, function, variable, …>*.
La solution 1 est simple, facile, classique. Je dirais même Java-like, avec les bons et les mauvais côtés.

La solution 2 me parait peu envisageable, pas vous ?
Certes, il sera toujours possible de rendre le code de la fonction modulaire et indépendant : le type de retour pourrait être passé en paramètre template. On pourrait imaginer un header définissant un typedef de ce variant.
Mais peut-on pousser le vice du polymorphisme paramétrique jusque là ?

(Ou alors tout autre chose, ce que je peux peut-être faire, c'est forcer le type de retour. Tout dépend des cas d'utilisation. Je vais essayer de réfléchir à ça…)

Peut être pourrait-on envisager une "amélioration" de la TypeList de loki...

Je fais tout cela de tête, et sans avoir réellement réfléchi, mais la typeliste loki par d'un truc proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 struct NullType{}; template <typename T, typename U> struct TypeList { typedef T Head; typedef U Tail; }; /* spécialisation de marqueur de fin de liste */ template <typename T> struct TypeList<T, NullType> { typedef T Head; typedef NullType Tail; };
Peut être, pourrait-on envisager de rajouter une "dimension" supplémentaire et "perpendiculaire" afin de créer un arbre, sous une forme proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 template <typename T, typename U, typename V> struct TypeTree { typedef T Head; typedef U Tail; typedef TreeType<T, U, V> Child; }; /* spécialisation représentant une feuille */ template<typename T, typename U, NullType> struct TypeTree { typedef T Head; typedef U Tail; typedef NullType Child; }; /* spécialisation d'un noeud "terminal" */ template <typename T> struct TypeTree<T, NullType, NullType> { typedef T Head; typedef NullType Tail; typedef NullType Child; };
Il faudra sans doute un peu "broder" autour pour que ce soit intéressant (comprend: fournir des foncteurs permettant de manoeuvrer ce type d'arbre), mais, lorsque tu sais rechercher quelque chose "d'horizontal", tu voyage entre Head et Tail, et, si tu veux rechercher quelque chose de " vertical" (un enfant), tu voyage de Head à Child...

Au final, étant donné que la notion de portée peut être étendue largement au delà des seuls espaces de noms, structures (classes) et fonctions, tu pourrais, pour ainsi dire,

partir d'un "projet" (qui est... nommé), subissant des restrictions telles qu'il ne peut contenir que... des modules,
Avoir des modules qui n'auraient pas d'autres restrictions que... de ne pas pouvoir contenir de projet (il peuvent contenir des fonctions, des structures, des espaces de noms et même des variables(globales en l'occurence), des énumérations, des alias de type ou des unions )
Avoir des espaces de noms qui pourraient avoir tout ce qu'un module peut avoir exception faite... d'un module
Avoir des structures (ou des classes) qui pourraient tout avoir tout ce qu'un espace de noms peut avoir exception faite... de l'espace de noms
Avoir des unions qui pourraient avoir tout ce qu'une structure (ou une classe) peut avoir à l'exception des fonctions
Avoir des énumérations qui ne pourraient avoir que... des valeurs énumérées
Avoir des alias de types qui ne pourraient avoir que... le nom de l'alias
Avoir des fonctions qui pourraient n'avoir que des variable, des instructions et des blocs d'instructions
Avoir des blocs d'instructions qui pourraient avoir des blocs d'instructions, des instructions et des variables
...
Pour gérer les différentes restictions, le recours à la TypeList by loki peut être intéressant sous une forme proche de
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 template <typename TList, typename T> struct check; template <typename Head , typename Tail , typename T> struct check<TypeList<Head,Tail>,T> { enum { value= SameType<Head,T>::value || check<Tail,T>::value }; }; template <typename T> struct check<NullType,T> { enum { value = false }; }; template <> struct check<NullType,NullType> { enum { value = true }; }; /* un alias de type fournit pour la facilité représentant un accord sans * restriction */ typedef check<NullType,NullType> AllowedTrait; /* un alias de type fournit par facilité représentant un désaccord sans * discussion */ typedef check<NullType,void> ForbiddenTrait;
En partant d'une interface unique telle que celle que j'ai présenté plus haut,
tu pourrais en arriver à quelque chose proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Scope { /* je vais pas tout réécrire, c'est une interface présentant exclusivement * des fonctions virtuelles pures */ }; template <typename Data // le type de donnée manipulé class PolicyOne, // pour chaque politique particulière (en dehors class PolicyTwo, // des types admis) on a le choix entre class PolicyThree, // un typedef adapté de check , class PolicyFour, // AllowedTrait ou ForbiddenTrait class TreePolicy // basé sur notre classe TypeTree, sans doute ;) > class TreeNode { /* une fonction qui a besoin de l'une des politiques autres */ virtual void foo() { if(!PolicyOne::value) throw ExceptionParticuliere(); } };
Et tu devrais presque pouvoir créer autant de type que tu veux avec un simple typdef à chaque fois :D

03/09/2009, 21h40
Jean-Marc.Bourguet

Citation:

Envoyé par Florian Goo

Finalement ça débouche peut-être sur une question plus simple : quand utiliser le pattern Visitor et quand utiliser boost::variant (ou autre) ?

J'ai du mal à voir pourquoi tu opposes les deux.

Le pattern visiteur, c'est quand tu as une structure de donnée et que tu veux appliquer une opération sur chaque élément contenu. On fait un object pour l'opération, la structure de donnée a un membre qui l'admet et l'applique à chaque élément -- ou à une sélection de ceux-ci. Si on a un arbre par exemple, on peut fournir des visiteurs pour une visite préfixe, infixe ou postfixe de l'arbre. Et un aspect variant dans les visiteurs, c'est commun ce contrôle -- choix et ordre des éléménts visités -- est fait; suivant les situations on le poussera plutôt dans la classe visitée ou dans le visiteur.

Une situation très commune est que le type des éléments contenus peut varier dynamiquement. Comme l'opération dépend dynamiquement aussi du visiteur on a besoin d'un double dispatch. Le C++ n'en ayant pas, on présente souvent ce pattern avec un des idiomes permettant le double dispatch. Cet aspect est tellement commun qu'il y a de la confusion qui s'est installée entre le pattern visiteur et l'idiome du double dispatch.

boost::variant, c'est un moyen simple de bâtir un type somme, avec une interface visiteur pour appliquer une opération sur l'unique élément contenu dedans (dans un cas dégénéré comme ici où il n'y a qu'un élémént, la différence entre double dispatch et visiteur est plus une différence d'intention que de méthode).

J'ai donc du mal à opposer les deux. Je vois mal à quoi j'opposerais le pattern visiteur en C++.

Boost variant peut s'opposer à la construction d'une hiérarchie fermée (ce dont dépendent l'idiome le plus fréquent de dispatch multiple). Quelques éléments:

- boost variant est bien adapté au sémantique de valeur, les hiérarchies à celles d'entité
- boost variant est bien adapté quand les types rassemblés sont indépendants, quand ils ne le sont pas les hiérarchies rendent l'aspect commun plus visible

Dans le cas de hiérarchie fermée, il faut aussi considérer la possibilité d'avoir un tag explicite (un membre indiquant de quelle classe il s'agit). Un test ou un switch sur celui-ci peut être plus clair qu'un double dispatch.

Dans ton cas, je pencherai plutôt vers la hiérarchie, justement à cause des deux points donnés: on a affaire à des entités ayant un comportement en partie commun. Je considérerais la possibilité d'avoir un tag. En passant, on est dans un cas où je vois de l'héritage multiple arriver naturellement: une classe est un scope tout comme elle est un type.