Prolog essaie un choix, puis revient en arrière
Le retour arrière est la façon dont Prolog cherche une réponse. Il fait un choix, et s’il échoue, il revient au choix précédent pour en essayer un autre.
C’est ainsi qu’un programme de quelques lignes trouve tous les trajets d’une carte. Un site de billets de train doit lister tous les itinéraires de Paris à Marseille. Prolog les trouve un par un, en essayant chaque ligne dans l’ordre. Cette leçon commence par les listes, la matière sur laquelle il travaille.
À la fin de cette leçon
Remarque
Je peux expliquer comment Prolog cherche et revient en arrière.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Liste | des éléments dans l’ordre, entre crochets | [a, b, c] |
| Tête et queue | le premier élément d’une liste et la liste de tous les autres | [T|Q] |
| Point de choix | un endroit où Prolog a plusieurs possibilités à essayer | |
| Retour arrière | revenir au dernier point de choix pour essayer la possibilité suivante | |
| Échec | une condition qui est fausse, ce qui déclenche le retour arrière |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une liste a une tête et une queue
Une liste s’écrit entre crochets : [rouge, vert, bleu]. La liste vide s’écrit [].
On coupe une liste en une tête, son premier élément, et une queue, la liste de tous les autres. [T|Q] désigne cette coupe. La plupart des règles sur les listes traitent la tête, puis rappellent la règle sur la queue.
Deux règles du fichier lists.pl
% lists.pl : [T|Q] coupe une liste en une tête T et une queue Q.
total([], 0).
total([T|Q], Somme) :- total(Q, Reste), Somme is Reste + T.
last_of([X], X).
last_of([_|Q], X) :- last_of(Q, X).
Ce que Prolog écrit reste en anglais
Les noms de prédicats comme total ou last_of, et les mots que Prolog écrit, restent en anglais. Les Runs suivants chargent lists.pl ou n’ont besoin d’aucun fichier.
Couper une liste en tête et queue
docker exec prolog swipl -q -g "[T|Q] = [1, 2, 3], write(T), nl, write(Q), nl" -t haltAffiché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.
La somme d’une liste
docker exec prolog swipl -q -g "total([4, 8, 15], S), write(S), nl" -t halt lists.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.
Le dernier élément
docker exec prolog swipl -q -g "last_of([a, b, c], X), write(X), nl" -t halt lists.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.
La longueur d’une liste
docker exec prolog swipl -q -g "length([a, b, c], N), write(N), nl" -t haltAffiché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.
Le retour arrière essaie la possibilité suivante
Dans member(X, [1, 2, 3, 4]), X > 2, le prédicat member offre quatre choix pour X. Prolog prend le premier. Le test X > 2 échoue : c’est un échec.
Prolog fait alors un retour arrière : il revient au point de choix de member et essaie le choix suivant. Il s’arrête au premier qui réussit.
Exemple travaillé : X plus grand que 2
| Essai | Valeur de X | Test X > 2 | Ce que fait Prolog |
|---|---|---|---|
| 1 | 1 | Échec | Retour arrière |
| 2 | 2 | Échec | Retour arrière |
| 3 | 3 | Réussite | Il écrit 3 et s’arrête |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Erreur fréquente
Attention
Beaucoup de gens pensent que Prolog calcule toutes les réponses en même temps. Il en cherche une à la fois. Il ne revient en arrière que si un test échoue ou si vous demandez la réponse suivante.
Le premier élément plus grand que 2
docker exec prolog swipl -q -g "member(X, [1, 2, 3, 4]), X > 2, write(X), nl" -t haltAffiché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 choix, un par ligne
docker exec prolog swipl -q -g "forall(member(X, [rouge, vert, bleu]), (write(X), nl))" -t haltAffiché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.
Deux points de choix l’un dans l’autre
docker exec prolog swipl -q -g "forall((member(X, [a, b]), member(Y, [1, 2])), (write(X-Y), nl))" -t haltAffiché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.
Toutes les façons de couper une liste
docker exec prolog swipl -q -g "forall(append(X, Y, [1, 2, 3]), (write(X-Y), nl))" -t haltAffiché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.
Chercher tous les chemins d’une carte
Le retour arrière sert à énumérer des chemins. Une règle chemin suit une ligne, puis rappelle chemin depuis la ville suivante. Elle garde la liste des villes déjà vues.
Le test \+ member(C, Vus) veut dire « C n’est pas déjà vue ». Sans lui, Lyon et Avignon, reliées dans les deux sens, feraient tourner la recherche sans fin.
Exemple : un réseau de lignes et sa règle
ligne(paris, dijon).
ligne(paris, lyon).
ligne(dijon, lyon).
ligne(lyon, avignon).
ligne(lyon, marseille).
ligne(avignon, lyon).
ligne(avignon, marseille).
chemin(A, A, _, [A]).
chemin(A, B, Vus, [A|Reste]) :-
ligne(A, C),
\+ member(C, Vus),
chemin(C, B, [C|Vus], Reste).
Les chemins de Paris à Marseille, dans l’ordre
| Numéro | Chemin trouvé | Par quel choix |
|---|---|---|
| 1 | Paris, Dijon, Lyon, Avignon, Marseille | Premier choix à chaque ville |
| 2 | Paris, Dijon, Lyon, Marseille | Retour à Lyon : deuxième ligne |
| 3 | Paris, Lyon, Avignon, Marseille | Retour à Paris : deuxième ligne |
| 4 | Paris, Lyon, Marseille | Retour à Lyon : deuxième ligne |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Pour aller plus loin
Ajoutez à la carte une ligne de Dijon vers Marseille. Combien de chemins de Paris à Marseille avez-vous ensuite ? Répondez d’abord sur papier avec le tableau, puis vérifiez avec votre fonction Python.
Dites aussi ce qui se passe si vous retirez le test « pas déjà vue ».