Une règle déduit un fait à partir d’autres
Une règle Prolog est un fait qui dépend d’autres faits : elle dit qu’une chose est vraie si d’autres choses le sont. Grâce aux règles, un petit fichier de faits répond à des questions qu’il ne contient pas.
Le fichier ne dit pas qui est le grand-parent de qui. Une seule règle le déduit des liens parent-enfant. Avec la récursivité, une autre règle remonte toute la famille, quel que soit le nombre de générations.
À la fin de cette leçon
Remarque
Je peux écrire une règle qui utilise d’autres faits, y compris une règle récursive.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Règle | un fait qui est vrai si d’autres faits le sont | |
| Tête | la partie de la règle avant :- | grandparent(X, Z) |
| Corps | la partie de la règle après :-, des conditions séparées par des virgules | |
| Récursivité | une règle qui s’appelle elle-même | |
| Cas de base | la règle qui arrête la récursivité | ancestor(X, Y) :- parent(X, Y). |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une règle a une tête et un corps
Une règle s’écrit avec :-, qui se lit « si ». À gauche, la tête : ce que la règle conclut. À droite, le corps : ce qui doit être vrai. Une virgule dans le corps veut dire « et ».
grandparent(X, Z) :- parent(X, Y), parent(Y, Z). se lit : X est un grand-parent de Z si X est un parent de Y, et Y un parent de Z.
Le fichier family.pl du labo
% family.pl : une règle dit « la tête est vraie si le corps est vrai ».
% La virgule veut dire « et ».
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.
% Une règle qui s’utilise elle-même.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
Ce que Prolog écrit reste en anglais
Les noms des personnes viennent des fichiers du labo et restent en anglais. Le Run ci-dessous interroge la règle grandparent de family.pl : il charge ce fichier à la fin de la commande.
Les petits-enfants de Tom
docker exec prolog swipl -q -g "forall(grandparent(tom, Z), (write(Z), nl))" -t halt family.plAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Exemple travaillé : grandparent(tom, Z)
| Étape | Ce que Prolog essaie | Résultat |
|---|---|---|
| 1 | parent(tom, Y) : premier fait | Y = ann |
| 2 | parent(ann, Z) | Z = cat |
| 3 | Retour à l’étape 1, fait suivant | Y = ben |
| 4 | parent(ben, Z) | Z = dan, puis Z = eve |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une règle donnée dans la commande
docker exec prolog swipl -q -g "assertz((grand_parent(X, Z) :- parent(X, Y), parent(Y, Z))), findall(Z, grand_parent(tom, Z), L), write(L), nl" -t halt facts.plAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Tous les frères et sœurs
docker exec prolog swipl -q -g "findall(X-Y, sibling(X, Y), L), write(L), nl" -t halt family.plAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une règle récursive remonte la famille
Combien de générations séparent deux personnes ? Une règle fixe ne peut pas le savoir. La récursivité résout cela : la règle s’utilise elle-même.
Un ancêtre est soit un parent, soit un parent d’un ancêtre. La première ligne est le cas de base, qui arrête la recherche. La seconde rappelle la règle, avec une personne plus proche.
Exemple travaillé : ancestor(X, dan)
| Clause essayée | Ce qui se passe | X |
|---|---|---|
| Cas de base : parent(X, dan) | Le fait parent(ben, dan) correspond | ben |
| Récursive, premier essai : X = tom, Z = ann | ancestor(ann, dan) échoue : aucun lien | Retour arrière |
| Récursive, essai suivant : X = tom, Z = ben | ancestor(ben, dan) réussit par le cas de base | tom |
| Récursive, faits suivants de parent | ann-cat, ben-dan, ben-eve : échec à chaque fois | Aucun autre |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Les ancêtres de Dan
docker exec prolog swipl -q -g "findall(X, ancestor(X, dan), L), write(L), nl" -t halt family.plAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Les descendants de Tom
docker exec prolog swipl -q -g "findall(Y, ancestor(tom, Y), L), write(L), nl" -t halt family.plAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ann est-elle une ancêtre d’Eve ?
docker exec prolog swipl -q -g "(ancestor(ann, eve) -> write(oui) ; write(non)), nl" -t halt family.plAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup de gens pensent que l’ordre des lignes d’un programme Prolog ne compte pas, comme dans une phrase de logique. Prolog essaie les clauses de haut en bas et les conditions de gauche à droite. Placer l’appel récursif avant le cas de base peut faire tourner le programme sans fin.
Pour aller plus loin
Ajoutez dans une copie de family.pl une règle cousin(X, Y) : deux personnes sont cousines si leurs parents sont frères ou sœurs. Servez-vous de sibling et de parent.
Posez ensuite la requête cousin(X, Y) et vérifiez que Cat, Dan et Eve se trouvent cousins, dans les deux sens.