Découvrez la programmation logique

Dans la plupart des langages que vous connaissez, programmer consiste à donner des ordres : « crée une liste vide, parcours le tableau, si la case vaut ceci, ajoute-la ». Prolog propose un tout autre contrat. Vous décrivez un petit monde avec des faits et des règles, puis vous lui posez des questions, et c’est le langage qui cherche les réponses.

Dans ce chapitre, vous allez découvrir ce style de programmation, la matière première du langage (les termes) et vos premières questions. Nous suivrons la carte d’une crêperie rennaise, que nous enrichirons au chapitre suivant.

Dire ce qui est vrai plutôt que comment le calculer

Imaginez que vous vouliez savoir quels desserts propose la crêperie. En Python, vous stockeriez la carte dans une structure, puis vous écririez une boucle pour filtrer les desserts. En Prolog, vous écrivez simplement ce qui est vrai :

dessert(far_breton).
dessert(crepe_caramel_beurre_sale).
dessert(kouign_amann).

Puis vous demandez : « quels sont les X tels que X est un dessert ? ». Aucune boucle, aucune structure de données : la question elle-même décrit ce que vous cherchez.

On appelle ce style la programmation déclarative : le programme déclare des connaissances, et un moteur générique se charge de les exploiter. Vous connaissez déjà un langage déclaratif, sans forcément le savoir : SQL. Quand vous écrivez SELECT nom FROM carte WHERE type = 'dessert', vous ne dites pas au moteur comment parcourir la table, vous décrivez le résultat voulu. Prolog pousse cette idée plus loin, jusqu’à la récursivité et au calcul.

Prolog (pour « programmation en logique ») est né à Marseille au début des années 1970, pour traiter la langue naturelle. Il repose sur un fragment de la logique des prédicats : un programme est un ensemble de clauses de Horn, c’est-à-dire d’énoncés de la forme « A est vrai si B1 et B2 et … sont vrais ». Dans ce cours, nous utiliserons ECLiPSe, un système Prolog développé pour la programmation par contraintes, mais tout ce qui suit fonctionne aussi dans SWI-Prolog ou GNU Prolog, à de petites différences d’affichage près.

Les termes : la matière première de Prolog

Tout, en Prolog, est un terme. Il en existe quatre sortes, et la différence se voit à l’écriture.

Un atome est une constante symbolique. Il commence par une minuscule (far_breton, rennes, crepe2) ou s’écrit entre apostrophes s’il contient des espaces ou des caractères spéciaux ('Saint-Malo', 'crêpe au sucre').
Un nombre est entier (42, -7) ou flottant (3.14).
Une variable commence par une majuscule ou par un tiret bas : X, Dessert, _Prix, _. Le tiret bas seul est la variable anonyme, qui signifie « peu importe la valeur ».
Un terme composé est formé d’un foncteur (un atome) suivi d’arguments entre parenthèses : galette(complete, 9), repas(entree(salade), dessert(far)). Les arguments sont eux-mêmes des termes, ce qui permet d’imbriquer les structures aussi profondément que l’on veut.

On désigne un foncteur par son nom et son arité (son nombre d’arguments), séparés par une barre oblique : galette/2, dessert/1. Deux foncteurs de même nom mais d’arités différentes sont complètement distincts : repas/1 et repas/3 n’ont rien à voir pour Prolog.

Un terme composé se représente naturellement comme un arbre : le foncteur à la racine, les arguments comme enfants. Le terme commande(table(4), galette(complete, 9)) est un arbre dont la racine commande a deux enfants, eux-mêmes des arbres. Cette vision arborescente vous servira pour les listes et pour l’unification.

Même une expression comme 2 + 3 est un terme composé : c’est une autre écriture de +(2, 3), un arbre de racine +. Prolog ne la calcule pas d’elle-même, nous y reviendrons au chapitre 5.

Un terme composé est un arbre : le foncteur à la racine, les arguments en dessous. 2 + 3 n'est qu'un arbre de racine +, pas le nombre 5.

Les faits : décrire un petit monde

Un fait affirme qu’une relation est vraie, sans condition. Il s’écrit comme un terme suivi d’un point. Voici la carte complète de notre crêperie :

