(These.cwk)

(These.cwk)

-

Documents
52 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Chapitre 5JuniorLes SugarCubes ont donné naissance à d’autres implémentations de l’ Approche Réactive au-dessus de Java. Certaines de ces implémentations cherchent à améliorer les capacités de traitement des systèmes réactifs ainsi créés, gérant un grand nombre (plusieurs milliers) de composants parallèles, en particulier, lorsque ces composants communiquent entre eux en utilisant un grand nombre (plusieurs centaines) d’événements diffusés différents. Cependant, la complexité relative de ces implémentations nous a poussés à développer un certain nombre d’outils pour les étudier dans un cadre formel. Ce chapitre présente l’effort de formalisation qui a été mené pour donner une sémantique précise aux principales primitives de l’ Approche Réactive au-dessus de Java. Cette sémantique formalisée par un ensemble de règles de réécriture, constitue une référence, nous permettant d’analyser ces différentes implémentations.Afin de mener à bien cette étude formelle, nous avons dégagé un noyau de primitives caractéristiques de l’Approche Réactive. Cet ensemble de primitives constitue un nouveau formalisme, appelé Junior. Ce chapitre reprend et étend un rapport de recherche [BHS1]. La création de ce nouveau formalisme, directement inspiré des SugarCubes, a pour but de réduire le nombre de primitives à analyser et de former un socle commun à l’ensemble des implémentations de l’ Approche Réactive au-dessus de Java. Junior reprend donc les principes qui ont servi de base ...

Sujets

Informations

Publié par
Nombre de visites sur la page 33
Langue Français
Signaler un problème

