IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C Discussion :

polymorphisme par sous-typage


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    amateur
    Inscrit en
    Avril 2012
    Messages
    145
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : amateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Avril 2012
    Messages : 145
    Par défaut polymorphisme par sous-typage
    Bonjour,

    J'ai sans doute besoin d'implanter manuellement l'équivalent du polymorphisme par sous-typage. Ci-dessous j'explique un peu mon appli pour que vous puissiez vous en faire une idée et peut-être avoir un point de vue différent ; puis je montre ma solution actuelle avec polymorphisme, au cas où vous verriez une façon plus simple de faire.
    Ca va être un peu long, désolé, mais autant vous fournir toutes les billes d'un coup putôt qu'au compte-gouttes.

    Le projet est une bibliothèque de parsing du style PEG. Voici un exemple de motif et de textes-sources qui y correspondent:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    définition du motif:
     
    nom         <-- lettre+
    DEUXPOINTS  <-- ":"
    téléphone   <-- chiffre{10}
    favori      <-- "*"
    opt_favori  <-- favori?
    contact     <-- nom DEUXPOINTS téléphone opt_favori
     
    sources corrects:
     
       "Marco:9876543210"
       "Maria:0123456789*"
    La bibliothèque définit une variété de *types* de motifs, comme les litéraux (DEUXPOINTS), les chaînes (nom), les composites (contact) et bien d'autres. On voit que certains motifs complexes incluent dans leur définition un ou plusieurs sous-motifs.
    Chaque type de motif est conceptuellement une struct d'un type donné avec les infos qui le définissent en fonction de son type (chaîne litérale, classe de caractère, sous-motif(s)...). Il y a au moins 2 méthodes pour chaque type : 'notation' construit un texte pour l'affichage, 'trial' tente de "matcher" (faire correspondre) le source avec le motif (à la position courante). Dans le cas d'un motif complexe, chacune de ces 2 routines doit (récursivement) faire appel aux routines correspondantes de ses sous-motifs : pour afficher contact, il faut afficher nom, DEUXPOINTS, téléphone, opt_favori ; de même pour matcher contact, il faut matcher chacun de ses sous-motifs.
    J'espère que je suis clair jusque là.

    Il me semble que pour faire cela, il n'y a pas moyen d'échapper à une sorte de sous-typage. Je suis obligé d'avoir une routine 'notation' et une routine 'trial' génériques, puisque je ne peux pas connaître à l'avance les types de sous-motifs. Ca veut dire qu'en fait il y a conceptuellement une sorte de super-type 'Pattern' (motif), avec une série de variantes. Pattern serait donc une union étiquetée (tag-ée), et ses 2 routines principales consisteraient chacune juste en un grand switch fonction du tag de type.
    Est-ce que vous voyez des alternatives possibles ? Comment réalise-t-on ce genre de choses, typiquement, en C ? Est-ce que je passe à côté d'une façon plus simple de faire ça ?

    Concrètement, j'ai plutôt scindé Pattern en deux, avec les champs génériques (juste le nom et le tag) d'une part, et de l'autre une union anonyme qui contient les données de définition du motif en fonction de son type. Ca donne:

    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
    26
    27
    28
    29
    30
    31
    32
    typedef struct PatternData * Pattern ;
     
    /* pattern type tags
    */
    typedef enum {
       LITERAL, CLASS, WORD,
       OPTION, CHOICE, 
       REPETE0, REPETE1, REPETEN,
       COMPOSE,
       /*PREFIX, POSTFIX, DELIM, LIST, */ /* ***TODO*** */
    } PatternType ;
     
    /* generic pattern type
    */
    typedef struct PatternData {
       PatternType type ;         // type tag
       Text name ;
       union {
          Literal     literal ;
          Class       class ;
          Word        word ;
          Option      option ;
          Choice      choice ;
          Repete0     repete0 ;
          Repete1     repete1 ;
          RepeteN     repeteN ;
          Compose     compose ;
       } ;
    } PatternData ;
     
    Text pat_notation (Pattern pat) ;
    Node pat_trial (Pattern pat, Source src) ;
    Et chaque type de motif consiste ainsi en une mini-struct avec (essentiellement) les versions spécifiques des 2 "méthodes" principales, plus un "constructeur" ; par exemple pour le type Compose:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    typedef struct Compose {
       Pattern     *subpats ;
       uint        count ;     // count of sub-patterns
    } Compose ;
     
    Pattern compose (Pattern *subpats, uint count) ;   // "constructeur"
    Text compose_format (Pattern pat) ;
    Node compose_trial (Pattern pat, Source src) ;
    La réalisation est ensuite toute con. Pout noter ou matcher un motif d'un type donné, j'accède juste à la variante correspondante de l'union, par exemple pat.compose. Et la routine générique est bien juste un big switch:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    Node compose_trial (Pattern pat, Source src) {
       Pattern * subpats = pat->compose.subpats ;
       uint count        = pat->compose.count ;
       // ... et puis matcher (les sous-motifs) ...
    }
     
    Node pat_trial (Pattern pat, Source src) {
       switch (pat->type) {
          case LITERAL   : return literal_trial (pat, src) ; break ;
          // ... tout plein d'autres types ...
          case COMPOSE : return compose_trial (pat, src) ; break ;
          default  : assert(0) ;
       }
    }
    Pour chaque type de motif, je définis donc un type de struct correspondant et les 2 méthodes spécifiques, ce qui est très bien. Mais en plus, je dois ajouter le type (1) dans la liste des tags (2) dans la liste des variantes de l'union (3) dans les switchs des méthodes génériques. Et tout ça ça me gonfle un peu : c'est stupide, c'est redondant, il n'y a pas de code dedans, bref c'est du boulot pour une machine.
    Y a-t-il mieux à faire ? Comment vous y prendriez-vous pour implanter une sorte de polymorphisme par sous-typage ?
    Tou conseil bienvenu,
    merci,
    Denis

  2. #2
    Membre confirmé
    Profil pro
    amateur
    Inscrit en
    Avril 2012
    Messages
    145
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : amateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Avril 2012
    Messages : 145
    Par défaut pas de succès !
    Bon, je reformule :
    Comment avoir le plus simplement possible en C l'équivalent de ce qu'apporte le sous-typage ? Càd que je peux appeler une méthode 'm' sur un élément 'e' et que la bonne méthode sera appelée en fonction du type effectif de 'e'.
    Sinon, comment faire autrement ?

    Denis

  3. #3
    Inactif  


    Homme Profil pro
    Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Inscrit en
    Décembre 2011
    Messages
    9 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : France, Loire (Rhône Alpes)

    Informations professionnelles :
    Activité : Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 9 026
    Par défaut
    Je dois avouer que je ne sais pas du tout comment faire sans utiliser ta méthode.

    Je ne sais pas exactement ce que tu veux faire, mais ne serait-il pas plus judicieux d'utiliser le C++ ?

  4. #4
    Membre confirmé
    Profil pro
    amateur
    Inscrit en
    Avril 2012
    Messages
    145
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : amateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Avril 2012
    Messages : 145
    Par défaut
    Citation Envoyé par Neckara Voir le message
    Je dois avouer que je ne sais pas du tout comment faire sans utiliser ta méthode.

    Je ne sais pas exactement ce que tu veux faire, mais ne serait-il pas plus judicieux d'utiliser le C++ ?
    Ouais, en fait ce que je veux faire ressemble tout-à-fait à ce qui est résolu en c++ par les vtables. Mais je voudrais éviter c++ absolument : trop compliqué pour moi, déjà que j'ai du mal avec certains aspects de C ; et aussi, à terme, il est possible que certains de mes projets ou sous-projets soient intéressants pour autrui, alors si j'utilise C presque tout programmeur peut au moins comprendre, si j'utilise c++ pour une majorité autant programmer en chinois. Non, en fait, si je veux vraiment un sur-ensemble de C avec OO mieux fait, je passe à D (que je connais assez bien), ou encore (pour la lisibilité) à Pascal Objet; ou à Go. J'ai considéré toutes ces options (et suffisamment programmé dans ces langages) et conclu que C est encore le mieux.

    Alors, je vais produire un exemple de ce que le "dynamic dispatch" pourrait donner selon mon point de vue, sur un cas fictif simpliste, dans une réponse d'ici peu. En gros, j'ai un gros problème de type pour la vtable.

    Merci de ta réponse,
    Denis

  5. #5
    Inactif  


    Homme Profil pro
    Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Inscrit en
    Décembre 2011
    Messages
    9 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : France, Loire (Rhône Alpes)

    Informations professionnelles :
    Activité : Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 9 026
    Par défaut
    Le C++ n'est pas plus compliqué que le C.
    Je dirais même au contraire, avec tous les conteneur de la STL on gagne un temps fou ainsi qu'en lisibilité.
    Mais c'est vrai que si tu ne fait que tu C, le C++ te paraîtra toujours plus compliqué^^


    si j'utilise C presque tout programmeur peut au moins comprendre, si j'utilise c++ pour une majorité autant programmer en chinois
    Je ne suis pas d'accord. Le C++ reste assez compréhensible même pour les personne n'en faisant pas car il intègre une syntaxe quasi identique avec celle du C. Ensuite le C++ reste un langage assez répandu, pas autant que le C certes.

    Ensuite, es-tu sûr qu'en essayant de faire ton "sur-ensemble de C avec OO mieux fait" tu resteras assez compréhensible par des personnes connaissant le C mais pas le C++? Est-ce que tu resteras même suffisamment compréhensible par les personne faisant du C++?


    Si tu veux que tes sources soient intéressante, je pense que la documentation (@see doxygen) est plus intéressante que le langage utilisé.
    Un code en C mal documenté et compliqué sera compris par bien moins de personnes qu'un code C++ bien documenté donc si tu commente correctement un code C++, n'importe qui pourrait comprendre ce que ton code fait. Après, l'auto-documentation est une chose omniprésente en informatique.


    Je ne critique en aucun cas ton choix, mais plutôt ton argument
    Sinon, j'ai cru voir pas mal de tutoriel sur la programmation orienté objet dans la partie tutoriel C mais il me semble que tu les as déjà lu.

    Bon courage pour la suite^^

  6. #6
    Membre confirmé
    Profil pro
    amateur
    Inscrit en
    Avril 2012
    Messages
    145
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : amateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Avril 2012
    Messages : 145
    Par défaut
    Citation Envoyé par Neckara Voir le message
    Ensuite, es-tu sûr qu'en essayant de faire ton "sur-ensemble de C avec OO mieux fait" tu resteras assez compréhensible par des personnes connaissant le C mais pas le C++? Est-ce que tu resteras même suffisamment compréhensible par les personne faisant du C++?
    Je voulais dire que le langage D est un "sur-ensemble de C avec OO mieux fait" (que C++) (d'après non pas moi-même, mais une myriade de commentateurs dont nombre d'amateurs et concepteurs de langages de prog). C'est la raison pour laquelle je me suis tourné vers D, Pascal Objet, Go, mais pas C++. Subjectivement, je considère C++ comme l'équivalent statique de Perl : un immense foutoir ; mais c'est pas un jugement, hein !, je dis bien sub-jec-ti-ve-ment.
    De mon côté, je me contente de chercher des solutions aussi claires que possibles pour les qq petites choses qui (me) manquent vraiment en C, dont pour l'instant:
    * la généricité, c'est-à-dire +/- le mal-nommé "polymorphisme pararamétrique", surtout pour un type standard de tableau dynamique -- objet d'une prochaine discussion
    * la "spécificité", c'est-à-dire +/- le le polymorphisme par sous-typage -- objet de cette discussion-ci
    * les espaces de noms (!)

    Bon courage pour la suite^^
    Merci,
    Denis

  7. #7
    Membre confirmé
    Profil pro
    amateur
    Inscrit en
    Avril 2012
    Messages
    145
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : amateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Avril 2012
    Messages : 145
    Par défaut exemple
    Alors voilà, le cas le plus simple de "supertype" avec 2 "soustypes", l'un équipé d'un entier naturel, l'autre d'un entier signé ; et 2 "méthodes", l'une affiche l'élément et l'autre dit si le nombre est impair :

    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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    // types
    typedef unsigned int uint ;
    typedef signed   int sint ;
    typedef enum {T_UINT, T_SINT} SubType ;
     
    typedef struct T {
       SubType subtype ;
       union {
          uint u ;
          sint s ;
       } ;
    } T ;
     
    // "contructors"
    T t_uint (uint u) { return (T) {T_UINT, .u=u} ;}
    T t_sint (uint s) { return (T) {T_SINT, .s=s} ;}
     
    // "methods"
    void t_uint_note (T t) {
       assert (t.subtype == T_UINT) ;
       printf ("T_UINT(%u)\n", t.u) ;
    }
    void t_sint_note (T t) {
       assert (t.subtype == T_SINT) ;
       printf ("T_SINT(%i)\n", t.s) ;
    }
    bool t_uint_odd (T t) {
       assert (t.subtype == T_UINT) ;
       return (t.u % 2 == 1) ;
    }
    bool t_sint_odd (T t) {
       assert (t.subtype == T_SINT) ;
       return (t.s % 2 == 1) ;
    }
    Pour l'instant, ce que je fais est d'ajouter des méthodes bidon au super-type avec un dispatch explicite via switch, pour chaque sous-type :

    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
    // "dispatch by code"
    void t_note (T t) {
       switch (t.subtype) {
          case T_UINT : t_uint_note (t) ;
          case T_SINT : t_sint_note (t) ;
          default : assert (0) ;
       }
    }
    void t_odd (T t) {
       switch (t.subtype) {
          case T_UINT : t_uint_odd (t) ;
          case T_SINT : t_sint_odd (t) ;
          default : assert (0) ;
       }
    }
    Alors c'est du code "idiot" au sens de mécanique, répétitif, prévisible. C'est à la machine de faire ça (en l'occurrence la "machinerie" du langage). Voilà comment je vois ça en pseudo-code:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // "dispatch by subtyping"
    typedef void (*Method) (T t) ;          // ???
    typedef enum {NOTE, ODD} MethodID ;
    const Method methods [2] [2] = {
       {&t_uint_note, &t_uint_odd} ,
       {&t_sint_note, &t_sint_odd}
    } ;
     
    void t_apply (MethodID m, T t) {
       methods[t.subtype][m] (t) ;
    }
    La table methods' est une sorte de tableau de vtables, une vtable par sous-type.. L'usage de t_apply serait simplement du genre "t_apply (NOTE, t)" ce qui afficherait t correctement en fonction de son type ; sans que j'aie besoin de connaître les versions de méthodes spécifiques aux sous-types (ni même s'il en existe une pour ce sous-type-là).

    Une optimisation (comme en c++ et tous les langages objets statiques, je pense) est de remplacer les tags de sous-types par un pointeur sur la vtable, mais j'en suis pas là !

    Ca risque pas de marcher car je ne sais pas du tout quel type donner au tableau 'methods', vu que chaque méthode a son propre type. De plus, chacune peut prendre d'autres paramètres que l'"objet" receiver (T t) ; ça, ça peut peut-être être résolu grâce aux varargs (paramètres variadiques). Mais aussi, chaque méthode peut retourner des résultats de types différents ; c'est pourquoi mon exemple plante (avec un type de pointeur erronné pour les méthodes _odd) ; la valeur de retour quand il y en a une devrait être récupérée (dans une variable de quel type?) et retournée par t_apply (ce qui change son propre type). Enfin, il peut y avoir changement de paramètres et/ou type de retour suivant le sous-type (notamment quand la valeur de retour est justement du sous-type).

    Voilà où j'en suis. Je pense donc pour l'instant que ce n'est pas faisable sans magie du compilateur.

    Denis

  8. #8
    Inactif  


    Homme Profil pro
    Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Inscrit en
    Décembre 2011
    Messages
    9 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : France, Loire (Rhône Alpes)

    Informations professionnelles :
    Activité : Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 9 026
    Par défaut
    J'ai peu être une idée :

    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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
     
    //vtable
     
    typedef struct
    {
             Fonction * listeFonction;
    } Vtable;
     
    //fonctions à rajouter :
    vtableAdd(Vtable *, Fonction *);
    vtableClear(Vtable *);
    lancerFonction(Vtable *, void * instanceClasse, char * nomFonction, Parametre *);
     
    //fonction
    typedef struct m_fonction
    {
              struct m_fonction * suivante;
              char * nomFonction;
              ListeTypeParam parametres;
              (void *)(Parametre *) fonction; //pointeur sur fonction
    }Fonction
     
    //Parametre
    typedef struct
    {
             ListeTypeParam param;
             ListeValeurs v;
    }Parametre;
     
    //fonctions à rajouter :
    addParam(Parametre *, int typeParam, void * valeur);
    clearParam(Parametre *);
     
    //ListeTypeParam :
    typedef struct m_ltp
    {
               struct m_ltp * suivant;
               int type;
    }TypeParam , * ListeTypeParam;
     
    //ListeValeur
    typedef struct m_valeur
    {
             struct m_valeur * suivant;
             void * valeur;
    }Valeur, *ListeValeur
    Avec ça tu pourras même faire des fonctions virtuelles théoriquement.

    Après, il y a certaines choses que tu ne pourras pas faire sans réécrire le compilateur.

  9. #9
    Membre confirmé
    Profil pro
    amateur
    Inscrit en
    Avril 2012
    Messages
    145
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : amateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Avril 2012
    Messages : 145
    Par défaut
    Citation Envoyé par Neckara Voir le message
    J'ai peu être une idée :

    Avec ça tu pourras même faire des fonctions virtuelles théoriquement.

    Après, il y a certaines choses que tu ne pourras pas faire sans réécrire le compilateur.
    Ouais, c'est la prochaine étape

    Trève de plaisanterie. Je te remercie beaucoup Neckara.
    Ton exemple de réalisation montre clairement (je crois) que ça peut pas être fait simplement sans "magie" du compilateur, ou l'équivalent réimplanté manuellement. En fait, il me semble que toute l'information que (re)crée et trimballe ton code, nécessaire pour bien gérer ces pseudo-méthodes, c'est très similaire à toutes les méta-informations que décode et trimballe un compilo (pour langage statique), qu'il abandonne ensuite pour l'efficacité. Et c'est aussi similaire à à ce que nous redonne en partie la RTTI (runtime type info) dans certains langages.

    Denis

Discussions similaires

  1. [A-07] - Etat trié par sous totaux
    Par burgall dans le forum IHM
    Réponses: 8
    Dernier message: 21/12/2008, 17h01
  2. Sous-typage et volume de données
    Par shadeoner dans le forum SQL
    Réponses: 7
    Dernier message: 17/10/2008, 11h29
  3. [POO] Sous-typage variance/contravariance dans Java
    Par yienyien dans le forum Langage
    Réponses: 3
    Dernier message: 30/03/2007, 10h43
  4. Heritage par sous classe avec discriminateur
    Par hipchic dans le forum Hibernate
    Réponses: 1
    Dernier message: 04/01/2007, 19h51
  5. Réponses: 36
    Dernier message: 09/09/2006, 03h06

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo