Download Fichier PDF

8.4. Compilation des évaluations locales
123
Ce mécanisme général se poursuit jusqu’à ce que la dernière évaluation locale if ok(1,
p8,p7...p1.nil) soit évaluée sans échec. Le membre droit de la règle est alors construit :
4.2.7.3.6.8.5.1.nil est un des 92 résultats que l’on peut obtenir en appliquant la règle
queensrule.
L’exemple précédent illustre notre manière uniforme de gérer le non-déterminisme lié au
filtrage AC, à la sélection d’une règle et à l’évaluation d’une stratégie. Elle consiste à adopter
un schéma unique de compilation : lorsque plusieurs possibilités se présentent, un point de choix
est posé par setChoicePoint, et lorsqu’un échec se produit, un fail est généré pour explorer les
possibilités restantes.
En suivant cette approche, compiler une suite d’évaluations locales revient à les compiler
séparément en utilisant les schémas décrits par les algorithmes 8.1 et 8.2.
Algorithme 8.1 Compilation d’une condition : if cond
1: c ← évaluation de la condition cond
2: si c 6= true alors
3:
fail
4:
finsi
Algorithme 8.2 Compilation d’une condition de filtrage : where p := (S)t
t0 ← un résultat de l’application de la stratégie S sur t
2: filtrage one-to-one de p vers t0
3: si filtrage échoue alors
4:
fail
1:
5:
finsi
La compilation de la construction choose { try { <évaluation locale> }+ }+ est un peu
plus complexe : chaque branche try { <évaluation locale> }+ est compilée en utilisant les
algorithmes 8.1 et 8.2, et des points de choix sont placés entre chaque branche try ..., pour
permettre, en fonction de la stratégie d’application des règles, de retourner un seul résultat, tous
les résultats correspondant à l’exploration d’une branche ou tous les résultats correspondant à
l’exploration de toutes les branches. Le schéma de compilation est présenté par l’algorithme 8.3.
Algorithme 8.3 Compilation du choose/try : choose try branche1 , . . . ,try branchen
1: pose d’un point de choix : setChoicePoint
2: compilation de branche1
3: setChoicePoint
4: compilation de branche2
5: . . .
6: setChoicePoint
7: compilation de branchen