Calculez avec les nombres

Posez à Prolog la question ?- X = 2 + 3. et il vous répondra, imperturbable, X = 2 + 3. Pas 5. Ce n’est pas un bug : pour Prolog, 2 + 3 est un terme comme un autre, un arbre de racine +, et l’unification ne calcule rien. Pour calculer, il faut le demander explicitement.

Dans ce chapitre, vous allez voir deux façons de faire de l’arithmétique : une façon purement logique, élégante mais lente, puis la façon pratique, avec le prédicat is. Notre fil rouge : le fichier des adhérents d’un club de voile de Saint-Malo, dont on veut calculer les âges.

L’arithmétique par la logique : les entiers de Peano

Peut-on compter avec seulement des termes et de l’unification ? Oui, avec deux symboles : une constante zero, et un foncteur suc/1 qui signifie « successeur de ». Le nombre 1 s’écrit suc(zero), 2 s’écrit suc(suc(zero)), et ainsi de suite. Ce sont les entiers de Peano, et leur définition est récursive :

entier(zero).
entier(suc(X)) :- entier(X).

En mode (+), ?- entier(suc(suc(zero))). vérifie ; en mode (-), ?- entier(X). énumère zero, suc(zero), suc(suc(zero))… sans fin : c’est une structure potentiellement infinie.

L’addition se définit par récurrence sur le premier argument : 0 + Y = Y, et (X + 1) + Y = (X + Y) + 1.

% somme(X, Y, Z) : Z = X + Y
somme(zero, Y, Y) :- entier(Y).
somme(suc(X), Y, suc(Z)) :- somme(X, Y, Z).

La magie, c’est que ce prédicat fonctionne dans plusieurs modes, parce qu’il ne fait que de l’unification :

?- somme(suc(zero), suc(suc(zero)), Z).          % 1 + 2 ?
Z = suc(suc(suc(zero)))

?- somme(suc(zero), Y, suc(suc(suc(zero)))).     % 1 + Y = 3 ?
Y = suc(suc(zero))

?- somme(X, Y, suc(suc(zero))).                  % X + Y = 2 ?
X = zero, Y = suc(suc(zero)) ;
X = suc(zero), Y = suc(zero) ;
X = suc(suc(zero)), Y = zero ;
No

La même définition additionne, soustrait et décompose un nombre : elle marche en modes (+, +, -), (+, -, +), (-, +, +) et (-, -, +). C’est l’aspect relationnel de Prolog à son meilleur. De même, inf_egal(zero, X) :- entier(X). et inf_egal(suc(X), suc(Y)) :- inf_egal(X, Y). définissent la relation « inférieur ou égal » sans aucun calcul.

En mode (+, +, −), somme retire un suc à X à chaque appel et en ajoute un au résultat : suc(zero) + suc(suc(zero)) donne suc(suc(suc(zero))).

En mode (−, −, +), le même prédicat énumère les trois décompositions de 2 : 0 + 2, 1 + 1, puis 2 + 0.

Mais écrire 1 000 000 avec un million de suc n’a rien de pratique : chaque opération coûte autant d’étapes que la valeur du nombre. Les entiers de Peano servent à comprendre et à raisonner, pas à calculer.

Évaluer une expression avec is

Les vrais nombres de Prolog (2, -12, 143.7) se manipulent avec des opérateurs prédéfinis : +, -, *, /, // (division entière), mod, abs, min, max… Mais attention, ces opérateurs ne sont qu’une facilité d’écriture : 2 + 1 est le terme +(2, 1), et il n’est jamais évalué de lui-même.

?- X = 2 + 1.
X = 2 + 1
?- 2 + 1 == 3.
No

Pour évaluer, on utilise le prédicat is/2 : R is E évalue l’expression E, puis unifie le résultat avec R.

Question	Résultat	Pourquoi
R is 3 + 5 * 2.	R = 13	la multiplication est prioritaire
13 is 3 + 5 * 2.	Yes	13 s’unifie avec 13
10 is 3 + 5 * 2.	No	10 ne s’unifie pas avec 13
X = 10, R is 3 + X.	R = 13	X est connu au moment de l’évaluation
10 is 3 + X.	échec, avec une erreur d’instanciation	X est libre : l’expression n’est pas évaluable
X = 3, X is X + 1.	No	3 ne s’unifie pas avec 4

