Maîtrisez la coupure

Le retour arrière est la grande force de Prolog : il explore toutes les pistes à votre place. Mais c’est parfois une faiblesse. Quand vous savez qu’une piste est la bonne, inutile de garder les autres en réserve ; et quand un choix exclut les suivants (« si l’enfant a moins de 14 ans, tarif enfant, sinon… »), il faut pouvoir le dire. C’est le rôle de la coupure (cut), notée !.

Dans ce chapitre, vous allez apprendre ce que fait exactement la coupure, la placer sans casser vos programmes, et distinguer les coupures inoffensives des coupures qui changent le sens du programme. Fil rouge : la grille tarifaire d’un cinéma rennais.

Ce que fait la coupure

La coupure est un prédicat prédéfini sans argument, qui s’écrit ! dans le corps d’une clause. Sur le plan logique, elle ne dit rien : elle réussit toujours. Mais elle a un effet de bord sur l’exécution : elle supprime des points de choix, c’est-à-dire des alternatives que Prolog gardait en réserve.

Précisément, quand une clause de la forme p :- b1, b2, !, b3. exécute son !, deux sortes d’alternatives sont abandonnées :

• les autres clauses de p qui n’ont pas encore été essayées ;
• les autres solutions des buts situés à gauche du ! dans la clause (b1 et b2).

En revanche, les buts à droite du ! (b3) ne sont pas touchés : s’ils ont plusieurs solutions, le retour arrière les explore normalement. Et si b3 échoue, p tout entier échoue, puisqu’il ne reste plus aucune alternative.

Pensez à la coupure comme à un engagement : « arrivé ici, je choisis cette clause et ces valeurs, définitivement ». Dans l’arbre de recherche, elle élague toutes les branches en attente entre le nœud où p a été appelé et le nœud où l’on se trouve.

Exemple

Considérons la base :

en_cuisine(lea).   en_cuisine(marc).
en_salle(ines).    en_salle(yves).
gourmand(marc).    gourmand(ines).

suspect1(X) :- en_cuisine(X), gourmand(X).
suspect1(X) :- en_salle(X), gourmand(X).

suspect2(X) :- en_cuisine(X), !, gourmand(X).
suspect2(X) :- en_salle(X), gourmand(X).

suspect3(X) :- en_cuisine(X), gourmand(X), !.
suspect3(X) :- en_salle(X), gourmand(X).

• ?- suspect1(X). donne marc puis ines : aucune coupure, tout l’arbre est exploré.
• ?- suspect2(X). ne donne rien. en_cuisine(X) propose d’abord X = lea, puis la coupure fige ce choix et abandonne à la fois marc (autre solution d’un but à gauche) et la seconde clause. Il reste gourmand(lea), qui échoue : c’est fini.
• ?- suspect3(X). donne seulement marc. Léa échoue sur gourmand avant la coupure, donc le retour arrière fonctionne encore et essaie Marc, qui réussit ; la coupure est alors atteinte et supprime les autres alternatives, dont Ines.

La position de la coupure change tout. Retenez la règle : tout ce qui est avant le ! est définitif une fois qu’on l’a franchi, tout ce qui est après reste soumis au retour arrière.

Sans coupure, tout l'arbre est exploré. Dans suspect2, la coupure franchie avec lea supprime marc et la clause 2 ; dans suspect3, elle n'est franchie qu'avec marc.

À retenir

Le ! réussit toujours, mais une fois franchi, il supprime les autres clauses du prédicat et les autres solutions des buts situés à sa gauche. Les buts à sa droite ne sont pas affectés.

Les coupures vertes : gagner du temps

Au chapitre 5, nous avions écrit :

correction(Auj, Anniv, 0) :- Auj >= Anniv.
correction(Auj, Anniv, 1) :- Auj < Anniv.

Les deux clauses s’excluent mutuellement : si la première réussit, la seconde échouera forcément. Pourtant, Prolog l’ignore. Il garde un point de choix après la première clause et, au moindre retour arrière, réévalue la comparaison de la seconde pour rien. Une coupure lui évite ce travail :

