UTILISATION DES AUTOMATES A PILE POUR LA SPECIFICATION DE DIALOGUES ET LA GESTION DE L’HISTORIQUE

Efrem Mbaki Luzayisu
FUNDP-Institut d'Informatique
21, rue grandgagnage B-5000 Namur Belgique
Tel +32-(0)81-72 52 59 Fax +32-(0)81-72 49 67
emb@info.fundp.ac.be 
Résumé — Si les machines à états conviennent bien pour spécifier les dialogues séquentiels ou mono-fils, elles sont non appropriées pour la description de dialogues multi-fils et hypermédia où, un support abstrait de gestion de l'historique des échanges inter tâches et  homme-machine  et un contrôleur abstrait de la concurrence inter tâches s'avèrent indispensables.  Ce papier présente une sémantique  de concepts d'automates à pile et montre comment ces derniers peuvent servir pour spécifier les trois types de dialogues susmentionnés tout en gérant l’historique des échanges.                                                                                                                                                                                   Mots clé : dialogue, mono-fil, multi-fil, hypermédia, automate, pile, état, transition, action, condition, objet du dialogue. 

1. Introduction
TRIDENT (Tools foR an Interactive Development Environment) est une méthodologie de conception assistée de la présentation d’une interface Homme-Machine ergonomique pour une application de gestion hautement interactive en intégrant partiellement, mais explicitement, l’Ergonomie Logicielle à la méthodologie d’application IDA [3 dans13].

Actuellement, TRIDENT supporte les dialogues mono-fils et, utilise les Machines à Etats (ME) plus un langage de règles pour leur spécification [7]. Mais, le fait que les ME soient sans mémoire, que seul le présent décide de l’avenir, pose un sérieux problème pour la spécification de dialogues multi-fils et hypermédia qui, nécessitent non seulement un outil abstrait pour gérer l’historique des échanges inter tâches et Homme-Machine  mais aussi, un mécanisme de contrôle de la concurrence inter tâches. Ces deux aspects ont déjà  fait l’objet de plusieurs investigations. Dans l’ensemble : 
•	les Réseaux de Pétri [9,12] ;
•	des extensions des ME[6,4] ; 
•	des valeurs,  objets et ensembles [5] ;
•	des grammaires, règles et contraintes [1, 2, 12] et ,
•	des notations spéciales [10]
ont été envisagés comme outils abstraits de modélisation.

En ce qui nous concerne, nous nous intéressons plus au premier aspect, l’historique des échanges et, optons pour les Automates à Pile (AP) comme outils de modélisation. Notons qu'intuitivement un  AP est formé de:
1.	un ruban d'entrée et une tête de lecture;
2.	un ensemble d'états parmi lesquels on distingue un état initial et des états accepteurs;
3.	une relation de transition et,
4.	une pile de capacité infinie.

Nous pouvons bien étendre le formalisme ensembliste présenté dans [5] de manière à supporter simultanément les trois types de dialogues précités. 

Mais, la palette des propriétés d'optimisation et de vérification offerte par les ensembles nous paraît moins riche que celle offerte par les formalismes orientés états (ME et Réseaux de Petri (RdP)). De ces deux dernières notations, par rapport à notre préoccupation de gérer l'historique, nous optons pour les ME à pile. Ce choix s’explique par la lourdeur que présente les RdP quant à la traçabilité des échanges. Comme nous le verrons plus loin, les états d'un automate des dialogues modélisent les différents contextes des dialogues tandis que sa pile contient les traces d'actions de l'utilisateur ainsi que les primitives et les événements des objets d'interfaces. Dans ces conditions, Le designer peut recourir aux fonctionnalités de la pile pour enrichir les coûts de transition entre différents états. 

La suite de ce papier est structurée en trois sections dont la première donne une sémantique de chaque concept relatif aux AP dans le contexte de spécification 
de dialogues. La deuxième traite de la construction des automates de dialogues à partir de l'arborescence de la décomposition de la tâche en sous-tâches et de la hiérarchie des Objets d'Application [13]. La troisième et dernière section  illustre les concepts définis au travers une application d’Aides aux Malades. Nous concluons en critiquant nos résultats et en présentant la suite de nos recherches.
 Afin de ne pas compliquer les notations et surtout d'établir un lien direct avec [8], nous gardons en Anglais les noms de primitives et événements des Objets du dialogue.