Chapitre 5
Junior
Les SugarCubes ont donné naissance à d’autres implémentations de l’ Approche Réactive au-dessus de
Java. Certaines de ces implémentations cherchent à améliorer les capacités de traitement des systèmes
réactifs ainsi créés, gérant un grand nombre (plusieurs milliers) de composants parallèles, en particulier,
lorsque ces composants communiquent entre eux en utilisant un grand nombre (plusieurs centaines)
d’événements diffusés différents. Cependant, la complexité relative de ces implémentations nous a
poussés à développer un certain nombre d’outils pour les étudier dans un cadre formel. Ce chapitre
présente l’effort de formalisation qui a été mené pour donner une sémantique précise aux principales
primitives de l’ Approche Réactive au-dessus de Java. Cette sémantique formalisée par un ensemble de
règles de réécriture, constitue une référence, nous permettant d’analyser ces différentes implémentations.
Afin de mener à bien cette étude formelle, nous avons dégagé un noyau de primitives caractéristiques
de l’Approche Réactive. Cet ensemble de primitives constitue un nouveau formalisme, appelé Junior. Ce
chapitre reprend et étend un rapport de recherche [BHS1]. La création de ce nouveau formalisme,
directement inspiré des SugarCubes, a pour but de réduire le nombre de primitives à analyser et de former
un socle commun à l’ensemble des implémentations de l’ Approche Réactive au-dessus de Java. Junior
reprend donc les principes qui ont servi de base au développement de la première version des
SugarCubes. Ainsi, les deux formalismes sont très proches. En particulier, Junior offre un style de
programmation impératif où les primitives sont pour la plupart similaires à celles des SugarCubes. Cet
ensemble relativement réduit d’opérateurs réactifs nous a permis de proposer un système de règles de
sémantique formelle assez simple exprimé sous la forme de règles de sémantique opérationnelle
structurelle (SOS).
Nous allons présenter les motivations qui ont présidé à la définition du noyau Junior. Puis, nous
posons la définition de ce formalisme. Nous décrivons alors la sémantique des primitives réactives de ce
noyau sous la forme de règles de réécriture en dégageant un premier formalisme de référence que nous
appelons REWRITE. Nous discutons des problèmes d’efficacité soulevés par une implémentation directe
de ce formalisme. Ceci nous permet d’introduire un second formalisme appelé REPLACE, dont
l’implémentation directe s’avère plus efficace. Enfin, nous présentons les différentes implémentations que
nous avons réalisées, chacune de ces implémentations représentant une étape intermédiaire entre
l’idirecte de la sémantique de référence relativement peu efficace et l’implémentation la
plus efficace, appelée Simple et réalisée par L. Hazard de FT R&D.
5.1 Motivations
L’origine du développement du noyau Junior est à rechercher dans les limitations décrites au
chapitre 3, révélées par la première implémentation des SugarCubes. En particulier, le développement de
Junior vise à proposer une sémantique de référence de chaque primitive, afin d’analyser des
implémentations plus efficaces de l’ Approche Réactive. On peut donc ordonner les motivations à l’origine 102 Chapitre 5 : Junior
de Junior autour de 4 grands axes :
• Approche sémantique. Les travaux autour de Junior ont été menés afin de donner une
sémantique formelle à l’ Approche Réactive au-dessus de Java. Il s’agit plus précisément de définir
un ensemble de règles décrivant formellement les opérateurs primitifs. Ces règles et
l’implémentation qui en découle directement constituent une référence qui nous permet de discuter
la validité des autres formalismes et/ou implémentations.
• Gestion efficace des événements. Junior a également pour objectif d’analyser des
implémentations efficaces de la gestion des événements diffusés instantanément. Pour cela Junior
définit à partir de sa sémantique de référence, un certain nombre d’étapes intermédiaires permettant
d’augmenter la compréhension et le “ degré de confiance” que l’on peut avoir dans des
implémentations optimisées du réactif (en général très éloignées d’une implémentation directe des
règles). La formalisation de ces techniques d’implémentation efficaces n’est pas évidente et Junior
propose donc une évolution progressive vers les techniques les plus efficaces en essayant de
maximiser à chaque étape la compréhension que l’on peut avoir de ces implémentations.
• Étude du parallélisme réactif. L’implémentation Simple réalisée par L. Hazard s’avère
particulièrement efficace en termes de traitement d’un grand nombre de composants parallèles
communiquant par un grand nombre d’événements diffusés différents. Cependant, cette
implémentation que nous décrivons en 5.4.3, se révèle incompatible avec l’opérateur Merge utilisé
dans les SugarCubes. En fait, l’opérateur de parallélisme implémenté par Simple adopte un choix
différent de celui d’un opérateur Merge. Junior se propose d’unifier ces choix différents en
définissant un nouvel opérate ur Par.
• Prise en compte du parallélisme physique. L’approche sémantique a également pour but de
formaliser et d’unifier le parallélisme physique d’une architecture réactive distribuée et le
parallélisme réactif exprimé dans un programme. Le modèle des machines réactives
distribuées[BHS2], développé autour des SugarCubes, décrit des systèmes réactifs physiquement
distribués au moyen de machines réactives synchronisées à travers le réseau. Si le parallélisme au
sein d’une machine ne pose pas de problème particulier et peut être décrit simplement et sans
ambiguïtés à partir de l’opérateur Merge, il n’en va pas de même lorsqu’il s’agit de donner une
signification au parallélisme entre deux composants exécutés sur deux machines différentes : ce
parallélisme physique, non déterministe par nature n’étant, à l’évidence, pas compatible avec le
déterminisme de l’opérate ur Merge. C ette expérience est décrite au chapitre 7.
5.2 Définition
À l’image des SugarCubes dont il hérite ses principales caractéristiques, Junior est un ensemble de
classes Java permettant d’implémenter des systèmes réactifs. Les classes Junior définissent des
primitives réactives permettant d’écrire un programme réactif dans un style impératif “ à la” SugarCubes.
Ces instructions réactives sont exécutées par des machines d’exécution. Les machines d’exécution sont
des objets capables d’accepter dynamiquement de nouveaux comportements en parallèle.
Cependant, Junior se démarque des SugarCubes par un certain nombre de points :
• Utilisation de l’opérateur primitif de parallélisme Par au lieu de Merge. Junior introduit
l’opérateur non déterministe Par afin de prendre en compte une variété plus grande de parallélisme
primitif : (i)choix déterministes différents, (ii)choix non déterministe, (iii)parallélisme physique …
L’opérateur Merge se présente alors comme un descendant particulier de l’opérateur Par , dans
lequel le choix non déterministe de l’ordre d’exécution des branches est remplacé par un ordre
déterministe figé.
• Gel d’instruction. Junior propose un mécanisme de gel d’instruction différent de celui des
SugarCubes, en définissant une primitive avec une sémantique formelle ne nécessitant pas d’étape Chapitre 5 : Junior 103
supplémentaire inter-instants pour se réaliser. Ce mécanisme remplit néanmoins une fonction
similaire et peut donc être utilisé pour implémenter des mécanismes de migration de code à travers
le réseau sur des machines distantes ou de persistance par sauvegarde sur un support de stockage de
l’état d’avancement d’un programme.
• Absence des opérateurs Close/Suspend. Les opérateurs Close/Suspend hérités du langage
Reactive-C permettent un programmation fine de l’interleaving du parallélisme en contrôlant le
déroulement des micro-étapes d’exécution. Ces primitives de bas niveau peuvent s’avérer utiles
pour implémenter des stratégies d’exécution ou de communication différentes. Cependant,
l’algorithme standard de résolution des instants en SugarCubes v1 décrit au chapitre 2 s’avère en
fait incompatible avec l’utilisation de Close et de Suspend, en particulier avec le mécanisme de
communication par événements diffusés instantanément déjà présent dans les SugarCubes. Junior
interdit donc l’utilisation de ces primitives afin d’éviter les problèmes qu’elles soulèvent.
• Interfaçage élémentaire avec Java. La conception de Junior permet de prendre en compte un
interfaçage élémentaire avec les objets Java. Cet interfaçage hérité des solutions proposées par les
SugarCubes, est moins élaboré (pas de mécanisme de notification, …), mais plus ouvert (interface
moins contraignante). Il permet très simplement d’associer un objet Java par défaut à un
programme réactif à l’aide de la primitive Link et définit les interfaces permettant de décrire les
expressions et les actions atomiques externes, qui en Junior comme en SugarCubes sont
exprimées en Java. Cette interface avec Java semble constituer un minimum commun aux
différentes solutions possibles permettant l’interopérabilité d’objets et de comportements réactifs.
• Ressource d’exécution. Junior propose de séparer clairement la notion de ressource d’exécution
d’un programme réactif, symbolisée par la machine réactive, de la notion d’instruction réactive,
cela, afin de simplifier la tâche de formalisation et éviter la confusion suscitée par le fait qu’une
machine soit elle même instruction en SugarCubes.
• Événements valués. Enfin, Junior propose une gestion des événements valués différente de celle
proposée dans le modèle des Cubes. En Junior, les occurrences d’événements sont collectées au
cours d’un instant et sont rendues disponibles à l’instant suivant. Cependant, une liste des
occurrences au cours d’un instant reste accessible dans l’environnement permettant d’envisager le
développement d’une primitive du style des Callbacks-Listener des SugarCubes.
Junior définit une interface de programmation pour l’utilisateur à l’image de ce qui a été présenté en
SugarCubes, permettant de masquer les différentes implémentations qui ont été expérimentées. Junior
découpe la liste des primitives mises à la disposition de l’utilisateur en deux classes : (i) la classe JrBase,
équivalente à la classe SC des SugarCubes, propose l’ensemble des primitives réactives implémentées par
Junior ; (ii) l’interface Jr qui étend la classe JrBase fournit un ensemble de facilités syntaxiques
simplifiant l’écriture de certains programmes réactifs.
Nous présentons maintenant les principales primitives qui ont été retenues en Junior. Ces primitives
sont données à partir de l’interface JrBase de l’ API-utilisateur de Junior[BHS3] :
• Jr.Nothing() : ne fait rien et termine immédiatement.
• Jr.Stop() : ma rque la fin de l’instant dans une séquence.
• Jr.Atom(a) : exécute une action atomique externe a (qui implémente l’interface JavaAction)
implémentée en Java et termine immédiatement.
• Jr.Seq(first,second) : met en séquence deux termes first et second. Lorsque first termine
on passe immédiatement en séquence au terme second.
• Jr.Loop(t) : exprime une boucle infinie. Le terme t est immédiatement redémarré dès qu’il
termine.104 Chapitre 5 : Junior
• Jr.Repeat(IntWrap,t) : exprime une boucle finie exécutant un certain nombre d’itérations du
terme t. Le nombre d’itérations à réaliser est déterminé lors de la première activation de
l’instruction Repeat par l’évaluation de l’expression externe IntWrap (qui implémente l’interface
IntegerWrapper) e xprimée en Java qui retourne une valeur entière.
• Jr.Par(left,right) : met en parallèle deux termes left et right. Contrairement à l’opérateur
Merge, l’opérateur Par ne fixe pas d’ordre particulier dans l’exécution des deux termes. La seule
garantie est que les deux branches seront exécutées à chaque instant. Par stoppe pour l’instant
courant lorsque ses deux branches ont marqué la fin d’instant. La construction parallèle termine
quand les deux branches terminent.
• Jr.Generate(IdWrap,ObjWrap) : génère un événement dans l’environnement d’exécution.
L’événement est identifié par un identificateur particulier déterminé à runtime par l’évaluation de
l’expression IdWrap (qui implémente l’interface IdentifierWrapper) qui retourne un
identificateur. La valeur associé à la génération d’événement est déterminée à runtime par
l’évaluation de l’expression ObjWrap (qui implémente linterface ObjectWrapper) qui retourne un
objet en guise de valeur.
• Jr.Await(C) : attend la satisfaction de la configuration C au cours d’un instant pour terminer et
permettre le passage en séquence.
• Jr.When(C,then,else) : te ste au cours d’un instant la configuration événementielle C. Si elle est
satisfaite, la branche then e st exécutée, sinon la branche else e st exécutée. L’exécution de l’une ou
l’autre des deux branches est instantanée si la configuration peut être évaluée avant la fin d’instant,
sinon l’exécution est repoussée à l’instant suivant.
• Jr.Until(C,body,handler) : réalise la préemption du corps body lorsque la configuration de
préemption C est satisfaite. C’est une préemption faible qui laisse le corps s’exécuter à l’instant où
C est satisfaite. Le handler est exécuté si la préemption est effective. Son exécution est immédiate
si la configuration est satisfaite avant la fin de l’instant et que le corps est stoppé, sinon le handler
est exécuté à l’instant suivant.
• Jr.Control(IdWrap,body) : contrôle l’exécution de l’instruction body en fonction de la
présence d’un événement de contrôle dans l’environnement d’exécution. L’identificateur de
l’événement de contrôle est déterminé à runtime lors de la première activation de l’instruction par
l’évaluation atomique de l’expression externe IdWrap (qui implémente l’interface
IdentifierWrapper) qui retourne un identificateur d’événement dans l’environnement
d’exécution. Le corps n’est exécuté pour un instant que lorsque l’événement de contrôle est présent.
• Jr.Local(id,t) : déclare un événement local identifié par l’identificateur id. La portée de
l’événement local est limitée au terme t.
• Jr.If(CondWrap,then,else) : choisit d’exécuter la branche then ou la branche else en
fonction du résultat de l’évaluation de la condition booléenne. L’évaluation de l’expression
booléenne externe CondWrap (qui implémente l’interface BooleanWrapper) exprimée en Java
s’effectue de façon atomique à la première activation du If. Si la condition est vraie la branche
then e st exécutée, sinon c’est la branche else.
• Jr.Link(ObjWrap,body) : associe un objet Java implicite au comportement body. L’objet est
renvoyé à runtime par l’évaluation de l’expression atomique externe ObjWrap (qui implémente
l’interface ObjectWrapper) qui est exprimée en Java et renvoie l’objet qui sera désormais associé
au c orps du Link.
• Jr.Freezable(id,body) : permet de geler une instruction body si l’événement de gel identifié
par id e st présent. À l’instant où l’événement de gel est présent, le corps est quand même exécuté, à a
¢
¾
˛
¢
¾
a

