La coupure et le problème de la négation

On présente en ce chapitre le prédicat prédéfini très important qui aura pour effet de stopper la recherche de Prolog dès qu’il aura trouvé une solution dont on veut qu’elle soit unique. Ce prédicat permet de contrôler l’espace de recherche, d’économiser le travail de Prolog et de définir une négation.

Contrôle de l’exploration de l’arbre par la primitive
1. « coupure »
Le prédicat prédéfini coupure permet de contrôler l’exploration de l’arbre de recherche. En effet, lorsque cette coupure (notée cut, slash « / » ou plus souvent point d’exclamation « ! ») s’efface, celui-ci est évalué à vrai et tous les choix en attente sont supprimés entre ce nœud et celui où est apparue la coupure. « ! » signifie donc que la première solution trouvée sur sa gauche suffira, mais que Prolog cherchera toutes les solutions aux prédicats sur la droite de « ! ».

Lorsque l’on est certain de l’unicité d’une solution, la coupure empêche les retours en arrière inutiles, voire néfaste, par exemple dans :

min(X, Y, X) :- X <= Y, !.
min(X, Y, Y) :- X > Y.

On pourrait supprimer la condition X > Y de la seconde clause au cas où le troisième argument (le résultat du min) est inconnu, ce qui est l’utilisation la plus courante, mais alors min(3, 5, 5). réussirait, ce qu’il vaut mieux éviter.

Cependant, cela peut convenir dans la mesure où min sera utilisé de façon fonctionnelle pour connaître le troisième argument. Aussi, la plupart du temps les clauses suivantes suffiront :

min(X, Y, X) :- X <= Y, !.
min(X, Y, Y).

Prenons maintenant l’exemple d’un programme Prolog où P, Q, R sont des propositions. Dans l’arbre de recherche, deux sous-arbres vont être coupés (trait gras).

Là où apparaît la coupure, c’est-à-dire pour trouver les solutions de P, la recherche des solutions par W est supprimée au cas où une première solution a été trouvée par Q et les autres solutions de Q ne sont par recherchées.

Par contre, la coupure, telle qu’elle est placée, ne limite pas les solutions de R, ce qui fait que même si la clause R :- S. était placée plus bas, toutes les solutions de R sont recherchées. On demande si R est prouvable, il le sera si P ou S le
sont.

R :- P.
R :- S.
P :- U.
P :- Q, !, V.
P :- W.

La description de l’effet de la coupure dans l’arbre de recherche n’est pas facile à donner, aussi, pour un second exemple, on considère quatre programmes ne variant que par la dernière clause pi mise à la place de p. Les axiomes sont :

q(a).
q(b).
q(c).
r(b, b1).
r(c, c1).
r(a, a1).
r(a, a2).
r(a, a3).

Les règles sont successivement :

p0(X, Y) :- q(X), r(X, Y).
p1(X, Y) :- q(X), r(X, Y), /.
p2(X, Y) :- q(X), //, r(X, Y).
p3(X, Y) :- ///, q(X), r(X, Y).
pi(d, d1).

Avec i successivement 0, 1, 2, 3.

2. Le prédicat « faux » ou « impasse »
Lorsque c’est le tour du prédicat prédéfini fail (l’impasse) d’être effacé, alors la recherche continue en remontant au nœud supérieur. Tout simplement parce que fail est toujours évalué à faux. Ce prédicat ne sert quasiment que pour la négation.

Cette négation n’est pas toujours présente dans les prédicats prédéfinis des différentes versions de Prolog ; en ce cas, elle est facile à redéfinir (paragraphe suivant).
Que se passe-t-il, dans l’exemple précédent, si l’on remplace les clauses p, successivement par les clauses p4 p5 p6 correspondant à p1 p2 p3 dans lesquelles « impasse » prend la place de « coupure » ? La réponse sera no dans tous les cas puisque fail est évaluée à faux, la différence sera qu’elle sera immédiate pour p6, surviendra après recherche des solutions de q pour p5 et après recherche des solutions de q et de r pour p4.

3. Négation
Le problème qui se pose pour la négation est que le « faux » est remplacé par le concept de « non prouvable ». Cette négation n’est donc qu’une « négation par l’absence », elle peut être simulée par les deux clauses dont l’ordre est indispensable :

not(P) :- P, !, fail.
not(P).

En effet, la première clause signifie que si P est attesté, alors la coupure cessera toute recherche ultérieure et l’impasse fail forcera la tête not(P) à être fausse. La seconde clause indique que si P n’est pas présent dans la base de connaissance, alors not(P) est vrai. Par exemple « différent » (prédéfini par \==) peut être redéfini par :

dif(X, X) :- !, fail.
dif(X, Y).

Il est également possible de construire un opérateur conditionnel :

if(P, Q, R) :- P, !, Q.
if(P, Q, R) :- R.

Supposons en effet que P soit vérifié, alors, le if, sans aller voir la seconde clause, va chercher à résoudre Q. Par contre, si P n’est pas satisfait, alors Prolog passe à la seconde clause qui l’oblige à résoudre R. Par ailleurs, not(P) n’instancie rien, P peut être résolu en donnant des solutions s’il contient des variables, alors que not(P) sera un succès sans donner d’instanciation. Un exemple extrêmement réduit aidera à comprendre ce mécanisme.

etudiant(max).
etudiant(luc).
mineur(jean).
etudiantmajeur(X) :- not(mineur(X)), etudiant(X).

La question etudiantmajeur(luc). donnera vrai dans la mesure où le fait mineur(luc) n’existe pas dans la base, mais la question etudiantmajeur(X). ne donnera rien, il n’y a pas d’instanciation pour X, sauf si on inverse l’ordre des hypothèses de etudiantmajeur, car alors X = max puis X = luc prouveront d’abord etudiant(X).

Voyons maintenant l’effet de la double négation, si on reprend le petit programme :

femme(eve).
petit(eve).
femme(irma).
taille(irma, 155).
femme(julie).
taille(julie, 165).
petit(X) :- taille(X, T), T < 160.
femme(X). → X = eve ; X = irma ; X = julie ; X = carmela ; no
not(femme(eve)). → no
homme(eve). → no
not(not(femme(eve))). → yes
petit(X). → X = eve ; X = irma ; X = carmela ; no
not(petit(X)). → no
not(not(femme(X))). → X = _1039
not(not(petit(X))). → X = _1685

On voit qu’il n’y a pas d’instanciation à ces deux dernières questions.