Un automate est-il un événement?

1. Introduction

Ayant entendu de lèvres autoritaires que «les automates sont une chose événementielle» [3], je me suis rendu compte que les automates finis sont entièrement marqués. Jugez par vous-même: dans la bibliothèque Qt, un modèle d'événement des automates [1] est implémenté, en UML ils sont aussi [2], nous regardons les automates du package d'extension Simulink-Stateflow du système MATLAB [4] (ci-après simplement Stateflow) et là-bas sur les événements, etc. etc. Dans ce contexte, la déclaration de Ph.D. A.A. C'est méchant d'interpréter d'une manière différente, car rien d'autre ne peut être, parce qu'il ne peut pas l'être.

Mais, si vous vous souvenez de la théorie des automates finis (TCA), alors il n'y a pas un mot sur les automates d'événements en elle! Mais pour contredire la théorie, des arguments de poids sont nécessaires. Y a-t-il une raison de douter du professionnalisme de D.Harell, en tant que créateur de la notation sur laquelle le langage UML, le package Stateflow, fonde ses idées, qui, à son tour, ne sont pas inconnues de A.A. Vilain? En effet, UML, Stateflow, la programmation SWITCH et d'autres options de programmation automatique existent et, à un degré ou à un autre, fonctionnent avec succès.

Est-il donc possible de supprimer la «stigmatisation des événements» du modèle de machine à états finis en séparant les «côtelettes des mouches»? C'est-à-dire séparer la théorie des automates et des modèles de calcul similaires aux modèles de D. Harel. Et de considérer que ces derniers, bien qu'utilisant la terminologie de la théorie des automates, représentent, à en juger par leur mise en œuvre, le développement d'un modèle de schémas fonctionnels de programmes.

Remarque 1. Dans ce cas, nous parlons du modèle de gestion de programme, et non du modèle de programme lui-même (pour plus de détails sur les modèles, voir [5]).

Donc, rappelez-vous, la bibliothèque Qt implémente un modèle d'événement d'une machine à états finis, qui a été emprunté à UML. Le même modèle est implémenté par Stateflow. C'est-à-dire la source des événements est UML, où les automates sont basés sur la notation proposée par D. Harel. Mais blâmer ce dernier pour la création d'une telle programmation automatique ne serait pas non plus vrai, car L '«événementiel» est une tendance des approches modernes à la mise en œuvre de modèles logiciels. Il est basé sur des opinions faisant autorité telles que les «machines sont un événement» et la grande popularité des langages et technologies tels que UML. C'est sans aucun doute le résultat du mimétisme des machines selon les principes de fonctionnement des systèmes d'exploitation existants.

Mais, répétons-le, car cela ne semble pas étrange, mais pour certains cela peut même devenir une nouveauté, dans la théorie des automates, il n'y a pas de modèle d'événement d'un automate fini. Au moins dans cette partie qui est considérée comme classique (voir pour plus de détails, par exemple, [6] ou [7]). Il existe une nette contradiction entre la théorie et la pratique. Dans une telle situation, vous devez faire quelque chose avec la théorie ou influencer d'une manière ou d'une autre la pratique. Mais, peut-être, les programmeurs ont-ils raison de vouloir finaliser le modèle d'une machine à états finis en y incluant le concept d '«événement» [8, 9]?

Mais comment relier les désirs des programmeurs au fait que «les plus grandes difficultés à utiliser l'approche des automates sont liées à la compréhension des caractéristiques du fonctionnement des automates dans les systèmes événementiels» (voir [8]). Je voudrais comprendre les causes de ces problèmes et, dans ce contexte, implémenter des machines événementielles et / ou leurs analogues. Pour cela, pour des spécificités, nous prenons l'implémentation d'automates dans Qt et les répétons en utilisant le modèle d'un automate fini classique.

