Raisonnez par l'échec et collectez les solutions

Le coach d’une équipe de football veut savoir qui peut jouer samedi : tous les joueurs qui ne sont pas blessés et qui ne sont pas suspendus. Deux difficultés surgissent. D’abord, Prolog ne sait démontrer que des choses positives : comment lui faire dire que quelqu’un n’est pas blessé ? Ensuite, Prolog donne ses réponses une à une, alors que le coach veut la liste des disponibles.

Dans ce chapitre, vous allez apprendre la négation à la façon de Prolog, avec ses pièges, puis les prédicats qui rassemblent toutes les solutions d’une question dans une liste. Nous finirons par un aperçu des entrées-sorties.

joueur(awa).  joueur(bastien).  joueur(chloe).  joueur(dylan).  joueur(elise).

blesse(bastien).
suspendu(dylan).

% poste(Joueur, Poste)
poste(awa, attaque).     poste(bastien, defense).  poste(chloe, attaque).
poste(dylan, gardien).   poste(elise, defense).

La négation par l’échec

Une base Prolog ne contient que des faits positifs : on y lit que Bastien est blessé, jamais qu’Awa ne l’est pas. Démontrer « Awa n’est pas blessée » au sens logique strict est impossible avec ces seuls faits.

Prolog contourne le problème avec une règle pragmatique. Il tente de démontrer blesse(awa), échoue en un temps fini, et en conclut que c’est faux. C’est la négation par l’échec (negation as failure) :

si la démonstration de A échoue en un temps fini, alors « non A » est considéré comme vrai ;
si elle réussit, « non A » est faux.

Derrière cette règle se cache l’hypothèse du monde clos : tout ce qui n’est pas démontrable à partir de la base est considéré comme faux. Si le médecin a oublié d’enregistrer la blessure d’Awa, Prolog la déclarera apte, sans aucun doute. La base est supposée complète.

On peut écrire cette négation soi-même, avec la coupure et le prédicat prédéfini fail, qui échoue toujours :

not(P) :- P, !, fail.    % si P réussit : on coupe, puis on échoue
not(_).                  % sinon (P a échoué) : on réussit

Si P réussit, la coupure supprime la seconde clause et fail fait échouer not(P). Si P échoue, on passe à la seconde clause, qui réussit. Ce couple !, fail s’appelle une coupure-échec. ECLiPSe fournit directement not/1 ; la notation standard, disponible partout, est \+, qui se lit « non démontrable ».

La coupure-échec en action : si P est démontrable, la coupure interdit la clause 2 et fail fait tout échouer ; sinon, la clause 2 réussit.

Le coach peut maintenant écrire :

disponible(X) :- joueur(X), not(blesse(X)), not(suspendu(X)).

?- disponible(X). donne Awa, Chloé et Élise.

Seuls deux faits existent ; toutes les autres cases valent faux par défaut, et c'est ce monde clos qui rend awa, chloe et elise disponibles.

Le piège des variables libres

Réécrivons le prédicat en changeant l’ordre des buts, ce qui semble innocent :

disponible_bis(X) :- not(blesse(X)), not(suspendu(X)), joueur(X).

?- disponible_bis(X). répond No. Pourquoi ? Au moment d’appeler not(blesse(X)), X est libre. Prolog tente blesse(X), qui réussit avec X = bastien, donc not(blesse(X)) échoue. La question posée n’était pas « X n’est-il pas blessé ? », mais « est-il faux qu’il existe un blessé ? » : c’est faux, puisque Bastien l’est.

Placé après joueur(X), not teste un joueur précis ; placé avant, il teste « existe-t-il un blessé ? », et la réponse est non pour tout le monde.

Le même raisonnement explique ce résultat étonnant, avec grand(pierre)., grand(paul). et petit(X) :- not(grand(X)). :

Question	Réponse	Pourquoi
`?- petit(arthur).`	Yes	`grand(arthur)` échoue
`?- petit(pierre).`	No	`grand(pierre)` réussit
`?- petit(X), X = arthur.`	No	`grand(X)` réussit avec X libre

