Comprenez comment Prolog cherche

Jusqu’ici, Prolog a répondu à nos questions comme par magie. Mais pour écrire des programmes qui terminent, qui ne répètent pas leurs réponses et qui ne s’égarent pas, il faut savoir exactement ce que fait le moteur. Bonne nouvelle : il n’utilise que deux mécanismes, l’unification et la résolution avec retour arrière, et vous pouvez les dérouler à la main.

Dans ce chapitre, vous allez apprendre à calculer une unification, à suivre la résolution d’une question pas à pas, à dessiner l’arbre de recherche et à lire une trace. Notre fil rouge reste la crêperie, avec la question : « quels plats coûtent moins de 10 euros ? ».

L’unification : rendre deux termes identiques

Quand Prolog cherche à démontrer le but prix(cotriade, E) avec le fait prix(cotriade, 16), il se demande : existe-t-il des valeurs pour les variables qui rendent ces deux termes identiques ? Oui, E = 16. Cette opération s’appelle l’unification, et c’est le cœur du langage : c’est elle qui fait à la fois le passage de paramètres, le filtrage et la construction des résultats.

Deux termes s’unifient selon trois règles.

Deux constantes (atomes ou nombres) s’unifient si elles sont identiques : cotriade et cotriade oui, cotriade et far_breton non, 16 et 16.0 non plus (un entier n’est pas un flottant).
Une variable libre s’unifie avec n’importe quel terme : elle est alors liée à ce terme. Deux variables libres s’unifient en devenant la même variable.
Deux termes composés s’unifient s’ils ont le même foncteur, la même arité, et si leurs arguments s’unifient deux à deux, de gauche à droite, en tenant compte des liaisons déjà faites.

Le résultat est une substitution, un ensemble de liaisons comme { E = 16 }. On peut demander une unification explicitement avec le prédicat = :

?- prix(cotriade, E) = prix(P, 16).
E = 16, P = cotriade

?- rep(entree(E), P) = rep(entree(salade_de_chevre), plat(cotriade)).
E = salade_de_chevre, P = plat(cotriade)

?- f(X, X) = f(far_breton, kouign_amann).
No

Le dernier cas échoue : le premier argument lie X à far_breton, et le second demande alors d’unifier far_breton avec kouign_amann, deux constantes différentes. Le = de Prolog n’est pas une affectation : il ne calcule rien, il cherche seulement à rendre deux termes égaux.

Le plus général unificateur

Considérons f(X, g(Y)) = f(g(Z), X). Le premier argument impose X = g(Z) ; le second devient alors g(Y) = g(Z), d’où Y = Z. La substitution obtenue est { X = g(Z), Y = Z }.

D’autres substitutions rendraient aussi les deux termes égaux, par exemple { X = g(far), Y = far, Z = far }. Mais celle-là est plus contraignante que nécessaire : elle fixe une valeur que rien n’impose. Prolog calcule toujours le plus général unificateur (pgu, en anglais most general unifier ou mgu), celui qui lie le moins possible ; toutes les autres solutions s’en déduisent en précisant les variables restantes. Ce pgu est unique, au renommage des variables près.

L'unification compare les arbres argument par argument, en tenant compte des liaisons déjà faites. En haut elle donne le pgu { X = g(Z), Y = Z } ; en bas, la seconde paire échoue.

Le test d’occurrence

Que donne X = f(X) ? Aucun terme fini n’est égal à un terme qui le contient strictement. Logiquement, l’unification devrait échouer. Le vérifier s’appelle le test d’occurrence (occur check) : avant de lier une variable à un terme, on vérifie qu’elle n’y apparaît pas. Ce test coûte cher, et la plupart des systèmes Prolog, dont ECLiPSe par défaut, ne le font pas : ils acceptent la liaison et fabriquent un terme cyclique. En pratique, cela n’arrive que dans des programmes erronés, mais il faut le savoir.