2. Concepts d’Automates à Pile
Il s’agit dans cette section de donner une sémantique à chaque  concept relatif aux AP et, cela dans le contexte de spécification de dialogues mono-fils, multi-fils et hypermédia. Rappelons qu’un dialogue mono-fil est celui dont l’utilisateur interagit avec l’interface d’une seule tâche activée. Un dialogue est dit multi-fil lorsque les trois conditions suivantes sont satisfaites :
1.	plusieurs tâches sont activées ;
2.	l’utilisateur interagit avec l’interface d’une tâche à la fois ;
3.	les tâches ouvertes s’interchangent mutuellement d’ informations.
Si en plus, l’utilisateur bénéficie de liens hypertextes pour naviguer d’une (sous-)tâche à une autre, le dialogue devient hypermédia. Dans ce dernier cas, en vue de fixer la charge à confier à notre objet coordinateur principal [8], nous nous limitons dans le cadre d’un intranet où nous supposons connues la liste ainsi que les différentes structures des  tâches susceptibles d’être exécutées par l’utilisateur. 
2. 1. Etat 
Nous définissons un  état (nœud) comme un contexte de l'utilisateur à un instant donné au travers le composant Présentation et la Machine fonctionnelle d'une interface. En se limitant aux commandes pouvant apporter des modifications dans le déroulement effectif d'une tâche via son interface, un état caractérise  un ensemble de primitives significatives, accessibles et actionnables à un instant donné.

Relativement à un moment  considéré, une primitive est dite significative lorsque son exécution produit un changement visible (ouverture ou fermeture d’une fenêtre, activation ou désactivation d’un ou plusieurs Objets Interactifs Concrets (OIC) [13] couramment visibles, affichage des résultats d’exécution d’une fonction sémantique,...) ou invisible (l’exécution d’une fonction sémantique,...). Elle est dite accessible lorsqu’en ce moment l’utilisateur peut  lancer son exécution au travers un OIC activé.  Une primitive actionnable est celle dont la Précondition est vraie au moment considéré.
 
