Écrivez des règles et interrogez une base

Avec des faits seuls, Prolog n’est qu’un carnet d’adresses : il ne sait que ce qu’on lui a dit mot pour mot. Tout change avec les règles, qui permettent de déduire de nouvelles connaissances. « Un plat, c’est une viande ou un poisson », « un repas, c’est une entrée, un plat et un dessert » : deux lignes, et la base sait composer 36 repas qu’on ne lui a jamais listés.

Dans ce chapitre, vous allez écrire vos premières règles sur la carte de la crêperie du chapitre 1, voir qu’elles suffisent à exprimer toute l’algèbre relationnelle des bases de données, et découvrir que l’ordre dans lequel on écrit les buts n’est pas anodin.

Une règle : une conclusion et des conditions

La carte distingue les plats de viande et les plats de poisson. Mais un client veut simplement savoir quels sont les plats. Écrivons-le :

plat(P) :- viande(P).
plat(P) :- poisson(P).

Une règle a une tête (à gauche du symbole :-) et un corps (à droite). Le symbole :- se lit « si » : « P est un plat si P est une viande ». Un fait n’est finalement qu’une règle sans corps, toujours vraie.

Ici, le prédicat plat/1 a deux clauses. Plusieurs clauses pour un même prédicat se lisent comme un ou : P est un plat si P est une viande, ou si P est un poisson. On peut d’ailleurs l’écrire en une seule clause avec le point-virgule, plat(P) :- viande(P) ; poisson(P)., mais deux clauses séparées sont plus lisibles et c’est la forme habituelle.

?- plat(P).
P = galette_saucisse ;
P = galette_complete ;
P = cotriade ;
P = noix_de_saint_jacques.

Les viandes arrivent avant les poissons : Prolog essaie la première clause jusqu’au bout, puis la seconde.

La portée des variables

Une variable n’a de sens qu’à l’intérieur de sa clause. Le P de la première clause de plat et celui de la seconde sont deux variables différentes, qui n’ont rien à voir. Il n’y a pas de variable globale en Prolog.

Logiquement, les variables d’une règle sont quantifiées universellement : plat(P) :- viande(P). signifie « pour tout P, si P est une viande alors P est un plat ». Une variable qui n’apparaît que dans le corps se lit plutôt comme un « il existe », vous allez le voir tout de suite.

Composer des relations : le « et »

Un repas se compose d’une entrée, d’un plat et d’un dessert. Dans le corps d’une règle, la virgule se lit « et » :

% repas(Entree, Plat, Dessert)
repas(E, P, D) :- entree(E), plat(P), dessert(D).

La règle réutilise plat/1, qui elle-même repose sur viande/1 et poisson/1 : on construit les connaissances par couches, comme on écrit des fonctions qui s’appellent. Avec 3 entrées, 4 plats et 3 desserts, ?- repas(E, P, D). produit 3 × 4 × 3 = 36 solutions.

La virgule du corps est un ET, les deux clauses de plat un OU : 3 entrées × (2 + 2) plats × 3 desserts donnent 36 repas.

À retenir

Dans une règle, la virgule est un et entre les buts du corps ; plusieurs clauses pour une même tête forment un ou. Une règle se lit « la tête est vraie si tous les buts du corps sont vrais ».

Ajoutons maintenant les prix, pour pouvoir sélectionner :

% prix(Plat, Euros)
prix(salade_de_chevre, 7).
prix(veloute_de_potiron, 6).
prix(huitres_de_cancale, 12).
prix(galette_saucisse, 9).
prix(galette_complete, 10).
prix(cotriade, 16).
prix(noix_de_saint_jacques, 18).
prix(far_breton, 4).
prix(crepe_caramel_beurre_sale, 5).
prix(kouign_amann, 5).

La règle suivante relie deux prédicats par une variable commune et filtre par une comparaison (< compare deux nombres ; nous verrons l’arithmétique en détail au chapitre 5) :

% un dessert à moins de 5 euros
petit_dessert(D) :- dessert(D), prix(D, Euros), Euros < 5.

La variable Euros n’apparaît pas dans la tête : elle sert d’intermédiaire. C’est le « il existe » : D est un petit dessert s’il existe un prix Euros de D qui est inférieur à 5. La seule réponse est le far breton.