Deux autres conséquences sont à connaître. D’abord, not ne lie jamais de variable : si P réussit, not(P) échoue et les liaisons sont défaites ; s’il échoue, il n’y avait rien à lier. Ensuite, not(not(P)) n’est pas équivalent à P : il vérifie que P est démontrable, mais sans renvoyer de valeur.

Collecter toutes les solutions

Le coach veut une liste, pas une suite de réponses. Prolog fournit trois prédicats pour rassembler les solutions d’un but.

`findall/3`

findall(Modele, But, Liste) cherche toutes les solutions de But et range dans Liste le Modele instancié par chacune, dans l’ordre où Prolog les trouve.

?- findall(X, disponible(X), L).
L = [awa, chloe, elise]

?- findall(J-P, poste(J, P), L).
L = [awa-attaque, bastien-defense, chloe-attaque, dylan-gardien, elise-defense]

?- findall(X, poste(X, milieu), L).
L = []

Le modèle peut être n’importe quel terme : une variable, une paire J-P, une structure. findall n’échoue jamais (sans solution, il rend la liste vide), garde les doublons et ne crée pas de point de choix. Pour compter, il suffit d’ajouter length/2 : findall(X, disponible(X), L), length(L, N) donne N = 3.

`bagof/3` et `setof/3`

bagof ressemble à findall, avec deux différences. Il échoue s’il n’y a aucune solution. Et il traite à part les variables du but qui n’apparaissent pas dans le modèle : il produit une liste par valeur de ces variables, au retour arrière.

?- bagof(J, poste(J, P), L).
P = attaque, L = [awa, chloe] ;
P = defense, L = [bastien, elise] ;
P = gardien, L = [dylan]

C’est un regroupement, l’équivalent d’un GROUP BY en SQL. Pour ne pas grouper, on marque la variable comme « existentielle » avec ^ : bagof(J, P^poste(J, P), L) se lit « les J tels qu’il existe un P avec poste(J, P) », et donne les cinq joueurs dans une seule liste.

setof fonctionne comme bagof, mais rend chaque liste triée et sans doublons :

?- setof(P, J^poste(J, P), L).
L = [attaque, defense, gardien]

Prédicat	Sans solution	Doublons	Trié	Variables libres du but
`findall/3`	rend `[]`	gardés	non (ordre de recherche)	ignorées (existentielles)
`bagof/3`	échoue	gardés	non	une liste par valeur (sauf `^`)
`setof/3`	échoue	supprimés	oui	une liste par valeur (sauf `^`)

findall rend une seule liste, bagof groupe par valeur de la variable libre P, setof trie et retire les doublons.

Enfin, sort(L1, L2) trie une liste selon l’ordre standard des termes en supprimant les doublons, et msort/2 trie en les gardant. Pour obtenir la liste triée des disponibles, même vide, on écrit donc :

disponibles(L) :- findall(X, disponible(X), L0), sort(L0, L).

Un aperçu des entrées-sorties

Les programmes réels doivent lire et écrire. Les prédicats d’entrée-sortie sont extra-logiques : leur effet (une ligne affichée, un terme lu) n’est pas défait par le retour arrière.

write(T) affiche un terme, nl passe à la ligne ; writeq(T) l’affiche avec les apostrophes nécessaires pour qu’il puisse être relu par Prolog ('Saint-Malo' et non Saint-Malo).
read(T) lit le terme suivant sur l’entrée, qui doit se terminer par un point, et l’unifie avec T.
printf(Format, Arguments) affiche avec un format, à la manière du C : printf("%w a %d ans%n", [yann, 25]).
get/1 et put/1 lisent et écrivent un caractère, par son code.
Les fichiers sont des flux : open(Fichier, Mode, Flux) avec le mode read, write ou append, puis close(Flux). La plupart des prédicats acceptent un premier argument de flux, comme write(Flux, T).

Voici un prédicat qui lit des termes au clavier jusqu’au mot fin, et les range dans une liste :

lire(L) :- read(T), traiter(T, L).

traiter(fin, []) :- !.
traiter(T, [T|L]) :- lire(L).

La structure en deux prédicats n’est pas un luxe. Une version naïve comme lire([T|L]) :- read(T), T \== fin, lire(L). avec une clause lire([]) :- read(fin). lit un nouveau terme dans la seconde clause au moindre échec de la première : le terme fin déjà lu est perdu, puisque read n’est pas annulé par le retour arrière. En lisant une seule fois puis en décidant quoi faire du terme lu, on évite le problème.

