Définissez des relations récursives

Jusqu’ici, nos règles définissaient une relation à partir d’autres relations : un plat, c’est une viande ou un poisson. Mais certaines relations se définissent en fonction d’elles-mêmes. Un ancêtre, c’est un parent, ou le parent d’un ancêtre. Un trajet en train, c’est une liaison directe, ou une liaison suivie d’un trajet. C’est la récursivité, et en Prolog c’est le seul moyen de répéter un calcul : il n’y a pas de boucle.

Dans ce chapitre, vous allez écrire des règles récursives sur un petit réseau ferré de l’Ouest, et découvrir que l’ordre des règles et des buts, anodin au chapitre 2, décide ici de l’ordre des solutions et même de la terminaison du programme.

Le fil rouge : un réseau de liaisons

Voici quelques liaisons ferroviaires directes, chacune à sens unique pour simplifier :

% liaison(Depart, Arrivee) : un train direct relie Depart à Arrivee
liaison(rennes, saint_malo).
liaison(rennes, laval).
liaison(rennes, vannes).
liaison(laval, le_mans).
liaison(le_mans, paris).
liaison(vannes, nantes).
liaison(nantes, angers).
liaison(angers, le_mans).

Rennes n’a pas de liaison directe avec Paris. Pourtant, on peut y aller, et même de deux façons : par Laval et Le Mans, ou par Vannes, Nantes, Angers et Le Mans. Comment le dire à Prolog ?

Écrire une règle récursive

Il existe un chemin de X à Y dans deux cas :

soit une liaison directe relie X à Y ;
soit une liaison relie X à une ville intermédiaire Z, et il existe un chemin de Z à Y.

Ce raisonnement se traduit mot pour mot :