Nous ne prenons donc pas en charge les commandes (primitives) telles:  réduire une fenêtre, la déplacer, l'agrandir,… qui elles, sont souvent offertes par le toolkit de la plate-forme d'implémentation et n'affectent en rien le déroulement réel de la tâche. Ces primitives ainsi que les événements qui leurs sont associés sont simplement ignorés dans ce travail. 
2. 2. Transition 
De ce qui précède, une transition (arc orienté) correspond à un changement de contexte; un passage d'un ensemble de primitives vers un autre (éventuellement le même). Le coût d'une transition    (poids d'un arc) est l'événement  ou  la primitive qui aurait provoqué la transition. 
2.3. Action et Condition 
Une  action est une   tâche élémentaire (primitive ou fonction sémantique) accomplie  dans un contexte donné. La notion de condition intervient particulièrement pour un script B dont l'exécution dépend des modalités de terminaison d'un autre script A. Une  condition est une phrase  précisant les modalités d'exécution ou de la non exécution de B après l'exécution de A.
2. 4.  Pile 
Une pile est un récipient abstrait de capacité infinie dans lequel sont sauvegardés les traces d’actions et d’ événements des échanges inter tâches et homme-machine. Un item d’une pile a la structure <e, li> où e est un état quelconque et li , la liste d’actions accomplies et d’événements survenus dans l’état e. Une pile est lue  en LIFO (Last In First Out) et admet les huit primitives suivantes:

Init:	-	®Ã 
Primitive qui crée une pile vide;	
Empty:	Ã ®BOOL
Donne vrai si la pile est vide, faux sinon.	
Makenull:	Ã®Ã
Vide la pile;	
Add:	Ã X Á®Ã
Ajoute une valeur dans la liste courante. Pour une pile P de sommet <e, <ae1,…,aen>> et une action ou événement ae reçus comme arguments, Add(P,ae) retourne une pile P' dont le contenu est exactement identique à celui de P, excepté le sommet qui lui, se transforme en <e, <ae1,…,aen,ae>> .	
Push:	Ã X (KX Á) ®Ã
Ajoute un item au sommet de la pile.
Push(P,<e,li>) place <e,li> au sommet de la pile P; 	
Top	Ã ® (KX Á)
Renvoie  l'item se trouvant au sommet de la pile  si cette dernière n’est pas vide. Sinon, elle renvoie un message d'erreur ;	
Pop	Ã ®Ã
Primitive qui dépile le sommet d’une pile sans renvoyer sa valeur ;	
Minus:	Ã ®Ã
Supprime une valeur dans la liste courante. Pour une pile P de sommet <e, <ae1,…,aen, ae>>, Minus(P) retourne une pile P' identique à P, à l’exception du  sommet qui se transforme en <e, <ae1,…,aen>>.  Si  le sommet de P est de type <e,<>>,  le résultat de Minus(P) est identique à celui de Pop (P). Par contre, Minus(P) retourne un message d’erreur si P est vide.	

Remarquons en passant que Init, Empty et Makenull sont des primitives d’initialisation de dialogues. La primitive Add garnit la pile au fur et à mesure que les dialogues évoluent dans un état donné. Une transition vers un état e’ d’un AP de pile P correspond à l’exécution de Push(P, <e’,<ev>>) si ev est l’événement qui aurait causé la transition. Les primitives Top et Pop aident pour consulter le passé (l’historique) ou revenir en arrière. La primitive Minus joue le rôle de la fonction Undo qui annule la dernière action de l’utilisateur. L’exécution N fois consécutives de Minus annule les N derniers items (actions ou événements) insérer dans la liste courante en commençant  par le dernier. 
Au besoin, les projections proj1 et proj2 peuvent être utilisées pour avoir la valeur de l’état courant ou celle de la liste courante. C’est-à-dire :

•	Proj1 (Top (Push(P, <e,li>)))=e, l’état courant 
•	Proj2 (Top (Push(P, <e,li>)))=li, la liste courante. 

De même, on peut utiliser la fonction exists qui reçoit une pile P et un état e comme arguments et, retourne vrai si e a été visité, c’est-à-dire s’il existe dans la pile un item de type <e, _>. Sinon, elle retourne faux. Formellement, cette fonction s’exprime de la manière suivante :
         exists (init, e)= faux
exists (Push(P, <e’,li>), e)= vrai               si  e=e’
                                           exists (P, e)  ailleurs
La pile ainsi décrite joue bien son rôle de gestionnaire de l'historique des dialogues dans la mesure où, son contenu informe sur le déroulement effectif des échanges en tout moment de l'exécution d'une tâche considérée. En plus, la pile couvre implicitement le rôle joué par les jetons d'un RdP. En effet, comme nous le disions ci-dessus, à l'aide des primitives Top et Pop, nous savons déterminer si oui ou non une transition est actionnable. De même, le résultat de la primitive Push suivant une transition renseigne sur l'état courant des jetons dans le nouvel état.
2. 5. L’alphabet 
Comme nous pouvons le constater, l’alphabet d'entrée est le même que celui de l'attribut de AT_SCENARIO des objets de contrôle de dialogues. Selon les actions d’un utilisateur et les événements reçus, la tête de lecture parcourt les équations contenu dans l’attribut AT_SCENARIO et sollicite une mise à jour de la Pile correspondante. Les états accepteurs sont ceux qui caractérisent une  fin normale d'une tâche donnée.
2. Construction des Automates de dialogues
Dans cette section, le but est de montrer comment construire les automates de dialogues à partir de l'Arborescence de la Décomposition de la Tâche en Sous-Tâches (ADTST) et de la Hiérarchie des Objets d'Application (HOA).
D'abord signalons en passant qu'il existe trois types de sommets dans une ADTST:
1.	La racine: sommet sans parent que nous appelons coordinateur;
2.	Des nœuds: sommets avec un père et au moins un fils. Ce sont des objets de contrôle de dialogues relatifs aux tâches et aux sous-tâches de premier niveau;
3.	Des feuilles: sommets avec un père mais sans fils. Ce sont des objets de contrôle de dialogues relatifs aux sous-tâches de second niveau. 

Si pour la racine et les nœuds la construction des automates est quasi évidente, il n'en est pas le cas pour les feuilles. Ainsi, nous découpons la présente section en deux sous-sections dont la première traite des automates déduits de deux premiers types de sommets et, la seconde propose un algorithme de construction des automates relatifs aux feuilles.
2.1. Automate de la racine et d'un noeud
Pour la racine (resp. un nœud), chacun de ses fils dans l'ADTST représente un état de l'automate associé. Si la racine (resp. un nœud) a N fils, l'automate associé aura:
•	N+1 états si l'ordonnancement de l'exécution des tâches (resp. des sous-tâches) dépend du choix préalable de l'utilisateur. Dans ces conditions, on ajoute un état initial consistant en la gestion du choix de l'utilisateur;
•	N  états si l'ordre d'exécution des tâches (resp. des sous-tâches) découle directement de l'énoncé de la tâche et, est indépendant du choix préalable de l'utilisateur. 
Dans ces conditions, les liens inter états sont déduits de l'attribut AT_SCENARIO de la racine ou du nœud considéré. Les coûts de transition représenteront les causes (événements ou primitives) de passage d'un état à un autre.
2.2. Automate d'une feuille
Pour une feuille, la construction de l'automate associé est déduite de l'analyse fonctionnelle  sur base des Pré et Post conditions des fonctions sémantiques utilisées par la feuille et cela, suivant l'algorithme décrit dans la figure1. Remarquons que chacun de trois  pavés rectangulaires de l'ordinogramme fournit un état de l'automate. Les pavés à traits discontinus sont optionnels; ils peuvent ne pas exister si la fonction encapsulée par l'OA ne nécessite pas d'arguments (et donc n'utilise aucune primitive d'Objet d'Interaction [13] d'Entrée-Sortie (OI-E/S)) ou ne fournit aucun résultat. Les flèches de l'ordinogramme donne un ensemble minimal de transitions de l'automate  car, à celles là, il faut ajouter des éventuels retours en arrière ou des boucles.

On dit d'un OA qu'il est indépendant lorsque l'exécution de la fonction sémantique qu'il encapsule ne dépend d'aucune autre fonction.

Si l'OA courant possède plusieurs pères, on appliquera l'opération à chacun d'eux.

Figure 1 — Construction de l'automate d'une feuille 
3. Aides Aux Malades
Une ASBL (Association Sans But Lucratif) de la Belgique offre un certains nombre de services aux Malades dont :
1.	le déplacement (simple ou aller-retour ) de la maison vers une institution hospitalière pour des soins médicaux ou une hospitalisation;
2.	le transfert d’un malade d’un hôpital vers un autre ;
3.	la garde à domicile d’un malade ;
4.	la réalisation des courses pour un malade ;
5.	l’encadrement d’un groupe de malades lors d’une visite guidée...
Ces services sont rendus en complicité avec de Bénévoles qui, sont des volontaires recrutés par l’ASBL. Aussi, Cette dernière utilise entre autres quatre programmes informatiques aidant chacun   à la gestion de  l’une de quatre tâches suivantes : le Transport des Malades (T1), la Gestion de Bénévoles (T2), la  Comptabilité générale (T3) et l’atlas routier (T4). Bien qu’autonomes, ces programmes sont inter dépendants car, par exemple, pour affecter une demande de transport, un utilisateur doit lancer la recherche d’un Bénévole par code postal ou par disponibilité. Aussi, une connexion hypermédia vers l’atlas routier  électronique  peut servir  pour aider un bénévole à décider sur une proposition de demande de transport qui lui est affectée. De même, au service de Comptabilité, le calcul de la prime d’un bénévole ou de la facture d’un malade se fait sur base des informations recueillies respectivement auprès de service de Gestion de Bénévoles et celui de transport de  malades. 
 
Une gestion harmonieuse de ces quatre programmes nécessite un coordinateur (C0)  dont l’automate est donné par  la figure 2   ci-dessous :

Figure 2 — dialogue inter tâches
La justification des états est évidente sur base de la section 2. L’état T0 représente une tâche théorique (technique) consistant en la gestion du menu d’entrée. 
En supposant que pour une demande de transport, l’utilisateur peut commencer exclusivement  par l’identification du Malade (ST1) ou par la saisie du corps de la demande (ST2) et que, l’affectation d’une demande à un bénévole (ST3) ne peut se faire qu’après terminaison de ST1 et ST2. En notant ST0, la sous-tâche d’ordonnancement, l’automate correspondant à la tâche Transport de Malade est donné par la figure 3 ci-dssous.
Dans ce qui suit, nous illustrons l'évolution du contenu de la pile suivant un exemple d'enregistrement de demande de transport. Nous notons P la pile  et, mettons entre crochets son contenu. Le dernier item inséré dans la pile est souligné et mis en gras.

Figure 3 — dialogues d’une demande de transport

Initialement, la pile P est vide. Au lancement du coordinateur, elle devient :

P	=Push(init, <<T0,<PR_Active(T0)>>)	
  	=[<T0,<PR_Active(T0)>> ]	

Après le choix de l’utilisateur pour la tâche Transport de Malade, T0 est suspendue et la pile devient :

P	=Push(P, <T1, < ev_select-T1 & PR_Suspend(T0) >>)	
	=[<T0,<PR-Activer(T0)>>, <T1, < ev_select-T1 & 
PR_Suspend(T0) >>	

Dans T1, admettons que l’utilisateur choisit de commencer par ST1. La pile devient : 

P	=Push(P, <ST1, <ev_select-ST1>>)	
	=[<T0,<PR_Active(T0)>>, <T1, <ev_select_T1 & 
PR_Suspend(T0) >>, <ST1, <ev_select-ST1>> ]	

Dans ST1, il exécute au moins l’une des sous-tâches pour identifier le Malade qui sollicite le transport. A la fin de ST1, étant donné que exists (P,ST2)=faux, l’automate bascule dans l’état ST2. Ce qui transforme la pile en :

P	=Push(P,...)           (Exécution de sous-tâches de ST1)	
	=Push(P+, <ST2, <ev_ok-ST1>>)
                              (Passage à l’état ST2)	
	=[<T0,<PR-Active(T0)>>, <T1, <ev_select-T1 & 
PR_Suspend(T0) >>, <ST1, <ev_select-ST1>>, ...,<ST2, <ev_ok-ST1>> ].	

Dans ST2, il  saisit les données relatives à la demande de transport et passe à ST3 car exists (P,ST1)=vrai . Ainsi, la pile se  transforme  en :

P	=Push(P,...)             (Saisie des données)	
	=Push(P+,<ST3, <ev_ok-ST3>>)
                                (Passage à l’état ST3)	
	=[<T0,<PR-Active(T0)>>, <T1, <ev_select-T1 & 
PR_Suspend(T0) >>, <ST1, <ev_select-ST1>>,...,<ST2, <ev_ok-ST1>>,..., <ST3, <ev_ok-ST3>>].

Pour achever ST3, l’utilisateur a besoin de trouver le bénévole qui répond au mieux aux données encodées. Ainsi, il abandonne provisoirement T1 et active T0 où il choisit T2. Ceci  transforme la pile en :

P	=Add (P, ev_Pause-ST3)                (Interruption de ST3)	
	=Push(P, <T0, <PR-Active(T0)>>) (Réactivation de T0)	
	=Push(P, <T2, <ev_select-T2 & PR_Suspend(T0)>])
                                                       (Choix de T2)	
	=[<T0,<PR-Active(T0)>>, <T1, <ev_select-T1 & 
PR_Suspend(T0) >>, <ST1, <ev_select-ST1>>,...,<ST2, <ev_ok-ST1>>,..., <ST3, <ev_ok-ST2, ev_Pause-ST3>>, <T0, <PR-Active(T0)>>, <T2, <ev_select-T2 & PR_Suspend(T0)>].	

Dans T2, il exécute les primitives nécessaires et trouve le Bénévole cherché. Ainsi, il achève T2 et réactive ST3. Ce qui donne :

P	=Push(P,...)                            (Recherche du Bénévole)	
	=Push(P+, <ST3, <PR-Active(ST3)>>)) 
                                               (Passage à l’état ST3)	
	=[<T0,<PR-Active(T0)>>, <T1, <ev_select-T1 & 
PR_Suspend(T0) >>, <ST1, <ev_select-ST1>>,...,<ST2, <ev_ok-ST1>>,..., <ST3, <ev_ok-ST2, ev_Pause-ST3>>, <T0, <PR-Active(T0)>>, <T2, <ev_select-T2 & PR_Suspend(T0)>,... ,<ST3, <PR-Active(ST3)>>].	

