Objets
du langage
sur lesquels est basé le formalisme PEI
Objets
du langageLes programmes
Un programme P possède en entrée un n-uplet (I1,...,In)
de champs de données, et
un m-uplet (O1,...,Om) de champs de
données en sortie. Un système d'équations S lie les
champs en sortie aux champs en entrée, faisant éventuellement
appel à d'autres champs de données intermédiaires.
(O1,...,Om)
Chaque équation du système S exprime l'égalité des expressions des champs de données à droite et à gauche du signe =. Une expression de champs de données est soit un champ simple, soit une superposition de champs soit une suite d'opérations.
Les opérations consistent en l'application d'une fonction sur un champ de données. Leur notation est dérivée du lambda-calcul.
Le formalisme PEI distingue trois sorte d'opérations :
,
et son inverse, la réduction géométrique, notée
;
,, et son inverse,
la réduction fonctionnelle, non utilisée.Le changement de base consiste à placer un ensemble de valeurs
dans un nouveau référentiel. On obtient ainsi un nouveau
champ de données, équivalent au premier.
Cette opération modifie le placement des valeurs dans le référentiel. Elle permet, par exemple, d'exprimer les communications dans une machine parallèle. Cette opération n'est pas nécessairement injective, ce qui permet d'exprimer des opérations de diffusion.
L'inverse de l'opération de routage, appelée réduction
géométrique, s'applique à un champ de donnée
X par une fonction g en plaçant en tout point de coordonnées
z, une séquence des valeurs de X situées en tous les points
y définis sur le domaine de g, tels que g(y)=z.
Cette opération est dite inverse du routage car, quand la fonction
est bijective, la réduction est identique au routage défini
par la fonction inverse.
Cette opération permet de changer les valeurs d'un champ de données en appliquant à chacune le même calcul.
SémantiqueLa définition du champ de
données X = (v : 
)
permet de définir la sémantique de l'application de chacune
des trois opérations.
Soit f une fonction dans un ensemble de valeurs W, telle
que img(v) soit inclus dans dom(f), l'opération
fonctionnelle Y = f X
définit Y comme (f o v : ).
Opération de routage
Soit g une fonction de Zn dans dom(v) telle
que dom(g) soit inclus dans dom(),
l'opération de routage Y = X
g définit Y comme étant (v o g : ).
Opération de changement de base
Soit h une bijection d'une partie de Zn dans Zp,
le changement de base Y = h :: X définit Y
comme étant (v o h-1 :
o h-1), si dom(v) est inclus dans dom(h).
Deux champs de données X1 = (v1 : 1)
et X2 = (v2 : 2)
peuvent être superposés si 1|dom(2)
= 2 ou 2|dom(1)
= 1. La sémantique
de (X1 /&/ X2) est alors (v : )
tel que :
= 1
si dom(2)
est inclus dans dom(1)
= 2
si dom(1)
est inclus dans dom(2)Equation
Soient les champs X1,...,Xn et Y1,...,Yn
et les deux expressions de champs de données e(X1,...,Xn)
et e'(Y1,...,Yn), respectivement égales aux
paires de fonctions (vX : X)
et (vY:Y).
La sémantique de l'équation E : e(X1,...,Xn)
= e'(Y1,...,Yn) est alors :
X
= Y) ^ CSoient deux champs de données X et Y. X et
Y sont dits fortement équivalents si et seulement si il existe
une bijection h telle que Y = h :: X et dom(X)
est inclus dans dom(h).
Equivalence faible
Soient deux champs de données X et Y. X et
Y sont dits faiblement équivalents si et seulement si ils
représentent un même multi-ensemble de valeurs.
L'interprétation fonctionnelle permet de manipuler les objets
PEI indépendemment de tout placement de référence.
Pour un champ de donnée X = (v : ),
une interprétation fonctionnelle [[X]] est une fonction qui
en définit les valeur quel que soit le placement de référence.
Par définition, [[X]] = v o -1
On montre alors les propriétés suivantes :
-1
[[f X]] = f o [[X]]
[[X g]] = [[X]] o
o g o -1