En résumé

Prolog ne démontre que du positif ; not(P) ou \+ P réussit si P échoue en un temps fini (négation par l’échec).
Cette négation repose sur l’hypothèse du monde clos : la base est supposée complète.
not(P) :- P, !, fail. not(_). illustre la coupure-échec.
Une négation sur une variable libre change de sens : placez-la après les buts qui instancient ses variables.
findall rend toujours une liste (éventuellement vide) ; bagof et setof échouent sans solution et groupent par variable libre, sauf avec ^ ; setof trie et supprime les doublons.
sort/2 trie sans doublons ; findall suivi de sort est la façon sûre d’obtenir une liste triée, même vide.
Les entrées-sorties (read, write, printf, flux) sont extra-logiques : le retour arrière ne les annule pas.

Exercices

Exercice · Prévoir l'effet d'une négation

facile

Avec la base de l’équipe, que répondent ces questions ?

?- not(blesse(chloe)).
?- not(joueur(zinedine)).
?- poste(X, attaque), not(blesse(X)).
?- not(blesse(X)), poste(X, attaque).
?- not(not(blesse(X))).

Voir la solution

Yes : blesse(chloe) échoue.
Yes : Zinedine n’est pas dans la base, donc, en monde clos, il n’est pas joueur.
X = awa, puis X = chloe : les attaquants ne sont pas blessés, et X est connu quand not est appelé.
No : avec X libre, blesse(X) réussit (Bastien), donc not(blesse(X)) échoue avant même de regarder les postes.
Yes, sans lier X : not(blesse(X)) échoue, donc not(not(...)) réussit, mais toutes les liaisons faites à l’intérieur sont défaites. Cela vérifie qu’il existe un blessé, sans dire lequel.

En code

?- not(blesse(chloe)).                   % Yes
?- not(joueur(zinedine)).                % Yes
?- poste(X, attaque), not(blesse(X)).    % X = awa ; X = chloe
?- not(blesse(X)), poste(X, attaque).    % No
?- not(not(blesse(X))).                  % Yes, et X reste libre

joueur = ["awa", "bastien", "chloe", "dylan", "elise"]
blesse = ["bastien"]
poste = [("awa", "attaque"), ("bastien", "defense"), ("chloe", "attaque"),
         ("dylan", "gardien"), ("elise", "defense")]

def prouvable(faits, x=None):      # x=None : variable libre, « il existe un X »
    return any(x is None or f == x for f in faits)

print(not prouvable(blesse, "chloe"))        # 1. True
print(not prouvable(joueur, "zinedine"))     # 2. True : monde clos
# 3. poste(X, attaque), not(blesse(X)) : X est connu quand la négation est testée
print([x for x, p in poste if p == "attaque" and not prouvable(blesse, x)])  # ['awa', 'chloe']
# 4. not(blesse(X)) avec X libre : « aucun blessé n'existe », faux, donc échec
#    avant même de regarder les postes
print([x for x, p in poste if p == "attaque"] if not prouvable(blesse) else [])   # []
# 5. not(not(blesse(X))) : « il existe un blessé », sans dire lequel
print(not (not prouvable(blesse)))           # True

joueur <- c("awa", "bastien", "chloe", "dylan", "elise")
blesse <- c("bastien")
poste <- data.frame(j = c("awa", "bastien", "chloe", "dylan", "elise"),
                    p = c("attaque", "defense", "attaque", "gardien", "defense"))

# x = NULL : variable libre, « il existe un X »
prouvable <- function(faits, x = NULL) if (is.null(x)) length(faits) > 0 else x %in% faits

!prouvable(blesse, "chloe")         # 1. TRUE
!prouvable(joueur, "zinedine")      # 2. TRUE : monde clos
# 3. poste(X, attaque), not(blesse(X)) : X est connu quand la négation est testée
att <- poste$j[poste$p == "attaque"]
att[!sapply(att, prouvable, faits = blesse)]    # "awa" "chloe"
# 4. not(blesse(X)) avec X libre : « aucun blessé n'existe », faux, donc échec
if (!prouvable(blesse)) att else character(0)  # character(0)
# 5. not(not(blesse(X))) : « il existe un blessé », sans dire lequel
!(!prouvable(blesse))               # TRUE