La variable D fait la jointure entre dessert et prix ; la comparaison fait ensuite la sélection et ne garde que le far breton.

Prolog, une base de données relationnelle

Si vous avez fait du SQL, vous avez peut-être déjà remarqué la ressemblance. Un prédicat comme prix/2 est une table à deux colonnes, et chaque fait en est une ligne. Les opérateurs de l’algèbre relationnelle, la théorie derrière SQL, s’écrivent tous très simplement.

Opérateur	Idée	En Prolog	En SQL
Sélection	garder certaines lignes	cher(P) :- prix(P, E), E > 15.	WHERE euros > 15
Projection	garder certaines colonnes	a_un_prix(P) :- prix(P, _).	SELECT plat
Union	réunir deux relations	les deux clauses de plat/1	UNION
Produit cartésien	toutes les combinaisons	repas/3 (buts sans variable commune)	FROM a, b
Jointure	combiner sur une valeur commune	dessert(D), prix(D, E) (variable partagée)	JOIN … ON

La jointure se fait uniquement par le partage d’une variable : dans dessert(D), prix(D, E), les deux buts doivent s’accorder sur la même valeur de D. Il n’y a pas de mot-clé, pas de condition ON : c’est le nom de variable qui fait tout.

Et la différence, « les plats qui ne sont pas au menu du jour » ? Elle demande une forme de négation, qui obéit à des règles délicates. Nous la verrons au chapitre 8.

En entretien

« Un prédicat Prolog, c’est une table ; un fait, c’est une ligne ; une règle, c’est une vue. La jointure se fait en partageant une variable entre deux buts, et plusieurs clauses font une union. »

Renvoyer des termes construits

Quand vous posez ?- repas(E, P, D)., Prolog renvoie trois variables séparées. Il serait plus lisible d’obtenir un seul objet qui représente le repas entier, par exemple :

R = rep(entree(salade_de_chevre), plat(galette_saucisse), dessert(far_breton))

Il suffit pour cela de placer un terme composé dans la tête de la règle :

repas(rep(entree(E), plat(P), dessert(D))) :-
    entree(E),
    plat(P),
    dessert(D).

Le prédicat s’appelle toujours repas, mais c’est un repas/1 : un nouveau prédicat, distinct de repas/3. Remarquez que les foncteurs rep, entree, plat et dessert qui apparaissent dans le terme ne sont pas des appels : ce sont de simples étiquettes qui structurent la donnée. Le même nom plat joue deux rôles, prédicat dans le corps et foncteur dans la tête, sans que Prolog les confonde.

Les foncteurs rep, entree, plat et dessert ne sont que des étiquettes qui structurent la réponse ; seules les feuilles viennent des buts du corps.

Ce procédé est l’équivalent Prolog des objets ou des dictionnaires : on construit des structures de données en imbriquant des termes. Vous le retrouverez au chapitre 4 pour représenter un itinéraire, et au chapitre 6 avec les listes.

Attention

Un terme composé n’est jamais « évalué ». plat(cotriade) écrit dans la tête d’une règle ne vérifie pas que la cotriade est un plat : c’est seulement une structure à deux étages. Seuls les buts du corps sont démontrés.

L’ordre des buts dans une question

Un client ne veut que des repas avec du poisson. Deux questions possibles :

?- repas(E, P, D), poisson(P).
?- poisson(P), repas(E, P, D).

Logiquement, elles sont équivalentes : le « et » est commutatif. Elles donnent d’ailleurs les mêmes 18 solutions (3 entrées × 2 poissons × 3 desserts). Mais le travail effectué n’est pas du tout le même.

• La première génère les 36 repas, puis teste pour chacun si le plat est un poisson. La moitié du travail est jetée.
• La seconde fixe d’abord P à un poisson, puis ne construit que les repas qui contiennent ce poisson. Rien n’est gaspillé.

L’ordre des solutions change aussi. La première question énumère entrée par entrée (la salade de chèvre avec la cotriade et ses 3 desserts, puis avec les noix de Saint-Jacques…), la seconde poisson par poisson (les 9 repas à la cotriade, puis les 9 aux Saint-Jacques).

Les deux questions rendent les mêmes 18 repas, mais générer puis tester en construit 36 et en jette la moitié.

