Réconciliation par consensus des mises à jour des répliques partielles d'un document structuré.

AnnexeB

Quelques fonctions Haskell pour le

calcul des consensus

Dans cette annexe, nous décrivons quelques fonctions et types Haskell permettant de représenter des documents structurés et d'effectuer la fusion consensuelle de ces derniers. Afin de mieux appréhender les notions présentées ici, une connaissance du langage Haskell (que le lecteur ne trouvera pas ici) est requise. Nous sommes persuadés que les références suivantes seront d'excellents compagnons et/ou guides pour le lecteur désireux de découvrir et/ou d'en apprendre plus sur l'univers de la programmation fonctionnelle avec Haskell: [Has, GHC, HPHF99].

Représentation des grammaires et des vues

Une grammaire est constituée d'un ensemble de symboles et d'un ensemble de productions. Nous représentons une grammaire par le type Gram suivant:

1 data Gram prod symb = Gram {prods::[prod],

2 symbols::[symb],

3 lhs::prod -> symb,

4 rhs::prod -> [symb]}

La fonction lhs (resp. rhs) prend en argument une grammaire G et une production p de G puis retourne le symbole en partie gauche ( resp. la liste des symboles en partie droite) de p. À partir de ce type, on peut construire la grammaire Gexpl (chap 2 exemple 8) grâce au code Haskell suivant:

1 2 3 4	data Prod = P1 | P2 | P3 | P4 | P5 deriving (Eq, Show) data Symb = A | B | C deriving (Eq,	| P6 | Show)	P7 | Aomega		|	Bomega		|	Comega
5	gram :: Gram Prod Symb
6	gram = Gram lprod lsymb lhs_ rhs_
7	where
8	lprod = [P1, P2, P3, P4, P5,	P6, P7]
9	lsymb = [A, B, C]
10	lhs_ p = case p of
11	P1 -> A; P2 -> A; P3 ->	B; P4	-> B; P5	->	C;	P6	->	C;	P7 -> C
12	rhs_ p = case p of
13	P1 -> [C, B]; P2 -> [];	P3 ->	[C, A];	P4	->	[B,	B];
14	P5 -> [A, C]; P6 -> [C,	C]; P7	-> []

Représentation des documents ou arbres 70

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

Les productions Aomega, Bomega et Comega ont été introduites pour pouvoir désigner les bourgeons de types respectifs A, B et C.

Comme dans [BTT08, TT09, BTT07], nous représentons une vue par un ensemble de prédicats sur les symboles de la grammaire. Ainsi, les vues V1 = {A,B} et V2 = {A,C}, définies sur la grammaire Gexpl, peuvent être déclarées de la manière suivante :

1 viewAB :: Symb -> Bool

2 viewAB symb = case symb of

3 A->True

4 B->True

5 C -> False

6

7 viewAC :: Symb -> Bool

8 viewAC symb = case symb of

9 A->True

10 B -> False

11 C -> True

Représentation des documents ou arbres

Conformément à notre approche, un AST est soit un bourgeon (BUD) soit un noeud (NODE) étiqueté par une production et possédant plusieurs AST comme fils. Le type Haskell correspondant est le suivant:

1 data AST a = BUD | NODE {node_label::a, unNODE::[AST a]} deriving Eq

Dans la même lancée, un arbre de dérivation dont les étiquettes des noeuds sont de type a peut être représenté par le type Haskell suivant:

1 data BTree a = BTree {value::a, sons::Maybe [BTree a]} deriving Eq

Un arbre de dérivation est donc un noeud étiqueté par value possédant peut être (Maybe) des fils (sous-arbres) rangés dans une liste (sons); lorsqu'il en possède (sons est construite grâce au constructeur de données Just), il est un noeud clos. Dans le cas contraire (sons est construite plutôt grâce à Nothing), l'arbre est réduit à un bourgeon. Nous pouvons par exemple coder les états initiaux des automates ⁽¹⁾ (replicatAB) et

(2) (replicatAC), de l'exemple du chapitre 3 (sect. ??), grâce au code Haskell suivant:

1 replicatAB = [BTree A (Just [BTree B (Just [BTree B (Just [BTree A (Just []),

2 BTree A (Just [])]), BTree B (Just [BTree A (Just [])])])]),

3 BTree B (Just [BTree A (Just [])])]

4

5 replicatAC = [BTree C (Just [BTree A (Just [BTree C (Just []),BTree C (Just []),

6 BTree A (Just []), BTree C (Just []), BTree A (Just [])]), BTree C

7 (Just [])]), BTree C (Just [BTree C (Just []), BTree C (Just [])]),

8 BTree A (Just [])]