correction(Auj, Anniv, 0) :- Auj >= Anniv, !.
correction(Auj, Anniv, 1) :- Auj < Anniv.

Le programme donne exactement les mêmes solutions avec ou sans cette coupure : elle ne sert qu’à l’efficacité, en temps (on n’essaie pas une clause inutile) et en mémoire (on ne garde pas le point de choix). On dit que c’est une coupure verte. Elle est typique des clauses mutuellement exclusives, mais pas seulement : si une personne peut avoir une réduction pour plusieurs raisons et qu’une seule suffit, couper après la première raison trouvée évite d’accorder la même réduction plusieurs fois.

Une coupure verte ne supprime qu'une branche qui aurait échoué de toute façon : la réponse C = 0 est la même, le travail en moins.

Les coupures rouges : changer le sens

Tentation naturelle : puisque la coupure garantit qu’on n’arrive à la seconde clause que si Auj >= Anniv a échoué, pourquoi refaire le test ? Passons au cinéma, qui applique un tarif enfant, puis un tarif étudiant, puis le plein tarif :

age(lucas, 10).   age(ines, 21).   age(marc, 45).
etudiant(ines).

tarif(P, 5) :- age(P, A), A < 14, !.
tarif(P, 7) :- etudiant(P), !.
tarif(_, 10).

La dernière clause n’a plus aucune condition : elle suppose que les précédentes ont échoué. Retirez les coupures, et Lucas aurait deux tarifs, 5 puis 10 (il n’est pas étudiant), tout comme Ines, 7 puis 10. Ces coupures changent l’ensemble des solutions : ce sont des coupures rouges. Elles ne sont pas interdites, mais elles rendent le sens du programme dépendant de l’ordre d’exécution, et c’est là que naissent les pièges.

Premier piège : vérifier un résultat

?- tarif(lucas, T).
T = 5
?- tarif(lucas, 10).
Yes

La première réponse est juste, la seconde absurde. Pourquoi ? Dans tarif(lucas, 10), la tête de la première clause, tarif(P, 5), ne s’unifie pas avec tarif(lucas, 10) : la clause est écartée avant d’atteindre la coupure. La deuxième échoue (Lucas n’est pas étudiant), et la troisième, sans condition, réussit.

Le remède consiste à ne lier le résultat qu’après la coupure : la tête accepte n’importe quel tarif, et c’est le corps qui le fixe, une fois la décision prise.

tarif(P, T) :- age(P, A), A < 14, !, T = 5.
tarif(P, T) :- etudiant(P), !, T = 7.
tarif(_, 10).

Maintenant, tarif(lucas, 10) entre dans la première clause, franchit la coupure, puis échoue sur 10 = 5 ; comme la coupure a supprimé les autres clauses, la réponse est « No ». Correct.

Avec la sortie dans la tête, la question saute la clause 1 avant sa coupure et tombe sur le tarif par défaut. Liée après la coupure, elle est rejetée.

Piège

Avec une coupure rouge, ne mettez jamais la valeur de sortie dans la tête de la clause. Écrivez mini(X, Y, Z) :- X < Y, !, Z = X. et non mini(X, Y, X) :- X < Y, !. : sinon, une question qui fournit déjà le résultat, comme ?- mini(2, 5, 5)., saute la clause avant la coupure et obtient une réponse fausse (ici « Yes »).

Second piège : générer au lieu de vérifier

Que donne ?- tarif(P, T)., pour connaître tous les tarifs ? Une seule réponse : P = lucas, T = 5. La coupure a figé P = lucas, puisque age(P, A) est à sa gauche, et supprimé toutes les autres personnes. Le prédicat, correct en mode (+, ?), est faux en mode (-, -).

En mode (−, −), la coupure fige la première personne trouvée par age(P, A) : Lucas. Les autres ne sont jamais essayées.

C’est la même chose pour ce prédicat, qui semble anodin :

a_des_enfants(X) :- parent(X, _), !.