Deux règles à graver :

• l’expression de droite doit être entièrement instanciée au moment de l’appel (sinon, erreur d’instanciation) : is ne résout pas d’équations ;
• is n’est pas une affectation. X is X + 1 ne peut jamais réussir : une fois liée, une variable Prolog ne change plus de valeur. Pour « incrémenter », on crée une nouvelle variable : N1 is N + 1.

Piège

is fonctionne dans un seul sens : il calcule la droite et unifie avec la gauche. Un prédicat qui utilise is perd donc souvent l’aspect relationnel des entiers de Peano. somme(X, 2, 5) trouvait X = 3 ; avec Z is X + Y, la même question provoque une erreur.

Comparer des valeurs

Six prédicats comparent la valeur de deux expressions, en évaluant les deux côtés (qui doivent donc être instanciés) :

Prédicat	Vrai si…
E1 < E2	la valeur de E1 est strictement inférieure
E1 > E2	strictement supérieure
E1 =< E2	inférieure ou égale (attention à l’ordre des symboles : pas <=)
E1 >= E2	supérieure ou égale
E1 =:= E2	les valeurs sont égales
E1 =\= E2	les valeurs sont différentes

Ainsi 2 + 1 =:= 3 réussit, là où 2 + 1 == 3 échouait. Voici le tableau des « égalités » de Prolog, source de confusions sans fin :

Écriture	Ce qu’elle fait	X = 2+1 puis…
A = B	unifie A et B (peut lier des variables)	X = 3 échoue
A == B	vérifie que A et B sont déjà identiques, sans rien lier	X == 2+1 réussit
A =:= B	compare les valeurs numériques	X =:= 3 réussit
A is B	évalue B et unifie le résultat avec A	3 is X réussit

Leurs négations sont \= (non unifiables), \== (pas identiques) et =\= (valeurs différentes).

À retenir

= unifie, == teste l’identité des termes, =:= compare des valeurs, et is évalue l’expression de droite (qui doit être instanciée) avant d’unifier. Aucun de ces prédicats n’est une affectation.

Calculer par récursion

Avec is, les calculs récursifs s’écrivent naturellement. La factorielle, n! = n × (n − 1)!, avec 0! = 1 :

% fact(+N, -F) : F = N!
fact(0, 1).
fact(N, F) :-
    N > 0,              % garde : évite de descendre sous zéro
    N1 is N - 1,        % nouvelle variable, pas de modification de N
    fact(N1, F1),
    F is N * F1.        % F1 est connu ici : on peut évaluer

?- fact(5, F). répond F = 120. L’ordre des buts est imposé par les instanciations : N1 doit être calculé avant l’appel récursif, et F après, quand F1 est connu. Sans la garde N > 0, une demande de solution supplémentaire après fact(0, 1) ferait descendre N à −1, −2… sans fin.

N1 est calculé avant chaque appel récursif, F seulement au retour, quand F1 est connu : 1, 1, 2, 6, 24, puis 120.

Ce prédicat ne marche qu’en mode (+, -) (ou (+, +) pour vérifier). En mode (-, +), ?- fact(N, 120). échoue sur une erreur, car N > 0 est évalué avec N libre.

Le fil rouge : les âges des adhérents

Le club de voile enregistre ses adhérents avec leur date de naissance, et la date du jour est un fait :

% adherent(Nom, Jour, Mois, Annee) : date de naissance
adherent(yann, 12, 3, 2001).
adherent(maelle, 29, 2, 2012).
adherent(gwen, 5, 11, 1960).
adherent(erwan, 30, 9, 1998).
adherent(nolwenn, 18, 9, 2008).

date_du_jour(18, 9, 2026).

Une première approximation de l’âge ne regarde que l’année :

age_approx(Nom, Age) :-
    adherent(Nom, _, _, A),
    date_du_jour(_, _, AA),
    Age is AA - A.