/* Carte de la crêperie « Le Bilig » */

% les entrées
entree(salade_de_chevre).
entree(veloute_de_potiron).
entree(huitres_de_cancale).

% les plats à base de viande
viande(galette_saucisse).
viande(galette_complete).

% les plats à base de poisson
poisson(cotriade).
poisson(noix_de_saint_jacques).

% les desserts
dessert(far_breton).
dessert(crepe_caramel_beurre_sale).
dessert(kouign_amann).

Chaque prédicat est une petite table ; chaque fait en est une ligne, et l'ordre des faits est celui du fichier.

Quelques règles d’écriture à connaître :

le nom d’une relation (on dit un prédicat) est un atome : entree, viande ;
chaque clause se termine par un point, l’oubli le plus fréquent des débutants ;
les commentaires s’écrivent % jusqu'à la fin de la ligne ou /* sur plusieurs lignes */ ;
les clauses d’un même prédicat doivent être regroupées dans le fichier. ECLiPSe, comme la plupart des systèmes, signale une erreur ou un avertissement si des clauses entree/1 sont dispersées entre des clauses d’autres prédicats.

Un fait peut avoir plusieurs arguments. prix(far_breton, 4). relie un dessert à son prix, liaison(rennes, laval). relie deux villes. C’est à vous de fixer le sens de chaque argument, et de vous y tenir : Prolog ne sait pas que le premier argument de prix est un plat. Un commentaire en tête de prédicat, comme % prix(Plat, Euros), évite bien des erreurs.

Poser des questions

Une fois le fichier écrit (disons bilig.pl), on le charge dans l’interpréteur, puis on pose des questions après l’invite ?-. Une question peut être de deux natures.

Une question fermée : vérifier

Une question sans variable demande si un fait est démontrable :

?- poisson(cotriade).
Yes

?- dessert(cotriade).
No

La cotriade est bien un poisson ; ce n’est pas un dessert, puisque rien dans la base ne permet de le démontrer.

Une question ouverte : chercher

Une question avec des variables demande pour quelles valeurs elle est vraie :

?- entree(E).
E = salade_de_chevre ;
E = veloute_de_potiron ;
E = huitres_de_cancale.

Prolog renvoie la première solution, puis attend. En tapant un point-virgule (;), vous demandez la suivante ; il répond enfin qu’il n’y en a plus. Remarquez que les solutions arrivent dans l’ordre des faits du fichier : ce n’est pas un hasard, et ce sera important. ECLiPSe affiche en plus des informations comme Yes (0.00s cpu, solution 1, maybe more), qui signalent qu’il reste peut-être d’autres solutions.

Une question peut combiner plusieurs buts séparés par des virgules, qui se lisent « et » :

?- entree(E), dessert(D).
E = salade_de_chevre, D = far_breton ;
E = salade_de_chevre, D = crepe_caramel_beurre_sale ;
...

Cette question énumère tous les couples entrée-dessert : 3 entrées fois 3 desserts, soit 9 solutions. Mais dans quel ordre ? Prolog fixe d’abord la première entrée, puis parcourt tous les desserts, avant de passer à l’entrée suivante, un peu comme deux boucles imbriquées. Le chapitre 3 expliquera précisément pourquoi.

Les 9 solutions sortent ligne par ligne : D parcourt les trois desserts avant que E ne passe à l'entrée suivante, comme deux boucles imbriquées.

Enfin, une variable qui apparaît plusieurs fois dans une question doit prendre la même valeur partout. C’est ainsi qu’on relie deux informations. Si la base contient prix(far_breton, 4). et prix(cotriade, 16)., la question suivante cherche les desserts et leur prix :

?- dessert(D), prix(D, P).
D = far_breton, P = 4 ;
...

La variable D fait le lien entre les deux buts : c’est une jointure, exactement comme en SQL.

Lire une réponse, et ce que « non » veut dire

Il faut bien comprendre ce que signifient les réponses de Prolog.

Yes (ou une substitution comme E = salade_de_chevre) veut dire : « j’ai trouvé une démonstration à partir de la base ».
No veut dire : « je n’ai pas trouvé de démonstration ». Ce n’est pas la même chose que « c’est faux dans le monde réel ».