En mode (+), la coupure est utile : on s’arrête au premier enfant trouvé, au lieu de répondre « Yes » autant de fois qu’il y a d’enfants. Mais en mode (-), ?- a_des_enfants(X). ne donne qu’un seul parent de la base. Une coupure rouge change donc la sémantique selon le mode d’utilisation : documentez le mode prévu, et testez les autres.

Coupure	Effet sur les solutions	Si on la retire	Usage
Verte	aucun, elle ne fait que gagner du temps	même programme, plus lent	clauses exclusives, une seule preuve suffit
Rouge	en supprime certaines	le programme devient faux	sinon implicite, « premier trouvé »

Écrire un si-alors-sinon

La coupure permet d’écrire la structure conditionnelle qui manque à Prolog :

si_alors_sinon(P, Q, _) :- P, !, Q.
si_alors_sinon(_, _, R) :- R.

Si P réussit, on s’engage dans la première clause et on exécute Q ; sinon, on exécute R. Remarquez qu’il n’y a pas besoin d’écrire la condition « non P » dans la seconde clause : on n’y arrive que si P a échoué. Logiquement, si_alors_sinon(P, Q, R) est vrai si P et Q sont vrais, ou si P est faux et R vrai.

Ce prédicat utilise des méta-variables : P, Q et R sont des variables placées là où l’on attend un but. Au moment de l’exécution, elles doivent être liées à des termes appelables, comme age(lucas, A) ; Prolog les exécute alors comme des buts (c’est ce que fait aussi le prédicat call/1). Un programme peut donc manipuler des buts comme des données.

En pratique, on utilise la construction prédéfinie ( Condition -> Alors ; Sinon ), qui a le même sens et coupe seulement dans la condition. Le tarif s’écrit alors en une seule clause, très lisible :

tarif(P, T) :-
    (   age(P, A), A < 14 -> T = 5
    ;   etudiant(P)       -> T = 7
    ;   T = 10
    ).

Attention

Le -> garde la première solution de la condition et oublie les autres. tarif(P, T) doit donc être appelé avec P connu, sinon la condition retient la première personne trouvée dans la base et s’y tient. C’est la même limite que la coupure rouge, simplement mieux cachée.

En entretien

« La coupure supprime les points de choix créés depuis l’appel du prédicat : les autres clauses et les autres solutions des buts à sa gauche. Une coupure verte ne fait que gagner du temps ; une coupure rouge change les solutions, et il faut alors lier les sorties après elle et vérifier chaque mode d’utilisation. »

En résumé

• ! réussit toujours et, une fois franchi, supprime les autres clauses du prédicat et les autres solutions des buts à sa gauche ; les buts à sa droite restent soumis au retour arrière.
• La position du ! dans la clause change radicalement les solutions (voir suspect2 et suspect3).
• Une coupure verte ne change pas les solutions, seulement l’efficacité ; une coupure rouge les change.
• Avec une coupure rouge, liez les résultats après le !, sinon une question qui fournit le résultat peut obtenir une réponse fausse.
• Une coupure rouge peut casser le mode génération : a_des_enfants(X) ne donne plus qu’une réponse.
• Le si-alors-sinon s’écrit avec une coupure, ou avec ( C -> A ; S ), qui garde la première solution de la condition.

Exercices

Exercice · Un maximum trop rapide

facile

Un camarade écrit :

maxi(X, Y, X) :- X >= Y, !.
maxi(_, Y, Y).

1. La coupure est-elle verte ou rouge ?
2. Que répondent ?- maxi(5, 2, M). et ?- maxi(5, 2, 2). ? Corrigez le prédicat.
3. Écrivez une version avec une coupure verte.

Voir la solution

1. Elle est rouge : sans elle, maxi(5, 2, M) donnerait M = 5 puis M = 2, car la seconde clause n’a pas de condition.

