2. Le contrôle de l'effacement des buts. PrologIA HERITAGE II+

A!ociation

Prolog

HERITAGE

2. Le contrôle de l'effacement des buts

2.1. Le contrôle

2.2. Geler

2.3. A propos des arbres infinis

2.4. Quelques conseils pour la programmation récursive

2.5. Les méta-structures

2.1. Le contrôle

A chaque étape la machine Prolog doit faire deux choix :

(1) L'un pour choisir un but dans une suite de buts à effacer. C'est le premier

élément de la suite qui est toujours choisi. C'est à dire que pour effacer une suite de buts q0 q1 … qn, on efface d'abord q0 et ensuite q1 … qn.

(2) L'autre pour choisir la règle qui sert à effacer un but b. C'est la première règle dont la tête s'unifie avec le but b qui est choisie.

Cela peut se résumer par le programme Prolog suivant :

effacer(nil) -> ; effacer(t.l) -> rule(t, q) effacer(q) effacer(l) ;

rule(t,q) est une règle prédéfinie (voir le chapitre 3) qui donne par énumération toutes les règles dont la tête s'unifie avec t et la queue avec q.

Le moyen de contrôle consiste à modifier ou à restreindre les deux choix précédents. La manière dont Prolog fait ces choix peut amener certains programmes

à boucler et par conséquent à ne pas se comporter comme on pouvait l'espérer. Les deux exemples suivants illustrent ce phénomène.

Exemple 1 : Un cas typique est celui de la transitivité. Quand on cherche à effacer

plus_grand(Jo,x) en utilisant le programme suivant, on retrouve une instance de ce même but à effacer. Le programme se met alors à boucler et se termine par un débordement 1 de pile (ou par une interruption utilisateur!). La manière correcte d'écrire ce programme consiste à enlever la récursivité à gauche.

plus_grand(Jo, Max) -> ; plus_grand(Max, Fred) -> ; plus_grand(x, y) -> plus_grand(x, z) plus_grand(z, y);

1

Si le système de réallocation automatique n'est pas désactivé au démarrage de Prolog, un certain nombre de réallocations se produiront avant le débordement.

©PrologIA

R 2 - 2

Manuel de Référence

> plus_grand(Jo, x);

{x=Max}

{x=Fred}

DEBORDEMENT

"Une bonne solution" plus_grand'(Jo, Max) -> ; plus_grand'(Max, Fred) -> ; plus_grand(x, z) -> plus_grand'(x, y) plus_grand_ou_egal(y, z); plus_grand_ou_egal(x, x) ->; plus_grand_ou_egal(x, y) -> plus_grand(x, y);

Exemple 2 : Cet exemple énumère toutes les listes construites avec 1. Avec le

(mauvais) programme ci-dessous, c'est d'abord la liste infinie qui devrait être produite; bien entendu, la bonne solution s'obtient en permutant l'ordre des deux règles.

liste_de_un(1.x) -> liste_de_un(x) ; liste_de_un(nil) -> ;

>liste_de_un(x);

DEBORDEMENT

1

La coupure “!”

Normalement Prolog essaye d'effacer une suite de buts de toutes les manières possibles. Mais si on utilise une règle contenant un «!» (ou coupure) pour effacer un but q, l'effacement de ce «!» supprimera tous les choix de règles restant à faire pour effacer ce but q. Cela restreint la taille de l'espace de recherche : on peut dire que «!» fait «oublier» les autres manières possibles d'effacer q.

Le «!» ne peut apparaître que parmi les termes qui constituent le membre droit d'une règle. Les choix qui restent à examiner et que l'effacement du «!» fait

«oublier» sont :

- les autres règles ayant la même tête que celle où le «!» figure

- les autres règles qui auraient pu être utilisées pour effacer les termes compris entre le début de la queue et le «!»

Cette question est illustrée par les exemples suivants : couleur(rouge) ->; couleur(bleu) ->; taille(grand) ->; taille(petit) ->; choix1(x.y) -> couleur(x) taille(y);

A!ociation

Prolog

HERITAGE

1

Si le système de réallocation automatique n'est pas désactivé au démarrage de Prolog, un certain nombre de réallocations se produiront avant le débordement.

©PrologIA

A!ociation

Prolog

HERITAGE

Le contrôle de l'effacement des buts

R 2 - 3 choix1("c'est tout") ->; choix2(x.y) -> ! couleur(x) taille(y); choix2("c'est tout") ->; choix3(x.y) -> couleur(x) ! taille(y); choix3("c'est tout") ->; choix4(x.y) -> couleur(x) taille(y) !; choix4("c'est tout") ->;

>choix1(u);

{u=rouge.grand}

