UP | HOME

Modèle chimique pour l'échange de messages

Voici une description synthétique du langage chimique utilisé pour spécifier les services, avec quelques exemples.

Table of Contents

1 Grammaire

On décrit tout d'abord la spécification d'un service par des règles chimiques.

1.1 Syntaxe

spécification ::= règle*
        règle ::= (prérègle -> production)
    prérègle  ::= consommation & condition
 consommation ::= messages & état
   production ::= messages & état 
     messages ::= Vide // Aucun message
                | message & messages // Conjonction de messages 
      message ::= k(t*) // canal k transportant les termes t*
         état ::= Vide // Etat vide 
                | atome & état // Conjonction d'atomes 
        atome ::=  R(t*) // Prédicat R appliquée aux termes t*
    condition ::= Vrai
                | assertion & condition // Conjonction d'assertions  
    assertion ::= P(t*) // Prédicat P appliqué aux termes t*
                | (prérègle inactive) // Pré-règle non applicable
        terme ::= ... // Eléments d'une algèbre

Une règle possède des variables. Les variables sont libres dans la partie consommation et liées ailleurs : autrement dit, la partie consommation agit comme un lieur.

Une exception : dans une condition exprimant l'inactivité d'une pré-règle, les variables qui ne sont pas liées sont supposées libres lorsqu'on vérifie l'inactivité de la règle. Autrement dit, on teste qu'il n'existe pas de valeurs prises par ces variables pour lesquelles la pré-règle est active, ou encore que pour toutes valeurs prises par ces variables, la pré-règle est inactive.

Les variables libres d'une règle reçoivent une valeur lorsqu'on cherche à déclencher une règle : c'est une forme de filtrage ("pattern matching").

1.2 Exemples

1.2.1 Réduction au maximum

R(x) & R(y) & (x <= y) -> R(y)

Considérons l'état initial suivant, formé à partir de la multi-relation R : c'est un multi-ensemble d'atomes.

R(0), R(0), R(1), R(2)

Remarque :

  • un multi-ensemble est un ensemble dont les éléments peuvent avoir de multiples occurrences (cf. Wikipedia pour des détails),
  • de même une multi-relation est une relation dont les éléments peuvent avoir plusieurs occurrences.

Dans l'état précédent, R(0) a plusieurs occurrences.

Plusieurs correspondances sont possibles entre l'état et la pré-règle R(x) & R(y) & (x <= y), produisant les valuations suivantes.

x = 0, y = 0
x = 0, y = 1
x = 0, y = 2
x = 1, y = 2

Si on applique les trois premières correspondances, on obtient après déclenchement de la règle l'état suivant.

R(0), R(1), R(2)

Si on applique la dernière correspondance, on obtient l'état suivant.

R(0), R(0), R(2)

En itérant, on obtient finalement un seul atome, avec la plus grande valeur, R(2).

1.2.2 Variantes pour calculer la maximum

Première tentative

R(x) & ((R(y) & (x < y)) inactive) -> R(x) & Max(x)

La pré-règle (R(y) & (x < y)) possède une variable libre y. La condition s'interprète donc ainsi : pour tout y, la pré-règle (R(y) & (x < y)) est inactive.

Etat initial

R(0), R(0), R(1), R(2)

Pour (x = 0), la pré-règle devient (R(y) & (0 < y)), qui est active, pour y valant 1 ou 2.

Pour (x = 1), la pré-règle devient (R(y) & (1 < y)), qui est active, pour y valant 2.

Pour (x = 2), la pré-règle devient (R(y) & (2 < y)), qui est inactive. Si on applique cette correspondance, on consomme R(2) pour produire R(2) et Max(2).

Après cette application, la seule possible, il s'avère que la règle peut encore s'appliquer : le programme bouclerait. On modifie donc la règle ainsi, pour garantir la terminaison.

Seconde tentative