2. maxi(5, 2, M) répond M = 5, ce qui est juste. Mais maxi(5, 2, 2) répond Yes : la tête de la première clause, maxi(X, Y, X), demanderait que 5 et 2 soient égaux, elle est donc écartée avant la coupure, et la seconde clause réussit sans condition. Correction : lier le résultat après la coupure (onglet Prolog ci-dessous).

3. Avec des conditions exclusives explicites, la coupure devient verte.

Ici, retirer la coupure ne change aucune réponse, et maxi(5, 2, 2) échoue bien.

En code

Prolog

% 2. version corrigée : le résultat est lié après la coupure
maxi(X, Y, Z) :- X >= Y, !, Z = X.
maxi(_, Y, Y).

% 3. version avec une coupure verte (à charger à la place de la précédente)
maxi(X, Y, X) :- X >= Y, !.
maxi(X, Y, Y) :- X < Y.

% avec l'une ou l'autre version :
% ?- maxi(5, 2, M).   M = 5
% ?- maxi(5, 2, 2).   No

Python

# Chaque version renvoie la liste des M pour lesquels maxi(X, Y, M) réussit ;
# m=None joue le rôle d'une variable libre, sinon M est imposé à l'appel.
def accepte(m, v): return m is None or m == v     # unification de M avec v

def maxi_faux(x, y, m=None):      # maxi(X, Y, X) :- X >= Y, !.   maxi(_, Y, Y).
    if accepte(m, x) and x >= y:  # la tête lie M = X AVANT la coupure
        return [x]                # coupure : la clause 2 est écartée
    return [y] if accepte(m, y) else []

def maxi_corrige(x, y, m=None):   # maxi(X, Y, Z) :- X >= Y, !, Z = X.
    if x >= y:
        return [x] if accepte(m, x) else []       # coupure, puis Z = X
    return [y] if accepte(m, y) else []

def maxi_vert(x, y, m=None):      # clauses exclusives : X >= Y, ou X < Y
    return [v for v, cond in [(x, x >= y), (y, x < y)] if cond and accepte(m, v)]

for f in (maxi_faux, maxi_corrige, maxi_vert):
    print(f.__name__, f(5, 2), bool(f(5, 2, 2)))
# maxi_faux [5] True        <- maxi(5, 2, 2) répond Yes, à tort
# maxi_corrige [5] False
# maxi_vert [5] False

R

# Chaque version renvoie les M pour lesquels maxi(X, Y, M) réussit ;
# m = NULL joue le rôle d'une variable libre, sinon M est imposé à l'appel.
accepte <- function(m, v) is.null(m) || m == v     # unification de M avec v

maxi_faux <- function(x, y, m = NULL) {   # maxi(X, Y, X) :- X >= Y, !.   maxi(_, Y, Y).
  if (accepte(m, x) && x >= y) return(x)  # la tête lie M = X AVANT la coupure
  if (accepte(m, y)) y else c()
}
maxi_corrige <- function(x, y, m = NULL) {   # maxi(X, Y, Z) :- X >= Y, !, Z = X.
  if (x >= y) return(if (accepte(m, x)) x else c())   # coupure, puis Z = X
  if (accepte(m, y)) y else c()
}
maxi_vert <- function(x, y, m = NULL) {      # clauses exclusives : X >= Y, ou X < Y
  sol <- c()
  if (x >= y && accepte(m, x)) sol <- c(sol, x)
  if (x < y && accepte(m, y)) sol <- c(sol, y)
  sol
}
for (f in c("maxi_faux", "maxi_corrige", "maxi_vert"))
  cat(f, get(f)(5, 2), length(get(f)(5, 2, 2)) > 0, "\n")
# maxi_faux 5 TRUE        <- maxi(5, 2, 2) répond Yes, à tort
# maxi_corrige 5 FALSE
# maxi_vert 5 FALSE

Exercice · Déplacer la coupure

moyen

Avec la base des suspects de ce chapitre, donnez toutes les réponses aux questions ?- suspect4(X). et ?- suspect5(X)., et justifiez à l’aide de l’arbre de recherche.