Mais Gwen, née en novembre 1960, n’a pas encore fêté son anniversaire le 18 septembre 2026 : elle a 65 ans, pas 66. Pour l’âge exact, on retire 1 si l’anniversaire n’est pas encore passé. Une astuce simple compare les dates dans l’année sous forme de nombres Mois * 100 + Jour (le 18 septembre donne 918, le 5 novembre 1105) :

age(Nom, Age) :-
    adherent(Nom, J, M, A),
    date_du_jour(JA, MA, AA),
    correction(MA * 100 + JA, M * 100 + J, C),
    Age is AA - A - C.

% correction(Aujourdhui, Anniversaire, C) : C = 1 si l'anniversaire est à venir
correction(Auj, Anniv, 0) :- Auj >= Anniv.
correction(Auj, Anniv, 1) :- Auj < Anniv.

Les comparaisons évaluent elles-mêmes les expressions MA * 100 + JA et M * 100 + J : pas besoin de is intermédiaire. Les deux clauses de correction s’excluent mutuellement, donc chaque adhérent reçoit exactement un âge. On obtient Yann 25 ans, Maëlle 14, Gwen 65, Erwan 27 (son anniversaire tombe le 30 septembre) et Nolwenn 18 (c’est son anniversaire aujourd’hui).

Tout anniversaire codé au plus 918 est déjà passé (C = 0) ; au-delà, il est à venir (C = 1). Nolwenn est pile sur la ligne : c'est aujourd'hui.

Exemple

Pour Erwan : MA * 100 + JA vaut 9 × 100 + 18 = 918, et M * 100 + J vaut 9 × 100 + 30 = 930. Comme 918 est inférieur à 930, seule la seconde clause s’applique, avec C = 1. L’âge vaut 2026 − 1998 − 1 = 27.

Définir ses propres opérateurs

Les opérateurs arithmétiques ne sont pas magiques : ce sont des foncteurs ordinaires déclarés avec une priorité et une position. Vous pouvez déclarer les vôtres avec la directive op/3 :

:- op(700, xfx, relie).      % opérateur infixe, même priorité que =

rennes relie laval.          % équivaut à relie(rennes, laval).

On peut alors poser ?- rennes relie X. Les trois arguments de op sont :

• la priorité, un nombre (plus il est petit, plus l’opérateur « lie fort » : * a la priorité 400 et + la priorité 500, d’où 3 + 5 * 2 lu comme 3 + (5 * 2)) ;
• le type, qui donne la position de l’opérateur f et de ses arguments x ou y : préfixe (fx, fy), infixe (xfx, xfy, yfx) ou postfixe (xf, yf) ;
• le nom, n’importe quel atome.

La différence entre x et y règle l’associativité. Un argument x doit avoir une priorité strictement inférieure à celle de l’opérateur, un argument y une priorité inférieure ou égale. Avec xfx, on ne peut pas enchaîner : a relie b relie c est une erreur de syntaxe. Avec xfy, a et b et c se lit et(a, et(b, c)) ; avec yfx, il se lit et(et(a, b), c), comme la soustraction, pour que 10 - 3 - 2 vaille bien 5.

La priorité décide quel opérateur est à la racine ; l'associativité yfx accroche le second − à gauche, pour que 10 − 3 − 2 vaille 5 et non 9.

Attention

Déclarer un opérateur ne lui donne aucun sens : cela change seulement la façon d’écrire et de lire les termes. rennes relie laval reste le terme relie(rennes, laval), que seules vos clauses rendront vrai ou faux.

En entretien

« En Prolog, 2 + 3 n’est qu’un terme : il faut is pour l’évaluer, et is exige que l’expression soit instanciée. Ce n’est pas une affectation, une variable liée ne change plus : pour compter, on crée une nouvelle variable à chaque étape. »

En résumé

• Les entiers de Peano (zero, suc/1) permettent une arithmétique purement logique, qui marche dans plusieurs modes mais reste très lente.
• Une expression comme 2 + 1 est un terme ; seul is l’évalue, à condition qu’elle soit entièrement instanciée.
• is n’est pas une affectation : X is X + 1 échoue toujours ; on crée une nouvelle variable.
• Les comparaisons <, >, =<, >=, =:=, =\= évaluent leurs deux côtés.
• Ne confondez pas = (unification), == (identité), =:= (égalité de valeur) et is (évaluation).
• Un prédicat qui calcule avec is fonctionne en général dans un seul mode ; ordonnez les buts pour que tout soit instancié au bon moment.
• op/3 déclare un opérateur avec une priorité et un type (xfx, xfy, yfx…), sans lui donner de sens.