R(x) & ((R(y) & (x < y)) inactive) & (Max(_) inactive) -> R(x) & Max(x)

La pré-règle Max(_) possède une variable libre _. La condition s'interprète ainsi : pour tout z, la pré-règle Max(z) est inactive, autrement dit, il n'y a pas d'atome Max(z) dans la solution.

1.3 Interprétation sémantique

Chaque agent (client ou serveur) exécute un ensemble de règles : à chaque tour, il détermine les règles applicables, en sélectionne une parmi celles-ci et la déclenche.

Initialement, il possède un état. Par la suite, à la fin de chaque tour, il reçoit des messages sur un ensemble de canaux initialement fixé et envoie des messages sur des canaux appartenant à d'autres agents.

Une règle (consommation & condition -> production) peut s'appliquer

  • lorsque les messages reçus et l'état correspondent avec la consommation attendue par la règle et
  • lorsque la condition est vérifiée.

Parmi toutes les règles pouvant s'appliquer, une seule est sélectionnée pour l'exécution. Les messages sont alors consommés, d'autres messages sont produits et l'état est modifié. Un nouveau tour peut commencer, après l'émission et la réception de messages.

1.4 Messages pour la communication

Les messages sont échangés entre les agents. Un agent contient un multi-ensemble de messages, ceux reçus et ceux à émettre. Le réseau dans lequel sont plongés les agents contient aussi un multi-ensemble de messages, ceux en transit.

Structure : k(v)

  • k : canal
  • v : valeur transmise (terme d'une algèbre)

Règles pour la communication asynchrone

- A[S & msg] -> A[S] & msg // Emission par l'agent A d'un message
- A[S] & msg -> A[S & msg] // Réception par l'agent A d'un message

Concept fondamental : la mobilité des canaux

  • La valeur v peut contenir un canal.
  • Exemple : ping(pong, OK)

1.5 Atomes pour l'état

L'état est un multi-ensemble d'atomes (des messages internes).

Structure : R(v)

  • R : multi-relation (d'arité quelconque)
  • v : terme appartenant à la multi-relation

Exemple: R(1), R(1), S(5) (1 avec deux occurrences dans R, 5 avec une occurrence dans S)

1.6 Conditions : des expressions booléennes

Une condition est une conjonction d'expressions booléennes, construites à partir de tout prédicat utile. Une condition permet aussi de tester si une pré-règle est inactive. C'est une forme d'introspection : il est possible pour un agent d'observer son état, formé des messages reçus et des atomes.

2 Exemple d'exécution : ping-pong

Voici un exemple avec deux agents.

Client

  • Etat : Debut, Attente, Fin(x)
  • Etat initial : Debut
  • Canal : pong
    Debut -> ping(pong, OK) & Attente
    Attente & pong(x)-> Fin(x) 
    

Au début, le client envoie le message ping avec OK pour contenu et attend la réponse sur le canal pong. Lorsqu'il la reçoit, il passe à l'état Fin(x), où x est le contenu reçu sur pong.

Serveur

  • Pas d'état
  • Canal : ping
    ping(k, x) -> k(x)
    

Lorsque le serveur reçoit le message (k, x) sur le canal ping, il répond en transmettant x sur le canal k.

Une exécution (A[X] indiquant que l'agent A a pour état et messages X)

   Client[Debut], Serveur[]
-> Client[ping(pong, OK), Attente], Serveur[] // Production
-> Client[Attente], ping(pong, OK), Serveur[] // Emission
-> Client[Attente], Serveur[ping(pong, OK)] // Réception
-> Client[Attente], Serveur[pong(OK)] // Consommation et production
-> Client[Attente], pong(OK), Serveur[] // Emission
-> Client[Attente, pong(OK)], Serveur[] // Réception
-> Client[Fin(OK)], Serveur[] // Consommation finale

Last Updated 2016-04-08T11:10+0200. Comments or questions: Send a mail.