chemin(X, Y) :- liaison(X, Y).                 % cas de base (condition d'arrêt)
chemin(X, Y) :- liaison(X, Z), chemin(Z, Y).   % cas récursif

La seconde clause utilise chemin dans son propre corps. Mais pourquoi cela ne tourne-t-il pas en rond ? Parce que chaque appel récursif porte sur un problème plus petit : de Z, on est plus près de Y que de X, et le but liaison(X, Z) a fait avancer d’une ville. Tant que le réseau ne contient pas de boucle, les chemins finissent par s’épuiser.

?- chemin(rennes, paris).
Yes ;
Yes ;
No

Deux fois « Yes » : Prolog a trouvé deux démonstrations, une par itinéraire. Pour la première, il essaie liaison(rennes, Z) : Saint-Malo mène à une impasse (aucune liaison n’en part), puis Laval donne chemin(laval, paris), qui aboutit par Le Mans. Au retour arrière, Vannes donne le second itinéraire.

Chaque valeur de Z ouvre une branche. Saint-Malo mène à une impasse ; Laval donne le premier Yes, Vannes le second, au retour arrière.

Le schéma de la fermeture transitive

La relation chemin est la fermeture transitive de liaison : la plus petite relation qui contient liaison et qui est transitive. Le schéma est toujours le même, quelle que soit la relation de départ :

fermeture(X, Y) :- rel(X, Y).
fermeture(X, Y) :- rel(X, Z), fermeture(Z, Y).

Avec rel = parent, on obtient ancetre ; avec rel = sous_categorie, on obtient « est une sorte de » ; avec rel = manager, toute la chaîne hiérarchique. Si l’on veut aussi que chaque élément soit relié à lui-même (la fermeture réflexo-transitive), on remplace le cas de base par fermeture(X, X).

Construire un itinéraire

Savoir qu’un chemin existe, c’est bien ; connaître les villes traversées, c’est mieux. Nous allons renvoyer l’itinéraire sous forme de terme construit, comme au chapitre 2. On représente la suite des villes intermédiaires avec une constante rien (aucune ville) et un foncteur par/2 : par(laval, par(le_mans, rien)) se lit « par Laval, puis par Le Mans, puis plus rien ».

% trajet(X, Y, T) : T décrit les villes intermédiaires entre X et Y
trajet(X, Y, rien) :- liaison(X, Y).
trajet(X, Y, par(Z, T)) :- liaison(X, Z), trajet(Z, Y, T).

?- trajet(rennes, paris, T).
T = par(laval, par(le_mans, rien)) ;
T = par(vannes, par(nantes, par(angers, par(le_mans, rien)))) ;
No

Regardez la seconde clause : le résultat par(Z, T) est écrit dans la tête, avant même que T soit connu. Prolog construit le terme au fur et à mesure de la descente, chaque appel récursif remplissant le « trou » T laissé par l’appel précédent. C’est une technique fondamentale, que vous retrouverez avec les listes : au chapitre 6, par(laval, par(le_mans, rien)) deviendra simplement [laval, le_mans].

Le terme résultat est posé dans la tête avant d'être complet : chaque appel récursif remplit le trou (en ambre) laissé par le précédent.

L’ordre des règles : l’ordre des solutions

Passons à une famille, où les liens sont parent(Parent, Enfant) :

parent(anne, bruno).
parent(bruno, chloe).
parent(chloe, denis).

ancetre(X, Y) :- parent(X, Y).
ancetre(X, Y) :- parent(X, Z), ancetre(Z, Y).

La question ?- ancetre(anne, Y). donne bruno, puis chloe, puis denis : du plus proche au plus lointain. Échangeons maintenant les deux clauses d’ancetre, en mettant le cas récursif en premier. Les réponses deviennent denis, chloe, bruno : l’arbre de recherche a les mêmes branches, mais dans l’ordre inverse, et Prolog descend d’abord jusqu’au bout de la lignée avant de remonter.

Échanger les clauses retourne l'arbre comme un miroir : mêmes feuilles, donc mêmes solutions, mais produites dans l'ordre inverse.

L’ensemble des solutions n’a pas changé, seulement leur ordre. C’est la règle générale : l’ordre des clauses fixe l’ordre des branches de l’arbre, donc l’ordre dans lequel les solutions sont produites. Sur un arbre fini, c’est une affaire de présentation ; mais si une branche est infinie, la placer à gauche empêche de jamais atteindre les solutions situées à sa droite.

L’ordre des buts : terminer ou boucler

Voici une variante tentante de chemin, où l’on inverse les deux buts du cas récursif :

chemin(X, Y) :- liaison(X, Y).
chemin(X, Y) :- chemin(X, Z), liaison(Z, Y).   % récursion à gauche

Logiquement, elle est tout aussi juste : un chemin de X à Z suivi d’une liaison de Z à Y. Mais la procédure est désastreuse. Pour démontrer chemin(X, Y), la seconde clause appelle immédiatement chemin(X, Z), avec le même X et sans avoir avancé d’une seule ville. Cet appel a lui aussi une seconde clause qui rappelle chemin(X, Z2), et ainsi de suite : l’arbre possède une branche infinie. On parle de récursion à gauche.

Selon l’ordre des clauses et des buts, on obtient quatre versions, qui n’ont pas du tout le même comportement :

Version	Clauses	Sur `chemin(rennes, paris)`	Sur `chemin(paris, rennes)`
A	base, puis `liaison(X, Z), chemin(Z, Y)`	2 solutions, puis « No »	« No »
B	`liaison(X, Z), chemin(Z, Y)`, puis base	2 solutions, puis « No »	« No »
C	base, puis `chemin(X, Z), liaison(Z, Y)`	2 solutions, puis boucle	boucle
D	`chemin(X, Z), liaison(Z, Y)`, puis base	boucle sans rien afficher	boucle

La version C est la plus trompeuse : elle trouve les bonnes réponses, et ne boucle que lorsqu’on en demande une de plus, ou quand la réponse est « non ». Un test rapide avec une question qui réussit ne révèle rien.

Avec liaison(X, Z) d'abord, l'arbre est fini et Prolog répond No. Avec chemin(X, Z) d'abord, chaque appel en crée un autre sans avancer : la branche est infinie.

Même la bonne version A a une limite : si le réseau contient un cycle (ajoutez liaison(paris, rennes).), chemin peut tourner indéfiniment autour, car rien n’interdit de repasser par une ville. Pour s’en protéger, il faut mémoriser les villes déjà visitées dans une liste, ce que vous saurez faire au chapitre 6. Les moteurs Datalog et le SQL récursif, eux, gèrent ce cas automatiquement (chapitre 9).

Les modes d’utilisation

Un prédicat Prolog n’a pas d’entrées ni de sorties fixées : chaque argument peut être connu ou inconnu à l’appel. On décrit la façon dont on l’appelle par un mode, avec une notation par argument :

Symbole	L’argument, au moment de l’appel…
`+`	est instancié (ce n’est pas une variable libre)
`-`	est une variable libre
`?`	peut être l’un ou l’autre
`++`	est clos (ground) : il ne contient aucune variable, même à l’intérieur

Notre prédicat chemin/2 fonctionne dans tous les modes, sur un réseau sans cycle :

chemin(+, +) vérifie : ?- chemin(rennes, paris). ;
chemin(+, -) énumère les destinations : ?- chemin(rennes, Y). ;
chemin(-, +) énumère les origines : ?- chemin(X, paris). ;
chemin(-, -) énumère tous les couples reliés.

C’est ce qu’on appelle l’aspect relationnel de Prolog : un même prédicat répond à plusieurs questions. Mais ce n’est pas automatique. Vous verrez que certains prédicats, notamment ceux qui calculent avec is (chapitre 5), ne marchent que dans certains modes. ECLiPSe permet de documenter le mode prévu avec une déclaration comme :- mode trajet(++, ++, -)., et une bonne habitude est de l’indiquer au moins en commentaire.

En résumé

Une règle récursive définit une relation en fonction d’elle-même ; elle a un cas de base et un cas récursif qui se rapproche du cas de base.
La fermeture transitive d’une relation rel s’écrit toujours avec le même schéma en deux clauses ; la version réflexo-transitive part de f(X, X).
Un résultat se construit dans la tête de la clause récursive, chaque appel complétant le terme laissé ouvert par le précédent.
L’ordre des règles fixe l’ordre des solutions ; une branche infinie à gauche masque les solutions situées à sa droite.
L’ordre des buts peut décider de la terminaison : la récursion à gauche boucle ; faites avancer le calcul avant l’appel récursif.
Les modes (+, -, ?, ++) décrivent comment un prédicat est appelé ; beaucoup de prédicats marchent dans plusieurs modes, mais pas tous.

Exercices

Exercice · Des relations familiales

facile

Avec les faits parent/2 du chapitre, écrivez :

grand_parent(X, Y) : X est un grand-parent de Y ;
descendant(X, Y) : X est un descendant de Y (sans réutiliser ancetre) ;
meme_lignee(X, Y) : X est Y, ou un ancêtre de Y (fermeture réflexo-transitive de parent).

Quel est le mode naturel de grand_parent si l’on cherche les petits-enfants d’Anne ?

Voir la solution

Pour descendant, X est un descendant de Y si Y est parent de X, ou si un parent Z de X est lui-même descendant de Y. Le premier but, parent(Z, X), remonte d’une génération avant l’appel récursif : il fait bien avancer le calcul.

Pour les petits-enfants d’Anne, on pose ?- grand_parent(anne, Y). : le mode est grand_parent(+, -). La seule réponse est Y = chloe.

En code

grand_parent(X, Y) :- parent(X, Z), parent(Z, Y).

descendant(X, Y) :- parent(Y, X).
descendant(X, Y) :- parent(Z, X), descendant(Z, Y).

meme_lignee(X, X).
meme_lignee(X, Y) :- parent(X, Z), meme_lignee(Z, Y).

% ?- grand_parent(anne, Y).    Y = chloe
% ?- descendant(X, anne).      X = bruno ; X = chloe ; X = denis
% ?- meme_lignee(anne, Y).     Y = anne ; Y = bruno ; Y = chloe ; Y = denis

parent = [("anne", "bruno"), ("bruno", "chloe"), ("chloe", "denis")]
personnes = ["anne", "bruno", "chloe", "denis"]

def grand_parent(x, y):
    return any((x, z) in parent and (z, y) in parent for z in personnes)

def descendant(x, y):          # X est un descendant de Y
    if (y, x) in parent:                       # clause 1 : parent(Y, X)
        return True
    return any(descendant(z, y) for z, e in parent if e == x)   # parent(Z, X), descendant(Z, Y)

def meme_lignee(x, y):         # fermeture réflexo-transitive de parent
    return x == y or any(meme_lignee(z, y) for p, z in parent if p == x)

print([y for y in personnes if grand_parent("anne", y)])   # ['chloe']  mode (+, -)
print([x for x in personnes if descendant(x, "anne")])     # ['bruno', 'chloe', 'denis']
print([y for y in personnes if meme_lignee("anne", y)])    # ['anne', 'bruno', 'chloe', 'denis']

parent <- data.frame(p = c("anne", "bruno", "chloe"), e = c("bruno", "chloe", "denis"))
personnes <- c("anne", "bruno", "chloe", "denis")
est_parent <- function(x, y) any(parent$p == x & parent$e == y)

grand_parent <- function(x, y) any(sapply(personnes, function(z) est_parent(x, z) && est_parent(z, y)))

descendant <- function(x, y) {          # X est un descendant de Y
  if (est_parent(y, x)) return(TRUE)    # clause 1 : parent(Y, X)
  any(sapply(parent$p[parent$e == x], descendant, y = y))   # parent(Z, X), descendant(Z, Y)
}
meme_lignee <- function(x, y)           # fermeture réflexo-transitive de parent
  x == y || any(sapply(parent$e[parent$p == x], meme_lignee, y = y))

Filter(function(y) grand_parent("anne", y), personnes)   # "chloe"  mode (+, -)
Filter(function(x) descendant(x, "anne"), personnes)     # "bruno" "chloe" "denis"
Filter(function(y) meme_lignee("anne", y), personnes)    # "anne" "bruno" "chloe" "denis"

Exercice · Prédire l'ordre des itinéraires

moyen

On échange les deux clauses de trajet/3 (cas récursif en premier). Donnez les réponses à ?- trajet(rennes, le_mans, T). dans l’ordre, pour la version d’origine puis pour la version modifiée.

Voir la solution

Deux itinéraires existent : direct par Laval, et par Vannes, Nantes et Angers.

Version d’origine (cas de base en premier). Au premier niveau, liaison(rennes, le_mans) échoue ; le cas récursif essaie Saint-Malo (impasse), puis Laval : dans trajet(laval, le_mans, T1), le cas de base réussit tout de suite. Puis Vannes, qui mène au second itinéraire.

T = par(laval, rien)
T = par(vannes, par(nantes, par(angers, rien)))

Version modifiée (cas récursif en premier). À chaque niveau, Prolog essaie d’abord d’aller plus loin. Depuis Laval, il tente liaison(laval, Z) avec Z = le_mans, puis trajet(le_mans, le_mans, T2) : le Mans mène à Paris, d’où ne part aucune liaison, donc échec ; le cas de base liaison(le_mans, le_mans) échoue aussi. Il revient alors au cas de base liaison(laval, le_mans), qui réussit. L’ordre des deux solutions est le même ici, car les deux itinéraires sont dans des branches différentes dès le premier niveau (Laval avant Vannes, dans l’ordre des faits). Seule l’exploration interne change : la version modifiée essaie des chemins plus longs avant les plus courts à l’intérieur de chaque branche.

En code

% version d'origine : cas de base en premier
trajet(X, Y, rien) :- liaison(X, Y).
trajet(X, Y, par(Z, T)) :- liaison(X, Z), trajet(Z, Y, T).

% version modifiée : cas récursif en premier
trajet2(X, Y, par(Z, T)) :- liaison(X, Z), trajet2(Z, Y, T).
trajet2(X, Y, rien) :- liaison(X, Y).

% ?- trajet(rennes, le_mans, T).     et de même avec trajet2 :
% T = par(laval, rien) ;
% T = par(vannes, par(nantes, par(angers, rien))) ;
% No

liaison = [("rennes", "saint_malo"), ("rennes", "laval"), ("rennes", "vannes"),
           ("laval", "le_mans"), ("le_mans", "paris"), ("vannes", "nantes"),
           ("nantes", "angers"), ("angers", "le_mans")]

def trajet(x, y, base_en_premier, appels):
    """Générateur : les T de trajet(X, Y, T), dans l'ordre de Prolog."""
    appels.append(x)
    def base():                                   # trajet(X, Y, rien) :- liaison(X, Y).
        if (x, y) in liaison:
            yield "rien"
    def recursif():                               # trajet(X, Y, par(Z, T)) :- ...
        for a, z in liaison:
            if a == x:
                for t in trajet(z, y, base_en_premier, appels):
                    yield ("par", z, t)
    clauses = [base, recursif] if base_en_premier else [recursif, base]
    for clause in clauses:
        yield from clause()

for version in (True, False):                     # d'origine, puis modifiée
    appels = []
    g = trajet("rennes", "le_mans", version, appels)
    premiere = next(g)
    print("appels avant la 1re réponse :", appels)
    print([premiere, *g])
# d'origine : ['rennes', 'saint_malo', 'laval']
# modifiée  : ['rennes', 'saint_malo', 'laval', 'le_mans', 'paris']
# les deux  : [('par', 'laval', 'rien'), ('par', 'vannes', ('par', 'nantes', ('par', 'angers', 'rien')))]

liaison <- data.frame(
  de = c("rennes", "rennes", "rennes", "laval", "le_mans", "vannes", "nantes", "angers"),
  a  = c("saint_malo", "laval", "vannes", "le_mans", "paris", "nantes", "angers", "le_mans"))
journal <- c()                          # ordre d'exploration : appels et succès

# Toutes les solutions T de trajet(X, Y, T), dans l'ordre de Prolog
trajet <- function(x, y, base_en_premier) {
  journal <<- c(journal, x)
  base <- function()                    # trajet(X, Y, rien) :- liaison(X, Y).
    if (any(liaison$de == x & liaison$a == y)) {
      journal <<- c(journal, "[OK]"); list("rien") } else list()
  recursif <- function() {              # trajet(X, Y, par(Z, T)) :- ...
    sol <- list()
    for (z in liaison$a[liaison$de == x])
      for (t in trajet(z, y, base_en_premier)) sol <- c(sol, list(paste0("par(", z, ", ", t, ")")))
    sol
  }
  if (base_en_premier) c(base(), recursif()) else c(recursif(), base())
}
for (version in c(TRUE, FALSE)) {       # d'origine, puis modifiée
  journal <- c()
  print(unlist(trajet("rennes", "le_mans", version)))
  cat(journal, "\n")
}
# les deux : "par(laval, rien)" "par(vannes, par(nantes, par(angers, rien)))"
# d'origine : rennes saint_malo laval [OK] le_mans paris vannes nantes angers [OK] le_mans paris
# modifiée  : rennes saint_malo laval le_mans paris [OK] vannes nantes angers le_mans paris [OK]

Exercice · Diagnostiquer une boucle

difficile

Un camarade écrit la fermeture symétrique et transitive d’une relation de voisinage entre communes :

voisin(rennes, cesson).
voisin(cesson, thorigne).

proche(X, Y) :- voisin(X, Y).
proche(X, Y) :- voisin(Y, X).
proche(X, Y) :- proche(X, Z), proche(Z, Y).

Que se passe-t-il pour ?- proche(rennes, thorigne). ? Et pour ?- proche(thorigne, brest). ?
Proposez une réécriture qui termine sur ces deux questions (on suppose toujours qu’il n’y a qu’un nombre fini de communes et qu’on accepte de revisiter des communes).

Voir la solution

Pour proche(rennes, thorigne), les deux premières clauses échouent ; la troisième appelle proche(rennes, Z), qui donne Z = cesson par la première clause, puis proche(cesson, thorigne) réussit : la réponse Yes arrive. Mais si l’on demande une autre solution, ou si l’on pose proche(thorigne, brest) (qui n’a aucune solution), Prolog finit par explorer la troisième clause de proche(X, Z) qui rappelle proche(X, Z2) avec le même X, sans rien consommer : c’est une récursion à gauche, et le programme boucle.
On fait d’abord avancer d’un pas avec un prédicat non récursif, puis on appelle la récursion (onglet Prolog ci-dessous).

Cela supprime la récursion à gauche. Mais attention : lien est symétrique, donc le graphe contient des cycles (Rennes, Cesson, Rennes…). proche(thorigne, brest) boucle encore, en faisant des allers-retours. La vraie solution consiste à mémoriser les communes visitées dans une liste et à refuser d’y revenir, ce que permet le chapitre 6 (voir le prédicat chemin_sur/4 dans ses exercices). C’est aussi exactement ce que Datalog garantit sans effort (chapitre 9).

En code

lien(X, Y) :- voisin(X, Y).
lien(X, Y) :- voisin(Y, X).

proche(X, Y) :- lien(X, Y).
proche(X, Y) :- lien(X, Z), proche(Z, Y).

% ?- proche(rennes, thorigne).   Yes
% ?- proche(thorigne, brest).    boucle encore (allers-retours sur le cycle) :
%    il faut une liste des communes visitées (chapitre 6)

voisin = [("rennes", "cesson"), ("cesson", "thorigne")]

def proche_naif(x):            # les Y de proche(X, Y), clauses dans l'ordre
    yield from (b for a, b in voisin if a == x)          # voisin(X, Y)
    yield from (a for a, b in voisin if b == x)          # voisin(Y, X)
    for z in proche_naif(x):                             # proche(X, Z), proche(Z, Y)
        yield from proche_naif(z)

def lien(x):
    return [b for a, b in voisin if a == x] + [a for a, b in voisin if b == x]

def proche_lien(x):            # lien(X, Z), proche(Z, Y) : plus de récursion à gauche
    yield from lien(x)
    for z in lien(x):
        yield from proche_lien(z)

def proche_vus(x, vus=None):   # la vraie solution : mémoriser les communes visitées
    vus = vus or {x}
    for z in lien(x):
        if z not in vus:
            vus.add(z)
            yield z
            yield from proche_vus(z, vus)

for nom, f in [("naïf", proche_naif), ("lien", proche_lien), ("visités", proche_vus)]:
    print(nom, "thorigne" in f("rennes"), end=" ")      # proche(rennes, thorigne)
    try:
        print("brest" in f("thorigne"))                  # proche(thorigne, brest)
    except RecursionError:
        print("boucle")
# naïf True boucle
# lien True boucle
# visités True False

voisin <- data.frame(a = c("rennes", "cesson"), b = c("cesson", "thorigne"))
lien <- function(x) c(voisin$b[voisin$a == x], voisin$a[voisin$b == x])

# proche(X, Y) :- lien(X, Y).  proche(X, Y) :- lien(X, Z), proche(Z, Y).
proche_lien <- function(x, y)
  y %in% lien(x) || any(sapply(lien(x), proche_lien, y = y))

# La vraie solution : mémoriser les communes visitées
proche_vus <- function(x, y, vus = x) {
  for (z in setdiff(lien(x), vus)) {
    if (z == y || proche_vus(z, y, c(vus, z))) return(TRUE)
    vus <- c(vus, z)
  }
  FALSE
}
proche_lien("rennes", "thorigne")                     # TRUE
tryCatch(proche_lien("thorigne", "brest"),
         error = function(e) "boucle (récursion infinie)")
proche_vus("rennes", "thorigne")                      # TRUE
proche_vus("thorigne", "brest")                       # FALSE