Sujet : un langage de programmation parallèle type
machine chimique
Encadrant
Phil. REITZ.
Objectif
Le TER consiste à écrire un interpréteur (voire
un compilateur) pour un langage de programmation parallèle assez
élémentaire permettant de contrôler une machine
abstraite parallèle
s'inspirant de la ChAM (Chemical Abstract Machine).
Le langage de programmation s'inspire quant à lui du langage Gamma.
La présentation de cette machine et du langage associé
est suivie de quelques exemples de programmes.
Définition de la machine abstraite et de son langage de
programmation
Description des états de la machine abstraite
A chaque instant t, l'état de la mémoire de la
machine est défini par un multi-ensemble de termes
(un multi-ensemble est une généralisation de la notion
d'ensemble : un même élément peut figurer en
plusieurs exemplaires dans un multi-ensemble, alors qu'il n'est
présent 0 ou 1 fois dans un ensemble classique ; la fonction
caractérisque d'un multi-ensemble discret est donc tout
simplement un histogramme).
Un terme s'écrit sous la forme rel[arg1,
arg2,..., argn] , où rel
et argi, quel que soit i, sont des
littéraux constants. Un littéral constant est au choix :
- un nombre
- un nom : c'est un identificateur commençant
nécessairement par une lettre minuscule, suivie par une
séquence éventuellement vide de lettres, chiffres ou
n'importe lequel des caractères suivants : blanc souligné
(_), apostrophe ('), point d'interrogation (?) ou d'exclamation (!).
L'entier n est appelé l'arité du terme.
Si n=0, le terme rel[] s'écrira
simplement rel.
Description d'un programme
Un programme pour cette machine est un ensemble de règles
de réaction, où une règle de
réaction s'écrit :
when c1 c2 ... cn
if t
then a1 a2 ... am
où :
- chaque ci est un filtre, i.e. un terme
de la forme rel[arg1, arg2,...,
argp], où rel et argk,
quel que soit k, sont des littéraux constants ou des variables
; une variable est un nom commençant nécessairement par
une lettre majuscule, ou se limitant simplement au caractère _
(blanc souligné).
- t est un test, i.e. une expression
booléenne quelconque ; toute variable présente dans le
test doit être présente dans au moins un filtre ci.
Si le test est toujours vrai, la clause if t
peut être omise.
- chaque aj est un filtre étendu,
i.e. un terme de la forme :
rel[arg1, arg2,...,
argq]
où rel et argk, quel que soit k,
sont des expressions de calcul comprenant des littéraux
constants, des variables ou des opérateurs ; toute variable
présente dans un filtre étendu doit être
présente dans un filtre ci.
Si aucun filtre étendu n'est spécifié, alors la
clause then peut être omise.
Sémantique d'un programme
Soit une règle de réaction de la forme :
when c1 c2 ... cn
if t
then a1 a2 ... am
Une telle règle est dite déclenchable si
toutes les conditions suivantes sont satisfaites :
- chaque filtre ci de la règle s'apparie
avec un terme Z en mémoire (notion d'unification
à la Prolog); un terme en mémoire ne peut s'apparier
qu'à un seul filtre à la fois. Si le filtre comporte des
variables, l'appariement doit être accompagné de la substitution
s correspondante, i.e. une fonction qui indique, pour chaque
variable du filtre, par quel littéral constant elle doit
être remplacée pour produire le terme apparié, i.e.
Z = s(ci)
. - l'évaluation du test s(t) est vraie
Le multi-ensemble des termes qui rendent une règle
déclenchable est appelé support de
déclenchement (plus simplement support) de la
règle.
Si une règle est déclenchable, la déclencher,
c'est :
- retirer de la mémoire tous les termes de son support, i.e.
tout terme s(ci) qui était apparié
avec un filtre ci.
- ajouter à la mémoire tout terme s(aj).
Exécuter un programme, c'est déclencher, de
façon non-déterministe, toute règle
déclenchable ; plusieurs règles peuvent être
déclenchées en parallèle si l'union de leurs
supports est incluse dans le multi-ensemble des termes en
mémoire. Si aucune règle n'est déclenchable, le
programme se termine.
Extensions utiles
Le langage de programmation, tel qu'il est spécifié
ci-dessus, suffit à décrire
n'importe quelle fonction calculable.
Néanmoins, certaines extensions au langage, bien
que n'apportant rien quant à la puissance de calcul, facilitent
l'écriture
de programmes.
Les deux extensions suivantes se révèlent très
utiles :
- le terme frozen joue un rôle
spécial
: lorsqu'un programme
se termine, et que ce terme n'est pas présent en mémoire,
alors il est rajouté
en mémoire (ce qui peut déclencher à nouveau des
règles).
- dans la clause when d'une
règle, si un
filtre est précédé du caractère !,
le terme qui lui sera éventuellement
apparié ne sera pas retiré
de la mémoire si la règle est déclenchée.
D'autres extensions peuvent être imaginées :
- définir des paquets de règles : chaque règle
est associée à un ou plusieurs paquets, chaque paquet
étant désigné par son nom. En cours
d'exécution,
seuls certains paquets sont actifs, les règles n'en faisant pas
partie étant
désactivées. Il doit donc exister des termes qui
s'interprètent comme des
signaux d'activation de paquets.
- les règles elles-mêmes sont des termes
présents en mémoire. Il doit donc
être possible, en cours d'exécution, d'effacer ou
d'ajouter des règles.
Bibliographie
G. Berry & G. Boudol : The Chemical Abstract Machine.
Theoretical Computer Science. Vol 96, N° 1, p217-248, avril
1992
(cham.ps).
J.P. Banâtre & D. Le Métayer : Gamma and
the chemical reaction model
: ten years after.
in Coordination programming : mechanisms, models and semantics,
IC Press, 1996
(gamma10.ps).
Annexe : exemples
Exemple 1 : maximum d'un multi-ensemble d'entiers
La mémoire contient au départ des entiers (termes
d'arité nulle). Lorsque le programme suivant s'arrête, la
mémoire ne contient qu'un seul entier : le plus grand de ceux
qui étaient présents au départ.
when X Y if X<=Y then Y
Exemple 2 : minimum et maximum d'un multi-ensemble d'entiers
La mémoire contient au départ des entiers (termes
d'arité nulle). Lorsque le programme suivant s'arrête, la
mémoire ne contient que deux termes :
- min[x], s'interprétant comme : le plus
petit entier est x
- max[y], s'interprétant comme : le plus
grand entier est y
when X then min[X] max[X]
when min[X] min[Y] if X<=Y then min[X]
when max[X] max[Y] if X<=Y then max[Y]
Exemple 3 : tri d'un tableau
La mémoire contient au départ des termes de la forme at[i,
v, t] signifiant : la valeur v est
stockée à l'index i du tableau t. Lorsque
le programme suivant s'arrête, le tableau T est
trié.
when at[I, X, T] at[J, Y, T]
if X<Y and J>I
then at[I, Y, T] at[J, X, T]
Exemple 4 : histogramme d'un multi-ensemble d'entiers
La mémoire contient au départ des entiers. Lorsque le
programme suivant s'arrête, la mémoire contient des termes
de la forme occ[k, n] s'interprétant
comme : l'entier k était présent n fois.
when X then occ[X, 1]
when occ[X, N] occ[X, M] then occ[X, N+M]