Piège

Le « et » de Prolog est logiquement commutatif, mais pas son exécution : les buts sont traités de gauche à droite. Placez en premier les buts qui filtrent le plus. Sur une petite carte, cela ne change que le temps de calcul ; vous verrez au chapitre 4 que, dans une règle récursive, cela peut décider si le programme termine ou tourne indéfiniment.

Pourquoi cet ordre gauche-droite, et comment Prolog revient-il en arrière pour trouver la solution suivante ? C’est tout l’objet du chapitre suivant.

En résumé

• Une règle tete :- corps. se lit « la tête est vraie si le corps est vrai » ; un fait est une règle sans corps.
• Dans le corps, la virgule est un et ; plusieurs clauses d’un même prédicat forment un ou.
• Les variables sont locales à leur clause ; celles qui n’apparaissent que dans le corps se lisent « il existe ».
• Prolog exprime l’algèbre relationnelle : sélection, projection, union, produit cartésien, et jointure par variable partagée.
• On renvoie des objets structurés en plaçant un terme composé dans la tête ; ses foncteurs sont des étiquettes, jamais des appels.
• L’ordre des buts ne change pas l’ensemble des solutions (ici), mais change leur ordre et le travail effectué : filtrez tôt.

Exercices

Exercice · Écrire des règles simples

facile

Avec la carte et les prix du chapitre, écrivez :

1. formule_mer(E, P), vraie si E est une entrée et P un plat de poisson ;
2. sucre_ou_sale(X), vraie si X est un dessert ou une entrée ;
3. plat_abordable(P), vraie si P est un plat (viande ou poisson) qui coûte au plus 10 euros (l’opérateur « inférieur ou égal » s’écrit =<).

Voir la solution

formule_mer est un produit cartésien (6 solutions), sucre_ou_sale une union (deux clauses), et plat_abordable une jointure suivie d’une sélection. Ses solutions sont galette_saucisse (9 euros) et galette_complete (10 euros).

En code

Prolog

formule_mer(E, P) :- entree(E), poisson(P).

sucre_ou_sale(X) :- dessert(X).
sucre_ou_sale(X) :- entree(X).

plat_abordable(P) :- plat(P), prix(P, Euros), Euros =< 10.

% ?- findall(E-P, formule_mer(E, P), L), length(L, N).   N = 6
% ?- plat_abordable(P).   P = galette_saucisse ; P = galette_complete

Python

entree = ["salade_de_chevre", "veloute_de_potiron", "huitres_de_cancale"]
viande = ["galette_saucisse", "galette_complete"]
poisson = ["cotriade", "noix_de_saint_jacques"]
dessert = ["far_breton", "crepe_caramel_beurre_sale", "kouign_amann"]
prix = {"salade_de_chevre": 7, "veloute_de_potiron": 6, "huitres_de_cancale": 12,
        "galette_saucisse": 9, "galette_complete": 10, "cotriade": 16,
        "noix_de_saint_jacques": 18, "far_breton": 4,
        "crepe_caramel_beurre_sale": 5, "kouign_amann": 5}
plat = viande + poisson                     # plat/1 : union de deux clauses

formule_mer = [(e, p) for e in entree for p in poisson]    # produit cartésien
sucre_ou_sale = dessert + entree                            # union (clause 1, puis 2)
plat_abordable = [p for p in plat if prix[p] <= 10]         # jointure + sélection

print(len(formule_mer))     # 6
print(sucre_ou_sale[:4])    # ['far_breton', 'crepe_caramel_beurre_sale', 'kouign_amann', 'salade_de_chevre']
print(plat_abordable)       # ['galette_saucisse', 'galette_complete']

R

entree  <- c("salade_de_chevre", "veloute_de_potiron", "huitres_de_cancale")
viande  <- c("galette_saucisse", "galette_complete")
poisson <- c("cotriade", "noix_de_saint_jacques")
dessert <- c("far_breton", "crepe_caramel_beurre_sale", "kouign_amann")
prix <- c(salade_de_chevre = 7, veloute_de_potiron = 6, huitres_de_cancale = 12,
          galette_saucisse = 9, galette_complete = 10, cotriade = 16,
          noix_de_saint_jacques = 18, far_breton = 4,
          crepe_caramel_beurre_sale = 5, kouign_amann = 5)