Une telle implémentation d'automates événementiels est nécessaire pour évaluer et / ou surmonter les «fonctionnalités» mentionnées. L'utilisation du modèle classique étendra également la théorie des automates à la «programmation d'événements». Et, au final, un analogue basé sur un autre modèle ne fera qu'élargir le domaine d'application des modèles de machines à états finis.

2. Événements, signaux et identité de genre des automates

En UML, un événement est «un phénomène significatif qui a une certaine position dans le temps et l'espace ... et entraîne certaines conséquences» [10]. Un événement dans la théorie des automates est un sous-ensemble des caractères d'entrée représentés par les caractères de l'alphabet de sortie (il y a même le concept de l'algèbre des événements dans le TCA) [6]. La même chose qui provoque la transition d'un automate est appelée signaux d'entrée dans la théorie des automates. Ce sont les conséquences et «la raison, la transition de l'automate d'un état à l'autre. Dans ce cas, les signaux de sortie sont la «réponse de l'automate aux signaux d'entrée». Ces deux «se réfèrent à des instants temporels déterminés par les transitions correspondantes de l'automate» [6]. En UML, le signal (signal) est «une entité nommée qui sert de moyen de communication entre les objets »[10].

Ainsi, les noms des termes sont les mêmes, mais le sens qui y est investi est différent. Bien que, si vous les réorganisez, vous pouvez trouver une similitude: il devient clair que les événements dans UML correspondent aux signaux des machines à états finis dans le TCA. Mais, peut-être, différentes entités sont également cachées sous le terme de «machine à états finis»? Essayons de le comprendre, en commençant par les événements ...

L'automate d'événement est un automate passif, car ne fonctionne qu'au moment de l'arrivée des événements. En revanche, l'automate classique représente le modèle actif. Il fonctionne sans référence à quoi que ce soit (pour plus de détails sur les automates passifs et actifs, voir [9]). Ici, l'association avec deux coureurs commence, où le premier est entraîné par des coups de pied (événements), et le second court par lui-même.

Contrairement à [8], nous n'associerons pas dans un premier temps les moments d'occurrence des événements au démarrage de l'automate. Nous resterons donc dans le cadre de la théorie des automates, qui détermine la nature asynchrone du fonctionnement des automates par rapport à l'environnement extérieur. Il ne parle que de temps discret, dans lequel le changement d'états est effectué pour une période en temps réel arbitrairement petite, mais non égale à zéro. Et la raison des transitions est l'état actuel et les signaux d'entrée de la machine, où les conséquences sont l'installation d'un nouvel état et les valeurs des signaux de sortie de la machine (pour plus de détails sur la définition des machines, voir [6]).

La théorie des automates est flexible pour déterminer le temps discret, qui est un modèle en temps réel. Ainsi, un cycle temporel discret peut avoir une valeur fixe ou flottante d'un intervalle en temps réel, et conformément à cela, les machines sont appelées synchrones ou asynchrones. Dans le même temps, l'intervalle de temps associé à l'horloge peut avoir n'importe quelle valeur, y compris une valeur infiniment petite, mais non égale à zéro.

Remarque 2. Un modèle de machine à états finis est l'un des rares modèles formels qui inclut dans sa définition un modèle en temps réel sous une forme explicite.