Et la variable anonyme ? Elle sert quand un argument ne vous intéresse pas. Pour savoir si au moins un plat coûte 16 euros, sans vouloir savoir lequel, on écrit ?- prix(_, 16). Chaque occurrence de _ est une variable différente et Prolog n’affiche pas sa valeur.

Élément	Exemple	Reconnaissable à
Atome	`cotriade`, `'Saint-Malo'`	minuscule initiale ou apostrophes
Nombre	`4`, `3.5`	chiffres
Variable	`X`, `Plat`, `_`	majuscule ou tiret bas initial
Terme composé	`prix(cotriade, 16)`	foncteur suivi de parenthèses
Fait	`poisson(cotriade).`	terme suivi d’un point, dans le fichier
Question	`?- poisson(X).`	posée à l’interpréteur

En résumé

Prolog est un langage déclaratif : on décrit ce qui est vrai par des faits et des règles, et un moteur cherche les réponses.
Tout est terme : atome (minuscule), nombre, variable (majuscule ou _), terme composé (foncteur et arguments, vu comme un arbre).
Un prédicat se désigne par nom/arité ; ses clauses doivent être regroupées et chacune se termine par un point.
Une question fermée vérifie un fait ; une question ouverte énumère les valeurs des variables, dans l’ordre du fichier, avec ; pour la suivante.
Une variable répétée dans une question relie les buts entre eux, comme une jointure SQL.
« No » signifie « non démontrable à partir de la base », pas « faux dans l’absolu ».

Exercices

Exercice · Reconnaître les termes

facile

Pour chacun des éléments suivants, dites s’il s’agit d’un atome, d’un nombre, d’une variable ou d’un terme composé (et, dans ce cas, donnez son foncteur sous la forme nom/arité).

crepe, Crepe, 'Crêpe', _crepe, crepe(sucre), 12, prix(crepe(sucre), 3), 3 + 4.

Voir la solution

crepe : atome (minuscule initiale).
Crepe : variable (majuscule initiale).
'Crêpe' : atome, grâce aux apostrophes (la majuscule entre apostrophes ne compte pas).
_crepe : variable (tiret bas initial), mais nommée, donc différente de _.
crepe(sucre) : terme composé de foncteur crepe/1.
12 : nombre.
prix(crepe(sucre), 3) : terme composé de foncteur prix/2, dont le premier argument est lui-même un terme composé.
3 + 4 : terme composé de foncteur +/2, autre écriture de +(3, 4). Prolog ne le calcule pas.

En code

% nature(+T, -N) : les prédicats de typage de Prolog classent un terme
nature(T, variable) :- var(T).
nature(T, nombre) :- number(T).
nature(T, atome) :- atom(T).
nature(T, compose(F/A)) :- compound(T), functor(T, F, A).

% ?- nature(crepe, N).                    N = atome
% ?- nature(Crepe, N).                    N = variable
% ?- nature('Crêpe', N).                  N = atome
% ?- nature(_crepe, N).                   N = variable
% ?- nature(crepe(sucre), N).             N = compose(crepe/1)
% ?- nature(12, N).                       N = nombre
% ?- nature(prix(crepe(sucre), 3), N).    N = compose(prix/2)
% ?- nature(3 + 4, N).                    N = compose(F/A), avec F = + et A = 2

import re

def arite(args):
    """Compte les arguments séparés par des virgules de premier niveau."""
    prof, n = 0, 1
    for c in args:
        prof += (c in "([") - (c in ")]")
        n += (c == "," and prof == 0)
    return n

def nature(t):
    """Classe un terme Prolog d'après son écriture."""
    if re.fullmatch(r"-?\d+(\.\d+)?", t):
        return "nombre"
    if re.fullmatch(r"[A-Z_]\w*", t):
        return "variable"
    if re.fullmatch(r"[a-z]\w*|'[^']*'", t):
        return "atome"
    m = re.fullmatch(r"(\S+) ([-+*/]) (\S+)", t)        # opérateur infixe
    if m:
        return f"terme composé {m[2]}/2"
    m = re.fullmatch(r"([a-z]\w*)\((.*)\)", t)          # foncteur(arguments)
    return f"terme composé {m[1]}/{arite(m[2])}"