Sans test d'occurrence, X = f(X) réussit et fabrique un terme cyclique f(f(f(…))), que la logique interdit.

La résolution : remplacer un but par un corps

Posons la question du fil rouge :

?- plat(P), prix(P, E), E < 10.

Prolog maintient une liste de buts à démontrer, ici trois. À chaque étape, il applique la résolution SLD (pour « Sélection Linéaire, clauses Définies ») :

il sélectionne le premier but de la liste, le plus à gauche ;
il cherche, dans l’ordre du fichier, une clause dont la tête s’unifie avec ce but, après avoir renommé les variables de la clause (pour qu’elles ne se mélangent pas avec celles de la question) ;
il remplace le but par le corps de la clause (rien, si c’est un fait), et applique la substitution trouvée à toute la liste.

Quand la liste devient vide, tout a été démontré : c’est un succès, et les liaisons des variables de la question forment la réponse. Si aucune clause ne convient au but sélectionné, c’est un échec sur cette voie.

À chaque étape, le premier but (en ambre) est remplacé par le corps de la clause choisie, et la substitution s'applique au reste. La liste vide signale le succès.

L’arbre de recherche et le retour arrière

À l’étape 2, plusieurs clauses peuvent convenir. Pour plat(P), il y en a deux ; pour viande(P), deux faits. Chaque fois, Prolog prend la première et mémorise qu’il reste des alternatives : c’est un point de choix. Si la suite échoue, ou si vous demandez une autre solution avec ;, il revient au dernier point de choix et essaie la clause suivante, en défaisant les liaisons faites depuis. C’est le retour arrière (backtracking).

L’ensemble des chemins possibles forme l’arbre de recherche : la racine est la question, chaque nœud une liste de buts, chaque branche une clause utilisée, et chaque feuille un succès ou un échec. Voici celui de notre question.

Prolog parcourt cet arbre en profondeur d’abord, de gauche à droite : il descend toujours dans la branche la plus à gauche, et ne remonte qu’en cas d’échec ou de demande d’une autre solution. Ici, il trouve le succès tout de suite ; si vous tapez ;, il revient au point de choix de viande, essaie la galette complète (échec, car 10 < 10 est faux), remonte au point de choix de plat, explore la branche des poissons (deux échecs), puis répond qu’il n’y a plus de solution.

L’ordre des branches est l’ordre des clauses dans le fichier, et l’ordre de traitement des buts est la lecture de gauche à droite. Voilà pourquoi, au chapitre 2, les viandes sortaient avant les poissons, et pourquoi ?- entree(E), dessert(D). énumérait les desserts pour chaque entrée : le but dessert(D) est plus profond dans l’arbre, il varie donc plus vite.

Lire une trace

Pour voir le moteur au travail, ECLiPSe propose un mode trace, qui affiche chaque étape selon le modèle des boîtes : chaque appel de prédicat est une boîte avec quatre portes.

Porte	Signification
`CALL`	on entre dans la boîte : le but est appelé pour la première fois
`EXIT`	on sort avec un succès (ECLiPSe écrit `*EXIT` s’il reste des alternatives)
`FAIL`	on sort sur un échec : plus aucune clause ne convient
`REDO`	on rentre dans la boîte pour chercher une autre solution (retour arrière)

Chaque appel est une boîte : on y entre par CALL, on en sort par EXIT (une solution) ou FAIL (plus rien), et le retour arrière y rentre par REDO.

Voici une trace simplifiée de notre question, jusqu’à la première réponse, puis après un ; :

CALL   plat(P)
CALL   viande(P)
*EXIT  viande(galette_saucisse)
*EXIT  plat(galette_saucisse)
CALL   prix(galette_saucisse, E)
EXIT   prix(galette_saucisse, 9)
CALL   9 < 10
EXIT   9 < 10
                          P = galette_saucisse, E = 9 ;