Par conséquent, la vitesse formellement «infinie» de l'automate actif permet de traiter tout événement comme un signal d'entrée potentiel (en termes d'UML, la condition [11] lui correspond). La machine n'aura besoin que de «capturer» de tels événements / signaux et des pauses entre eux. Tout cela définit en fait le protocole du travail conjoint du médium et de l'automate. Le protocole devrait également résoudre le problème de la reconnaissance d'événements identiques reçus successivement. Sans cela, par exemple, deux symboles identiques, reçus l'un après l'autre, peuvent être perçus comme un seul.

Formellement, les nuances du traitement des événements ne sont pas significatives (voir les mêmes automates abstraits), mais dans la mise en œuvre pratique d'algorithmes construits par le type de modèle d'événement, elles doivent être prises en compte. Dans le cas de la bibliothèque Qt, leur comptabilité est cachée dans les classes d'implémentation de l'automate. De plus, nous prendrons en compte les différences entre les automates événementiels et classiques en utilisant l'exemple de l'implémentation du calculateur le plus simple de [1], où son «implémentation événementielle» est donnée. Contrairement à cette solution, des modèles équivalents seront créés sur la base de la machine à états finis classique.

3. Modèles de calculatrice

Alors, commençons ... Nous appelons des signaux d'événements, des événements d'automates ordinaires ... ou dans l'ordre inverse et / ou vice versa? Ugh! Confus. En bref, la «budlanula glocky cuzdra shteko» complète et quelque chose de «boucles». Pour savoir qui est qui, quoi et quoi appeler, le plus sûr est de choisir un «bokra» spécifique et de le «bump» ... Le programme «calculatrice automatique» continuera à être un tel «côté».

3.1. Modèle de calculateur actif

Dans la fig. 1 montre le modèle original de la classe Calculatrice de [1]. En apparence, il ressemble à une machine abstraite classique sans issue. La différence est que Qt connecte des actions lorsqu'il entre et sort d'un état. En sortie, ils sont déclenchés par le signal sorti (), et à l'entrée dans l'état, par le signal entré (). Mais, notons-le, ces actions ne sont en aucun cas représentées dans le graphique.

Si nous comparons le modèle de la Fig. 1 avec un automate à état abstrait (ses autres noms sont automate structurel et logique), on peut facilement voir que les actions à la sortie de l'état correspondent aux signaux de l'automate Mealy, et les actions à l'entrée correspondent aux signaux de l'automate Moore.
Remarque 3. De plus, compte tenu de l'implémentation logicielle du modèle, nous ne parlerons pas de signaux, d'événements, de conditions, etc., mais des actions des automates, en supposant qu'au niveau du programme, ils sont associés à certaines actions du programme, ce qui dans le cas général représentés par des fonctions logicielles.

L'automate Mili-Moore dit combiné (ou un automate différemment mélangé [12]), équivalent à l'automate de la Fig. 1, est représentée sur la Fig. 2, où les fonctions correspondant aux signaux d'entrée et de sortie de l'automate sont également représentées à droite du graphique.


Fig.1. Diagramme de machine d'événement de calculatrice


Fig.2. Calculatrice de classe d'automates Count Miley-Moore

Pour un modèle similaire à un automate dans la Fig. 2, par actions d'entrée / sortie, nous entendons des prédicats et des actions, qui sont des fonctions de programme-méthodes des classes [automate]. Les prédicats n'analysent en aucun cas l'état actuel des éléments de la mémoire (variables, propriétés de classe) (c'est important!) Sans les affecter, mais en fonction de leur valeur, renvoyer une valeur booléenne. Les actions d'une valeur ne retournent pas, mais modifient les éléments de mémoire.
De la fig. 2, il s'ensuit que le modèle de calculatrice, comme la «boîte noire», a quatre canaux d'entrée et sept canaux de sortie en termes de nombre de prédicats et d'actions. Il est facile de voir qu'en comparaison avec un automate abstrait, qui par définition n'a pas plus d'un canal d'entrée et un canal de sortie, un automate structurel à plusieurs canaux est plus universel, flexible et pratique.

Le modèle de la fig. 2 peut être simplifié en «collant» les états 1 et 2. Pour ce faire, vous devez d'abord transformer l'automate d'origine en automate Mealy. On l'obtient en chargeant les arcs entrant dans l'état des signaux avec les signaux représentés par les signaux des sommets de l'automate Moore. Après cela, l'opération de collage devient apparente. Le résultat du collage des états à l'état 2, qui devient maintenant initial, est illustré à la Fig. 3.


Fig.3. Le résultat de la transformation et du collage des états de l'automate sur la figure 2