Dans ST3, il clôture la demande et rentre au menu d’entrée. Ce qui donne :

P	=Add(P, ...)                               (clôture de la demande)	
	=Push(P+, <T0, ev_ok-T3 & PR-Active(T0)>>)
                                                 (retour au menu d’entrée)	
	=[<T0,<PR-Active(T0)>>, <T1, <ev_select-T1 & 
PR_Suspend(T0) >>, <ST1, <ev_select-ST1>>,...,<ST2, <ev_ok-ST1>>,..., <ST3, <ev_ok-ST2, ev_Pause-ST3>>, <T0, <PR-Active(T0)>>, <T2, <ev_select-T2 & PR_Suspend(T0)>,... ,<ST3, <PR-Active(ST3),...>, <T0, ev_ok-T3 & PR-Active(T0)>>].	

Si l’utilisateur décide d’arrêter l’exécution de T0, la pile se vide de la manière suivante :

P	=Makenull(P)	
	=[ ]	
4. Conclusions
1.	Les résultats obtenus confirment bien la prédiction proposée  dans [8] à propos du lien direct entre les objets du dialogue et les états de l'automate. En effet, nous constatons que chaque objet du dialogue représente bien un état d'un automate de dialogues.
2.	La construction des automates de dialogues devient quasi systématique. En effet, à partir d'une ADTST le designer peut aisément obtenir l’automate de la racine et ceux des nœuds. Et, suivant l’ordinogramme de la figure 1, il construit les automates relatifs aux feuilles. Remarquons 