La fonction projection dont le code est le suivant, permet de projeter un document quelconque suivant une vue donnée. Elle retourne donc une forêt (liste d'arbres) représentant la réplique partielle du dit document pour la vue considérée.

1 projection :: (symb -> Bool) -> BTree symb -> [BTree symb]

2 projection view t@(BTree a Nothing) = if view a then [t] else []

3 projection view t@(BTree a (Just xs)) = if view a then [BTree a (Just sons_)]

Génération des documents 71

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

4 else sons_

5 where

6 sons_ = concat (map (projection view) xs)

Calcul de l'automate associé à une vue

Rappelons que, nous définissons un automate d'arbre à états de sortie par le type Automata suivant:

1 data Automata p q = Auto {exit::q -> Bool, next::q -> [(p, [q])]}

Le type générique p est le type des productions qui étiquettent les transitions et q est le type des états de l'automate.

L'adaptation de la fonction gram2autoview [BTT08, TT09, BTT07] suivante, permet de construire un automate à états de sortie capable de reconnaître les documents globaux qui sont des expansions d'une réplique partielle suivant une vue donnée.

1 gram2autoview :: Eq t => Gram a t -> (t -> a) -> (t -> Bool)

2 -> Automata a (Tag t, [BTree t])

3 gram2autoview gram symb2prod view = Auto exit next

4 where

5 exit (Open symb,[]) = True

6 exit _ = False

7

8 next (Open symb,_) = [(symb2prod symb,[])]

9 next (Close symb,ts) = [(p, zipWith trans (rhs gram p) tss) |

10 p <- prods gram, symb == lhs gram p,

11 tss <- match_ view (rhs gram p) ts]

12

13 trans symb (Close ts) = (Close symb, ts)

14 trans symb (Open ts) = (Open symb, ts)

15

16 match_ :: (Eq symb)=> (symb -> Bool)->[symb]->[BTree symb]->[[Tag [BTree symb]]]

17 match_ view [] ts = if null ts then [[]] else []

18 match_ view (symb:symbs) ts = [(ts1:tss)| (ts1,ts2) <- matchone_ view symb ts,

19 tss <- match_ view symbs ts2]

20

21 matchone_ :: (Eq symb) => (symb -> Bool) -> symb -> [BTree symb]

22 -> [(Tag [BTree symb],[BTree symb])]

23 matchone_ view symb ts =

24 if view symb

25 then if null ts then []

26 else case (head ts) of

27 (BTree symb' Nothing) -> if symb==symb'

28 then [(Open [], tail ts)]

29 else []

30 (BTree symb' (Just ts')) -> if symb==symb'

31 then [(Close ts', tail ts)]

32 else []

33 else [(Open [], ts)]++

34 [(Close (take n ts),drop n ts) | n <- [1..(length ts)]]

Génération des documents 72

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

Génération des documents

Nous définissons notre générateur par la fonction Haskell suivante qui prend un automate A et un état q quelconque en paramètre et retourne la liste des AST les plus simples du langage accepté par A à partir de q :

1 enum :: (Eq b) => Automata a b -> b -> [AST a]

2 enum auto init = enum_ [ ] init

3 where

4 enum path state | elem state path = []

5 | otherwise = (if((exit auto state) && (null (next auto state)))

6 then [BUD]

7 else []) ++ [NODE elet list_tree |

8 (elet, states) <- next auto state,

9 list_tree <- dist (map (enum_ (state : path)) states)]

Le combinateur dist ¹ fabrique un ensemble L2 de listes à partir d'un ensemble L1 de listes tel que chaque liste de L2 contient un élément de chaque liste de L1.

Grâce à toutes ces fonctions, il est donc possible de calculer l'ensemble des préfixes maximums sans conflits les plus simples issus de la fusion de plusieurs (deux) répliques partielles. Dans cette optique, on peut se servir d'un code comme celui ci (ce code est valide pour l'exemple présenté dans le chapitre 3 (sect. ??)) :

1 docconsensus = enum auto initstate where

2 initstate = ((Close A, replicatAB2), (Close A, replicatA))

3 autoview1 = gram2autoview gram symb2BudProd viewAB

4 autoview2 = gram2autoview gram symb2BudProd viewAC

5 auto = autoconsens symb2BudProd autoview1 autoview2

Dans ce code, initstate est l'état initial à partir duquel la génération se fait. Il est, comme prévu, un vecteur composé des états initiaux des automates qui sont fusionnés. L'automate autoview1 (resp. autoview2) est l'automate associé à la réplique partielle suivant la vue viewAB (resp. viewAC). La fonction symb2BudProd permet de transformer un symbole en une production étiquetant un bourgeon de type ce symbole. Son code, pour cet exemple, est le suivant:

1 symb2BudProd symb = case symb of

2 A -> Aomega

3 B -> Bomega

4 C -> Comega

L'automate auto est le produit consensuel de autoview1 et autoview2. Les documents consensuels les plus simples sont ainsi énumérés par la fonction enum et l'ensemble résultant est désigné par docconsensus.

1. dist est défini par pattern matching comme suit:

dist: : [[a]] ? [[a]]

dist [ ] = [[ ]]

dist (xs : xss) = [y : ys | y f- xs, ys f- dist xss]