Free Automatons with State and Transitions : soumission d'un projet

Rapide cours sur les templates : un template n'est instanciée qu'à l'utilisation. Ceci signifie qu'une classe template n'aura son code qui ne sera défini qu'au moment de la première utilisation de la classe. Un exemple pour visualiser (non testé) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <iostream>   struct AnnoncerInstanciation { AnnoncerInstanciation() { std::cout << "AnnoncerInstanciation instancie !" << std::endl; } };   template <typename T> struct TrucMuche { static AnnoncerInstanciation ann; }; template <typename T> static AnnoncerInstanciation TrucMuche::ann;   int main() { TrucMuche<int> t; // On instancie TrucMuche<int> => Va afficher }   void foo(TrucMuche<float>) { // On instancie TrucMuche<float> => Va afficher TrucMuche<int> t; // TrucMuche<int> a déjà été instancié par main => Ne va rien afficher }

---

On devrait donc ici voir deux fois le message d'instanciation affiché.

Bien. Maintenant que le principe d'instanciation est compris (si il ne l'était pas déjà), le problème d'une "variable template".
En effet, une variable template est impossible !

Exemple :

Code:

---

template <typename T> TrucMuche<T> truc;

---

Comment utiliser truc ? Comment le compilateur sait-il, lorsqu'il voit une référence à truc, qu'il a affaire à TrucMuche<int> ou à TrucMuche<float> ? Ou même à TrucMuche<UnTypeQueJeNeConnaissaisPasMaisQuiEstUtiliseQuelquePart> ?

D'où l'astuce de la variable statique dans une structure template.

D'ailleurs, jusqu'à c++11, c'était aussi un typedef dans une structure template qui était utilisé pour les alias partiels de templates, par exemple :

Code:

---

1 2 3 4 5 6 7

template <typename T, typename U> Truc { /* ... */ };   template <typename T> DoubleTruc { typedef Truc<T, T> type; };

---

Cette technique est très utilisée dans de nombreuses bibliothèques, par exemple boost.MPL, bibliothèque de travail sur les types à la compilation.

Salut,

Effectivement comme l'a précisé le prologinien du dessus je ne pensais pas vraiment à une variable globale (qui sont a prohibé au maximum et particulièrement en C++, et si jamais tu dois en utiliser, met les dans des namespaces associés).

Utiliser une variable globale dans ce cas ne résout aucun problème car ça revient plus ou moins à utiliser une variable d'instance, donc ce n'est ni thread safe, ni rien du tout.

Je pensais que l'utilisateur pourrait faire quelque chose du style (je n'ai pas le code sous les yeux pour le moment, mais je vais essayer de ne pas écrire de bétises):

Code:

---

1 2 3 4 5 6 7 8 9 10 11

// Dans le main state current_state = mon_automate.get_initial_states(); std::string ma_sequence = "aaaba"; std::string::iterator b = ma_sequence.begin(); std::string::iterator e = ma_sequence.end(); for(; b != e; ++b) { current_state = mon_automate.process(current_state, *b); } if(mon_automate.is_in_final_state(current_state)) std::cout << "La séquence: " << ma_sequence << "est valide." << std::endl

---

C'est bien entendu à adapter mais c'est pour que tu vois le concept.

"state" devrait être opaque à l'utilisateur et peut par exemple représenter plusieurs états si l'automate est non déterministe.

J'espère avoir pu aider, bonne chance pour la suite ;)

@Ekleog : j'avais déjà bien ce principe en tête, ce que j'imaginais ressemblais plus à ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

namespace truc { template<typename type, typename label> extern State<type,label>* currentState; }   //pendant ce temps là, dans une autre galaxie... //à l'utilisation using namespace truc; State<int, string>* currentState = null;   //bon ça doit surement vous défriser, mais je ne voyais rien de gênant à cela personnellement, après tout je ne suis qu'un débutant

---

@Trademark : oui désolé des fois je réfléchis pas trop :aie:

j'ai vu ta phrase "pense à ext..." vrrroooooom je te pondais une variable globale template non résolvable (apparemment) à la compilation et non conseillée de surcroît.

Je comprend mieux, mais maintenant je me pose une question que j'aurais du te poser plus tôt, pourquoi avoir cette donnée en membre de la classe Automate empêche de partager ce même automate entre plusieurs thread ? je veux dire, un premier thread lock la variable, s'en sert, la delock, ensuite l'autre peut en faire autant dès que c'est fini, s'il était en attente, et tout le monde est comptant, non ? sémaphore (ou ressource partagée) quoi... tu peux m'expliquer où est mon erreur ?

