Modèle chimique pour l'échange de messages

Le langage décrit ici est une version simplifiée du langage le plus général. En effet, on considère une structure plate formée d'un réseau contenant des agents. Chaque agent possède une solution initiale et des règles. Le réseau lui-même peut contenir des règles particulières de communication impliquant les agents. Le langage le plus général autorise une structure arborescente d'agents, permettant de représenter des réseaux de réseaux.

Chaque agent possède un état initial et des règles permettant de consommer et produire des messages ainsi que de modifier l'état. Il fournit également des canaux de communications, sur lesquels il peut recevoir des messages.

   agent ::= M[initial][règle*] // agent M avec état initial et règles
       M ::= ... // nom d'agent

 initial ::= solution fermée // sans variable libre
solution ::= vide 
           | atome & solution // atome inséré dans solution
           | S // variable
  atome  ::= R(valeur) // fait atomique
           | k(valeur) // message
           | A  // variable              
  valeur ::=  f valeur*  // terme 
           | k // canal fourni par un agent
           | V // variable
       R ::= ... // relation décrivant l'état
       k ::= ... // canal de communication fourni par un agent
       f ::= ... // fonction permettant de construire des valeurs

    règle ::= solution & garde -> solution // consommation & garde -> production 
    garde ::= Vrai
            | garde & garde // conjonction de gardes
            | P(valeur*) // prédicat P appliqué à des valeurs
            | (solution & garde inactive) // pré-règle (solution & garde -> ...) non applicable

Le réseau qui contient les agents peut lui-même posséder un état et des règles. Les règles peuvent agir sur un nouveau type d'atome, représentant un agent.

atome  ::= ... // cf. supra
         | M[solution] // Agent M avec solution

Une règle possède des variables, en plus de la variable de solution S qui représente le reste de la solution. Cette dernière variable est linéaire : elle possède une occurrence au plus à gauche ou à droite d'une règle, ce qui donne trois cas.

... & S -> ... & S // préservation du reste de la solution
... & S -> ...     // consommation du reste de la solution
...     -> ...     // aucune variable pour représenter le reste de la solution

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 (soit la partie gauche d'une 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"). Une correspondance entre le filtre et la solution produit une valuation, qui à chaque variable donne une valeur.

La variable de solution S est omise dans l'écriture des règles : il est nécessaire de la rajouter à gauche et à droite des règles, en garantissant ainsi la préservation du reste de la solution. On précisera explicitement lorsque cet ajout ne doit pas être fait, en mentionnant que la correspondance doit être exacte.

Convention

  ...     -> ...     
// à interpréter ainsi :
  ... & S -> ... & S

Dans les exemples ci-dessous, on applique la convention.

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. La communication se fait suivant les règles de communication définies dans le réseau : par défaut, la communication est asynchrone.

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, ce qui a pour effet d'associer una valeur à chaque variable libre de 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, après une instanciation de la production par la valuation résultant de la correspondance, et l'état est modifié. Un nouveau tour peut commencer, après l'émission et la réception de messages.

Le réseau contient des agents et garantit que les messages peuvent être échangés entre les agents. Un agent contient un multi-ensemble de messages, ceux reçus et ceux à émettre. Le réseau contient aussi un multi-ensemble de messages, ceux en transit.

Structure d'un message : k(v)

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

Emission (pour un canal k qui n'est pas fourni par l'agent M)

M[k(x) & S] -> k(x) &  M[S]

Réception (pour un canal k qui est fourni par l'agent M)

k(x) & M[S] -> M[k(x) & S]

Ces deux règles sont toujours supposées présentes lorsque la communication est asynchrone.

Concept fondamental : la mobilité des canaux

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

Ce mécanisme de mobilité des canaux permet de communiquer avec des agents initialement inconnus : un agent est découvert à réception d'un canal qu'il fournit.

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)

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.