Expliquez l'action y1 et la variable nTypeButtons. Au total, ils implémentent un protocole qui simule des événements. La variable nTypeButtons détermine le type de symboles d'entrée de l'automate en les divisant en symboles numériques, symboles de fonctionnement, symbole "reset" et symbole "égal". Sa valeur égale à zéro signifie l'absence de caractères saisis (aucune touche de la calculatrice n'est enfoncée). Après traitement du symbole, cela signifie également que le symbole d'entrée est perçu automatiquement. Cela bloque la réponse au caractère saisi.

Le code de la classe de la calculatrice créée dans le cadre de l'environnement de programmation automatique de composants visuels (VKPa) [5] est indiqué dans les listes 1, 2.


Expliquons. Dans VKPa, toute classe d'automate hérite des propriétés de la classe d'automate de base LFsaAppl. La méthode Create () crée des copies des classes incluses dans les bibliothèques dynamiques des processus automatiques. La méthode virtuelle MooreAction () se chevauche lorsqu'un modèle d'automate Moore est sélectionné, définissant les actions associées aux états de l'automate. Les méthodes x [n] et y [n] sont les prédicats et actions associés aux canaux d'entrée / sortie de l'automate. L'algorithme de comportement de la classe [automate] est représenté par la table de transition (voir Listing 2), qui consiste en un tableau de chaînes de type LArc. Le reste du code répète le code de la calculatrice de la classe source.


L'avis 2 contient trois tables de saut (deux sont commentées). C’est ainsi que les capacités de contrôle dédié sont réalisées lorsque, après avoir supprimé le commentaire, le comportement de la classe peut être modifié «par clic» sans affecter ses méthodes et ses propriétés. La méthode y10 et la ligne correspondante dans le tableau de transition (voir la ligne marquée avec le commentaire SWICH) ont été introduites pour simuler la technologie SWITCH (pour plus de détails voir [9]) dans le cadre de la technologie VKPA. Dans ce cas, le comportement de tout automate est modélisé par un appel cyclique à l'opérateur SWITCH, qui imite le comportement de l'automate (ici l'automate VKPa agit comme un environnement externe).

3.2. Modèle de calculateur passif

Le modèle de calculateur actif balaye constamment les canaux d'entrée. Dès que la valeur de la variable nTypeButtons devient non nulle, cela sert de signe de l'arrivée du prochain symbole à l'entrée de l'automate. Par conséquent, la transition et l'action y1 sont déclenchées, réinitialisant la variable nTypeButtons, bloquant le redémarrage automatique de la machine par le même caractère.
Contrairement au modèle «calculatrice active», un automate d'événements ne peut pas, par définition, retraiter un symbole d'entrée. Il est maintenant clair que "les plus grandes difficultés à utiliser l'approche des automates ... dans les systèmes d'événements" semblent se résumer à supprimer l'activité d'un automate actif et à lier son fonctionnement aux événements. Nous montrons la procédure pour passer à un automate passif en utilisant l'exemple de la «calculatrice active» qui vient d'être créée.
L'environnement VKPa contient un mode de fonctionnement pas à pas introduit pour le débogage des processus automatiques. Mais il peut être utilisé pour simuler des machines d'événements. Pour ce faire, 1) définissez l'espace de l'automate dans lequel l'automate est placé un mode de fonctionnement pas à pas (notez, pas un automate séparé, mais tout l'espace de l'automate contenant des automates), et 2) reliez les moments d'occurrence des événements avec l'exécution d'une étape discrète du fonctionnement de l'espace. Le listing 3 montre comment procéder, reflétant uniquement les modifications apportées au modèle (l'en-tête de classe reste inchangé).


Ici, tout d'abord, un état [initial] supplémentaire est introduit, dans lequel la référence à l'espace où se trouve la machine et le lien vers l'objet qui détermine les propriétés de l'espace (y compris son mode de fonctionnement) sont vérifiés. Eh forme l'action de y12. Lorsque les liaisons sont établies, il y a une transition vers [l'ancien] état initial du modèle de calculatrice avec l'installation d'un mode de fonctionnement pas à pas de l'espace automate.