que les nœuds et transitions de ces automates répondent bien aux définitions du point 2. 
3.	La pile telle que décrite ci-dessus, permet de mémoriser aisément l’historique des échanges inter tâches et Homme-Machine. Aussi, elle nous offre des primitives nécessaires pour retrouver une information dans le passé ou même de revenir en arrière.
4.	Pour la suite, nous envisageons d'exploiter les attributs, primitives et événements des objets de dialogues définis dans [8] afin de définir des structures de données d'un langage de règles pour la spécification de dialogues. Les aspects dynamiques de ce langage s'appuierons, sans aucun doute, sur les résultats obtenus dans cette communication. Un tel langage est utile pour la réalisation d'un outil case graphique d'apprentissage et d'évaluation de spécifications de dialogues.

Bibliographie 
 [1] 	Alexander H., Formally-Based tools and techniques for Human-Computer Dialogues. Ellis Horwood limited, Chichester, 1987.
[2]  Bass L. et Coutaz J., Developing Software for User Interface, Addison-Wesley Publishing Compagny, USA, 1991.
[3] Bodart F. et Pigneur Y, Conception assistée des systèmes d’information- méthodes, modèles, outils,. Dunod, Paris, 3, 1989.
 [4] Coutaz J., Interface homme-ordinateur. Conception et réalisation, Dunod Informatique, Paris, 1990.