Edit : pour les automates non-deterministes, je compte l'interdire, soit par un algo de "determinisation", soit par un de détection d'automaton non deterministe et un message d'avertissement, ou je ne sais pas...

En faisant ça, tu déclares une unique variable currentState, qui a tous les types possibles. (enfin, state<int, int>, state<int, std::string>...)
Dès lors, comment le compilateur pourrait-il savoir quel est le réel type de la variable ?

Par ailleurs, j'ai oublié de mentionner un fait important : en général, on n'"externalise" pas les templates (je ne trouve pas de meilleur mot pour le dire).
C'est-à-dire que, pour faire simple (l'export existe bien, mais bon ...), les templates doivent être totalement disponibles au moment de leur utilisation, elles n'utilisent jamais un fichier cpp séparé - ce qui serait le cas avec extern mavar - tant qu'elles dépendent encore d'un paramètre template (il est possible de déplacer dans un .cpp une spécialisation state<int, int> ; mais pas une spécialisation partielle, par exemple).

J'espère que je suis compréhensible ...

Pour le multithread, le problème est que (avec le state inclus dans l'automate), celà signifierait que l'automate doit être verrouillé à *chaque* utilisation. Même si l'accès est en lecture seule. Parce qu'un programme qui accède à la fois en lecture et en écriture dans une variable contient une race condition, ce qui ferait tout planter.
Dans le cas du state stocké à part, il permet de ne verrouiller que les accès concurrents concernant le state, et non les accès concurrents (en lecture seule) concernant l'automate lui-même.

Par ailleurs, il y a un autre avantage à sortir l'état de l'automate : il est réutilisable en parallèle.
C'est-à-dire qu'on peut utiliser l'automate (une fois construit et avec les transitions bien définies) à partir de plusieurs threads, chaque thread ayant un état à lui ; et donc que l'automate peut être utilisé sur plusieurs états en même temps.

Ce peut être utile pour un programme de gestion de mots de passe, par exemple. Supposons que la validation du mot de passe se fasse par un automate. On veut pouvoir accepter des mots de passes de plusieurs sources : depuis un clavier et par ssh, par exemple.
Les mots de passe sont bien évidemment indépendants : si quelqu'un s'amuse à taper sur le clavier pendant qu'on s'identifie en ssh, on ne veut pas que le mot de passe soit considéré comme invalide !
Du coup, on utilise deux threads : un gérant le clavier, et un gérant la connexion ssh. Bien sûr, l'automate est créé avant la séparation des deux threads, à l'initialisation du programme.
Plutôt que de copier l'automate dans les deux threads, ce qui serait obligatoire si l'état était stocké dans l'automate, il est possible de conserver simplement les états dans les deux threads, sans influencer sur l'automate, et sans même avoir de perte de performance par l'utilisation d'un mutex, vu que l'automate est accédé en lecture seule.
En plus, tu y gagnes en performance ! Si l'automate est un peu gros (100.000.000 transitions et 10.000.000 d'états, chacun identifié par une string, par exemple, si on veut essayer de prendre une définition allégée de la langue française (exemple au hasard)), tu y gagnes énormément en temps de copie !

Bref, que du bénéfice à externaliser l'état de l'automate !

Citation:

---

Envoyé par Ekleog

En faisant ça, tu déclares une unique variable currentState, qui a tous les types possibles. (enfin, state<int, int>, state<int, std::string>...)
Dès lors, comment le compilateur pourrait-il savoir quel est le réel type de la variable ?

Par ailleurs, j'ai oublié de mentionner un fait important : en général, on n'"externalise" pas les templates (je ne trouve pas de meilleur mot pour le dire).
C'est-à-dire que, pour faire simple (l'export existe bien, mais bon ...), les templates doivent être totalement disponibles au moment de leur utilisation, elles n'utilisent jamais un fichier cpp séparé - ce qui serait le cas avec extern mavar - tant qu'elles dépendent encore d'un paramètre template (il est possible de déplacer dans un .cpp une spécialisation state<int, int> ; mais pas une spécialisation partielle, par exemple).

J'espère que je suis compréhensible ...