De plus, le modèle fonctionne dans un mode pas à pas de fonctionnement spatial. Le lancement d'une étape implémente le code inséré dans les gestionnaires d'événements associés à l'entrée du caractère suivant (voir le listing 3 pour les modifications apportées aux méthodes digitButtonPressed et operationButtonPressed).

4. Pourquoi?

Pourquoi inventer quelque chose, s'il existe, comme on peut le supposer, un modèle d'événement plus avancé de D. Harel. Et comment penser différemment s'il était exécuté en UML, Stateflow, dans la bibliothèque Qt, etc. etc. et il n'y a pas beaucoup de panique à propos de ses défauts. Eh bien, ils ont appelé les événements de signaux, et ont transformé la machine active en une machine passive ... Et si le modèle, comme on dit, est aussi formellement équivalent aux machines Mili / Moore classiques, alors comment ne pas y croire? Et il en est ainsi, si toutes ces déclarations ne sont prises que sur la foi ...

Prenez pour le début de l'événement (c'est exactement ce que nous avons fait ci-dessus). Un automate structurel classique possède, par exemple, de nombreux canaux d'entrée, chacun étant associé à un signal, et ils peuvent être traités simultanément / en parallèle. Mais UML dit que «chaque objet ne peut traiter qu'un seul événement à la fois» et même «si deux événements se produisent simultanément, l'objet les traitera toujours un à la fois» [10]. Ainsi, au niveau de la définition, les signaux et les événements sont équivalents, mais l'idylle s'effondre dans le processus de mise en œuvre des transitions du modèle.

Prenons l'exemple avec lequel je commence à tester / apprendre n'importe quelle langue ou technologie. Il s'agit de l'implémentation logicielle du modèle d'élément ET-NON. Au niveau structurel, il correspond à la «boîte noire», qui a deux canaux d'entrée et une sortie, et sur l'algorithmique, l'automate représenté sur la Fig. 4.


Fig. 4. Le modèle automate de l'élément ET NON

Comment créer un modèle procédural régulier (voir Listing 4) ou comment implémenter un automate en VKPa (voir Listing 5) est compréhensible, mais comment répéter cela sur la base de l'automate d'événement de la bibliothèque Qt n'est pas très clair en raison du problème de mise en œuvre de la transition de l'état "1" indiquer "0", ce qui nécessite l'analyse simultanée de plusieurs événements.

Listing 4. Implémentation d'objet du modèle procédural AND-NOT



Ainsi, que l'implémentation du modèle d'événement de l'élément NAND dans le cadre des classes d'automates Qt soit un «devoir» pour les Habrovans. Je ne peux que citer sa décision dans Stateflow comme une «cerise sur le gâteau». Il est illustré sur la fig. 5. Le relief Stateflow est utilisé ici, ce qui permet de ne pas marquer la transition avec un événement: si le nom de l'événement n'est pas spécifié, alors la transition se produira lorsqu'un événement se produit (voir l'étiquette de transition dans [13] pour un exemple).


Fig. 5. Un modèle d'automate d'un élément AND-NOT dans Stateflow

Ainsi, les machines à états sont un modèle hybride (actif-passif) d'une machine. Certes, il n'est pas clair comment la machine se comportera en l'absence de tout événement. On peut supposer qu'il «gèlera» en prévision des événements. Et s'ils ne le seront pas? C'est-à-dire en fin de compte, il s'agit toujours plus d'un modèle passif que d'un modèle de machine active. Bien que seulement en apparence, il est difficile de les distinguer de ces derniers.

5. Conclusion