REDO   plat(galette_saucisse)
REDO   viande(galette_saucisse)
EXIT   viande(galette_complete)
*EXIT  plat(galette_complete)
CALL   prix(galette_complete, E)
EXIT   prix(galette_complete, 10)
CALL   10 < 10
FAIL   10 < 10
...

Dans la vraie trace, chaque ligne porte aussi deux numéros : l’identifiant de la boîte et sa profondeur dans l’arbre. Lire une trace demande un peu d’habitude, mais c’est le meilleur moyen de comprendre pourquoi un programme boucle ou répond deux fois la même chose.

Deux lectures d’un même programme

Vous avez maintenant deux façons de lire un programme Prolog.

La lecture déclarative : chaque clause est un énoncé logique vrai (« P est un plat si P est une viande »). Elle dit quelles réponses sont correctes.
La lecture procédurale : chaque clause est une procédure (« pour démontrer plat(P), démontrer viande(P) »), exécutée dans un ordre précis. Elle dit comment, et dans quel ordre, les réponses sont trouvées, et si la recherche termine.

Un bon programme Prolog est juste pour les deux lectures. La lecture déclarative sert à écrire les clauses ; la lecture procédurale sert à les ordonner. Toute la suite du cours consiste à apprendre à concilier les deux.

En résumé

L’unification rend deux termes identiques en liant des variables ; = la déclenche explicitement et n’a rien d’une affectation.
Prolog calcule le plus général unificateur, et ne fait pas de test d’occurrence par défaut (X = f(X) réussit à tort).
La résolution SLD sélectionne le premier but, l’unifie avec la première clause possible (variables renommées) et le remplace par le corps ; la liste vide signifie succès.
Chaque alternative laissée crée un point de choix ; en cas d’échec ou de ;, Prolog revient au dernier point de choix.
L’arbre de recherche est parcouru en profondeur d’abord, de gauche à droite ; une branche infinie peut cacher des solutions.
La trace montre les portes CALL, EXIT, FAIL et REDO de chaque appel.

Exercices

Exercice · Unifier à la main

facile

Pour chaque paire, dites si les termes s’unifient et, si oui, donnez le plus général unificateur.

commande(T, cotriade) et commande(table2, P)
galette(X, 9) et galette(complete, 10)
f(X, g(a)) et f(b, Y)
f(X, Y, X) et f(Z, Z, far)
plat(P) et prix(P, 16)

Voir la solution

Oui : T = table2, P = cotriade.
Non : X = complete convient, mais 9 et 10 sont deux constantes différentes.
Oui : X = b, Y = g(a).
Oui. Le premier argument lie X = Z, le second Y = Z, le troisième X = far, donc Z = far. Le pgu est X = far, Y = far, Z = far.
Non : les foncteurs diffèrent (plat/1 contre prix/2, ni le nom ni l’arité ne correspondent).

En code

?- commande(T, cotriade) = commande(table2, P).   % T = table2, P = cotriade
?- galette(X, 9) = galette(complete, 10).          % No
?- f(X, g(a)) = f(b, Y).                           % X = b, Y = g(a)
?- f(X, Y, X) = f(Z, Z, far).                      % X = far, Y = far, Z = far
?- plat(P) = prix(P, 16).                          % No

# Termes : variable = chaîne en majuscule, atome = chaîne en minuscule,
# nombre = int, terme composé = tuple (foncteur, arg1, arg2, ...)
def est_var(t):
    return isinstance(t, str) and t[0].isupper()

def valeur(t, s):
    """Suit les liaisons de la substitution s et reconstruit le terme."""
    while est_var(t) and t in s:
        t = s[t]
    return (t[0], *(valeur(a, s) for a in t[1:])) if isinstance(t, tuple) else t

def unifier(a, b, s):
    a, b = valeur(a, s), valeur(b, s)
    if a == b:
        return s
    if est_var(a) or est_var(b):
        return {**s, a: b} if est_var(a) else {**s, b: a}
    if isinstance(a, tuple) and isinstance(b, tuple) and len(a) == len(b) and a[0] == b[0]:
        for x, y in zip(a[1:], b[1:]):
            s = unifier(x, y, s)
            if s is None:
                return None
        return s
    return None                     # constantes ou foncteurs différents