Exercice · Tous, aucun, au moins un

moyen

On dispose d’un prédicat titulaire/1 (par exemple titulaire(awa). et titulaire(elise).). Écrivez, sans utiliser not :

tous(+L) : tous les éléments de L sont titulaires ;
un(+L) : au moins un élément de L est titulaire (une seule réponse, même s’il y en a plusieurs) ;
aucun(+L) : aucun élément de L n’est titulaire (utilisez la coupure-échec) ;
unpas(+L) : au moins un élément de L n’est pas titulaire.

Voir la solution

tous est une simple récursion : une liste vide satisfait trivialement « tous ».
Dans un, la coupure arrête la recherche au premier titulaire, pour ne répondre qu’une fois.
aucun utilise la coupure-échec : dès qu’un titulaire est trouvé, on coupe les autres clauses et on échoue ; sinon, on continue sur la queue.
unpas est la négation de tous, écrite avec le même schéma que not. Cas limite : tous([]) réussit, donc unpas([]) échoue, ce qui est logique, puisqu’une liste vide ne contient aucun élément non titulaire.

En code

tous([]).
tous([X|Q]) :- titulaire(X), tous(Q).

un([X|_]) :- titulaire(X), !.
un([_|Q]) :- un(Q).

aucun([]).
aucun([X|_]) :- titulaire(X), !, fail.
aucun([_|Q]) :- aucun(Q).

unpas(L) :- tous(L), !, fail.
unpas(_).

% ?- tous([awa, elise]).        Yes
% ?- un([awa, bastien]).        Yes (une seule fois)
% ?- aucun([bastien, dylan]).   Yes
% ?- unpas([]).                 No

titulaire = ["awa", "elise"]

def tous(l):                 # tous([X|Q]) :- titulaire(X), tous(Q).
    return not l or (l[0] in titulaire and tous(l[1:]))

def un(l):                   # s'arrête au premier titulaire (la coupure)
    return bool(l) and (l[0] in titulaire or un(l[1:]))

def aucun(l):                # coupure-échec : un titulaire trouvé -> échec
    return not l or (l[0] not in titulaire and aucun(l[1:]))

def unpas(l):                # négation de tous
    return not tous(l)

for l in (["awa", "elise"], ["awa", "bastien"], ["bastien", "dylan"], []):
    print(l, tous(l), un(l), aucun(l), unpas(l))
# ['awa', 'elise'] True True False False
# ['awa', 'bastien'] False True False True
# ['bastien', 'dylan'] False False True True
# [] True False True False

titulaire <- c("awa", "elise")

tous  <- function(l) length(l) == 0 || (l[1] %in% titulaire && tous(l[-1]))
un    <- function(l) length(l) > 0 && (l[1] %in% titulaire || un(l[-1]))   # s'arrête au 1er
aucun <- function(l) length(l) == 0 || (!(l[1] %in% titulaire) && aucun(l[-1]))
unpas <- function(l) !tous(l)                                             # négation de tous

listes <- list(c("awa", "elise"), c("awa", "bastien"), c("bastien", "dylan"), character(0))
t(sapply(listes, function(l) c(tous = tous(l), un = un(l), aucun = aucun(l), unpas = unpas(l))))
#       tous    un aucun unpas
# [1,]  TRUE  TRUE FALSE FALSE
# [2,] FALSE  TRUE FALSE  TRUE
# [3,] FALSE FALSE  TRUE  TRUE
# [4,]  TRUE FALSE  TRUE FALSE     <- la liste vide

Exercice · La diffusion d'une nouvelle

difficile

Chaque jour, un joueur qui connaît une nouvelle la transmet à ses contacts :

contact(awa, bastien).
contact(bastien, chloe).
contact(chloe, awa).
contact(chloe, dylan).
contact(elise, dylan).