a
Chapitre 5 : Junior 105
la manière de la préemption faible. Le corps gelé est ajouté dans la table des instructions gelées
dans l’environnement, en parallèle avec les autres instructions gelées par le même événement s’il y
en a.
Les configurations événementielles sont construites à partir des configurations élémentaires suivantes :
Jr.Presence(IdWrap), Jr.Not(C), Jr.Or(C) , Jr.And(C).
5.3 Sémantique
Junior formalise la sémantique des opérateurs de l’ Approche Réactive à travers un ensemble de règles
SOS très simple. Ce formalisme est tiré d’un article de Plotkin [Pl]. Pour ce faire, nous opérons un certain
nombre de simplifications par rapport à l’API complète de Junior :
• Nous ne considérons que la sémantique des opérateurs réactifs. Ainsi tous les mécanismes
d’interface avec le monde extérieur aux seules instructions réactives ne sont pas considérés. Par
exemple, les méthodes add ou generate d’une machine d’exécution qui ne sont pas utilisées en tant
qu’instructions réactives ne sont pas formalisées.
• L’interfaçage avec le langage Java n’est pas considéré ici. En particulier, les instructions Link,
If, etc. et les mécanismes d’évaluation à runtime ne sont pas formalisés. En effet, l’environnement
Java d’un programme réactif est défini indépendamment de la notion d’instant. Il s’agit d’objets
Java définis par ailleurs dans un programme applicatif standard. De plus, le non déterminisme (en
termes d’effet de bord), apporté par l’opérateur Par de Junior, implique que la prise en compte des
effets de bords Java dans ces conditions n’apporte aucune information pertinente et contribue à
alourdir les notions.
• Les facilités syntaxiques offertes par l’API Junior (classe Jr), exprimant des simplifications
dans l’utilisation de certains opérateurs ne sont pas considérées (par exemple, l’opérateur Until
sans handler). En effet, ce type d’opérateurs s’exprime directement par des macro-instructions où
les branches absentes sont remplacées par une instruction Nothing. Leur sémantique peut donc être
directement déduite. Il en va de même pour les simplifications permettant l’utilisation de chaînes de
caractères directement comme identificateurs d'événements etc.
• Les notions d’événements valués et leur génération ne sont pas considérées. On ne traite ici que
le cas des événements purs.
Nous allons maintenant proposer un système de règles de sémantique formelle de référence, appelé
REWRITE, exprimé sous la forme de règles de réécritures.
5.3.1 Les règles SOS
Dans le cadre de l’ Approche Réactive, nous donnons un système de règles décrivant le comportement
de chaque primitive en termes de micro-étapes (micro-step). On parlera donc de sémantique micro-step.
Le format général d’une règle de réécriture est le suivant :
Pour chaque activation d’un terme t on a :
t, E t , E SUSP, STOP,TERM{ }
Cette règle signifie : un terme t est exécuté dans un environnement E. Il se réécrit en un terme t’ dans
un environnement E’ et renvoie un statut d’exécution , ayant l’une des trois valeurs suivantes :
• SUSP : indique que la réaction du terme n’est pas terminée pour l’instant courant, le terme t se ¢