paires = [(("commande", "T", "cotriade"), ("commande", "table2", "P")),
          (("galette", "X", 9), ("galette", "complete", 10)),
          (("f", "X", ("g", "a")), ("f", "b", "Y")),
          (("f", "X", "Y", "X"), ("f", "Z", "Z", "far")),
          (("plat", "P"), ("prix", "P", 16))]
for a, b in paires:
    s = unifier(a, b, {})
    print("échec" if s is None else {v: valeur(v, s) for v in sorted(s)})
# T = table2, P = cotriade
# échec
# X = b, Y = g(a)
# X = far, Y = far, Z = far
# échec

# Termes : variable = chaîne en majuscule, atome = chaîne en minuscule,
# nombre = numérique, terme composé = list(foncteur, arg1, arg2, ...)
est_var <- function(t) is.character(t) && grepl("^[A-Z]", t)

valeur <- function(t, s) {          # suit les liaisons et reconstruit le terme
  while (est_var(t) && !is.null(s[[t]])) t <- s[[t]]
  if (is.list(t)) c(t[1], lapply(t[-1], valeur, s = s)) else t
}
unifier <- function(a, b, s) {
  if (is.null(s)) return(NULL)      # un échec se propage
  a <- valeur(a, s); b <- valeur(b, s)
  if (identical(a, b)) return(s)
  if (est_var(a)) { s[[a]] <- b; return(s) }
  if (est_var(b)) { s[[b]] <- a; return(s) }
  if (is.list(a) && is.list(b) && length(a) == length(b) && identical(a[[1]], b[[1]])) {
    for (i in seq_along(a)[-1]) s <- unifier(a[[i]], b[[i]], s)
    return(s)
  }
  NULL                              # constantes ou foncteurs différents
}
ecrire <- function(t) if (is.list(t))
  paste0(t[[1]], "(", paste(sapply(t[-1], ecrire), collapse = ", "), ")") else t

paires <- list(
  list(list("commande", "T", "cotriade"), list("commande", "table2", "P")),
  list(list("galette", "X", 9), list("galette", "complete", 10)),
  list(list("f", "X", list("g", "a")), list("f", "b", "Y")),
  list(list("f", "X", "Y", "X"), list("f", "Z", "Z", "far")),
  list(list("plat", "P"), list("prix", "P", 16)))
for (p in paires) {
  s <- unifier(p[[1]], p[[2]], list())
  if (is.null(s)) cat("échec\n") else
    cat(paste(sort(names(s)), sapply(sort(names(s)), function(v) ecrire(valeur(v, s))),
              sep = " = ", collapse = ", "), "\n")
}
# T = table2, P = cotriade
# échec
# X = b, Y = g(a)
# X = far, Y = far, Z = far
# échec

Exercice · Dessiner un arbre de recherche

moyen

On considère le programme suivant :

aime(lea, crepes).
aime(lea, cidre).
aime(marc, cidre).

partage(X, Y) :- aime(X, Z), aime(Y, Z), X \= Y.

Dessinez l’arbre de recherche de ?- partage(lea, Y). et donnez les réponses dans l’ordre où Prolog les trouve.

Voir la solution

La question se réécrit en aime(lea, Z), aime(Y, Z), lea \= Y.

aime(lea, Z) a deux solutions, donc deux branches.
- Branche Z = crepes : il reste aime(Y, crepes), lea \= Y. Seul aime(lea, crepes) convient, donc Y = lea, puis lea \= lea échoue.
- Branche Z = cidre : il reste aime(Y, cidre), lea \= Y. Deux faits conviennent.
  - Y = lea : lea \= lea échoue.
  - Y = marc : lea \= marc réussit. Succès.