suspect4(X) :- !, en_cuisine(X), gourmand(X).
suspect4(X) :- en_salle(X), gourmand(X).

suspect5(X) :- en_cuisine(X), gourmand(X).
suspect5(X) :- en_salle(X), !, gourmand(X).

Voir la solution

suspect4 : la coupure est le premier but. Elle supprime immédiatement la seconde clause, mais il n’y a encore aucun but à sa gauche. Les buts à sa droite gardent donc leur retour arrière : en_cuisine(X) propose Léa (échec sur gourmand), puis Marc (succès). Réponse : X = marc seulement. La seconde clause n’est jamais essayée, Ines n’apparaît pas.

suspect5 : la première clause, sans coupure, donne X = marc (Léa échoue). Au retour arrière, on passe à la seconde clause : en_salle(X) propose Ines, la coupure fige ce choix (Yves ne sera jamais essayé), puis gourmand(ines) réussit. Réponses : X = marc, puis X = ines, puis « No ». La coupure de la seconde clause n’a aucun effet sur la première, déjà entièrement explorée.

En code

Prolog

en_cuisine(lea).   en_cuisine(marc).
en_salle(ines).    en_salle(yves).
gourmand(marc).    gourmand(ines).

% suspect4/1 et suspect5/1 : ceux de l'énoncé
% ?- findall(X, suspect4(X), L4), findall(X, suspect5(X), L5).
% L4 = [marc], L5 = [marc, ines]

Python

en_cuisine = ["lea", "marc"]
en_salle = ["ines", "yves"]
gourmand = ["marc", "ines"]

def suspect4():
    # clause 1 : ! en premier but -> la clause 2 est supprimée,
    # mais en_cuisine(X) garde son retour arrière (il est à droite de la coupure)
    yield from (x for x in en_cuisine if x in gourmand)

def suspect5():
    yield from (x for x in en_cuisine if x in gourmand)   # clause 1, sans coupure
    x = en_salle[0]            # clause 2 : la coupure fige le PREMIER choix d'en_salle
    if x in gourmand:
        yield x

print(list(suspect4()))   # ['marc']
print(list(suspect5()))   # ['marc', 'ines']  (yves n'est jamais essayé)

R

en_cuisine <- c("lea", "marc")
en_salle   <- c("ines", "yves")
gourmand   <- c("marc", "ines")

# suspect4 : ! en premier but -> la clause 2 est supprimée,
# mais en_cuisine(X) garde son retour arrière (il est à droite de la coupure)
suspect4 <- function() en_cuisine[en_cuisine %in% gourmand]

suspect5 <- function() {
  sol <- en_cuisine[en_cuisine %in% gourmand]    # clause 1, sans coupure
  x <- en_salle[1]            # clause 2 : la coupure fige le PREMIER choix d'en_salle
  if (x %in% gourmand) sol <- c(sol, x)
  sol
}
suspect4()   # "marc"
suspect5()   # "marc" "ines"  (yves n'est jamais essayé)

Exercice · Ajouter à un ensemble

difficile

On représente un ensemble par une liste sans doublons. Écrivez ajouter(+P, +E1, -E2), qui ajoute P en tête de l’ensemble E1 s’il n’y est pas encore, et laisse E1 inchangé sinon :

1. d’abord sans coupure, en utilisant membre/2 et hors/2 (du chapitre 6) ;
2. puis avec une coupure, sans appeler hors/2.

Vérifiez votre version avec coupure sur la question ?- ajouter(a, [a, b], [a, a, b]).

Voir la solution

1. Sans coupure, les deux cas doivent être exclusifs explicitement (onglet Prolog ci-dessous).

Petit défaut : si P est présent, membre peut réussir plusieurs fois (s’il y avait des doublons) et chaque succès redonnerait la même réponse.

2. Avec une coupure rouge, le test hors devient inutile, mais il faut lier le résultat après la coupure.