{u=rouge.petit}

{u=bleu.grand}

{u=bleu.petit}

{u="c'est tout"}

>choix2(u);

{u=rouge.grand}

{u=rouge.petit}

{u=bleu.grand}

{u=bleu.petit}

>choix3(u);

{u=rouge.grand}

{u=rouge.petit}

>choix4(u);

{u=rouge.grand}

>choix1(u) !;

{u=rouge.grand}

On peut considérer le «!» comme une annotation que l'on fait à un programme pour le rendre plus efficace; bien entendu, cela ne se justifie que si on ne s'intéresse qu'à la première solution fournie par ce programme.

Des utilisations classiques du «!» sont :

" Première solution uniquement " premiere_solution_uniquement(b) -> b !;

" Si Alors Sinon " si_alors_sinon(p,a,b) -> p ! a; si_alors_sinon(p,a,b) -> b;

" non " non(p) -> p ! fail; non(p) -> ;

Dans le cas de non montré ci-dessus, il faut remarquer que l'on peut avoir des résultats inattendus si p contient des variables libres. C'est ce que montre le petit exemple suivant :

homme(Abélard) -> ; femme(x) -> non(homme(x));

>femme(Eloïse);

{}

>femme(Abélard);

>femme(x) eq(x, Eloïse);

>

©PrologIA

R 2 - 4

Manuel de Référence

^(X,Y)

X doit être une variable et Y un terme quelconque.

^(X, Y) signifie: il existe X tel que Y soit vrai, et est équivalent à un appel de Y.

L'utilisation de ce prédicat (qui est aussi un opérateur) n'a de sens que dans les prédicats bagof/3 et setof/3 , pour indiquer les variables existentielles et les retirer de l'ensemble des variables libres.

bagof(x, p, l)

Pour chaque instantiation différente de l'ensemble des variables libres du but

p, non existentielles et n'apparaissant pas dans le terme x, unifie l avec la liste de toutes les solutions x lorsqu'on efface p. Chaque liste l est construite suivant l'ordre des solutions trouvées. Exemple:

aa(2,1) -> ; aa(1,2) -> ; aa(1,1) -> ; aa(2,2) -> ; aa(2,1) -> ;

>bagof(X, aa(X,Y),L);

{Y=1, L= 2.1.2.nil}

{Y=2, L= 1.2.nil}

> bagof(X,Y^aa(X,Y),L);

{L=2.1.1.2.2.nil}

> block(e, b), block_exit(e)

block est une règle prédéfinie qui permet de terminer brutalement l'effacement d'un but b. Cette primitive est faite essentiellement pour la récupération des erreurs. On peut considérer que :

- Pour effacer block(e, b) on efface b en ayant auparavant créé une paire de parenthèses fictives, étiquetées par e, autour du but b.

- block_exit(e) provoque l'abandon immédiat de l'effacement de tous les buts inclus entre les parenthèses étiquetées par e et supprime tous les choix éventuels en attente pour ces buts. L'effacement continue ensuite normalement, après les parenthèses étiquetées par e.

De plus :

- Une étiquette est un terme Prolog quelconque, et on considère que deux parenthèses étiquetées sont identiques si leurs étiquettes respectives sont unifiables.

- S'il y a plusieurs parenthèses étiquetées par e, block_exit(e) s'arrête au couple de parenthèses le plus interne.

- Si block_exit(e) ne rencontre pas de parenthèses e, alors on revient au niveau de commande avec le message d'erreur correspondant à e, si e est un entier, ou le message 'block_exit' SANS 'block' CORRESPONDANT, si e n'est pas un entier.

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Le contrôle de l'effacement des buts

R 2 - 5

C'est ce même mécanisme qui est utilisé pour la gestion des erreurs dans

Prolog. Une erreur rencontrée dans l'exécution de Prolog provoque l'effacement du but block_exit(i) où i est un entier correspondant au numéro de l'erreur. De cette manière l'utilisateur peut récupérer toutes les erreurs de

Prolog, pour pouvoir les traiter dans son application.

Lorsque les optimisations de compilation sont actives (option -f o1 au lancement de Prolog), la compilation de block est optimisée et la décompilation d'un tel but ne sera pas identique mais équivalente au but d'origine. Le but block(e,b) apparaissant dans une queue de règles, sera décompilé en block(e',_,b').

La règle prédéfinie quit génère un block_exit(14). Elle est définie ainsi : quit -> block_exit(14); quit(i) -> block_exit(14,i);

A titre d'illustration voici un programme qui lit une suite de commandes :

executer_commande ->