L’arbre a trois feuilles : deux échecs et un succès. Prolog répond une seule fois, Y = marc, puis « No » si l’on demande une autre solution. Le test X \= Y sert à éviter la réponse absurde « Léa partage un goût avec elle-même ».

En code

% partage/2 instrumenté : chaque feuille de l'arbre s'affiche
partage_trace(X, Y) :-
    aime(X, Z),
    aime(Y, Z),
    (   X \= Y
    ->  writeln(succes(Z, Y))
    ;   writeln(echec(Z, Y)), fail
    ).

% ?- partage_trace(lea, Y).
% echec(crepes, lea)
% echec(cidre, lea)
% succes(cidre, marc)
% Y = marc

aime = [("lea", "crepes"), ("lea", "cidre"), ("marc", "cidre")]

def partage(x):
    # partage(X, Y) :- aime(X, Z), aime(Y, Z), X \= Y.
    for a, z in aime:                      # aime(lea, Z) : une branche par fait
        if a != x:
            continue
        for y, z2 in aime:                 # aime(Y, Z)
            if z2 != z:
                continue
            ok = x != y                    # X \= Y
            print(f"Z = {z}, Y = {y} : {'succès' if ok else 'échec'}")
            if ok:
                yield y

print(list(partage("lea")))
# Z = crepes, Y = lea : échec
# Z = cidre, Y = lea : échec
# Z = cidre, Y = marc : succès
# ['marc']

aime <- data.frame(qui  = c("lea", "lea", "marc"),
                   quoi = c("crepes", "cidre", "cidre"))

# partage(X, Y) :- aime(X, Z), aime(Y, Z), X \= Y.
partage <- function(x) {
  reponses <- c()
  for (z in aime$quoi[aime$qui == x]) {          # aime(lea, Z) : une branche par fait
    for (y in aime$qui[aime$quoi == z]) {        # aime(Y, Z)
      ok <- x != y                               # X \= Y
      cat(sprintf("Z = %s, Y = %s : %s\n", z, y, if (ok) "succès" else "échec"))
      if (ok) reponses <- c(reponses, y)
    }
  }
  reponses
}
partage("lea")
# Z = crepes, Y = lea : échec
# Z = cidre, Y = lea : échec
# Z = cidre, Y = marc : succès
# "marc"

Exercice · Un unificateur piégé

difficile

Calculez le plus général unificateur de f(X, g(X), Y) et f(h(Z), Y, W).
Que devrait répondre ?- p(X, f(X)) = p(Y, Y). en logique ? Et que répond un système Prolog sans test d’occurrence ? Expliquez.

Voir la solution

Premier argument : X = h(Z). Deuxième argument : g(X) = Y, soit Y = g(h(Z)). Troisième argument : Y = W, donc W = g(h(Z)). Le pgu est X = h(Z), Y = g(h(Z)), W = g(h(Z)). Z reste libre : c’est ce qui rend l’unificateur le plus général.
Le premier argument impose X = Y. Le second demande alors f(X) = X : X devrait être égal à un terme qui le contient strictement, ce qui est impossible pour un terme fini. En logique, l’unification échoue. Sans test d’occurrence, Prolog lie quand même X à f(X) et crée un terme cyclique, f(f(f(…))) à l’infini ; la question réussit donc à tort, et l’affichage du résultat peut même boucler. Pour obtenir le comportement logique, on utilise le prédicat unify_with_occurs_check/2, disponible dans la plupart des systèmes.

En code

?- f(X, g(X), Y) = f(h(Z), Y, W).
% X = h(Z), Y = g(h(Z)), W = g(h(Z))

?- unify_with_occurs_check(p(X, f(X)), p(Y, Y)).
% No : le test d'occurrence refuse X = f(X)

?- p(X, f(X)) = p(Y, Y).
% réussit à tort : X = Y = f(f(f(...))), un terme cyclique

def est_var(t):
    return isinstance(t, str) and t[0].isupper()