Écrivez atteint(+N, +X, ?Y), vrai si une nouvelle lancée par X peut atteindre Y en au plus N jours (N au moins 1).
Écrivez diffusion(+X, +N, -L), où L est la liste triée et sans doublons des joueurs, autres que X, qui connaissent la nouvelle au bout de N jours. Elle doit rendre [] si personne n’est atteint.
Donnez diffusion(awa, 2, L), diffusion(awa, 3, L) et diffusion(dylan, 5, L). Pourquoi la recherche termine-t-elle malgré le cycle Awa, Bastien, Chloé ?

Voir la solution

En un jour, on atteint ses contacts directs ; en N jours, on atteint aussi ce qu’un contact atteint en N − 1 jours (onglet Prolog ci-dessous).
On collecte avec findall, on retire X après coup (Y est alors instancié), et on trie.

Le but collecté est une conjonction entre parenthèses. findall suivi de sort garantit une liste vide plutôt qu’un échec, contrairement à setof.

diffusion(awa, 2, L) donne L = [bastien, chloe]. diffusion(awa, 3, L) donne L = [bastien, chloe, dylan] : au troisième jour, Chloé transmet à Awa (retirée, car c’est l’émettrice) et à Dylan. diffusion(dylan, 5, L) donne L = [], car Dylan n’a aucun contact.

La recherche termine malgré le cycle parce que N décroît à chaque appel récursif et que la garde N > 1 arrête la descente : la profondeur de l’arbre est bornée par N. Les doublons que produisent les différents chemins (Awa, Bastien, Chloé, Awa…) sont éliminés par sort.

En code

atteint(N, X, Y) :- N >= 1, contact(X, Y).
atteint(N, X, Y) :-
    N > 1,
    contact(X, Z),
    N1 is N - 1,
    atteint(N1, Z, Y).

diffusion(X, N, L) :-
    findall(Y, (atteint(N, X, Y), Y \== X), L0),
    sort(L0, L).

% ?- diffusion(awa, 2, L).     L = [bastien, chloe]
% ?- diffusion(awa, 3, L).     L = [bastien, chloe, dylan]
% ?- diffusion(dylan, 5, L).   L = []

contact = [("awa", "bastien"), ("bastien", "chloe"), ("chloe", "awa"),
           ("chloe", "dylan"), ("elise", "dylan")]

def atteint(n, x):
    """Générateur des Y de atteint(N, X, Y), doublons compris."""
    if n >= 1:
        yield from (b for a, b in contact if a == x)       # un jour : contacts directs
    if n > 1:                                              # garde : N décroît
        for a, z in contact:
            if a == x:
                yield from atteint(n - 1, z)

def diffusion(x, n):
    # findall(Y, (atteint(N, X, Y), Y \== X), L0), sort(L0, L)
    return sorted(set(y for y in atteint(n, x) if y != x))

print(diffusion("awa", 2))     # ['bastien', 'chloe']
print(diffusion("awa", 3))     # ['bastien', 'chloe', 'dylan']
print(diffusion("dylan", 5))   # []
print(list(atteint(4, "awa"))) # ['bastien', 'chloe', 'awa', 'dylan', 'bastien'] : doublon

contact <- data.frame(de = c("awa", "bastien", "chloe", "chloe", "elise"),
                      a  = c("bastien", "chloe", "awa", "dylan", "dylan"))

# Tous les Y de atteint(N, X, Y), doublons compris
atteint <- function(n, x) {
  directs <- contact$a[contact$de == x]
  res <- if (n >= 1) directs else c()                    # un jour : contacts directs
  if (n > 1) for (z in directs) res <- c(res, atteint(n - 1, z))   # garde : N décroît
  res
}
# findall(Y, (atteint(N, X, Y), Y \== X), L0), sort(L0, L)
diffusion <- function(x, n) { y <- atteint(n, x); sort(unique(y[y != x])) }

diffusion("awa", 2)     # "bastien" "chloe"
diffusion("awa", 3)     # "bastien" "chloe" "dylan"
diffusion("dylan", 5)   # character(0)
atteint(4, "awa")       # "bastien" "chloe" "awa" "dylan" "bastien" : doublon

Raisonnez par l'échec et collectez les solutions

La négation par l’échec

Le piège des variables libres

Collecter toutes les solutions

findall/3

bagof/3 et setof/3

Un aperçu des entrées-sorties

En résumé

Exercices

`findall/3`

`bagof/3` et `setof/3`