block(fin_commande, toujours(lire_et_exec)); lire_et_exec -> outm("?") in_char'(k) exec(k); exec("q") -> block_exit(fin_commande) ; exec("f") -> block_exit(16) ; /* Interruption */ exec("n") -> ; toujours(p) -> repeter p fail ; repeter -> ; repeter -> repeter ;

Dans cet exemple, la commande "q" utilise block_exit pour retourner au niveau supérieur de executer_commande. La commande "f" simule une erreur

Prolog et rend le contrôle au block qui traite les erreurs de Prolog (puisque 16 ne peut s'unifier avec fin_commande). S'il n'y a pas de block englobant, on revient au niveau supérieur de Prolog.

block(e, c, b), block_exit(e, c)

Fonctionnement analogue aux formes précédentes, avec deux «étiquettes» e et

c à la place d'une seule. b est le but à effacer. block(e,c,b) lance l'effacement de

b; l'effacement ultérieur de block_exit à deux arguments produira la recherche d'un block dont les deux premiers arguments s'unifient avec les deux arguments de block_exit.

Lorsque les optimisations de compilation sont actives (option -f o1 au lancement de Prolog), la compilation de block est optimisée et dans certains cas la décompilation d'un tel but ne sera pas identique mais équivalente au but d'origine. Le but block(e,c,b) apparaissant dans une queue de règles, sera décompilé en block(e',c',b').

Ensemble, ces deux règles prédéfinies constituent une sorte de raffinement du mécanisme de récupération des erreurs; en pratique, e correspond au type d'erreur guetté; c correspond à un «complément d'information» rendu par le mécanisme de détection.

©PrologIA

R 2 - 6

Manuel de Référence

Un grand nombre de règles prédéfinies utilisent cette deuxième étiquette comme complément d'erreur. C'est souvent l'argument, cause de l'erreur, qui y est transmis. En phase de mise au point de programmes, cela peut paraître encore insuffisant. Dans le kit, des modules objets : dbgbase.mo,

dbggraph.mo et dbgedin.mo, sont fournis. Ils permettent, après rechargement, en cas d'erreur, d'avoir des messages encore plus complets. Le deuxième argument de block sera unifié avec un terme de la forme : prédicat d'appel ou < prédicat d'appel, complément d'erreur>

Lorsque block_exit(e,c) est effacé dans un environnement «parenthésé» par

block(e',b), alors block_exit(e,c) se comporte comme block_exit(e).

Inversement, lorsque block_exit(e) est effacé dans un environnement

«parenthésé» par block(e',c',b) alors block_exit(e) se comporte comme

block_exit(e,nil)

Erreurs et sous-sessions Prolog

Tout ce qui est dit ci-dessus concernant le mécanisme d'erreur block /

block_exit, est vrai à l'intérieur d'une même session Prolog. Lorsqu'il s'agit de transmettre une erreur à travers une ou plusieurs sous-sessions (par exemple lorsqu'un but est lancé par menu), deux restrictions sont à mentionner :

- le deuxième argument de block_exit (souvent utilisé comme complément d'erreur) n'est pas transmis. Il vaudra toujours nil.

- le premier argument de block_exit est transmis uniquement s'il est de type entier. Dans le cas contraire c'est l'entier 317, pour l'erreur :

'block_exit' SANS 'block' CORRESPONDANT, qui est propagé.

Interruption

A tout instant un programme Prolog peut être interrompu au moyen d'une touche déterminée, dépendant du système utilisé (par exemple : <Ctrl-C>).

Cette interruption est prise en compte par le mécanisme général des erreurs de

Prolog et correspond à l'erreur 16. Cette erreur peut donc être récupérée par l'utilisateur. Sinon on revient au niveau de commande avec le message d'erreur suivant : INTERRUPTION UTILISATEUR.

bound(x)

bound(x) s'efface si x est lié. Une variable est considérée comme liée si elle a

été unifiée contre :

- une constante (entier, réel, identificateur, chaîne),

- un terme de la forme t1.t2,

- un terme de la forme <t1, t2, … , tn> ou ff(t1, t2, … , tn).

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Le contrôle de l'effacement des buts

R 2 - 7

dif(t1, t2)

La règle prédéfinie dif(t1, t2) est utilisée pour contraindre t1 et t2 à représenter toujours des objets différents. Dès que cette contrainte ne peut plus être satisfaite, on revient en arrière (backtracking). L'implantation de dif utilise un mécanisme similaire à geler.

Voici deux primitives intéressantes que l'on peut écrire avec dif : hors_de(x, l) qui vérifie que x n'appartiendra jamais à la liste l; et tous_differents(l) qui vérifie que les composants de la liste l seront toujours différents deux à deux.

hors_de(x, nil) -> ; hors_de(x, y.l) -> dif(x, y) hors_de(x, l); tous_differents(nil) -> ; tous_differents(x.l) -> hors_de(x, l) tous_differents(l);

Avec ces deux primitives on peut par exemple écrire un programme qui calcule des permutations : il suffit de dire que l'on a une liste d'entiers et que tous les éléments de cette liste sont différents deux à deux :

permutation(x1,x2,x3,x4) -> tous_differents(x1.x2.x3.x4.nil) chiffre(x1) chiffre(x2) chiffre(x3) chiffre(x4); chiffre(1) -> ; chiffre(2) -> ; chiffre(3) -> ; chiffre(4) -> ;

Remarquons que dans cet exemple, Prolog met d'abord en place toutes les inégalités avant d'exécuter le programme non-déterministe classique. Ceci donne une programmation plus claire et plus efficace.

L'utilisation de dif permet également l' écriture de programmes qui auraient un comportement incorrect si l'on utilisait une définition utilisant la coupure. Par exemple la définition de la relation "x est élément de l à la valeur v" peut s'écrire :

élément(x,nil,false) ->;

élément(x,x.l,true) ->;

élément(x,y.l,v) -> dif(x,y) élément(x,l,v);

> élément(x,1.2.nil,v);

{x=1, v=true}

{x=2, v=true}

{x#1, x#2, v=false}

Si l'on définissait une telle relation en utilisant la primitive !, on introduirait de nombreux comportements anormaux :

élément(x,nil,false) ->;

élément(x,x.l,true) -> ! ;

élément(x,y.l,v) -> élément(x,l,v);

> élément(x,1.2.nil,v);

{x=1, v=true}

> élément(2,4.2.3.nil,false);

{}

% une seule solution !!

% succès !!

©PrologIA

R 2 - 8

Manuel de Référence

default(t1, t2)

La règle prédéfinie default permet de réaliser le contrôle suivant: Si on peut effacer t1, alors on l'efface de toutes les manières possibles, sinon on efface

t2. Il faut remarquer que contrairement à ce que l'on pourrait penser à première vue, cette primitive ne peut pas être réalisée avec '!'. Voyons sur un exemple une utilisation de cette règle: répondre(p) -> default(p,outml("personne")); homme(jean) ->; homme(pierre) ->;

> répondre(homme(x));

{x=jean}

{x=pierre}

> répondre(femme(x)); personne

{}

eq(t1, t2)

Unification de t1 et t2 : correspond simplement à la règle :

eq(x,x) -> ; .

fail

Règle prédéfinie provoquant toujours un échec (backtracking).

findall(x, p, l)

Unifie l avec la liste de toutes les solutions x lorsqu'on efface p.

free(x)

S'efface uniquement si x n'est pas lié.

list_of(x, y, p, l)

Fournit la liste triée, sans répétition, de tous les individus qui satisfont une certaine propriété.

x est une variable.

y est une liste de variables.

p est un terme Prolog contenant au moins toutes ces variables.

Pour chaque ensemble de valeurs de y, unifie l avec la liste des valeurs de x pour que p soit vraie (c'est à dire pour que p s'efface).

L'ordre de la liste l est identique à celui défini sur les termes (cf. term_cmp/3)

Exemple : Prolog contenant la base de règles suivante : homme(grand, michel, 184) ->; homme(grand, alain, 183) ->; homme(grand, henry, 192) ->; homme(petit, nicolas, 175) ->; homme(petit, julien, 176) ->; homme(petit, gilles, 120) ->;

> list_of(x,t.nil,homme(t,x,h),l);

{t=grand, l=alain.henry.michel.nil}

{t=petit, l=gilles.julien.nicolas.nil}

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Le contrôle de l'effacement des buts

R 2 - 9

not(X)

Est décrit par les règles: not(X) :- X,!,fail.

not(X).

repeat

Est décrit par les règles : repeat ->; repeat -> repeat;

setof(x, p, l)

Pour chaque instantiation différente de l'ensemble des variables libres du but

p, non existentielles et n'apparaissant pas dans le terme x, unifie l avec la liste de toutes les solutions x lorsqu'on efface p. Chaque liste l est triée et sans répétition. L'ordre de la liste l est identique à celui défini sur les termes (cf.

term_cmp/3).

Exemple : Prolog contenant la base de règles suivante : aa(2,1) -> ; aa(1,2) -> ; aa(1,1) -> ; aa(2,2) -> ; aa(2,1) -> ;

> setof(X, aa(X,Y),L);

{Y=1, L= 1.2.nil}

{Y=2, L= 1.2.nil}

> setof(X,Y^aa(X,Y),L);

{L=1.2.nil}

>

or(x,y)

Définit un ou logique transparent à la coupure. Exemple:

> op(900,xfy,or);

{}

> enum(i,4) (eq(i,1) or eq(i,2));

{i=1}

{i=2}

> enum(i,4) ([eq(i,3),'!'] or [outl(no),fail]); no no

{i=3}

>

2.2. Geler

Il s'agit de résoudre de manière efficace un problème qui se pose souvent en

Prolog : retarder le plus possible certaines décisions. Ce qui revient à dire qu'il faut avoir suffisamment d'information avant de poursuivre l'exécution d'un programme, ou que certaines variables doivent avoir reçu une valeur pour pouvoir continuer. On profite alors des avantages de la programmation déclarative, tout en gardant une exécution efficace.

©PrologIA

R 2 - 10

Manuel de Référence freeze(x, q)

Le but de cette règle prédéfinie est de retarder l'effacement de q tant que x est inconnu. Plus précisément :

(1) Si x est libre, alors freeze(x, q) s'efface et l'effacement de q est mis en attente (on dit que q est gelé). L'effacement effectif de q sera déclenché au moment où x deviendra liée.

(2) Si x est liée alors freeze lance l'effacement de q normalement.

C'est au programmeur de s'assurer qu'une variable gelée sera toujours dégelée dans le futur, pour que le but associé ne reste pas indéfiniment en attente. Ceci n'est pas vérifié par Prolog, et peut conduire à des solutions trop générales.

Remarque : Les impressions des variables d'une question sur lesquelles il reste des buts gelés se fait d'une manière spéciale :

> freeze(x,foo);

{x~foo.nil}

Voyons maintenant quelques exemples d'utilisation de freeze.

Exemple 1 : Evaluation de somme(x, y, z). On veut résoudre l'équation

z = x + y seulement si les deux variables x et y sont connues.

somme(x, y, z) -> freeze(x, freeze(y, somme1(x, y, z))) ; somme1(x, y, z) -> val(x+y, z);

Exemple 2 : Mais on peut faire mieux : On veut résoudre la même équation si deux au moins des variables x, y, z sont connues :

somme (x, y, z) -> freeze(x, freeze(y, ou_bien(u, somme1(x, y, z)))) freeze(y, freeze(z, ou_bien(u, somme2(x, y, z)))) freeze(x, freeze(z, ou_bien(u, somme3(x, y, z)))); ou_bien(u, p) -> free(u) ! eq(u, Cst) p; ou_bien(u, p) ->; somme1(x, y, z) -> val(x+y, z); somme2(x, y, z) -> val(z-y, x); somme3(x, y, z) -> val(z-x, y);

Ci-dessus, la variable u, qui devient liée dès que l'une des additions est effectuée, sert à empêcher que les autres additions, redondantes, soient calculées.

Exemple 3 : Cet exemple montre comment utiliser une variable pour contrôler un programme de l'extérieur. La règle liste_de_un qui a été donnée dans un exemple précédent, bouclait. Pour empêcher cette boucle on utilise simplement une condition externe : longueur(l, n) qui vérifie que la longueur d'une liste l est inférieure ou égale à n.

longueur(l,n) -> freeze(l,longueur'(l,n)); longueur'(nil, n) ->;

©PrologIA

A!ociation

Prolog

HERITAGE

A!ociation

Prolog

HERITAGE

Le contrôle de l'effacement des buts

R 2 - 11

longueur'(e.l, n) ->

dif(n,0) val(n-1, n') longueur(l, n'); liste_de_un(1.x) -> liste_de_un(x); liste_de_un(nil) -> ;

> longueur(l,5) liste_de_un(l);

{l=1.1.1.1.1.nil}

{l=1.1.1.1.nil}

{l=1.1.1.nil}

{l=1.nil}

{l=nil}

Quand tous les buts ont été effacés, il se peut qu'il reste encore certains buts gelés sur des variables qui sont encore libres.

Remarque : Les optimisations de compilation ne permettent pas de déclencher les buts gelés dès l'unification de la tête de règle mais seulement sur le premier but de la queue non optimisé. En particulier, l'exemple suivant

échouera :

> insert;

nombre(<i>) -> integer(i); lier(<1>) ->;;

{}

> freeze(x, lier(x)) nombre(x);

>

En effet, les prédicats de test de type étant optimisés, le dégel de lier(<i>) ne se fera pas puisqu'il n'y a pas d'autres buts dans la queue de nombre/1.

2.3. A propos des arbres infinis

Ce paragraphe donne quelques informations pratiques sur l'utilisation dans

Prolog II des arbres infinis. Tout d'abord, il faut remarquer qu'un certain nombre de règles prédéfinies ne travaillent que sur des arbres finis. En particulier, in ne peut pas lire d'arbres infinis, et assert ne peut pas ajouter de règles contenant des arbres infinis.

infinite no_infinite

Ces règles servent à définir le type d'impression de résultat utilisé: il faut avoir activé l'option infinite si l'on désire imprimer des solutions contenant des arbres infinis.

Voici un exemple qui utilise freeze et qui vérifie qu'un arbre est toujours fini.

Ceci est un moyen indirect de faire le test dit d'occur_check. Ce programme vérifie que l'on n'a pas deux fois le même sous-arbre dans chaque branche de l'arbre.

arbre_fini(x) -> branche_finie(x, nil); branche_finie(x, l) -> freeze(x, branche_finie'(x, l)); branche_finie'(x, l) -> hors_de(x, l) domine (x, l') branches_finies(l', x.l);

©PrologIA

R 2 - 12

Manuel de Référence branches_finies(nil, l) -> ; branches_finies(x.l', l) -> branche_finie (x, l) branches_finies (l', l) ; domine(x1.x2, x1.x2.nil) -> ! ; domine(x, x') -> tuple(x) ! split(x, x') ; domine(x, nil) -> ; infinite_flag

Symbole dont la valeur (0 ou 1) indique si infinite ou no_infinite est actif.

Cette valeur peut être testée par l'intermédiaire de la règle prédéfinie val.

equations(t, t', l)

Cette règle prédéfinie sert à transformer un arbre fini ou infini t en une liste d'équations l qui a comme solution t. t' indique la variable de l représentant la racine de l'arbre t. C'est cette primitive qui est utilisée pour imprimer les solutions lorsque l'option infinite est active. Regardons une utilisation sur l'exemple suivant :

> infinite eq(x,ff(ff(x))) equations(x,t',l) out(t')

outm(" : ") outl(l) ;

v131 : eq(v131,ff(v131)).nil

{x=v131, v131=ff(v131), l=eq(t',ff(t')).nil}

> eq(x,ff(ff(x)));

{x=v120,v120=ff(v120)}

Mais une des utilisations principales de cette primitive est le fait de pouvoir ajouter des arbres infinis. Nous utilisons la primitive assert (chapitre suivant) qui permet d'ajouter une règle.

ajout_infini(t) -> equations(t,t',l) assert(arbre(t'),l) ;

> infinite eq(x, ff(ff(x))) ajout_infini(x) ;

{x=v131, v131=ff(v131)}

> list(arbre/1) ;

arbre(x11) -> eq(x11, ff(x11)) ;

{}

> arbre(x) ;

{x=v131, v131=ff(v131)}

2.4. Quelques conseils pour la programmation récursive

Le système Prolog II+ comporte un récupérateur de mémoire (garbage collector) automatique. Ce "ramasse-miettes" est très performant et est capable de ne garder dans les piles que les données dont vous avez effectivement besoin; ceci permet d'utiliser à fond les définitions récursives de programmes. Malgré tout, certaines techniques de programmation peuvent vous aider à récupérer encore plus d'espace.

Pratiquement, il s'agit d'utiliser adroitement la coupure des points de choix ainsi que de tirer un maximum de profit de l'optimisation de récursion et d'appel terminal que fait le compilateur Prolog II+. L'utilisation de ces techniques permet l'écriture de programmes qui se rappellent eux-mêmes indéfiniment, sans jamais déborder.

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Le contrôle de l'effacement des buts

R 2 - 13

Ceci sera plus clair à partir d'un exemple:

> insert;

répéter -> out(1) répéter ;;

{}

> répéter ;

11111111111111111111111...

est un programme tournant indéfiniment sans déborder, car la récursion se fait sur le

dernier littéral de la règle. Par contre le programme suivant débordera, car la récursion accumule les littéraux à effacer (récursion non terminale):

répéter -> out(1) répéter out(2);

> répéter ;

11111111111111111111111...

-> DEBORDEMENT

1

PILE DE RECURSIVITE

> de même le fait qu'il reste des choix à la règle exécutée accumule de l'information à garder. L'effacement du but avec la définition qui suit provoquera un débordement par accumulation de points de choix:

> insert;

répéter -> répéter ; répéter ->;;

{}

> répéter fail;

-> DEBORDEMENT PILE DE RECURSIVITE

>

En revanche le programme suivant tournera indéfiniment (heureusement on peut l'interrompre avec Control-C!):

répéter -> ;

répéter -> répéter ;

Le coupe-choix "!" permet au ramasse-miettes de récupérer davantage d'espace, en supprimant des points de choix. Il faut cependant remarquer que si on le place en fin de règle, on fait disparaître la propriété de récursion terminale:

répéter -> out(1) répéter !; répéter ->;

Le programme ci-dessus provoquera un débordement (le "!" est un littéral à effacer), alors que le programme ci-dessous tournera indéfiniment:

répéter -> out(1) ! répéter ; répéter ->;

1

Si le système de réallocation automatique n'est pas désactivé au démarrage de Prolog, un certain nombre de réallocations se produiront avant le débordement.

©PrologIA

R 2 - 14

Manuel de Référence

2.5. Les meta-structures

2.5.1. Création

Il est possible en PrologII+ d'attacher à une variable une liste de termes. On parlera alors de méta-structure ou variable attribuée et de termes attribués.

La particularité de ces variables est que l'unification avec un terme connu ou bien avec une autre variable attribuée est remplacée par des appels à des prédicats utilisateurs.

En effet, une tentative d'unification d'une variable attribuée avec un terme connu est remplacée par autant d'appels que de termes dans la liste attachée à cette variable. De la même manière, une tentative d'unification de deux variables attribuées se traduira par des appels successifs à tous les prédicats contenus dans chacune des deux listes.

Les paramètres de chacun de ces prédicats sont imposés: le premier paramètre sera la variable attribuée elle même, le second sera le terme avec lequel on essaie de l'unifier, et le troisième sera le terme attribué correspondant dans la liste.

Le lien d'un terme avec une variable peut s'effectuer au moyen de deux prédicats prédéfinis: new_tlv/3 et add_tlv/3 (TLV: Term Linked to Variable).

new_tlv(v, t, i)

Attache à la variable v le terme t. La liste de termes attribués à la variable v sera donc réduite à un seul élément: le terme t. Si v était déja une variable attribuée, l'ancienne liste est perdue. Si v n'est pas une variable, une erreur est générée.

Le troisième argument i doit être un identificateur: il s'agit du nom de la règle utilisateur décrite plus haut (d'arité 3) qui sera appelée lors d'une tentative d'unification de la variable v avec un terme connu ou bien avec une autre variable attribuée.

add_tlv(v, t, i)

Ajoute à la variable v le terme t. La liste de termes attribués à la variable v sera donc augmentée d'un élément: le terme t. Si v n'était pas déja une variable attribuée, ce prédicat a le même effet que le précédent. Si v n'est pas une variable, une erreur est générée. Le troisième argument i a la même signification que précédemment.

L'ordre dans lequel les prédicats utilisateurs seront appelés n'est pas spécifié.

Exemple:

> insert; rule1(V,T,A) -> outm("Rule1 ") out(T) outm(" ") outl(A); rule2(V,T,A) -> outm("Rule2 ") out(T) outm(" ") outl(A); rule3(V,T,A) -> outm("Rule3 ") out(T) outm(" ") outl(A);

;

{}

> new_tlv(V,1.2.nil, rule1) add_tlv(V,3.4.nil,rule2)

©PrologIA

A!ociation

Prolog

HERITAGE

A!ociation

Prolog

HERITAGE

Le contrôle de l'effacement des buts

R 2 - 15

add_tlv(V,5.6.nil,rule3) eq(V,foo);

Rule1 foo 1.2.nil

Rule2 foo 3.4.nil

Rule3 foo 5.6.nil

{V@rule1(1.2.nil).rule2(3.4.nil).rule3(5.6.nil).nil}

Une combinaison de ces deux prédicats peut être simplement obtenue par un appel au prédicat :

set_tlv(v, l)

où l doit être une liste d'éléments de la forme i(t), i et t ayant la même signification que dans les prédicats précédents. Si la liste l comporte N

éléments, l'appel à ce prédicat est équivalent à un premier appel à new_tlv/3, suivi de N-1 appels à add_tlv/3.

Exemple:

> set_tlv(X,foo(1).aa(2).nil);

{X@foo(1).aa(2).nil}

2.5.2. Récupération

La liste des termes attribués à une variable peut être obtenue au moyen du prédicat

get_tlv(v, l)

Unifie l avec la liste formée des termes attribués à la variable v, chacun de ces termes étant encapsulé par le prédicat utilisateur appelé lors d'une tentative d'unification de cette variable avec une autre variable attribuée ou un terme connu. Cette liste l est donc de la forme: id1(t1).id2(t2)....nil avec l'association de chaque identificateur id (prédicat utilisateur) au terme correspondant. Si v n'est pas une variable, l est unifiée avec nil.

Exemple:

> new_tlv(V,1.2.nil, rule1) add_tlv(V,3.4.nil,rule2)

add_tlv(V,5.6.nil,rule3) get_tlv(V,T);

{V@rule1(1.2.nil).rule2(3.4.nil).rule3(5.6.nil).nil,

T=rule1(1.2.nil).rule2(3.4.nil).rule3(5.6.nil).nil}

2.5.3. Unification forcée

Une unification classique (sans appel aux prédicats utilisateurs) peut être forcée entre une variable attribuée et un terme connu ou bien une autre variable attribuée.

Cette unification s'effectue au moyen d'un prédicat spécial:

unify_tlv(t1, t2)

Réalise une unification ordinaire entre les deux termes t1 et t2. Voyons tous les cas possibles:

- Si ni t1 ni t2 ne sont des variables attribuées, est équivalent à eq/2.

- Si t1 est une variable attribuée:

©PrologIA

R 2 - 16

Manuel de Référence

- Si t2 est une variable ordinaire, t2, unifié avec t1, deviendra donc une variable attribuée.

- Si t2 est un terme connu, t1, unifié avec t2 deviendra donc ce terme connu (la liste de termes attribués sera alors perdue).

- Si t2 est aussi une variable attribuée, après unification t1 et t2 désigneront une variable attribuée ayant pour liste de termes attribués la concaténation des deux listes initiales (celle de t1 et celle de t2).

Exemple:

> new_tlv(V,1.2.nil,foo) unify_tlv(V,3);

{V=3}

> new_tlv(V,1.2.nil,foo) unify_tlv(Z,V);

{V=Z,V@foo(1.2.nil).nil,Z@foo(1.2.nil).nil}

> new_tlv(V,1.2.nil,foo) new_tlv(X,3.4.nil,faa)

unify_tlv(V,X);

{V=X,V@foo(1.2.nil).faa(3.4.nil).nil,

X@foo(1.2.nil).faa(3.4.nil).nil}

2.5.4. Sorties

Les impressions des variables attribuées d'une question se fait d'une manière spéciale : <nom de variable>@<terme>

Le terme qui suit @ est la liste des termes attribués à la variable, présentée de manière identique au prédicat get_tlv/2.

Exemple:

> new_tlv(x,zz,foo);

{x@foo(zz).nil}

2.5.5. Exemple

Ce programme attache à une variable l'ensemble de ses valeurs possibles. S'il ne reste plus qu'une seule valeur, elle est affectée à la variable.

insert;

% Si X est une nouvelle variable, lui attache l'ensemble

% de valeurs L, sinon lui attache l'intersection de L avec

% l'ensemble déja attaché be_in(X,L) -> get_tlv(X,L1) be_in(L1, X, L); be_in(nil,X,L) -> ! new_set(X,L); be_in(L1,X,L) -> get_values(L1, L2) inters(L,L2,L3) attach_or_affect(X, L3);

% attache à X la liste L de ses valeurs possibles new_set(X,L) -> new_tlv(X,L,verify_in);

% Récupère la liste des valeurs possibles get_values([],[])->!; get_values(t_ag(L1).L2, L)-> get_values(L2,L3) conc(L1,L3,L);

% concatenation de 2 listes conc(nil,L,L)->;

©PrologIA

A!ociation

Prolog

HERITAGE

A!ociation

Prolog

HERITAGE

Le contrôle de l'effacement des buts

R 2 - 17

conc(X.L1,L2,X.L3) -> conc(L1,L2,L3); attach_or_affect(X,[F]) -> !

unify_tlv(X,F);% une seule valeur possible -> on affecte attach_or_affect(X,L) -> dif(L,nil) new_set(X,L); % nouvel ensemble possible

% Le 3ème argument est l'intersection des 2 listes inters([],L,[])->; inters(x.l,l1,x.l2)-> member(x,l1) ! inters(l,l1,l2); inters(x.l,l1,l2)-> inters(l,l1,l2);

% Predicat utilisateur verify_in(V_arlibc, T_unifie, T_att) -> member(T_unifie,T_att) unify_tlv(V_arlibc, T_unifie);

% End of insertion ;

{}

> % quelques exécutions

be_in(x,[1,2,3,4]) be_in(x,[1,3,7]) be_in(x,[1,7,8]);

{x=1}

> be_in(x,[4,5,6]) be_in(x,[7,8,9]) ; % Echec

> be_in(x,[1,2,3,4,5]) be_in(y,[1,6,7,8]) eq(x,y);

{x=1,y=1}

> be_in(x,[1,2,3,4,5]) be_in(y,[1,2,6,7,8]) eq(x,y);

{x=1,y=1}

{x=2,y=2}

©PrologIA

R 2 - 18

Manuel de Référence

A!ociation

Prolog

HERITAGE

©PrologIA