Exercices

Exercice · Prévoir les réponses

facile

Que répond Prolog à chacune de ces questions ?

1. ?- X is 7 // 2, Y is 7 mod 2.
2. ?- 6 =:= 2 * 3.
3. ?- 6 == 2 * 3.
4. ?- 2 * 3 = X * Y.
5. ?- N = 4, N is N * 1.
6. ?- Y is X + 1, X = 2.

Voir la solution

1. X = 3, Y = 1 : division entière et reste.
2. Yes : les deux valeurs valent 6.
3. No : le nombre 6 et le terme 2 * 3 ne sont pas identiques.
4. X = 2, Y = 3 : c’est une unification de deux termes *(2, 3) et *(X, Y), sans aucun calcul.
5. Yes : N * 1 vaut 4, qui s’unifie avec N déjà égal à 4. Ce n’est pas une affectation, juste une vérification.
6. Erreur d’instanciation : au moment d’évaluer X + 1, X est encore libre. Il faut inverser les buts : X = 2, Y is X + 1.

En code

Prolog

?- X is 7 // 2, Y is 7 mod 2.   % X = 3, Y = 1
?- 6 =:= 2 * 3.                 % Yes
?- 6 == 2 * 3.                  % No
?- 2 * 3 = X * Y.               % X = 2, Y = 3
?- N = 4, N is N * 1.           % N = 4
?- Y is X + 1, X = 2.           % erreur d'instanciation

Python

