Sujet : compilation d'un langage de programmation parallèle type machine chimique

Encadrant

Objectif

Le TER consiste à écrire un compilateur pour un langage de programmation assez rudimentaire 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.

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 (plusieurs occurences d'un même terme sont possibles).

Un terme s'écrit sous la forme rel[arg₁, arg₂,..., arg_n], où rel et arg_i, 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 c₁ c₂ ... c_n
  if t
then a₁ a₂ ... a_m

où :

chaque c_i est un filtre, i.e. un terme de la forme rel[arg₁, arg₂,..., arg_p], où rel et arg_k, 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 c_i. Si le test est toujours vrai, la clause if t peut être omise.
chaque a_j est un filtre étendu, i.e. un terme de la forme : rel[arg₁, arg₂,..., arg_q] où rel et arg_k, 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 c_i. 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 c₁ c₂ ... c_n
  if t
then a₁ a₂ ... a_m

Une telle règle est dite déclenchable si toutes les conditions suivantes sont satisfaites :

chaque filtre c_i 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(c_i)
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(c_i) qui était apparié avec un filtre c_i.
ajouter à la mémoire tout terme s(a_j).

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 leurs supports sont disjoints. 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 nom 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]