suivant: B. Aspects dynamiques d'une monter: A. Structure d'une configuration précédent: A.2 Les quatre briques Table des matières

Sous-sections

A.3 Les connexions

A.3.1 Contraintes sur les connexions

Tout ensemble de connexions doit obéir aux trois contraintes suivantes:

Couplage:

Une connexion appartenant à une configuration

peut relier soit:

Un slot de sortie appartenant à un dispositif de à un slot d'entrée appartenant à un dispositif de ;
Un slot de sortie appartenant à un dispositif de à un slot d'entrée externe appartenant à ;
Un slot de sortie externe appartenant à à un slot d'entrée appartenant à un dispositif de ;

En résumé, une connexion doit relier deux slots de sens opposés et être orientée du slot de sortie vers le slot d'entrée, et ne peut relier deux slots externes.

Unicité en entrée:

Il existe au plus une connexion comportant un élément entrée donné. Ceci implique notamment que les connexions multiples sur un slot d'entrée sont interdits, ainsi que les connexions redondantes.

Acyclisme:

Un ensemble de connexions ne doit pas générer de dépendances cycliques: pour toute configuration

, le graphe de dépendances ( $\rightarrow$ section A.3.5) de la décomposition totale ( $\rightarrow$ section A.4) de

doit être acyclique.

A.3.2 Types et sous-typage

Hormis les contraintes énumérés précédemment, toute connexion est autorisée indépendamment des types des slots. Cependant, notre modèle de connexion est typé et différencie les connexions compatibles des connexions incompatibles.

**Figure:** Exemple de graphe de types pour les slots.
$\begin{figure} \begin{center} \includegraphics[scale=0.8]{soustypes} \end{center} \end{figure}$

La figure A.2 représente le graphe de types que nous utilisons dans notre implémentation en Java, avec les relations de sous-typage. Les différents types de slots sont les int (nombres entiers), boolean (booléens), double (nombres flottants), string (chaînes de caractères), et object (objets). À cela s'ajoutent les types spéciaux any (qui représente tous les types possibles) et null (qui ne représente aucun type). Ce graphe, comportant notamment le type object, est adapté à un langage à objets tel que Java.

Notre modèle ne nécessite pas la définition explicite d'un graphe de types. Au lieu de cela, il suppose qu'il existe un graphe de types avec à son sommet le type any, et à sa base le type null, et définit sur ce graphe les relations et opérations suivantes:

$\bullet$ Nous dirons que est un sous-type de (relation notée $t_s \subseteq t$ ) ssi est successeur inclusif de dans le graphe, c'est-à-dire ssi ou est successeur direct ou indirect de . De même, nous nommerons union de plusieurs types leur premier prédécesseur inclusif commun dans le graphe, et intersection de plusieurs types leur premier successeur inclusif commun dans ce même graphe. Les opérations d'union et d'intersection seront respectivement notées $\bigcup(t_1, \dots, t_n)$ et $\bigcap(t_1, \dots, t_n)$ .

A.3.3 Attributs de connexions dérivés des slots

Nous nommons attribut dérivé un attribut d'un objet dont la valeur est fonction de celle des autres attributs de cet objet ou de ses objets accessibles (objets-fils ou objets référencés). Ils seront précédés d'un triangle $\blacktriangleright$ . Ces attributs n'apportent pas d'information supplémentaire mais peuvent néanmoins servir à introduire des définitions utiles. Nous verrons également que lorsque la valeur de certains attributs est fixée dans un objet, d'autres attributs initialement libres peuvent devenir des attributs dérivés.

Les connexions comportent des caractéristiques de compatibilité, ainsi que d'autres attributs dérivés dont les valeurs sont fonction de leurs slots d'entrée et de sortie. Nous décrivons ces attributs, résumés dans le tableau A.3.3, en introduisant de nouveaux termes ainsi que leurs définitions.


	`externe`		vrai/faux
	`compatibilité`		compatible/incompatible
	`compatibilitéStatique`		compatible/incompatible/mutable

$\blacktriangleright$ #1 :: Une connexion externe est une connexion reliant un slot de dispositif (slot pour lequel externe=faux) à un slot externe (slot pour lequel externe=vrai). Une connexion non externe, ou connexion de dispositifs est une connexion reliant deux slots de dispositifs. Une connexion ne peut relier deux slots externes.
$\blacktriangleright$ #1 :: Une connexion est dite compatible ssi le type de son slot de sortie est un sous-type de celui de son slot d'entrée. Dans le cas contraire, elle est incompatible.
$\blacktriangleright$ #1 :: Une connexion est dite statiquement compatible ssi le supertype de son slot de sortie est un sous-type de celui de son slot d'entrée, et que son slot d'entrée est ni s-mutable ni t-mutable. Une connexion est dite statiquement incompatible ssi le supertype de son slot de sortie n'est pas un sous-type de celui de son slot d'entrée, et que son slot de sortie est ni s-mutable ni t-mutable. Dans tous les autres cas, la connexion est dite mutable. Une connexion mutable est soit compatible soit incompatible, mais sa compatibilité peut changer suite à une mutation ( $\rightarrow$ annexe B). À l'inverse, une connexion statiquement compatible est toujours compatible, et une connexion statiquement incompatible est toujours incompatible.