¾
¾
¢
a
106 Chapitre 5 : Junior
suspend momentanément et devra être réactivé au cours du même instant.
• STOP : indique la fin de la réaction du terme pour l’instant courant. L’instant peut terminer si les
autres branches en parallèle ont terminé; le terme t reprendra son exécution lors de sa prochaine
réaction, là où il s’est arrêté c’est à dire t’.
• TERM : indique simplement que le terme a définitivement achevé son exécution et qu’il ne
réagira plus à d’autres activations (il n’y a plus rien à exécuter).
Le terme t’ représente ce qu’il reste à exécuter de l’instruction de départ après avoir exécuté la micro-
étape. Si la réaction termine (retourne STOP) avec cette réécriture, le terme t’ correspond au résidu de
l’instruction à la fin de l’instant. Ce terme réécrit coïncide donc avec le résultat du calcul de résidu mis en
œuvre lors d’un gel d’instruction (décrit au chapitre 3).
Certains opérateurs peuvent voir leur exécution conditionnée par des prédicats ou des réécritures de
sous-termes. On utilise alors des règles de réécriture conditionnelles de la forme :
...
t, E t , E
Les prédicats et réécritures de sous-termes préalables sont placés au numérateur tandis que la règle de
réécriture du terme sera placée au dénominateur.
Pour décrire la sémantique des primitives Junior suivant ce schéma de règles, on commence par définir
une syntaxe abstraite des primitives Junior basée sur la syntaxe concrète que l’on utilise à travers l’ API-
utilisateur.
5.3.2 Syntaxe
Les règles de sémantiques que nous présentons ici utilisent une syntaxe abstraite de Junior plutôt que
la syntaxe concrète. Cette syntaxe abstraite nous permet d’introduire ainsi un codage de certains éléments
de l’état interne d’une instruction qui évoluent au gré de son exécution, souvent à chaque micro-étape. Il
s’agit souvent de la mémoire que l’instruction garde de ses activations antérieures afin de sélectionner la
règle correspondant à une nouvelle activation.
Syntaxe abstraite
Dans cette syntaxe, a représente une action atomique, t, u et v sont des termes, n est une valeur entière,
S est un événement et C est une configuration événementielle. Nous donnons maintenant la syntaxe
abstraite de chaque primitive Junior.
Un certain nombre de primitives ont une syntaxe abstraite qui coïncide avec leur syntaxe concrète :
- Nothing
- Stop
- Atom(a)
- Seq(t,u)
- Loop(t)
- Repeat(n,t)
- Generate(S)
- Await(C)
- When(C,t,u)
- Control(S,t)b
a
b
Chapitre 5 : Junior 107
L’opérateur de parallélisme Par nécessite de mémoriser l’état de ses deux branches à chaque activation
(a, représente le statut de t et , le statut de u) :
- Par (t,u),
La déclaration locale d’événement nécessite de mémoriser l’état de l’événement local; pour cela on
introduit deux formes particulières :
- Local+(S,t)
- Local-(S,t)
Le signe + signifie que l’événement local est présent et le signe - signifie qu’il ne l’est pas.
L’opérateur Until ajoute une forme particulière Until* dans la syntaxe abstraite. Cette forme
particulière de l’opérateur est utilisée lorsque, au cours d’un instant, le corps à préempter a terminé son
exécution pour la réaction courante et que la configuration de préemption n’est toujours pas fixée.
- Until(C,t,u)
- Until*(C,t,u)
L’opérateur Freezable qui est très similaire à l’opérateur Until introduit lui aussi une forme particulière
Freezable* :
- Freezable(S,t)
- Freezable*(S,t)
On définit enfin deux instructions particulières qui permettent de formaliser les opérations d’une
machine d’exécution réactive :
- Instant(t)
Instant permet de clôturer l’exécution d’une réaction en exécutant autant de micro-étapes que
nécessaire pour terminer un instant.
La machine d’exécution est représentée par la forme :
- ExecContext(t)
Traduction de la syntaxe concrète vers la syntaxe abstraite
On définit une fonction tr permettant de traduire un terme exprimé dans la syntaxe concrète en un terme
exprimé dans la syntaxe abstraite. Cette fonction est définie récursivement comme suit :
• tr(Jr.Nothing()) = Nothing
• tr(Jr.Stop()) = Stop
• tr(Jr.Atom(a)) = Atom(a)
• tr(Jr.Seq(t,u)) = Seq(tr(t),tr(u))
• tr(Jr.Loop(t)) = Loop(tr(t))
• tr(Jr.Repeat(n,t)) = Repeat(n,tr(t))
• tr(Jr.Par(t,u)) = Par (tr(t),tr(u))SUSP,SUSP
• tr(Jr.Generate(S)) = Generate(S)
• tr(Jr.Await(C)) = Await(C)
• tr(Jr.When(C,t,u)) = When(C,tr(t),tr(u))
• tr(Jr.Until(C,t,u)) = Until(C,tr(t),tr(u))
• tr(Jr.Control(S,t)) = Control(S,tr(t))
• tr(Jr.Local(S,t)) = Local-(¾
¾
˛
˛
¾
¾
¾

¾

108 Chapitre 5 : Junior
• tr(Jr.Freezable(S,t)) = Freezable(S,tr(t))
• tr(Jr.Machine(t)) = ExecContext(tr(t))
Remarques :
• L’opérateur Par est initialisé avec SUSP comme valeur du statut mémorisant l’état de chaque
branche.
• L’opérateur Local est initialisé avec l’événement absent.
5.3.3 Définition de l’environnement d’exécution
L’environnement d’exécution des instructions réactives, symbolisé par la lettre E dans les règles de
réécriture, est constitué d’un certain nombre de composants :
• Un ensemble d’événements présents au cours d’un instant.
• Une valeur booléenne eoi(E) qui indique si la fin d’instant a été décidée par la machine
d’exécution ( true) ou non ( false).
• Une valeur booléenne move(E) qui est positionnée à vrai lorsqu’un changement dans
l’environnement d’exécution intervient au cours d’une activation du programme.
• Une table utilisée pour stocker les instructions gelées au cours d’un instant.
Ainsi, un événement S qui est présent dans E s’écrit : S E. L’ajout de l’événement S dans
l’environnement E est noté E + S tandis que E - S représente l’environnement E auquel on a retiré
l’événement S. La notation E[move = b] représente l’environnement E dans lequel le drapeau move a été
affecté avec la valeur b. De la même manière, la notation E[eoi = b] indique que le drapeau eoi est affecté
avec la valeur b.
La notation E / F[S] représente un environnement égal à E + S si S F et E - S sinon. Cette notation
signifie que l’environnement E / F[S] est identique à l’environnement E sauf dans le cas du signal S dont
le statut est déterminé par son statut dans l’environnement F. Ces notations sont utilisées dans la définition
des événements locaux (cf. section 5.3.5.).
Enfin, la notation E{S = t} associe l’instruction gelée t à l’événement S et la notation E{S} représente
l’instruction gelée associée à S.
5.3.4 Primitives de base
Nothing
L’instruction Nothing ne fait rien et termine instantanément.
TERMNothing, E Nothing, E
Stop
L’instruction Stop arrête l’exécution d’une séquence pour l’instant courant. À l’instant suivant il ne
reste rien à faire.
STOPStop, E Nothing, E¾
¾
¢

¾
¾
¾
¾
¾
a
a
a

¢
¢
¢
¾
¢

¢
¢
¾
a
¾
¾

¢
¾
a
¢
a
¢
¾
¢
¢
¾
¾

¾
¾
¢
¢
¾
¢
¾
¢
a
¾
¢

¾
¾

b
¢
a
¾
d
¾
b
a
a
a
d
¢
b
¢
a

g
¢
b
¢
a

¢
¢
¢
¢
¾
¾
¾
¾

¢
¾

¢

¢
¢
¾


¾
¢
Chapitre 5 : Junior 109
Les actions atomiques
Les actions atomiques terminent immédiatement en une seule micro-étape après avoir exécuté une
action externe a. Celle-ci est exécutée de façon atomique (aucune interférence concurrente ne peut venir
perturber l’exécution de a).
TERMAtom(a), E Nothing, E
On ne rend pas compte ici de l’effet de bord produit par l’action a comme nous l’avons précisé plus
haut.
L’opérateur de séquence binaire
La séquence est un opérateur défini par deux règles. Le choix de l’une ou l’autre de ces règles est dicté
par le statut d’exécution de la première branche :
Si la première branche ne termine pas alors on applique la règle :
t, E t , E TERM
Seq(t,u), E Seq(t ,u), E
Si la première branche termine (retourne TERM), alors la seconde branche est immédiatement activée :
TERM
t, E t , E u, E u , E
Seq(t,u), E u , E
L’opérateur de parallélisme
Si les deux branches de l’opérateur Par sont suspendues (ce qui est la situation initiale), alors on
exécute au choix (non déterministe) l’une des 4 règles suivantes.
Pour les deux premières, une seule branche est activée et on positionne le drapeau move à true pour
indiquer que la décision de fin d’instant doit être repoussée après la micro-réaction suivante afin de donner
une chance à la branche qui n’a pas été exécutée de l’être ultérieurement au cours du même instant :
t, E t , E
SUSP
Par (t,u), E Par (t ,u), E [move = true]
SUSP,SUSP ,SUSP
u, E u , E
SUSP
Par (t,u), E Par (t,u ), E [move = true]
SUSP,SUSP SUSP,
Cependant il est également possible que les deux branches soient exécutées au cours de la même micro-
étape et ce dans un ordre quelconque. Ceci est traduit par les deux règles suivantes :
t, E t , E u, E u , E
( , )Par (t,u), E Par (t ,u ), E
SUSP,SUSP ( , ), ( , )1 2¾
b

b
d
d
a
a
b
b
b
a
¢
¢
¢
¢
¢
¾
¢

g
¾
g

a
¢
a
¢
b
¾
¢

d
¾
a
a
¾
a

a

¢
a
¢
a
¾
b
¾
a

a
¾
b

b
¢
¢
¢
¢
¾


¾
¾
¢
a
¢
b
b
a
g
d
b
b
¢
a
¾
b
¾
a
¢
g
¾
a
¾
b
b
d
d
a
b
b
a
d
d
a
a
b
b
¾
d

b
¾
d
¢
b
¢
a
¢
a
¾
a

¾
¾
110 Chapitre 5 : Junior
u, E u , E t, E t , E
( , )Par (t,u), E Par (t ,u ), E
SUSP,SUSP ( , ), ( , )1 2
Notations :
• Le statut correspondant à la notation ( , ) correspond aux valeurs issues du tableau à double
entrées suivant :
\ TERM STOP SUSP
TERM TERM STOP SUSP
STOP STOP STOP SUSP
SUSP SUSP SUSP SUSP
Tableau 2 :Combinaison des statuts d’exécution par un opérateur Par.
• ( , ) est égal à SUSP si est égal à STOP et est égal à STOP ou TERM, sinon ( , )
1 1
est égal à .
• ( , ) est égal à SUSP si est égal à STOP et est égal à STOP ou TERM, sinon ( , )
2 2
est égal à .
Remarque : La première de ces deux règles faisant réagir les deux branches au cours de la même
micro-étape correspond à la sémantique de l’opérateur Merge des SugarCubes qui, à chaque activation,
fait réagir ses deux branches toujours dans le même ordre (branche 1 puis branche 2 -gauche puis droite-).
On retrouve bien ici, la volonté de Junior d’unifier les différentes formes de parallélisme primitif au sein
du même opérateur.
Si une seule des deux branches est suspendue, alors l’opérateur Par se contente de l’activer.
t, E t , E SUSP
( , )Par (t,u), E Par (t ,u), E
SUSP, ( , ), ( , )1 2
u, E u , E SUSP
( , )Par (t,u), E Par (t,u ), E
,SUSP ( , ), ( , )1 2
L’instruction Loop
Une boucle exécute son corps et se réécrit en une séquence si son corps ne termine pas
immédiatement :
t, E t , E TERM
Loop(t), E Seq(t , Loop(t)), E
Lorsque le corps de la boucle termine immédiatement alors la boucle est immédiatement réactivée pour
la même micro-étape :