Sur ajouter(a, [a, b], [a, a, b]) : membre(a, [a, b]) réussit, la coupure supprime la seconde clause, puis [a, a, b] = [a, b] échoue. Réponse : « No », ce qui est juste. La version naïve ajouter(P, E, E) :- membre(P, E), !. aurait écarté la première clause dès la tête ([a, b] ne s’unifie pas avec [a, a, b]) et la seconde aurait répondu Yes, à tort.

En code

Prolog

% 1. sans coupure, avec membre/2 et hors/2 du chapitre 6
ajouter(P, E, E) :- membre(P, E).
ajouter(P, E, [P|E]) :- hors(P, E).

% 2. avec une coupure rouge (à charger à la place de la version 1)
ajouter(P, E, R) :- membre(P, E), !, R = E.
ajouter(P, E, [P|E]).

% ?- ajouter(c, [a, b], R).           R = [c, a, b]
% ?- ajouter(a, [a, b], [a, a, b]).   No

Python

# Chaque version renvoie la liste des R pour lesquels ajouter(P, E, R) réussit ;
# r=None : R libre ; sinon R est imposé à l'appel.
def accepte(r, v): return r is None or r == v

def ajouter_sans_coupure(p, e, r=None):
    sol = [e for x in e if x == p and accepte(r, e)]  # membre(P, E) : un succès par occurrence
    if p not in e and accepte(r, [p] + e):             # hors(P, E)
        sol.append([p] + e)
    return sol

def ajouter_coupure(p, e, r=None):     # ajouter(P, E, R) :- membre(P, E), !, R = E.
    if p in e:
        return [e] if accepte(r, e) else []            # coupure, PUIS R = E
    return [[p] + e] if accepte(r, [p] + e) else []

def ajouter_naif(p, e, r=None):        # ajouter(P, E, E) :- membre(P, E), !.
    if accepte(r, e) and p in e:       # R = E dès la tête, avant la coupure
        return [e]
    return [[p] + e] if accepte(r, [p] + e) else []

print(ajouter_sans_coupure("c", ["a", "b"]))          # [['c', 'a', 'b']]
print(ajouter_sans_coupure("a", ["a", "b", "a"]))     # [['a', 'b', 'a'], ['a', 'b', 'a']] : deux fois
print(ajouter_coupure("a", ["a", "b"], ["a", "a", "b"]))   # [] : No, c'est juste
print(ajouter_naif("a", ["a", "b"], ["a", "a", "b"]))      # [['a', 'a', 'b']] : Yes, à tort

R

# Chaque version renvoie la liste des R pour lesquels ajouter(P, E, R) réussit ;
# r = NULL : R libre ; sinon R est imposé à l'appel.
accepte <- function(r, v) is.null(r) || identical(r, v)

ajouter_sans_coupure <- function(p, e, r = NULL) {
  sol <- rep(list(e), sum(e == p) * accepte(r, e))    # membre(P, E) : un succès par occurrence
  if (!(p %in% e) && accepte(r, c(p, e))) sol <- c(sol, list(c(p, e)))   # hors(P, E)
  sol
}
ajouter_coupure <- function(p, e, r = NULL) {    # ajouter(P, E, R) :- membre(P, E), !, R = E.
  if (p %in% e) return(if (accepte(r, e)) list(e) else list())   # coupure, PUIS R = E
  if (accepte(r, c(p, e))) list(c(p, e)) else list()
}
ajouter_naif <- function(p, e, r = NULL) {       # ajouter(P, E, E) :- membre(P, E), !.
  if (accepte(r, e) && p %in% e) return(list(e)) # R = E dès la tête, avant la coupure
  if (accepte(r, c(p, e))) list(c(p, e)) else list()
}
str(ajouter_sans_coupure("c", c("a", "b")))          # une réponse : "c" "a" "b"
length(ajouter_sans_coupure("a", c("a", "b", "a")))  # 2 : deux fois la même réponse
length(ajouter_coupure("a", c("a", "b"), c("a", "a", "b")))   # 0 : No, c'est juste
length(ajouter_naif("a", c("a", "b"), c("a", "a", "b")))      # 1 : Yes, à tort