# 1. X is 7 // 2, Y is 7 mod 2 : division entière et reste
print(7 // 2, 7 % 2)              # 3 1

# 2. 6 =:= 2 * 3 : on compare des VALEURS
print(6 == 2 * 3)                 # True

# 3. 6 == 2 * 3 : on compare des TERMES ; le terme 2 * 3 est l'arbre ('*', 2, 3)
terme = ("*", 2, 3)
print(6 == terme)                 # False

# 4. 2 * 3 = X * Y : unification de deux arbres, sans calcul
foncteur, x, y = terme            # déstructuration de *(2, 3)
print(x, y)                       # X = 2, Y = 3

# 5. N = 4, N is N * 1 : simple vérification, N ne change pas
N = 4
print(N == N * 1)                 # True

# 6. Y is X + 1, X = 2 : X n'a pas encore de valeur
try:
    Y = X + 1
except NameError as e:
    print("erreur :", e)          # erreur : name 'X' is not defined

R

# 1. X is 7 // 2, Y is 7 mod 2 : division entière et reste
c(7 %/% 2, 7 %% 2)                 # 3 1

# 2. 6 =:= 2 * 3 : on compare des VALEURS
6 == 2 * 3                         # TRUE

# 3. 6 == 2 * 3 : on compare des TERMES ; quote() garde l'expression non évaluée
terme <- quote(2 * 3)
identical(6, terme)                # FALSE

# 4. 2 * 3 = X * Y : on lit les arguments de l'arbre *(2, 3), sans calcul
as.list(terme)[-1]                 # 2 puis 3

# 5. N = 4, N is N * 1 : simple vérification, N ne change pas
N <- 4
N == N * 1                         # TRUE

# 6. Y is X + 1, X = 2 : X n'a pas encore de valeur
tryCatch(Y <- X + 1, error = function(e) conditionMessage(e))   # objet 'X' introuvable

Exercice · Interroger le club

moyen

Avec les faits du club et le prédicat age/2, écrivez :

1. bissextil(Nom) : l’adhérent est né un 29 février ;
2. actif(Nom) : l’adhérent a strictement plus de 20 ans et strictement moins de 60 ans ;
3. hors_actifs(Nom) : l’adhérent a 20 ans ou moins, ou 60 ans ou plus ;
4. majeur(Nom) : l’adhérent a au moins 18 ans aujourd’hui.

Donnez les réponses de chaque prédicat.

Voir la solution

• bissextil : Maëlle. La sélection se fait par unification, avec des constantes dans la tête du but.
• actif : Yann (25) et Erwan (27).
• hors_actifs : Maëlle (14) et Nolwenn (18) par la première clause, puis Gwen (65) par la seconde. Le « ou » s’écrit avec deux clauses.
• majeur : Yann, Gwen, Erwan et Nolwenn, dont c’est l’anniversaire : c’est pour elle que l’âge exact compte (avec age_approx, le résultat serait le même ici, mais faux pour quelqu’un né le 19 septembre 2008).

En code

Prolog

bissextil(Nom) :- adherent(Nom, 29, 2, _).

actif(Nom) :- age(Nom, A), A > 20, A < 60.

hors_actifs(Nom) :- age(Nom, A), A =< 20.
hors_actifs(Nom) :- age(Nom, A), A >= 60.

majeur(Nom) :- age(Nom, A), A >= 18.

% ?- bissextil(N).     N = maelle
% ?- actif(N).         N = yann ; N = erwan
% ?- hors_actifs(N).   N = maelle ; N = nolwenn ; N = gwen
% ?- majeur(N).        N = yann ; N = gwen ; N = erwan ; N = nolwenn

Python

# adherent(Nom, Jour, Mois, Annee)
adherent = [("yann", 12, 3, 2001), ("maelle", 29, 2, 2012), ("gwen", 5, 11, 1960),
            ("erwan", 30, 9, 1998), ("nolwenn", 18, 9, 2008)]
jour, mois, annee = 18, 9, 2026                       # date_du_jour(18, 9, 2026)

def age(j, m, a):
    correction = 1 if mois * 100 + jour < m * 100 + j else 0   # anniversaire à venir
    return annee - a - correction

ages = {nom: age(j, m, a) for nom, j, m, a in adherent}
print(ages)   # {'yann': 25, 'maelle': 14, 'gwen': 65, 'erwan': 27, 'nolwenn': 18}

bissextil = [nom for nom, j, m, _ in adherent if (j, m) == (29, 2)]
actif = [n for n, a in ages.items() if 20 < a < 60]
hors_actifs = [n for n, a in ages.items() if a <= 20] + [n for n, a in ages.items() if a >= 60]
majeur = [n for n, a in ages.items() if a >= 18]
print(bissextil)     # ['maelle']
print(actif)         # ['yann', 'erwan']
print(hors_actifs)   # ['maelle', 'nolwenn', 'gwen']  (clause 1, puis clause 2)
print(majeur)        # ['yann', 'gwen', 'erwan', 'nolwenn']

R

adherent <- data.frame(nom = c("yann", "maelle", "gwen", "erwan", "nolwenn"),
                       j = c(12, 29, 5, 30, 18), m = c(3, 2, 11, 9, 9),
                       a = c(2001, 2012, 1960, 1998, 2008))
jour <- 18; mois <- 9; annee <- 2026                    # date_du_jour(18, 9, 2026)

# correction = 1 si l'anniversaire est encore à venir cette année
correction <- as.integer(mois * 100 + jour < adherent$m * 100 + adherent$j)
age <- setNames(annee - adherent$a - correction, adherent$nom)
age                  # yann 25, maelle 14, gwen 65, erwan 27, nolwenn 18

adherent$nom[adherent$j == 29 & adherent$m == 2]        # bissextil : "maelle"
names(age)[age > 20 & age < 60]                         # actif : "yann" "erwan"
c(names(age)[age <= 20], names(age)[age >= 60])         # hors_actifs : "maelle" "nolwenn" "gwen"
names(age)[age >= 18]                                   # majeur : "yann" "gwen" "erwan" "nolwenn"

Exercice · Multiplier selon Peano

difficile

1. Écrivez produit(X, Y, Z), vrai si Z = X × Y en entiers de Peano, en vous appuyant sur somme/3 et sur l’égalité (X + 1) × Y = X × Y + Y.
2. Que se passe-t-il pour la question ?- produit(X, suc(suc(zero)), suc(suc(suc(suc(zero))))). (soit X × 2 = 4) ? Donnez la première réponse, puis dites ce qui arrive si l’on en demande une autre.

Voir la solution

1. On calcule d’abord P = X × Y par l’appel récursif, puis Z = P + Y (onglet Prolog ci-dessous).

2. X est libre. La première clause propose X = zero avec un produit zero, qui ne s’unifie pas avec 4 : échec. La seconde pose X = suc(X1) et appelle produit(X1, 2, P) avec X1 et P libres : ce but énumère X1 = 0, 1, 2… avec P = 0, 2, 4… Pour chaque couple, somme(P, 2, 4) vérifie si P + 2 = 4 : c’est vrai pour P = 2, donc X1 = 1 et X = suc(suc(zero)). Prolog répond bien X = 2, une division « gratuite ».

Si l’on demande une autre solution, l’énumération continue : X1 = 2 (P = 4, et 4 + 2 ne vaut pas 4), X1 = 3, et ainsi de suite, sans fin, car rien n’indique à Prolog que P ne fera que grandir. Le programme boucle. Pour l’éviter, il faudrait borner la recherche, par exemple en exigeant inf_egal(X, Z) avant l’appel récursif.

En code

Prolog

produit(zero, Y, zero) :- entier(Y).
produit(suc(X), Y, Z) :- produit(X, Y, P), somme(P, Y, Z).

% ?- produit(suc(suc(suc(zero))), suc(suc(zero)), Z).          3 × 2
% Z = suc(suc(suc(suc(suc(suc(zero))))))
% ?- produit(X, suc(suc(zero)), suc(suc(suc(suc(zero))))).     X × 2 = 4
% X = suc(suc(zero)) ;   puis la recherche boucle

Python

from itertools import islice

ZERO = "zero"
def suc(x): return ("suc", x)
def peano(n): return ZERO if n == 0 else suc(peano(n - 1))
def entier(t): return 0 if t == ZERO else 1 + entier(t[1])

def somme(x, y):             # somme(+X, +Y, -Z) : récurrence sur X
    return y if x == ZERO else suc(somme(x[1], y))

def produit(x, y):           # produit(suc(X), Y, Z) :- produit(X, Y, P), somme(P, Y, Z).
    return ZERO if x == ZERO else somme(produit(x[1], y), y)

print(entier(produit(peano(3), peano(2))))       # 6

def produit_libre(y):        # produit(-X1, +Y, -P) : énumère X1 = 0, 1, 2… sans fin
    x1, p = ZERO, ZERO
    while True:
        yield x1, p
        x1, p = suc(x1), somme(p, y)

# ?- produit(X, 2, 4). : X = suc(X1), où produit(X1, 2, P) énumère et somme(P, 2, 4) teste
deux, quatre = peano(2), peano(4)
candidats = islice(produit_libre(deux), 200)     # Prolog, lui, ne s'arrête jamais
print([entier(suc(x1)) for x1, p in candidats if somme(p, deux) == quatre])
# [2] : une seule réponse parmi les 200 premiers candidats, puis une recherche sans fin

R

# zero = "zero", suc(X) = list("suc", X)
suc <- function(x) list("suc", x)
peano <- function(n) if (n == 0) "zero" else suc(peano(n - 1))
entier <- function(t) if (identical(t, "zero")) 0 else 1 + entier(t[[2]])

somme <- function(x, y)       # somme(+X, +Y, -Z) : récurrence sur X
  if (identical(x, "zero")) y else suc(somme(x[[2]], y))
produit <- function(x, y)     # produit(suc(X), Y, Z) :- produit(X, Y, P), somme(P, Y, Z).
  if (identical(x, "zero")) "zero" else somme(produit(x[[2]], y), y)

entier(produit(peano(3), peano(2)))           # 6

# ?- produit(X, 2, 4). : produit(X1, 2, P) énumère X1 = 0, 1, 2… et somme(P, 2, 4) teste
deux <- peano(2); quatre <- peano(4)
x1 <- "zero"; p <- "zero"; reponses <- c()
for (essai in 1:200) {                          # Prolog, lui, ne s'arrête jamais
  if (identical(somme(p, deux), quatre)) reponses <- c(reponses, entier(suc(x1)))
  x1 <- suc(x1); p <- somme(p, deux)
}
reponses      # 2 : une seule réponse parmi les 200 premiers candidats