plat <- c(viande, poisson)                  # plat/1 : union de deux clauses

formule_mer <- expand.grid(P = poisson, E = entree)[, c("E", "P")]   # produit cartésien
sucre_ou_sale <- c(dessert, entree)                                  # union
plat_abordable <- plat[prix[plat] <= 10]                             # jointure + sélection

nrow(formule_mer)        # 6
head(sucre_ou_sale, 4)   # "far_breton" "crepe_caramel_beurre_sale" "kouign_amann" "salade_de_chevre"
plat_abordable           # "galette_saucisse" "galette_complete"

Exercice · Les commandes du soir

moyen

On enregistre les commandes du soir sous la forme commande(Table, Plat) :

commande(table1, cotriade).
commande(table1, far_breton).
commande(table2, galette_complete).
commande(table3, cotriade).
commande(table3, kouign_amann).

Écrivez :

1. table_mer(T) : la table T a commandé au moins un plat de poisson ;
2. depense_dessert(T, D, Euros) : la table T a commandé le dessert D, qui coûte Euros ;
3. voisins_de_gout(T1, T2) : les tables T1 et T2, différentes, ont commandé un même plat. On écrira T1 \= T2 pour exprimer que T1 et T2 sont différentes.

Quelles réponses donne ?- voisins_de_gout(T1, T2). ?

Voir la solution

Le test T1 \= T2 est placé en dernier, quand les deux variables ont une valeur (nous verrons au chapitre 8 pourquoi un test de différence sur des variables libres pose problème). La jointure se fait sur P. Les réponses sont T1 = table1, T2 = table3 puis T1 = table3, T2 = table1 : le couple apparaît dans les deux sens, car rien n’impose d’ordre entre T1 et T2.

En code

Prolog

table_mer(T) :- commande(T, P), poisson(P).

depense_dessert(T, D, Euros) :- commande(T, D), dessert(D), prix(D, Euros).

voisins_de_gout(T1, T2) :-
    commande(T1, P),
    commande(T2, P),
    T1 \= T2.

% ?- table_mer(T).                  T = table1 ; T = table3
% ?- depense_dessert(T, D, E).      T = table1, D = far_breton, E = 4 ;
%                                   T = table3, D = kouign_amann, E = 5
% ?- voisins_de_gout(T1, T2).       T1 = table1, T2 = table3 ;
%                                   T1 = table3, T2 = table1

Python

poisson = ["cotriade", "noix_de_saint_jacques"]
dessert = ["far_breton", "crepe_caramel_beurre_sale", "kouign_amann"]
prix = {"far_breton": 4, "crepe_caramel_beurre_sale": 5, "kouign_amann": 5}
commande = [("table1", "cotriade"), ("table1", "far_breton"),
            ("table2", "galette_complete"), ("table3", "cotriade"),
            ("table3", "kouign_amann")]

# table_mer(T) : dict.fromkeys retire les doublons en gardant l'ordre
table_mer = list(dict.fromkeys(t for t, p in commande if p in poisson))
depense_dessert = [(t, d, prix[d]) for t, d in commande if d in dessert]

def voisins_de_gout():
    for t1, p in commande:            # commande(T1, P)
        for t2, p2 in commande:       # commande(T2, P), jointure sur P
            if p2 == p and t1 != t2:  # T1 \= T2, testé en dernier
                yield t1, t2

print(table_mer)                # ['table1', 'table3']
print(depense_dessert)          # [('table1', 'far_breton', 4), ('table3', 'kouign_amann', 5)]
print(list(voisins_de_gout()))  # [('table1', 'table3'), ('table3', 'table1')]

R

poisson <- c("cotriade", "noix_de_saint_jacques")
dessert <- c("far_breton", "crepe_caramel_beurre_sale", "kouign_amann")
prix <- c(far_breton = 4, crepe_caramel_beurre_sale = 5, kouign_amann = 5)
commande <- data.frame(
  table = c("table1", "table1", "table2", "table3", "table3"),
  plat  = c("cotriade", "far_breton", "galette_complete", "cotriade", "kouign_amann"))

