Réseaux d'interaction, Yves Lafont

23 janvier 2013

Lucas Verney

Sommaire

Réseaux d'interaction

Nouvelle façon de programmer :

  • Basée sur une sémantique de réécriture de graphes.
  • Avec une symétrie entre constructeurs et destructeurs.
  • Un typage facilitant un parallélisme sans interblocage.

Principes de base

  • Graphes non dirigés avec des nœuds étiquetés.
  • Chaque nœud a un certain nombre de ports et un port principal.

  • On ajoute des règles de réécriture, qui traduisent des interactions :

On ajoute des propriétés à vérifier :

  1. (linéarité) Dans chaque règle, une variable apparaît exactement deux fois, dans le membre de gauche et dans le membre de droite.
  2. Les interactions ne se font que par leur port principal.

  3. (pas d'ambiguïté) Au plus une règle pour chaque paire distincte de symboles $S, T$ et aucune pour $S, S$.

Ces trois conditions nous assurent la propriété suivante :

Si $N$ se réduit en une étape en $P$ et $Q$, avec $P \neq Q$, alors $P$ et $Q$ se réduisent en une étape en un même $R$.

Les règles 2 et 3 assurent qu'il n'y a pas d'interférences entre les deux règles. La règle 1 assure que les interactions sont locales.

L'ordre relatif des opérations de réductions concurrentes n'importe pas.

Il reste à ajouter une règle pour assurer la réductibilité.

  1. Les membres de droite des règles ne contiennent pas de symboles connectés par leur port principal.

⇒ De tels symboles pourraient être réduits à nouveau.

Note : Cette règle n'assure pas la terminaison.

Parseur de notation polonaise (préfixe)

Typage

Comment faire interagir Parse et Append ?

⇒ Il faut introduire un système de typage et donner un type à chaque port, en caractérisant une entrée (+) ou une sortie (-).

Un réseau est bien typé si toutes les entrées sont connectées à des sorties de même type.

Une règle est bien typée si

  • Les symboles du membre de gauche se correspondent, i.e. ont des types opposés (+ / -) sur leurs ports principaux.
  • Le membre de droite est bien typé (en utilisant les types du membre de gauche).

Nous pouvons donc introduire deux conditions supplémentaires pour avoir des interactions typées :

  1. (typage) Les règles sont correctement typées.
  2. (complétude) Il y a une règle pour chaque paire de symboles se correspondant.

Note : La dénomination d'entrée / sortie est arbitraire. La notion de Constructeur et de destructeur est donc symétrique.

Nous avons une notion de correction locale pour l'instant. Qu'en est-il d'une correction globale (pour prévenir des interblocages) ?

Supposons $N$ bien typé, fini, non vide, avec des variables libres $x_1 \dots x_n$. Si $N$ est irréductible, alors:

  • Soit un des $x_i$ est connecté à un port principal, ou à une autre variable.
  • Soit $N$ contient un cercle vicieux (qui reste toujours alors) :

Les cercles vicieux sont des interblocages. Il faut rajouter des contraintes pour empêcher leur formation.

Première idée

Interdire les cycles.

Impossible

Solution

Partition sur les ports auxiliaires de chaque symbole, pour distinguer les bons et les mauvais cycles.

Les réseaux valides (simples) sont donc :

+ et le réseau vide = semi-simples

Dans le cas discret, un réseau est simple si c'est un graphe connexe sans cycle, et il est semi-simple quand il n'a aucun cycle.

Un réseau semi-simple ne contient aucun cercle vicieux.

Une règle est simple si, en groupant les variables suivant les partitions dans le membre de gauche, le membre de droite devient simple.

Les réseaux simples sont clos par réduction par des règles simples.

On peut donc introduire une dernière règle :

  1. (Simplicité) Les règles sont simples.

qui aboutit à

Un réseau simple garantit l'absence d'interblocage.

Un langage de programmation

On définit un langage par trois parties :

  • Une déclaration de type (liste d'identificateurs)
  • Une déclaration de symboles (liste d'identificateurs avec typage et partitions)
  • Des règles d'interaction

Cons [z,Append(v,t)] )( Append [v,Cons(z, t)]

Conclusion

  • Fort parallélisme (entrées / sorties) et typage (comme en fonctionnel).
  • Déterminisme et anti-interblocage qui n'a pas été introduit ailleurs.

Implémentations réelles ?

⇒ Lier à un clavier, une souris, un écran… Exemples de la vie courante.