Design pattern : Proxy

Le pattern Proxy ou Mandataire est aussi un pattern comportemental (on ne voit que ça on dirait des fois...). Son rôle est simple: déporter la référence sur un objet, un service ou un composant de façon a faciliter son utilisation. Il fournit ainsi une vue simplifier au client qui n'aura pas a manipuler directement l'objet.





















Ainsi le pattern Proxy va s'employer dans les cas ou il est nécessaire soit de simplifier la communication dans une architecture client/serveur(en fournissant localement au client un objet proxy qui sera l'interlocuteur d'un objet dans le serveur) ou lorsque l'on souhaitera mettre en cache des objets avec en façade des proxys découplant ainsi les mécanismes associés a la gestion du cache, des mécanismes associés à la manipulation des objets.

Enfin et c'est probablement l'utilisation la plus spécifique des proxy est sa possibilité de greffer en interne des objets cible des comportements (comme on voudrait le faire avec un décorateur mais celui ci s'attache surtout a de la structure plus que du comportement)

On aura alors comme exemple, les EJB qui sont gérer par des proxy et des invocationHandler, permettant de faire la glu entre l’implémentation du Bean faites par le développeur et toute la partie technique associé au conteneur d'application.

On aura également comme exemple les appels RMI qui utilise ce mécanisme également.

Il est fort a parié que vous en utilisé même sans le savoir.

SQL en Groovy

Petit article aujourd'hui pour compléter celui sur Groovy avec un petit exemple pour accéder a une base de données avec du SQL

 Pour cela il suffit d'utiliser la classe groovy.sql.Sql.

import groovy.sql.Sql

def sql = Sql.newInstance("jdbc:mysql://localhost:6666/mabd", "user", "pwd", "com.mysql.jdbc.Driver")

sql.execute("create table MATABLE (INDEX VARCHAR(3), INFOS VARCHAR(100))")
sql.execute("insert into MATABLE values ('001','Data1')")
sql.execute("insert into MATABLE values ('002','Data2')")

sql.eachRow("select * from MATABLE") {
    println "Mes données = ${it.INDEX}->${it.INFOS}"
}

Finite State Machine

Dans l'article sur les SED , nous avons vu que les langages offrent un cadre théorique éprouvé, pour la modélisation et la manipulation des systèmes à événements discrets. Cependant, l’utilisation et la manipulation directe des ensembles décrivant les langages n'est pas réaliste. Ainsi, il est nécessaire d’expliquer les notions liées aux automates à états, modèles des langages, qui sont plus concrets et plus faciles à manipuler.

Les automates à états sont, par définition, des outils mathématiques permettant la modélisation et la manipulation de langages décrivant le comportement des SED. Ils peuvent avoir une représentation graphique grâce aux diagrammes à états permettant une analyse visuelle. 

Un automate à état, est un n-uplet noté G=(X, S,  f,  x0, Xm) tel que :

·         X : Ensemble des états de l’automate.

·         S : Alphabet ou ensemble des événements réalisables par l’automate.

·         f : Relation de transition qui définit pour un état courant et un événement appartenant à l’alphabet un second état qui devient l’état courant.

·         x0 : l’état initial de l’automate

·         Xm : l’ensemble des états marqués de l’automate permettant la validation de séquence d’événements.

Exemple:Si G un automate tel que : 

     X = {0,1,2} 

     S = {a,b,c} 

     f = {(0,a)->1,(1,b)->0,(1,c)->1,(0,c)->2} 

     x0= 0 

     Xm= {1} 

Ce type d’automate est très général et peut avoir un nombre infini d’états empêchant une implémentation concrète. Dans cette étude on se limite aux automates à états finis qui se caractérisent par le fait que l'ensemble des états doit être fini. Les automates à états finis sont des implantations pour les langages dits réguliers

Langage des automates à états finis

Un automate à états finis décrit deux langages, comme illustré par la figure 8. Le premier langage est dit le langage généré par l’automate. Il correspond à toutes les possibilités de transitions offertes par la relation de transition. Le second langage est le langage marqué, il correspond à la réalisation de toutes les possibilités de transitions offertes par la relation de transition menant à un état final marqué. Le marquage est utile dans le cadre de la définition de comportements valides pour l’automate.



L’utilisation d'un automate à états finis permet de voir un SED dans sa globalité grâce au langage généré mais aussi de voir ce SED dans son comportement souhaité via le langage marqué. La différence entre ces deux langages permet de définir le langage bloquant de l’automate. En effet, le langage marqué est inclus ou égal au langage généré de l’automate. La caractérisation du langage bloquant d’un automate est alors mise en évidence par la différence des langages marqués et générés comme cela est illustré par la figure 9. Mathématiquement, pour un automate G, avec L(G) son langage généré et Lm(G) son langage marqué, l’automate est bloquant si  Lmpréf(G) inclu dans L(G). Il est non bloquant si Lmpréf(G)=L(G).

Exemple:Si G un automate, illustré en figurer 10, tel que: 

X  = {0,1,2} 

  = {a,b,c} 

f  = {(0,a)->1,(1,b)->1,(0,c)->2} 

x0 = 0 

Xm = {1} 

On a:

L(G) = {epsilon, c, ab*}
Lm(G) = {ab*}
Lmpréf(G) = {epsilon, ab*}Et Lmpréf(G) inclu dans L(G) donc G est bloquant (voir figure 10)

Opérations sur les automates à états finis

Les automates d’états finis étant les modèles des langages réguliers, toutes les opérations présentées sur les langages leur sont applicables. Certaines variations existent dans les termes utilisés pour les nommer. Il est donc nécessaire de les présenter dans le détail afin de clarifier la dénomination utilisée.

Calcul de la partie accessible : L'opération calculant la partie accessible d'un automate supprime les états dans l'automate à la suite d’une séquence d’évènements.
Calcul de la partie coaccessible : L'opération de permet de rendre non bloquant un automate bloquant en supprimant les états à partir desquels il n’existe pas de séquences d’évènements permettant d’atteindre un état marqué.

Opération Trim

L’opération Trim réalise successivement les opérations d'accessibilité et de coaccessibilité ou inversement. Cette opération est importante car elle permet de rendre le langage généré de l'automate égal à la fermeture préfixée du langage marqué. (L(G)=Lmpréf(G))

Exemple:
Dans l’automate G, illustrée par la figure 11, l'état 3 n'est pas accessible et l'état 2 ne permet pas d'accéder à un état marqué. Via l'opération Trim, ces états seront supprimés (figure 12)

Projection

La projection d'un automate est directement issue de la projection des langages puisqu'un automate est le modèle d'un langage. Même si le mécanisme reste le même au niveau langage, il est un peu plus complexe à mettre en œuvre au niveau d'un automate. Pour projeter un automate, il faut identifier les transitions à supprimer et ensuite raccorder les états afin de restaurer le langage projeté.

Exemple:
La projection, illustrée par les figures 13 et 14, de l’automate G de langage L(G)={bd,abc} sur l’alphabet ={b,d} renvoie un automate dont le langage est P(L,)={b,bd} conforme à la projection définie pour les langages.



Remarque:
Le résultat peut donner un automate à états finis non déterministe. En effet, sur la figure 14 de l’exemple, l’état 0 génère un événement b menant à l’état 2 et 4.
La projection peut rendre des états non atteignables.

Projection inverse

De la même façon que la projection inverse d'un langage, sur un automate cette opération va compléter chaque état avec les événements non présents dans l'alphabet de l'automate.

Exemple:
La projection inverse, illustrée par les figures 15 et 16, d’un automate G de langage L(G)={ab} définit sur l’alphabet ={a,c} renvoie un automate G’ de langage L(G')={c*ac*bc*}.



Il faut noter que l’évènement "a" faisant déjà partie de l'alphabet n'a pas fait l'objet de l'opération de projection inverse. En terme de SED et d'état, cela signifie que "a" est une action importante qui ne peut être ignorée, contrairement à l’événement "c" qui sera ignoré (en terme d’évolution de l’automate, pas en terme de langage) puisqu'il reste dans l'état courant.

Union

L’union fusionne les états initiaux des différents automates réalisant ainsi l'union des langages. Cette opération peut également amener à un automate non déterministe si les états initiaux génèrent des évènements identiques, comme illustré par les figures 17, 18 et 19.

Exemple:

Produit libre

Le produit libre entre automates permet la fusion de leur langage, cela signifie qu’il est toujours possible d’évoluer à chaque instant dans l’automate résultant de cette opération, de la même façon que les automates d’origines fonctionnant en parallèle. En terme de SED, cela correspond à la visualisation de deux systèmes fonctionnant en parallèle sans communication ni synchronisation. Le langage résultant de cette opération est donc bien plus important que leur simple somme qui correspondrait plutôt à l'union. Ainsi cette opération met en évidence que la modélisation des SED devient rapidement complexe dès que de nombreux systèmes mis en parallèles sont modélisés. Le produit libre est  illustré en figure 20 montrant toutes les combinaisons des deux automates, il est noté ||.




Exemple:
Cet exemple illustre plus concrètement le produit libre de deux automates, G1 (figure 21) et G2 (figure 22). La figure 23 illustre la complexité du résultat des deux automates (de l’ordre n*m, n étant le nombre d’états du premier automate et m celui du second).

Produit strict 

Le produit strict (ou produit cartésien dans la littérature [10], [1]) est une opération permettant de réaliser l'intersection des langages. Comme illustré par les figures 24, 25 et 26, cette opération réalise le produit cartésien des états et relie ces derniers sur les transitions communes aux différents automates.

En terme de SED, le produit strict représente la synchronisation totale des systèmes. Ils doivent réaliser les mêmes actions en même temps, si cela n'est pas possible alors aucune action n'est réalisée. Le produit strict est noté x.

Exemple:

Produit synchronisé

Le produit synchronisé est un produit permettant de modéliser le comportement de plusieurs SED mis en parallèle (comme pour le produit libre). Les automates dont certains événements de leur alphabet sont synchronisés transitent ensemble sur ces derniers, les autres évènements restant libres. Plusieurs cas sont à prendre en compte. Si les alphabets sont totalement disjoints, le produit synchronisé revient à la réalisation d'un produit libre. Si les alphabets sont égaux, le produit synchronisé revient à la réalisation d'un produit strict. Si les alphabets ont une intersection non vide alors la combinaison des deux opérations (libre et strict) est réalisée puisque le comportement commun est extrait sur les évènements communs, et les comportements libres des automates sont ajoutés pour les évènements non communs.

Le produit synchronisé a la particularité d’être réalisable à partir d’opérations déjà définies comme la projection inverse et le produit strict, comme illustré par les figures 27, 28 et 29. Si L1 et L2 sont deux langages alors L3=intersect(IP(L1,2),IP(L2,1)) est le produit synchronisé. Pour plus de souplesse, ce produit est noté      L3=L1 ||s L2. Il est nécessaire de préciser que la manipulation des alphabets permet de modifier la configuration du produit synchrone et donc son résultat, un événement défini dans l'alphabet ne se trouve pas forcement dans la relation de transition de l'automate, comme illustré par les figures 30, 31 et 32.

Exemple:
Si L1(G1)={(ab)*} et L2(G2)={(ac)*} avec 1={a,b} et 2={a,c} alors L(G1||sG2)=intersect(IP(L1,2),IP(L2,1))={(a(bc|cb))*}




Par contre, si 1={a,b,c} et 2={a,c,b} avec L1(G1)={(ab)*} et L2(G2)={(ac)*} alors L3=interssect(IP(L1,2),IP(L2,1))={a} c’est à dire le produit strict.

Remarque sur les automates d’états finis non déterministes

Le problème du déterminisme dans les automates à états apparaît dans de nombreuses opérations comme celle de projection ou d’union ou encore du produit libre. Le non-déterminisme d’un automate est caractérisé par une particularité dans la relation de transition. Cette particularité est que pour un état et un évènement donné, la relation de transition donne deux états possibles. Dans le cadre d’une implémentation et d‘une exécution, il est impossible de définir dans quel état se trouve l’automate.

En terme de langage, la notion de déterminisme n’existe pas [1] et [10], par contre la théorie des langages définis que s’il existe plusieurs automates modèles d’un même langage, ces derniers peuvent être déterministes ou non. Il existe une relation d’équivalence (en terme de langage) entre ces automates permettant de transformer un automate non déterministe en un automate déterministe tout en préservant le langage comme illustré par les figures 33 et 34. Il est nécessaire de noter qu’un automate possédant plusieurs états initiaux est considéré comme non déterministe car il est possible de construire un état initial  à partir duquel partiront des transitions epsilons allant vers chaque état initial de l’automate.

Exemple :

Conclusions

La théorie des langages et des automates à états offre un cadre idéal à la modélisation et à la manipulation des SED grâce aux diverses opérations comme le produit synchronisé ou celles issues de la théorie des ensembles comme l’union, le produit strict etc. De nombreuses particularités sont aussi à prendre en compte afin de rester dans un cadre d’implémentation réalisable comme les problèmes liés au non-déterminisme ou la nécessité d’utiliser les langages réguliers et les automates à états finis. Les éléments présenté dans ce chapitre sont les bases essentielles à l’étude de la théorie de la supervision définie par P.J.Ramadge et W.M.Wonham.

References

[1] Ramadge P.J., Wonham W.M. The control of discrete-event systems. IEEE Transactions on Automatic Control, 1989, Vol. 77, N° 1, p. 81-98.

[10] C. G. Cassandras, and S. Lafortune. Introduction to discrete event systems, Kluwer Academic Publishers, 1999, ISBN: 0-7923-8609-4

Design pattern : Patron de methode

Le pattern méthode template est un pattern d’écriture. Un pattern d’écriture est une façon d’écrire un ensemble de ligne de code afin de répondre a un problème. Je rappelle qu'un pattern de conception, est une façon d'organiser les classes/objets et composants afin de répondre la aussi a des problématique standard.

Ce pattern est très couramment employé car il permet de construire dans une classe abstraite une logique d’exécution non finalisé que devront définir les classes filles

public abstract class AbstractCommand {

    protected abstract void precond();
    protected abstract void execute();
    protected abstract void postcond();
   
    public final void operate()
    {
        this.precond();
        this.execute();
        this.postcond();
    }
   
}

Ainsi par exemple, dans le cas de cet exemple, toutes les commandes dérivant la classe abstraite devront se conformer a définir les trois méthode precond, execute et postcond, celle-ci étant orchestrées de façon standard pour toutes les commande par la méthode operate.

Cet exemple soufre évidement d'une trivialité sans nom, et ne retranscrit pas complétement l’intérêt de ce pattern très puissant mais l'on peut facilement imaginé que dans la classe abstraite certain comportement soit inconnu et que l'on préfère déléguer aux classes filles la responsabilité de remplir les trous.

A noter que pour contraindre l'utilisation de la méthode operate, on définira les 3 méthodes abstraites a protected et la méthode operate a final.

public class MaCommande extends AbstractCommand {

    @Override
    protected void precond() {
        System.out.println("precond");
    }

    @Override
    protected void execute() {
        System.out.println("execute");
    }

    @Override
    protected void postcond() {
        System.out.println("postcond");
    }

}

Systèmes à événements discrets

Les systèmes à événements discrets (SED) sont des systèmes caractérisés par une structure à états et à transitions étiquetées par des événements. L’exécution d’un SED se déroule par la génération d’un événement lors du passage d’un état à un autre via une transition donnée. L’ensemble des événements réalisables par le SED est appelé alphabet et la génération successive de plusieurs événements de cet alphabet défini un mot ou une chaîne d’actions. Un SED peut être modélisé par un langage ou par un automate à états. Un automate est également le modèle d'un langage.

Le langage

Pour comprendre les notions liées à la théorie de la supervision, il est nécessaire de présenter celles liées à la théorie des langages. La théorie des langages est fondée sur la théorie des ensembles. Il s’agit donc d’une théorie éprouvée pour la modélisation et la manipulation des SED. Un langage est composé de deux ensembles, un alphabet noté S et un ensemble de mots noté L. L’alphabet est constitué de l'ensemble des événements ou des actions réalisables par le SED. La concaténation des éléments de l’alphabet forme des mots ou traces qui sont des modèles de séquences d’événements ou séquences d’actions. La théorie des langages définit e qui représente à la fois la chaîne vide et l’événement vide.

Exemple:

Soit S={a,b,c,d} et L={ab,bc}, le langage de L définit sur S compte les 2 mots ab et bc.

Opérations sur les langages

La théorie des langages étant fondée sur la théorie des ensembles, elle bénéficie des opérations telles que l’union, l’intersection, la différence etc. De façon à rester cohérent avec la théorie de la supervision, seules les opérations fondamentales sont présentées.

Fermeture de kleene

La fermeture de Kleene d'un langage consiste en la réalisation d'un langage noté S* modélisant toutes les combinaisons d'événements possibles à partir de S incluant la chaîne vide e.

Exemple:

Si S={a,b}; L={ab,bc} alors S*=(a|b)* (le symbole * sur un événement signifie que ce dernier peut apparaître de 0 à n fois. Le langage constitué de L'=a* équivaut à L'={e,a,aa,aaa,aaaa,aaaaaa,…})

 Fermeture préfixée

La fermeture préfixée est l'augmentation du langage à l'aide de tous les préfixes des mots contenus dans le langage incluant e. Le préfixe d’un mot est une partie antécédente du mot qui n’est pas e.

Exemple:

Si S={a,b,c}; L={ab,bc}  alors Lpréf={e,a,b,ab,bc}

Union

L'union est l’opération permettant de mettre dans un seul langage l’ensemble des mots des différents langages.

Exemple:

Si S1={a,b,c}; L1={ab,bc} et S2={a,b,y,z}; L2={ab,yz} alors, L1 U L2 = L3 tel que : S3={a,b,c,d,y,z}; L3={ab,bc,yz}

L'intersection

L'intersection est une opération permettant de créer un langage à partir des mots se trouvant dans les deux langages.

Exemple:

Si S1={a,b,c}; L1={ab,bc} et S2={a,b,c,d}; L2={ab,bbd,dc} alors, INTER(L1,L2) =L3 tel que : S3={a,b}; L3={ab,b}

Le complement

Le complément d'un langage L1 correspond au langage L2 = L1comp contenant tous les mots réalisables avec l'alphabet de L1 moins les traces de L1. Mathématiquement, cela correspond à réaliser L2=S1*-L1.

Exemple:

Si S1={a}; L1={aa} alors L1comp=L2={a|aaa(a)* }

 La projection

L'opération de projection d'un langage s'effectue par rapport à un alphabet de projection, ce dernier étant inclus ou égal à l’alphabet du langage. Cette opération est assimilable à un filtrage sur les événements contenus dans les mots du langage. Les événements restant dans les mots étant les événements présents dans l’alphabet de projection.

Exemple:

Si S1={a,b,c}; L1={ab,bc} et Sp={b,c} l'alphabet sur lequel L1 est projeté alors P(L1,Sp)={b,bc}.

La projection inverse

L'opération de projection inverse permet de compléter un langage avec des événements non contenus dans son alphabet. Ces événements vont être insérés entre chaque événement de chaque mot du langage de façon à construire un langage de taille maximale. La projection inverse permet pour le langage de considérer les nouveaux événements ajoutés comme étant possibles à chaque instant. La projection inverse sera notée IP tels que si A est la projection inverse de B suivant un alphabet S alors A=IP(B,S). Il est nécessaire de préciser que les opérations de projection et de projection inverse ne sont pas des réciproques.

Exemple:

Si S1={a,b,c}; L1={ab,bc} et Sp={b,d} l'alphabet sur lequel la projection inverse est réalisée alors IP(L1,Sp)={d*ad*bd*,d*bd*cd*}

References:

Ramadge P.J., Wonham W.M. The control of discrete-event systems. IEEE Transactions on Automatic Control, 1989, Vol. 77, N° 1, p. 81-98
C. G. Cassandras, and S. Lafortune. Introduction to discrete event systems, Kluwer Academic Publishers, 1999, ISBN: 0-7923-8609-4.