En ce qui concerne les événements, on peut dire qu'en raison de l'activité, la mise en œuvre du modèle classique des automates semble préférable au modèle des automates synchrones. Si nous parlons de la programmation automatique en général, le package d'extension Stateflow montre ce qu'un type de programmation complètement différent peut être. Mais, malheureusement, jusqu'à présent seulement en perspective, car des problèmes subsistent en raison du modèle de calcul Stateflow, qui reste essentiellement un schéma fonctionnel. Il semble que précisément pour ces raisons, avec les automates, la programmation visuelle dans Statefow est représentée par la notation des organigrammes.

Découvrir où se trouve la véritable programmation automatique et où se trouve son imitation est l'un de nos principaux objectifs. Dans l'article précédent [5], nous avons résolu l'une des tâches de base posées - nous avons formulé le concept de programmes d'automates. Ensuite, vous devez traiter de la définition d'un modèle de gestion de programme, qui devrait être un automate fini et être efficace et pratique pour les programmeurs.

Après avoir traité des événements, nous avons jeté les bases d'un tel travail. Dans d'autres articles, nous comprendrons déjà les détails du modèle proposé par D. Harel. En courant un peu plus loin, nous disons que, pour le dire franchement, elle a déformé la compréhension des automates. Mais, d'un autre côté, ici nous devons lui rendre son dû, elle a révélé des problèmes qui ne permettraient pas, sans elle, de former une programmation automatique efficace dans le cadre du modèle classique qui attirerait les programmeurs.

Nous avons découvert ci-dessus qu'au moins au niveau de l'événement, les automates classiques n'ont aucun problème. Nous comprendrons plus loin ... En attendant, ce n'est que le début. Nous attendons beaucoup de choses intéressantes et, notons, n'allons pas au-delà de la théorie classique des automates. Ceci est crucial si nous voulons une programmation vraiment automatisée. Nous vous souhaitons beaucoup de succès! :)

Les références

1. Borovsky A.N. Qt4.7. Programmation C ++ pratique. - SPb.: BHV-Petersburg, 2012 .-- 496 p.
2. BUCH G., RAMBO J., JACOBSON I. UML. Manuel d'utilisation. Deuxième édition. Akademiya IT: Moscou, 2007 .-- 493 p.
3. Shalyto A. A. Une nouvelle conférence sur la programmation automatique. 2019, [Ressource électronique], Mode d' accès: www.youtube.com/watch?v=PPWTxceMutk&feature=youtu.be , gratuit. Yaz. Russe (date du traitement 5 décembre 2019).
4. Stateflow. www.mathworks.com/products/stateflow.html , gratuit. Yaz. Anglais (date de diffusion 7.01.2020).
5. Machine de Turing, comme modèle de programmes d'automates. habr.com/en/post/481998 , gratuit. Yaz. Russe (date de diffusion 7.01.2020).
6. Melikhov A.N. Graphes orientés et machines à états finis. - M.: Nauka, 1971. - 416 p.
7. KUDRYAVTSEV VB, Aleshin S.V., PODKOLZIN A.S. Introduction à la théorie des automates - M.: Science. Ch. éd. Phys.-Math. lit., 1985 .-- 320 p.
8. Tukkel N.I., Shalyto A.A. Implémentation d'automates lors de la programmation de systèmes d'événements. "Programmer", 2002. No. 4. C.74-80.
9. Polikarpova N., A. Shalyto A. Programmation des automates. 2e éd., Saint-Pétersbourg.: Peter, 2011 .-- 176 p.
10. Rambo J., Jacobson A., Butch G. UML: référence spéciale. - Saint-Pétersbourg: Peter, 2002 .-- 656 p.
11. Goma H. ​​UML. Conception de systèmes temps réel, d'applications parallèles et distribuées: Per. de l'anglais - M.: DMK Press, 2002. - 2002. - 704 p.
12. SHALYTO A.A. Technologie SWITCH. Algorithmisation et programmation des tâches de contrôle logique. Saint-Pétersbourg: Nauka, 1998.628 s.
13. Rogachev G.N. Notations Stateflow. bourabai.kz/cm/stateflow13.htm , gratuit. Yaz. Russe (date de l'appel 01.10.2020).