[5]   Duval E., K. Hendrikx et Olivie H., Building hypermedia with objects and sets, Journal of Universal Computer Science, pp 501-521, 28/5/1998
[6] Larson J. A., Tools for Building Interactive User Interfaces, Yourdon Press Computing Series, Yourdon, 1986.
[7] Leheureux J.-M., Architecture logicielle de la méthode TRIDENT, Institut d’Informatique (FUNDP), Namur, 1995
[8] Mbaki Luzayisu E., Extending software architecture and dialog’s objects specification in TRIDENT methodology,  Institut d’Informatique (FUNDP), 1999.
[9] Palanque P. , Modélisation par Objets Coopératifs Interactifs d’Interface Homme-Machine dirigées par l’utilisateur, PhD Thesis, Université Toulouse I, 1992.
[10] Paterno F., Mancini C., Meniconi S., ConcurTaskTrees: A Diagrammatic Notation for specifying Task Models, in Proceedings of Interact'97, pp 262--269, Chapman & Hall, Londres, 1997
[11]  Popping M. et Szwillus G., Constraint-based definition of application-specific graphics, In Human-Computer Interaction (Interact’95), pp 85-90, Great Britain, Oxford, 1995.
[12] Sheneiderman B., Designing the User Interface : Strategies for effective Human-Computer Interaction. Addison Wesley Longman, Inc., USA, 3, 1998.
[13] Vanderdonckt J., Conception assistée de la présentation d’une interface homme-machine ergonomique pour application de gestion hautement interactive, Phd thesis, Institut d’Informatique (FUNDP), 1997.