La compatibilité de types n'entre pas en ligne de compte dans les contraintes de connexion vues précédemment car, comme nous le verrons dans l'annexe B, une connexion compatible peut très bien devenir incompatible au cours de l'édition et vice-versa. La compatibilité statique décrit cependant les évolutions possibles de cette compatibilité, et il est tout à fait possible (bien que nous ne le faisions pas) de refuser les connexions statiquement incompatibles.

A.3.4 Attributs de slots dérivés des connexions

De même que les slots induisent un certain nombre de propriétés sur les connexions, certaines propriétés caractérisent les slots en fonction des connexions existantes. Nous décrirons ces attributs dérivés tout en introduisant de nouveaux termes qui nous seront utiles dans les deux prochaines annexes. Ces attributs sont résumées dans le tableau A.3.4.


	`connexions`		Connexion [ ]
	`slotsConnectés`		Slot [ ]
	`connecté`		vrai/faux
	`typeConnecté`		(selon l'implémentation)

$\blacktriangleright$ #1 :: Les connexions d'un slot sont les connexions comportant en entrée ou en sortie. Pour un slot d'entrée, cet attribut comporte au plus un élément.
$\blacktriangleright$ #1 :: Les slots connectés à S sont les slots reliés à par des connexions. Pour un slot d'entrée, cet attribut comporte au plus un élément.
$\blacktriangleright$ #1 :: Un slot est dit connecté ssi il comporte au moins une connexion.
$\blacktriangleright$ #1 :: Le type connecté d'un slot de sortie est l'intersection des types de ses slots connectés, ou any s'il n'est pas connecté. Le type connecté d'un slot d'entrée est le type de son slot connecté, ou null s'il n'est pas connecté.

**Figure:** Exemples de connexions: le slot de sortie s comporte trois connexions c1, c2 et c3 qui le relient aux slots d'entrée e1, e2 et e3. Le slot d'entrée e comporte une connexion *c'1* qui le relie au slot de sortie s1. e ne peut comporter d'autre connexion.
$\begin{figure} \begin{center} \includegraphics[scale=0.5]{vocab_connexions3} \end{center} \end{figure}$

A.3.5 Graphe de dépendances

**Figure:** Graphe de dépendances d'un ensemble de connexions.
$\begin{figure} \begin{center} \includegraphics[scale=0.28]{graphe_dependances2} \end{center} \end{figure}$

Les connexions de dispositifs sont des arcs orientés reliant deux slots qui ont chacun un dispositif pour parent. Il est donc possible, à partir d'un ensemble de connexions de dispositifs, de construire un graphe orienté exprimant des dépendances entre les dispositifs (figure A.4). Ce graphe nous permet d'introduire les deux relations suivantes sur les dispositifs:

$\bullet$ Un dispositif $D_{1}$ est successeur direct d'un dispositif $D_{0}$ ssi il existe un arc $D_{0} \rightarrow D_{1}$ dans le graphe de dépendances.

$\bullet$ Un dispositif $D_{1}$ est successeur indirect d'un dispositif $D_{0}$ ssi il existe un chemin qui va de $D_{0}$ à $D_{1}$ dans le graphe de dépendances. Cette relation

A.3.6 Dispositifs composites

Un dispositif composite est entièrement défini par sa configuration fille. Hormis l'attribut parent, l'ensemble de ses attributs (précédés d'une flèche dans la liste ci-dessous) est fonction des attributs de cette configuration fille:

$\blacksquare$ #1 :: La configuration à laquelle appartient le dispositif, ou null.
$\blacksquare$ #1 :: La configuration d'entrée qui décrit le dispositif composite.
$\blacktriangleright$ #1 :: Le nom d'un dispositif composite est le nom de sa configuration fille.
$\blacktriangleright$ #1 :: Les slots d'un dispositif composite correspondent aux slots externes utilisés dans la configuration fille, dans l'ordre indiqué par leur attribut index. Chaque slot du dispositif composite hérite des attributs du slot externe qui lui est associé.
$\blacktriangleright$ #1 :: Un dispositif composite ne comporte pas de paramètre.
$\blacktriangleright$ #1 :: Cet attribut vaut vrai.
$\blacktriangleright$ #1 :: Cet attribut vaut faux.
$\blacktriangleright$ #1 :: Chacun de ces attributs vaut vrai ssi il est vrai pour au moins un dispositif dans la configuration fille.

A.3.7 Composition et décomposition

**Figure:** Deux types de connexions inter-niveaux équivalentes à la connexion $s \rightarrow e$ . À gauche, la connexion inter-niveaux *descendante* $(s \rightarrow e^\star , s_x \rightarrow e)$ . À droite, la connexion inter-niveaux *ascendante* $(s \rightarrow e_x, s^\star \rightarrow e)$ . Les slots intermédiaires permettent à la connexion $s \rightarrow e$ de remonter ou de redescendre d'un niveau dans l'arbre des configurations.
$\begin{figure} \begin{center} \includegraphics[scale=0.9]{compos_equiv} \end{center} \end{figure}$

Nous appellerons connexion inter-niveaux toute paire de connexions reliant deux slots par l'intermédiaire d'un slot externe et de son slot de dispositif composite associé. Si cette connexion passe par le slot du dispositif composite puis par le slot externe, nous sommes dans le cas d'une connexion inter-niveaux descendante; dans le cas contraire, il s'agit d'une connexion inter-niveaux ascendante (figure A.7). Dans les deux cas, la connexion inter-niveaux est équivalente du point de vue de l'exécution à une connexion directe entre le deux slots.

**Figure:** Exemple de composition et de décomposition d'une configuration d'entrée. Les dispositifs , et sont déplacés dans la configuration-fille $C^\star$ et remplacés par le dispositif composite $d^\star$ . Les connexions scindées telles que $s11 \rightarrow e3$ sont remplacées par des connexions inter-niveaux, tandis que les connexions internes telles que ( $s2 \rightarrow e41$ ) sont préservées (voir l'algorithme algo:composition). L'opération de décomposition supprime le dispositif composite et la configuration-fille, après avoir replacé les dispositifs-fils dans la configuration initiale et remplacé les connexions inter-niveaux par des connexions simples (voir l'algorithme algo:decomposition).
$\begin{figure} \begin{center} \includegraphics[scale=0.5]{décomposition} \end{center} \end{figure}$

Des opérations de composition et de décomposition permettent de construire des structurations alternatives de l'arbre des configurations. La figure A.8 montre un exemple de composition ajoutant un niveau de configuration. Les dispositifs , et sont regroupés au sein d'un dispositif composite, qui peut ensuite être aplati pour redonner la configuration initiale.

**Figure:** Formes factorisées de connexions inter-niveaux multiples sur un slot de sortie.
$\begin{figure} \begin{center} \includegraphics[scale=0.8]{compos_factorisation} \end{center} \end{figure}$

La composition d'un ensemble de dispositifs $\Delta$ dans une configuration s'obtient par l'algorithme A.1. L'opération inverse, consistant à décomposer un dispositif composite $d^\star$ dans s'obtient par l'algorithme A.1. Ces algorithmes emploient la factorisation des connexions multiples sur un slot de sortie (figure A.9).

Enfin, la décomposition totale d'une configuration , utilisée pour le calcul des dépendances cycliques, s'obtient en appliquant récursivement l'algorithme A.1 sur l'ensemble des dispositifs de la configuration .

$\begin{algorithm} % latex2html id marker 10251 \caption{\small Composition de... ...$e_x$. \end{itemize} \end{enumerate} \end{enumerate}\par \end{algorithm}$

$\begin{algorithm} % latex2html id marker 10255 \caption{\small Décomposition ... ...$\ et sa configuration-fille $C^\star$. \end{enumerate}\par \end{algorithm}$

A.3.8 Slots i-connectés

Il est utile d'introduire une définition alternative de la connexion, la i-connexion, qui ne prend en compte que les connexions effectives (éventuellement inter-niveaux) entre slots de dispositifs. Nous dirons ainsi qu'un slot de dispositif est i-connecté à un slot de dispositif si est relié à soit par une connexion, soit par une ou plusieurs connexions inter-niveaux successives.

Soit un slot appartenant à un dispositif dans une configuration . Soit la racine de l'arbre de configurations dont fait partie .

$\bullet$ Le slot est i-connecté à ssi est connecté à dans la décomposition totale de .

$\bullet$ L'ensemble des slots i-connectés à est l'ensemble des slots connectés à dans la décomposition totale de .

suivant: B. Aspects dynamiques d'une monter: A. Structure d'une configuration précédent: A.2 Les quatre briques Table des matières

Pierre Dragicevic 2005-07-22