def deref(t, s):                     # suit les liaisons d'une variable
    while est_var(t) and t in s:
        t = s[t]
    return t

def apparait(v, t, s):               # test d'occurrence : v figure-t-il dans t ?
    t = deref(t, s)
    return t == v or (isinstance(t, tuple) and any(apparait(v, a, s) for a in t[1:]))

def unifier(a, b, s, occurs):
    a, b = deref(a, s), deref(b, s)
    if a == b:
        return s
    if est_var(b):
        a, b = b, a
    if est_var(a):
        return None if occurs and apparait(a, b, s) else {**s, a: b}
    if isinstance(a, tuple) and isinstance(b, tuple) and len(a) == len(b) and a[0] == b[0]:
        for x, y in zip(a[1:], b[1:]):
            if (s := unifier(x, y, s, occurs)) is None:
                return None
        return s
    return None

def valeur(t, s):                    # terme final (boucle si le terme est cyclique)
    t = deref(t, s)
    return (t[0], *(valeur(a, s) for a in t[1:])) if isinstance(t, tuple) else t

s = unifier(("f", "X", ("g", "X"), "Y"), ("f", ("h", "Z"), "Y", "W"), {}, True)
print({v: valeur(v, s) for v in "XYW"})
# {'X': ('h', 'Z'), 'Y': ('g', ('h', 'Z')), 'W': ('g', ('h', 'Z'))}

a, b = ("p", "X", ("f", "X")), ("p", "Y", "Y")
print(unifier(a, b, {}, occurs=True))     # None : échec, comme en logique
s = unifier(a, b, {}, occurs=False)
print(s)                                  # {'Y': 'X', 'X': ('f', 'X')} : X = f(X)
try:
    valeur("X", s)
except RecursionError:
    print("terme cyclique f(f(f(...)))")  # l'affichage ne termine pas

est_var <- function(t) is.character(t) && grepl("^[A-Z]", t)
deref <- function(t, s) { while (est_var(t) && !is.null(s[[t]])) t <- s[[t]]; t }
apparait <- function(v, t, s) {       # test d'occurrence : v figure-t-il dans t ?
  t <- deref(t, s)
  identical(t, v) || (is.list(t) && any(sapply(t[-1], apparait, v = v, s = s)))
}
unifier <- function(a, b, s, occurs) {
  if (is.null(s)) return(NULL)
  a <- deref(a, s); b <- deref(b, s)
  if (identical(a, b)) return(s)
  if (est_var(b)) { tmp <- a; a <- b; b <- tmp }
  if (est_var(a)) {
    if (occurs && apparait(a, b, s)) return(NULL)
    s[[a]] <- b; return(s)
  }
  if (is.list(a) && is.list(b) && length(a) == length(b) && identical(a[[1]], b[[1]])) {
    for (i in seq_along(a)[-1]) s <- unifier(a[[i]], b[[i]], s, occurs)
    return(s)
  }
  NULL
}
ecrire <- function(t, s) {            # affiche le terme final (boucle s'il est cyclique)
  t <- deref(t, s)
  if (!is.list(t)) return(t)
  paste0(t[[1]], "(", paste(sapply(t[-1], ecrire, s = s), collapse = ", "), ")")
}
s <- unifier(list("f", "X", list("g", "X"), "Y"), list("f", list("h", "Z"), "Y", "W"),
             list(), occurs = TRUE)
sapply(c("X", "Y", "W"), ecrire, s = s)      # X = h(Z), Y = g(h(Z)), W = g(h(Z))

a <- list("p", "X", list("f", "X")); b <- list("p", "Y", "Y")
is.null(unifier(a, b, list(), occurs = TRUE))       # TRUE : échec, comme en logique
s <- unifier(a, b, list(), occurs = FALSE)          # réussit : Y = X, X = f(X)
tryCatch(ecrire("X", s), error = function(e) "terme cyclique f(f(f(...)))")