B.3 Algorithmes

B.3.1 Mutation d'un dispositif

La mutation d'un dispositif consiste en la réévaluation des valeurs de ses attributs à la suite d'une modification de son paramétrage, dans le but d'assurer sa consistance. Cette réévaluation n'est nécessaire que dans la mesure où ce dispositif est mutable. Le mécanisme de mutation d'un dispositif est décrit par l'algorithme B.1.

L'algorithme de mutation met à jour les slots du dispositif en fonction du m-paramétrage, en supprimant, en ajoutant, ou en mettant à jour le type des slots. L'emploi de slots absents évite la suppression de connexions à la suite d'une mutation. En particulier, un slot supprimé puis créé à nouveau conservera ses connexions.

L'algorithme distingue six cas possibles pour chaque slot: Les slots s-mutables de $d$ qui sont absents du m-paramétrage sont supprimés s'ils ne sont pas connectés (slots $\Sigma^-$) et transformés en slots absents s'ils sont connectés (slots $\Sigma_a^+$). Les nouveaux slots s-mutables décrits par le m-paramétrage sont ajoutés s'ils n'existent pas en tant que slots absents (valuations $V^+$), et dérivés des slots absents dans le cas contraire (slots $\Sigma_a^-$). Enfin, l'algorithme met à jour les types des slots t-mutables (slots $\Sigma_t$) et des slots s-mutables qui sont présents à la fois sur le dispositif et dans le m-paramétrage (slots $\Sigma^=$). À la fin de l'algorithme, $\Sigma$ comprend l'ensemble des slots ayant changé de type, qui servira à la propagation des mutations.

B.3.2 Propagation des mutations

La mutation d'un dispositif $d$ est provoquée par une ou plusieurs des causes élémentaires suivantes:

1. la modification du type connecté d'un des slots déclencheurs de $d$;
2. une connexion ou une déconnexion sur l'un des slots déclencheurs de $d$;
3. la modification de la valeur d'un des paramètres de $d$.

En outre, la mutation de $d$ a pour résultat une ou plusieurs conséquences élémentaires qui peuvent être classées en quatre catégories:

1. la modification du type d'un slot t-mutable ou s-mutable de $d$;
2. la suppression d'un slot s-mutable connecté de $d$;
3. la suppression d'un slot s-mutable non connecté de $d$;
4. l'ajout d'un slot s-mutable à $d$.

Figure: Propagation d'une mutation : Le slot $S$, t-mutable, et le slot $S'$, déclencheur, sont reliés par une connexion $c$ de sens quelconque. À la suite d'une mutation du dispositif $d$, le type de $S$ est modifié, ce qui a pour effet de modifier également le type connecté du slot $S'$ et provoquer une mutation de $d'$.

Par l'intermédiaire des connexions, les conséquences de type 1 et 2 peuvent provoquer sur d'autres dispositifs des causes de type 1 et y déclencher des mutations: la mutation est alors propagée (figure B.2). La mutation d'un dispositif est susceptible d'être propagée à tous les dispositifs directement connectés, indépendamment du sens des connexions. Ce mécanisme de propagation est décrit par l'algorithme B.2.

L'algorithme B.2 consiste à appliquer l'algorithme de mutation sur un ensemble de dispositifs, en se servant de la valeur de retour $\Sigma$ pour déterminer l'ensemble des dispositifs vers lesquels les mutations doivent être propagées. L'algorithme est à nouveau appliqué sur ce dernier ensemble, et ainsi de suite jusqu'à ce qu'il n'y ait plus de dispositifs candidats. Notons que la propagation des mutations peut monter ou descendre dans l'arbre des configurations, à travers les slots i-connectés (voir section A.4.5).

Il est également important de noter que cet algorithme récursif opère en largeur d'abord plutôt qu'en profondeur d'abord: les dispositifs cibles de la propagation sont stockés au lieu d'être mutés immédiatement. Au niveau du slot, c'est l'algorithme de mutation (algorithme B.1) qui se charge du stockage des propagations. La propagation en largeur d'abord a pour avantage d'éviter des déclenchements inutiles de mutations (figure B.3).

Figure: Exemples de mutations inutiles. À gauche, une propagation en profondeur d'abord au niveau du slot: le dispositif $d$ modifie son slot $S1$ puis son slot $S2$. La propagation instantanée des mutations déclenche deux mutations successives sur le dispositif $d'$. À droite, une propagation en profondeur d'abord au niveau du dispositif: le dispositif $d1$ déclenche une mutation sur $d2$ puis sur $d3$. Là aussi, la propagation instantanée déclenche deux mutations successives de $d4$.

B.3.3 Propagation bornée