table_mer <- unique(commande$table[commande$plat %in% poisson])
dd <- commande[commande$plat %in% dessert, ]
depense_dessert <- data.frame(dd, euros = prix[dd$plat], row.names = NULL)

# voisins_de_gout : jointure de commande avec elle-même sur le plat, puis T1 != T2
j <- merge(commande, commande, by = "plat", suffixes = c("1", "2"))
voisins <- j[j$table1 != j$table2, c("table1", "table2")]

table_mer          # "table1" "table3"
depense_dessert    # table1 far_breton 4 ; table3 kouign_amann 5
voisins            # table1 table3 ; table3 table1

Exercice · Un repas qui dit ce qu'il contient

moyen

Modifiez repas/1 pour que le plat indique aussi s’il s’agit de viande ou de poisson, sous la forme :

R = rep(entree(salade_de_chevre), plat(cotriade, poisson), dessert(far_breton))

Écrivez ensuite la question qui ne renvoie que les repas de poisson, de la façon la plus efficace possible.

Voir la solution

On introduit un prédicat auxiliaire qui associe un plat à sa nature (onglet Prolog ci-dessous).

nature/2 remplace plat/1 : chacune de ses clauses produit un plat et sa nature. Pour ne garder que les repas de poisson, le plus efficace est de fixer la nature dans la question elle-même :

?- repas(rep(E, plat(P, poisson), D)).

Le terme de la question impose N = poisson dès l’appel. La première clause de nature échoue alors immédiatement (l’atome viande ne correspond pas à poisson), et Prolog ne construit que les 18 repas de poisson, sans générer puis jeter les repas de viande.

En code

Prolog

nature(P, viande) :- viande(P).
nature(P, poisson) :- poisson(P).

repas(rep(entree(E), plat(P, N), dessert(D))) :-
    entree(E),
    nature(P, N),
    dessert(D).

% ?- findall(P, repas(rep(_, plat(P, poisson), _)), L), length(L, N).
% N = 18

Python

entree = ["salade_de_chevre", "veloute_de_potiron", "huitres_de_cancale"]
viande = ["galette_saucisse", "galette_complete"]
poisson = ["cotriade", "noix_de_saint_jacques"]
dessert = ["far_breton", "crepe_caramel_beurre_sale", "kouign_amann"]
essais = 0                                  # nombre de plats construits

def nature(n=None):
    """nature(P, N) : chaque clause produit un plat et sa nature."""
    global essais
    for n_clause, plats in [("viande", viande), ("poisson", poisson)]:
        if n is None or n == n_clause:       # la clause est écartée dès la tête
            for p in plats:
                essais += 1
                yield p, n_clause

def repas(n=None):
    for e in entree:
        for p, nat in nature(n):
            for d in dessert:
                yield ("rep", ("entree", e), ("plat", p, nat), ("dessert", d))

r = list(repas("poisson"))                  # ?- repas(rep(E, plat(P, poisson), D)).
print(len(r), essais)                       # 18 6 : seuls les 6 plats de poisson
print(r[0])   # ('rep', ('entree', 'salade_de_chevre'), ('plat', 'cotriade', 'poisson'), ('dessert', 'far_breton'))
essais = 0
print(len([x for x in repas() if x[2][2] == "poisson"]), essais)   # 18 12 : générer puis tester

R

entree  <- c("salade_de_chevre", "veloute_de_potiron", "huitres_de_cancale")
viande  <- c("galette_saucisse", "galette_complete")
poisson <- c("cotriade", "noix_de_saint_jacques")
dessert <- c("far_breton", "crepe_caramel_beurre_sale", "kouign_amann")

# nature(P, N) : une ligne par clause, le plat et sa nature
nature <- rbind(data.frame(P = viande, N = "viande"),
                data.frame(P = poisson, N = "poisson"))

# repas avec la nature fixée d'avance : on filtre nature AVANT de combiner
repas <- function(n) {
  plats <- nature[nature$N == n, ]
  g <- expand.grid(D = dessert, i = seq_len(nrow(plats)), E = entree)
  data.frame(E = g$E, P = plats$P[g$i], N = plats$N[g$i], D = g$D)
}
r <- repas("poisson")
nrow(r)      # 18
r[1, ]       # salade_de_chevre cotriade poisson far_breton