for t in ["crepe", "Crepe", "'Crêpe'", "_crepe", "crepe(sucre)", "12",
          "prix(crepe(sucre), 3)", "3 + 4"]:
    print(f"{t:22} {nature(t)}")
# crepe : atome            Crepe : variable       'Crêpe' : atome
# _crepe : variable        12 : nombre            crepe(sucre) : terme composé crepe/1
# prix(crepe(sucre), 3) : terme composé prix/2    3 + 4 : terme composé +/2

# Compte les arguments séparés par des virgules de premier niveau
arite <- function(args) {
  prof <- 0; n <- 1
  for (c in strsplit(args, "")[[1]]) {
    prof <- prof + (c %in% c("(", "[")) - (c %in% c(")", "]"))
    n <- n + (c == "," && prof == 0)
  }
  n
}
# Classe un terme Prolog d'après son écriture
nature <- function(t) {
  if (grepl("^-?[0-9]+(\\.[0-9]+)?$", t)) return("nombre")
  if (grepl("^[A-Z_][A-Za-z0-9_]*$", t)) return("variable")
  if (grepl("^([a-z][A-Za-z0-9_]*|'[^']*')$", t)) return("atome")
  if (grepl("^\\S+ [-+*/] \\S+$", t))                  # opérateur infixe
    return(paste0("terme composé ", strsplit(t, " ")[[1]][2], "/2"))
  foncteur <- sub("\\(.*", "", t)                      # foncteur(arguments)
  args <- sub("^[^(]*\\((.*)\\)$", "\\1", t)
  paste0("terme composé ", foncteur, "/", arite(args))
}
termes <- c("crepe", "Crepe", "'Crêpe'", "_crepe", "crepe(sucre)", "12",
            "prix(crepe(sucre), 3)", "3 + 4")
for (t in termes) cat(sprintf("%-22s %s\n", t, nature(t)))
# crepe : atome            Crepe : variable       'Crêpe' : atome
# _crepe : variable        12 : nombre            crepe(sucre) : terme composé crepe/1
# prix(crepe(sucre), 3) : terme composé prix/2    3 + 4 : terme composé +/2

Exercice · Interroger la carte

facile

Avec la carte de la crêperie, écrivez les questions qui permettent de savoir :

si le kouign-amann est un dessert ;
quels sont les plats de poisson ;
quels menus « entrée et plat de viande » on peut composer. Combien de solutions obtient-on ?

Voir la solution

?- dessert(kouign_amann). Réponse : Yes.
?- poisson(P). Réponses : P = cotriade, puis P = noix_de_saint_jacques.
?- entree(E), viande(V). On obtient 3 × 2 = 6 solutions, dans l’ordre : la salade de chèvre avec chacune des deux galettes, puis le velouté avec chacune, puis les huîtres avec chacune.

En code

?- dessert(kouign_amann).
% Yes

?- poisson(P).
% P = cotriade ;
% P = noix_de_saint_jacques

?- entree(E), viande(V).
% E = salade_de_chevre, V = galette_saucisse ;
% E = salade_de_chevre, V = galette_complete ;
% E = veloute_de_potiron, V = galette_saucisse ;
% ... 6 solutions en tout

?- findall(E-V, (entree(E), viande(V)), L), length(L, N).
% N = 6

# Les faits de la carte : une liste par prédicat, dans l'ordre du fichier
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"]

# 1. question fermée : ?- dessert(kouign_amann).
print("kouign_amann" in dessert)          # True

# 2. question ouverte : ?- poisson(P).
for p in poisson:
    print("P =", p)                       # cotriade, puis noix_de_saint_jacques

# 3. ?- entree(E), viande(V). : deux boucles imbriquées, comme le retour arrière
menus = [(e, v) for e in entree for v in viande]
print(len(menus))                         # 6
print(menus[:2])   # [('salade_de_chevre', 'galette_saucisse'), ('salade_de_chevre', 'galette_complete')]

# Les faits de la carte : un vecteur par prédicat, dans l'ordre du fichier
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")