Bien que les connexions d'une configuration d'entrée ne génèrent pas de dépendance cyclique, ce n'est pas le cas des mutations, qui se propagent indépendamment de l'orientation des connexions. Lorsque les mutations comportent des dépendances cycliques, l'algorithme B.2 peut ne pas se terminer, mais peut également converger.

L'algorithme B.3 est une variante de l'algorithme B.2, qui se termine toujours. Le nombre de mutations sur chaque dispositif est limité à $i_{max}$. Lorsqu'un dispositif a muté $i_{max}$ fois, celui-ci est considéré comme non stabilisé. À terme, l'algorithme fournit dans $\Delta _{NS}$ l'ensemble des dispositifs non stabilisés. Si cet ensemble est non vide, la propagation est considérée comme non stabilisée dans son ensemble.

De par sa propriété de terminaison, l'algorithme B.3 est de loin préférable à l'algorithme B.2. Deux stratégies sont possibles pour l'exploiter: soit interdire les connexions qui induisent une propagation non stabilisée, soit autoriser provisoirement (hors exécution) les dispositifs non stabilisés dans une configuration. Un éditeur interactif pourrait par exemple mettre en évidence les « erreurs » dans l'espoir que l'utilisateur les corrige. Une manière de stabiliser la partie problématique de la configuration consiste à insérer des dispositifs « typeurs », dont les types en entrée et en sortie sont fixés par paramétrage: cela équivaut à ajouter des contraintes à un problème sous-contraint.

B.3.4 Exemples de fonctions de mutation

Le système de mutations, très général, peut se décliner en un certain nombre de mécanismes de spécialisation concrets. Parmi ceux-ci, nous donnerons un exemple de typage, de spécialisation structurelle par paramétrage, et d'adaptation bi-directionnelle. D'autres exemples peuvent être donnés, tels que la spécialisation structurelle par connexion, ou le typage par paramétrage.

B.3.4.1 Exemple de typage

Voici un exemple de dispositif dont les slots prennent le type int lorsque les slots d'entrée sont connectés à des entiers et le type double dans les autres cas:

Soit un dispositif mutable $add$ ayant deux slots d'entrée nommés $in1$ et $in2$, un slot de sortie nommé $out$, et ne comportant pas de paramètre. $in1$, $in2$ et $out$ sont t-mutables et possèdent comme supertype double. Les slots déclencheurs sont $in1$ et $in2$. La fonction de mutation $\mu_{add}$ de ce dispositif est la suivante:

$\mu_{add}: \left\vert\begin{array}{l} \mathcal{P} \rightarrow \mathcal{P}_m \... ...gle, \langle out, sortie, y \rangle \bigr\} \Bigr\rangle \end{array} \right.$

avec:

$\left\vert\begin{array}{l} y = int \text{ si } x_1 = int \text{ et } x_2 = int \\ y = double \text { sinon.} \end{array}\right.$

B.3.4.2 Exemple de spécialisation structurelle

Voici un exemple de dispositif dont le nombre de slots de sortie et d'entrée est paramétrable:

Soit un dispositif mutable $multipass$ comportant deux paramètres respectivement nommés $inCount$ et $outCount$. Le dispositif ne comporte pas d'autre slot que les slots s-mutables générés par la fonction de mutation. La fonction de mutation $\mu_{multipass}$ de ce dispositif est la suivante:

$\mu_{multipass}: \left\vert\begin{array}{l} \mathcal{P} \rightarrow \mathcal{... ...langle V_{Ss}^1 \cup V_{Ss}^2, \varnothing \bigr\rangle \end{array} \right.$

avec:

$\left\vert\begin{array}{l} V_{Ss}^1 = \varnothing \hspace{7pt} \text{si } x_... ...e}e, int \rangle \bigr\} \hspace{7pt} \text{sinon.} \\ \end{array} \right.$

$\left\vert\begin{array}{l} V_{Ss}^2 = \varnothing \hspace{7pt} \text{si } x_... ...tie, int \rangle \bigr\} \hspace{7pt} \text{sinon.} \\ \end{array} \right.$

B.3.4.3 Exemple d'adaptation bi-directionnelle

Enfin, voici un exemple de dispositif de type « adaptateur », dont les types s'adaptent en entrée et en sortie:

Soit un dispositif mutable $autocast$ comportant un slot d'entrée et un slot de sortie respectivement nommés $in$ et $out$, et ne comportant pas de paramètre. $in$ et $out$ sont déclencheurs et t-mutables, et possèdent comme supertype any. La fonction de mutation $\mu_{autocast}$ de ce dispositif est la suivante:

$\mu_{autocast}: \left\vert\begin{array}{l} \mathcal{P} \rightarrow \mathcal{P... ..., \langle out, sortie, x_2 \rangle \bigr\} \Bigr\rangle \end{array} \right.$