Pour le multithread, le problème est que (avec le state inclus dans l'automate), celà signifierait que l'automate doit être verrouillé à *chaque* utilisation. Même si l'accès est en lecture seule. Parce qu'un programme qui accède à la fois en lecture et en écriture dans une variable contient une race condition, ce qui ferait tout planter.
Dans le cas du state stocké à part, il permet de ne verrouiller que les accès concurrents concernant le state, et non les accès concurrents (en lecture seule) concernant l'automate lui-même.

Par ailleurs, il y a un autre avantage à sortir l'état de l'automate : il est réutilisable en parallèle.
C'est-à-dire qu'on peut utiliser l'automate (une fois construit et avec les transitions bien définies) à partir de plusieurs threads, chaque thread ayant un état à lui ; et donc que l'automate peut être utilisé sur plusieurs états en même temps.

Ce peut être utile pour un programme de gestion de mots de passe, par exemple. Supposons que la validation du mot de passe se fasse par un automate. On veut pouvoir accepter des mots de passes de plusieurs sources : depuis un clavier et par ssh, par exemple.
Les mots de passe sont bien évidemment indépendants : si quelqu'un s'amuse à taper sur le clavier pendant qu'on s'identifie en ssh, on ne veut pas que le mot de passe soit considéré comme invalide !
Du coup, on utilise deux threads : un gérant le clavier, et un gérant la connexion ssh. Bien sûr, l'automate est créé avant la séparation des deux threads, à l'initialisation du programme.
Plutôt que de copier l'automate dans les deux threads, ce qui serait obligatoire si l'état était stocké dans l'automate, il est possible de conserver simplement les états dans les deux threads, sans influencer sur l'automate, et sans même avoir de perte de performance par l'utilisation d'un mutex, vu que l'automate est accédé en lecture seule.
En plus, tu y gagnes en performance ! Si l'automate est un peu gros (100.000.000 transitions et 10.000.000 d'états, chacun identifié par une string, par exemple, si on veut essayer de prendre une définition allégée de la langue française (exemple au hasard)), tu y gagnes énormément en temps de copie !

Bref, que du bénéfice à externaliser l'état de l'automate !

---

Ok, je vois où est mon erreur, je pensais qu'il n'avaient besoin de le connaitre qu'à partir de la définition..
Pour le reste, tu as raison, et je vais partir dans ce sens. Merci de ton aide, et bonne chance pour la finale ;)