# 1. question fermée : ?- dessert(kouign_amann).
"kouign_amann" %in% dessert        # TRUE

# 2. question ouverte : ?- poisson(P).
poisson                            # "cotriade" "noix_de_saint_jacques"

# 3. ?- entree(E), viande(V). : E varie lentement, V vite (ordre de Prolog)
menus <- data.frame(E = rep(entree, each = length(viande)),
                    V = rep(viande, times = length(entree)))
nrow(menus)                        # 6
head(menus, 2)   # salade_de_chevre avec galette_saucisse, puis galette_complete

Exercice · Trouver l'erreur

moyen

Un camarade a écrit ce fichier, et il s’étonne que ?- boisson(X). réponde X = cidre mais que ?- boisson(chouchen). réponde Yes alors qu’il n’a jamais déclaré de chouchen. Il s’étonne aussi d’un avertissement au chargement. Expliquez.

boisson(cidre).
dessert(far_breton).
boisson(Lait_ribot).

Voir la solution

Deux erreurs.

Lait_ribot commence par une majuscule : c’est une variable, pas un atome. Le fait boisson(Lait_ribot). signifie donc « pour tout X, X est une boisson ». Voilà pourquoi boisson(chouchen) est démontrable, comme n’importe quoi d’autre. Il fallait écrire boisson(lait_ribot). Avec la question ?- boisson(X)., Prolog donne d’abord X = cidre, puis, si on demande la suite, une réponse où X reste libre, ce qui trahit le problème.
Les clauses de boisson/1 ne sont pas regroupées : la clause de dessert/1 s’intercale entre elles. C’est la cause de l’avertissement (clauses discontiguës). Le système peut aussi signaler que Lait_ribot est une variable « singleton », qui n’apparaît qu’une fois dans sa clause : c’est souvent le signe d’une faute de frappe. Il faut placer les deux clauses boisson l’une après l’autre.

En code

% version corrigée : un atome, et les deux clauses de boisson/1 regroupées
boisson(cidre).
boisson(lait_ribot).

dessert(far_breton).

% ?- boisson(chouchen).   No
% ?- boisson(X).          X = cidre ; X = lait_ribot

LIBRE = None   # une variable dans un fait : s'unifie avec n'importe quelle valeur

# boisson(cidre).  boisson(Lait_ribot).
boisson = ["cidre", LIBRE]

def demontre(faits, x):
    """Question fermée : un fait égal à x, ou un fait « variable »."""
    return any(f is LIBRE or f == x for f in faits)

print(demontre(boisson, "chouchen"))    # True : tout est une boisson
print(["X libre" if f is LIBRE else f for f in boisson])   # ['cidre', 'X libre']

corrige = ["cidre", "lait_ribot"]       # boisson(lait_ribot). avec une minuscule
print(demontre(corrige, "chouchen"))    # False

# Clauses discontiguës : un prédicat qui réapparaît après un autre
fichier = ["boisson", "dessert", "boisson"]          # ordre des clauses du fichier
for i, p in enumerate(fichier):
    if p in fichier[:i] and fichier[i - 1] != p:
        print("clauses discontiguës :", p)           # clauses discontiguës : boisson

# boisson(cidre).  boisson(Lait_ribot).  NA joue le rôle de la variable
boisson <- c("cidre", NA)

# Question fermée : un fait égal à x, ou un fait « variable » (NA)
demontre <- function(faits, x) any(is.na(faits) | faits == x)

demontre(boisson, "chouchen")       # TRUE : tout est une boisson
ifelse(is.na(boisson), "X libre", boisson)   # "cidre" "X libre"

corrige <- c("cidre", "lait_ribot")  # boisson(lait_ribot). avec une minuscule
demontre(corrige, "chouchen")       # FALSE

# Clauses discontiguës : un prédicat qui réapparaît après un autre
fichier <- c("boisson", "dessert", "boisson")
for (i in seq_along(fichier)[-1])
  if (fichier[i] %in% fichier[1:(i - 1)] && fichier[i - 1] != fichier[i])
    cat("clauses discontiguës :", fichier[i], "\n")   # boisson