Edit : serait-il envisageable que les variables globales template puissent avoir un traitement différent des variables globales classiques (je comprend l'intérêt de pouvoir utiliser une var globale de type renseigné dès sa déclaration, mais je me dis que cela peut être différent pour les templates), du genre : résolution du type à la définition et on laisse passer à la déclaration, mais interdiction de s'en servir sans définition préalable...

Ce qui m'intéresse aussi, c'est de savoir : si je pouvais directement parler de ça avec le comité, quelle serait leur réponse (je me doute que non, mais je veux surtout connaitre la raison que j'ignore pour laquelle une telle chose n'est pas envisageable)

La réponse serait très probablement non (ils y auraient déjà pensé !).

Un exemple de code problématique dans le cas contraire :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

template <typename T> T var;   template <> int var; // Définition de int var (le template<> est placé pour faire comme si on faisait une spécialisation de template)   int foo() { return var; // var de type int }   template <> float var;   float foo() { return var; // Est-ce qu'on doit utiliser var de type int ou float ? (le C++ ne prend pas en compte le type de retour) }

---

Si on prend en considération le type de retour (ce qui serait déjà étonnant), on se retrouve avec ce problème :

Code:

---

1 2 3 4 5 6 7 8 9

template <typename T> T var;   template <> int var; template <> float var;   void foo() { auto v = var; // v est de type int ou float ? UneStructTemplate<decltype(var)> s(var); // s est de type UneStructTemplate<int> ou UneStructTemplate<float> ? }

---

Certes, c'est du c++11, mais le c++ old-gen a le même problème :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

template <typename T> T var;   template <> int var; template <> float var;   template <typename T> void foo(const T &) { std::cout << "foo(?)\n"; } template <> void foo(const int &) { std::cout << "foo(int)\n"; }   void bar() { foo(var); // Affichage de foo(?) ou foo(int) ? }

---

Si, enfin, on décide d'utiliser la variable comme var<int> pour la variable var de type int, on se heurte au problème suivant : les arguments templates n'étant pas des types (je ne connais pas le nom, désolé) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

template <int I> struct S { int val[I]; };   template <int I> S<I> var; // Définition autorisée pour une classe, alors pourquoi pas pour une variable ?   template <> S<42> var<42>; // Définition de var<42>.   void foo() { return var < 42 > ; // Ambiguïté : var <INFERIEUR> 42 <SUPERIEUR> ou var<42> ? }

---

Si on adopte le même système de résolution que celui qui a été choisi pour les fonctions templates dans le cas de paramètres templates, on se retrouve avec template var<I> à chaque utilisation.

Alors, y a-t-il vraiment un avantage par rapport à la variable coincée dans une struct ?

@Ekleog: Son idée n'est pas si stupide que ca. Dans le cadre des template, on pourrait très bien envisager de déclarer un identifiant sans type tant que celui-ci (le template) n'est pas instancié. C'est restrictif mais pas idiot.

D'autre part je me demande ce que la norme impose exactement au niveau de la vérification de la syntaxe dans un template. Tout les identifiants doivent-ils être déclaré ou peuvent-ils ne pas exister tant qu'ils existeront avant le POI. Et d'autre part ce que la norme impose sur ces POI.

Par exemple :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include<iostream>   template<class T> struct A {};   template<class T> void foo(const A<T>&) { std::cout << a; }   int a;   int main() { A<int> b; foo(b); }

---

Compile sous VC++. En effet il n'y a aucun problème, la syntaxe dans le template est bonne tant que l'identifiant a sera d'un type supportant la syntaxe std::cout << a; ce qui peut être vérifier au moment de l'instanciation. Dans ce code le POI peut être mis juste avant le main, ce qui donne après instanciation des templates :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include<iostream>   int a;   struct A<int> {};   void foo<int>(const A<int>&) { std::cout << a; }   int main() { A<int> b; foo<int>(b); }

---

(pseudo-syntaxe après génération des "instances template")

Il pourrait d'ailleur exister quelque chose similaire à typename/template (qui servent respectivement à dire que l'identifiant suivant est un type ou un template), pour indiquer que l'identifiant suivant est un objet :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include<iostream>   template<class T> struct A {};   template<class T> void foo(const A<T>&) { std::cout << object a; }   int a;   int main() { A<int> b; foo(b); }

---

Edit:
On peut d'ailleurs noter qu'une telle idée (dire "l'identifiant qui suit est un objet") existe déjà dans un cas particulier. Lorsque l'on écrit un classe template dérivant d'une autre classe template :

Code:

---

1 2 3

template<class T> struct A : B<T> {};

---

Pour utiliser les données membres de B<T>, on doit utiliser une syntaxe (this-> ou using) qui veut dire exatement ceci, ie "l'identifiant qui suit est un sous-objet membre de la classe mère". Pourquoi ne pas l'avoir fait pour d'autre identifiant d'objet (globale entre autre) ? Aucune idée, les besoins pratiques n'ont peut-être tout simplement jamais amené à se poser ce genre de question, ou la solution a peut-être été jugée trop restrictive (que ce soit à l'utilisation ou au niveau des possibilités d'implémentation pour les compilateur) pour être accepté. Je n'en sais rien.

Bon j'ai posé la question certes, mais je n'ai pas une connaissance aussi approfondie que vous, actuellement. Je vais donc essayer de ne pas dire trop de bêtises.


@ Ekleog : Pour répondre à ta dernière intervention, je vais réutiliser ta réponse précédente :

Citation:

---

Envoyé par Ekleog

En faisant ça, tu déclares une unique variable currentState, qui a tous les types possibles. (enfin, state<int, int>, state<int, std::string>...)
Dès lors, comment le compilateur pourrait-il savoir quel est le réel type de la variable ?

---

(Je précise que ce que je dis ne concerne que le cas précis d'une variable globale unique).

Justement, Il ne cherche pas à savoir quel est son type tant qu'elle n'est pas utilisée. Et il gueule si on cherche à l'utiliser sans définir son type. Et si on le définit deux fois il gueule quand il rencontre le deuxième type. C'est assez restrictif, mais cela permet de ne pas réécrire du code pour chaque type dans le cas d'utilisation d'une donnée manipulée indépendamment de son type et commune à tout un programme.

@Flob90 : C'est quoi les POI ? :)

POI = Point of Instanciation, c'est l'endroit où le template est instancié avec les paramètres template voulu.

Merci. J'ai cherché dans le draft mais je ne voyais pas de def.

Citation:

---

Envoyé par Kaamui

Bon j'ai posé la question certes, mais je n'ai pas une connaissance aussi approfondie que vous, actuellement. Je vais donc essayer de ne pas dire trop de bêtises.

---

C'est en disant des bêtises qu'on apprend !

Citation:

---

Envoyé par Kaamui

Justement, Il ne cherche pas à savoir quel est son type tant qu'elle n'est pas utilisée. Et il gueule si on cherche à l'utiliser sans définir son type. Et si on le définit deux fois il gueule quand il rencontre le deuxième type. C'est assez restrictif, mais cela permet de ne pas réécrire du code pour chaque type dans le cas d'utilisation d'une donnée manipulée indépendamment de son type et commune à tout un programme.

---

Le problème est qu'à ce moment, les templates ne servent plus à rien.
Puisque la variable est inutilisable tant qu'elle n'est pas définie, la première déclaration (la template) est celle qui est possible à retirer : elle ne sert strictement à rien.
Mais, lorsque tu définis le type de la variable, il n'y a plus d'aspect template. Ce que tu voudrais faire se fait donc déjà sans variables globales templates :

Code:

---

1 2 3 4 5 6 7 8 9 10

// Commentaire volontaire : // extern template<T> Struct<T> A; // Indique au lecteur (puisque le compilateur n'y verrait aucun avantage) que A existe   // [...]   Struct<int> A; // Définit le type de la variable pour le compilateur   // [...] (utilisation de A : OK)   Struct<float> B; // Là, le compilateur "gueule".

---

Le même comportement est déjà obtenu !

@Flob90: En fait, j'essaie simplement de comprendre les bénéfices que Kaamui souhaite en retirer, et la syntaxe qu'il voudrait. Tant que je n'aurai pas bien compris le problème, celui-ci sera dur à résoudre ! (En tout cas pour moi, mais je ne suis certainement pas le plus à même de répondre !)

Citation:

---

Envoyé par Ekleog

Le problème est qu'à ce moment, les templates ne servent plus à rien.
Puisque la variable est inutilisable tant qu'elle n'est pas définie, la première déclaration (la template) est celle qui est possible à retirer : elle ne sert strictement à rien.

---

Oui sauf que les template font que l'ordre d'utilisation n'est pas l'ordre après instanciation.

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

#include<iostream>   template<class T> struct A;   template<class T> struct B : A<T> { void foo() { std::cout << this->bar; } };   template<> struct A<int> { double bar; };   template<> struct A<double> { int bar; };   int main() { B<int> a; B<double> b; a.foo(); b.foo(); }

---

Dans l'ordre d'écriture on utilise bar avant de le définir et même de le déclarer. Cependant les POI font qu'au final rien n'est utilisé sans avoir été au moins déclaré.
(Après instanciation ca pourrait ressembler à ca :)

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

#include<iostream>   struct A<int> { double bar; };   struct A<double> { int bar; };   struct B<int> : A<int> { void foo() { std::cout << bar; } };   struct B<double> : A<double> { void foo() { std::cout << this->bar; } };   int main() { B<int> a; B<double> b; a.foo(); b.foo(); }

---

Le même raisonnement pourrait s'appliquer aux globales, le C++ ne propose pas de moyen de le faire. Ce que Kaamui avait écrit aurait pu être une syntaxe pour faire ca. De même que VC++ permet de faire ca sans aucune syntaxe : aussi bien pour une globale que pour un membre hérité (ce n'est pas du C++ valide) :
-> Pour un membre hérité

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

#include<iostream>   template<class T> struct A;   template<class T> struct B : A<T> { void foo() { std::cout << bar; } //Sans le this->, compile sous VC++ mais n'est pas standard };   template<> struct A<int> { double bar; };   template<> struct A<double> { int bar; };   int main() { B<int> a; B<double> b; a.foo(); b.foo(); }

---

-> Pour une globale

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include<iostream>   template<class T> struct A { void foo() { std::cout << a; } //Dans l'ordre d'écriture j'utilise a alors qu'il n'est ni déclaré ni définie //Grace aux templates bien entendu };   int a; //Tant que le POI se retrouve après ce point, il n'y a pas vraiment de problème int main() { A<int> b; b.foo(); }

---