Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

Règles complexes – Découverte

Cette activité de découverte consiste à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.

Activité de découverte B.dec

Introduction

Nous allons découvrir comment et pourquoi écrire des règles récursives, mais aussi quelques briques de constructions permettant d’enrichir la puissance d’expression des prédicats, telles que la négation, les variables anonymes, et le moyen de réaliser des calculs arithmétiques.

B.dec1 : Récursivité

On introduit une nouvelle relation qui décrit une hiérarchie entre joueurs. Cette relation est définie par le prédicat mentor.

pB1

Dans le code Prolog, ce prédicat est défini par les faits suivants :

mentor(anne,charlie).
mentor(charlie,dave).
mentor(dave,edouard).
mentor(anne,bart).

On définit un prédicat sup, représentant le concept de supérieur hiérarchique, de la manière suivante :

sup(S,J) :- mentor(S,J).
sup(S,J) :- mentor(S,T), sup(T,J).

Ce prédicat est récursif. Il est définit par deux clauses qui pourraient être traduite en français de la manière suivante.

Première clause :

Si S est un mentor de J, alors S est un supérieur hiérarchique de J.

Deuxième clause :

Si S est un mentor de T et si T est un supérieur hiérarchique de J, alors S est un supérieur hiérarchique de J.

Par exemple, le but…

sup(S,edouard).

…a pour résultat :

S = dave
S = anne
S = charlie

Dans un Prolog idéal, on devrait pouvoir donner les sous-buts d’une clause dans n’importe quel ordre, et écrire par exemple :

sup(S,J) :- mentor(S,J).
sup(S,J) :- sup(T,J), mentor(S,T).

Mais en pratique, une telle implémentation va conduire à des bouclages infinis lors de l’exécution de certains buts.

La bonne pratique à respecter est de faire les appels récursifs le plus tardivement possible dans la liste des sous-buts des clauses récursives.

Exercice de découverte B.x1

Sans utiliser d’interpréteur Prolog, déterminez le résultat du but suivant :

sup(charlie,J).
"Réponse"

J = dave
J = edouard


On dit que deux joueurs sont condisciples s’ils ont au moins un supérieur hiérarchique commun. Spécifiez un prédicat cond/2 tel que cond(A,B) est satisfait si et seulement si A et B sont condisciples.

"Réponse"

cond(A,B) :- sup(S,A), sup(S,B).

B.dec2 : Négation et variables anonymes

On dit qu’un joueur L est leader d’un joueur J si et seulement si L est un supérieur hiérarchique de J et n’a lui-même aucun supérieur hiérarchique.

Pour définir le prédicat leader exprimant cette propriété, nous utilisons une négation et une variable anonyme :

leader(L,J) :- sup(L,J), not(mentor(_,L)).

Le premier sous-but étant évident, intéressons-nous au deuxième :

  • Dans mentor(_,L), le symbole _ représente une variable dont la valeur n’est pas réutilisée et n’a pas d’importance. Le but mentor(_,L) est satisfait si L a au moins un mentor, dont le nom est sans importance.
  • La négation not(mentor(_,L)) a pour résultat la négation logique de l’évaluation de mentor(_,L).

L’évaluation d’une négation ne peut pas instancier de variable. Son résultat est juste une valeur de vérité, true ou false. En d’autres termes, les variables situées dans un not ne peuvent être utilisées comme sorties. Si elle ne sont pas instanciées (n’ont pas de valeur) au moment de l’évaluation du not, elle sont considérées comme des variables anonymes.

Par exemple, le but…

not(leader(L,charlie)).

…a pour résultat false. Ce but ne permet pas de récupérer tous les joueurs qui ne sont pas leader de Charlie, comme on aurait pu l’espérer. C’est une limitation de la négation en Prolog.

Si on veut déterminer les joueurs qui ne sont pas leader de Charlie, on peut utiliser le but suivant :

jc(J,_), not(leader(J,charlie)).

On obtient la réponse :

J = bart
J = charlie
J = dave
J = edouard

Le premier sous-but permet d’instancier J, utilisée en sortie, successivement avec tous les joueurs. Pour chaque valeur de J remontée, le deuxième sous-but réussi si et seulement si la valeur de J, qui est utilisée en entrée, n’est pas leader de Charlie.

Exercice de découverte B.x2

Donnez le but permettant de rechercher les joueurs qui ont au moins un supérieur hiérarchique et ne sont supérieur hiérarchique de personne. (Le résultat devrait être edouard et bart.)

"Réponse"

sup(_,J), not(sup(J,_)).


On veut afficher les joueurs qui ne sont pas paladin. Le but suivant ne permet pas de réaliser cette requête car son exécution retourne false.

not(jc(J,paladin)).

Proposez un moyen de produire le résultat attendu.

"Réponse"

jc(J,_), not(jc(J,paladin)).

B.dec3 : Arithmétique

Les entiers naturels peuvent être représentés par des termes fonctionnels, comme les autres données pouvant être traitées par Prolog, mais cette approche, bien que très puissante (elle permet à Prolog de de résoudre des équations), est inefficace pour beaucoup d’applications pratiques, lorsque les valeurs manipulées dépassent quelques centaines d’unités.

Cette limitation peut être contournée avec des extensions de Prolog permettant de spécifier et résoudre des contraintes arithmétiques sur des entiers ou des réels. On entre alors dans le domaine, très vaste, de la programmation logique avec contraintes.

Mais en Prolog de base, l’instruction is est le seul moyen d’évaluer le résultat d’un calcul arithmétique. Par exemple, le but…

X is (10-4) * 3.

…a pour résultat :

X = 18

Si on remplace is par le symbole =, appelé symbole d’unification, comme ceci…

X = (10-4) * 3.

…on obtient :

X = (10-4)*3

Il n’y a pas d’erreur de syntaxe, mais l’expression arithmétique n’est pas évaluée. La variable X est instanciée avec l’expression elle-même, qui a le statut de terme fonctionnel, et non avec le résultat. L’évaluation peut d’ailleurs être différée. Le but…

X = (10-4) * 3, Y is X.

…produit le résultat :

X = (10-4)*3, Y = 18

L’instruction is ne fonctionne que si toutes les valeurs de l’expression à évaluer sont connues au moment de l’évaluation. Elle n’est pas réversible. Par exemple, le but…

12 = 7 + X.

…échoue. Il ne permet pas de trouver la valeur X telle que 7 + X vaut 12.

Voici un prédicat permettant de calculer une factorielle. C’est un exemple complètement bateau, mais qui permet de comprendre certains points importants.

fact(0,1).
fact(N,F) :- N>0, N1 is N-1, fact(N1,F1), F is N*F1.

Voici un exemple d’utilisation de ce prédicat pour calculer la factorielle de 5.

fact(5,R).

Le résultat est :

R = 120

Le prédicat fact est défini de manière récursive. Il s’appuie sur la définition par récurrence de la fonction factorielle :

  • $0! = 1$
  • Pour tout $N > 0$, $N! = N \cdot (N-1)!$

Si vous êtes habitué à un langage de programmation procédural, objet ou même fonctionnel, la définition du prédicat fact peut vous paraître déroutante, mais elle est en fait facile à comprendre si on tient compte de deux faits :

  1. Un prédicat Prolog ne retourne pas de valeur. Il peut juste réussir ou échouer. Mais il peut permettre de produire une ou plusieurs valeurs en les faisant remonter dans une variable non instanciée située dans un slot utilisé en sortie.
  2. Tout calcul arithmétique doit être réalisé en utilisant l’instruction is.

Le premier slot de fact ne peut être utilisé qu’en entrée en raison des limitations de l’instruction is. Le deuxième slot peut être utilisé en entrée, mais nous allons raisonner uniquement sur la cas où il est utilisé en sortie, pour récupérer le résultat du calcul d’une factorielle, ce qui est la vocation première du prédicat.

Cette figure illustre les différentes étapes de calcul dans le cas où N a une valeur supérieure à 0 et montre le cheminement des résultats intermédiaires successifs.

Nous sommes assez loin de l’idéal déclaratif de Prolog, mais pour utiliser ce langage en pratique, il ne faut pas s’enfermer dans un dogmatisme rigide.

pB2

Supposons donc qu’une valeur d’entrée N supérieure à 0 soit placée dans le premier slot. Voici les différentes étapes d’évaluation de cette clause, qui correspondent au buts numérotés de 1 à 4.

  1. Le but N>0 réussit seulement si N est strictement positif. Dans le cas contraire, c’est la première clause qui aura fournit le résultat.
  2. Le but N1 is N-1 calcule la valeur $N-1$ et place le résultat dans la variable N1.
  3. Le but fact(N1,F1) invoque récursivement le prédicat fact pour calculer la factorielle de $N-1$ et faire remonter le résultat dans la variable F1.
  4. Le but F is N*F1 calcule le résultat en multipliant factorielle de $N-1$ par $N$ et le place dans la variable de sortie F.

On peut aussi décrire cette clause de manière déclarative :

Si N est strictement positif et N1 vaut N-1 et F1 est la factorielle de N1 et F vaut N fois N1 alors F est la factorielle de N.

Cette description est toutefois un peu trompeuse dans le cas de ce prédicat pour lequel l’ordre des buts est critique (alors qu’en logique, le connecteur et est commutatif) et qui utilise l’instruction is qui n’est pas déclarative, mais impérative : elle décrit un calcul et non une relation.

Exercice de découverte B.x3

Définissez le prédicat fibo tel que le but…

fibo(N_in,R_out).

…, où N_in est une valeur d’entrée et R_out une variable de sortie, produise dans la variable R_out le terme de rang N_in de la suite de Fibonacci.

La suite de Fibonacci est définie de la manière suivante :

  • Les termes de rang 0 et 1 ont la valeur 1.
  • Chacun des autres termes a pour valeur la somme des deux termes précédents.

Voici le début de cette suite.

rang 0 1 2 3 4 5 6
valeur 1 1 2 3 5 8 13

Par exemple, le but…

fibo(4,R).

…produit le résultat R=5.

Dans cet exercice, vous ne devez pas vous soucier de l’efficacité de l’implémentation, mais opter pour la solution la plus simple.

"Indice1"

Trois clauses sont nécessaires. Les deux premières déterminent les valeurs des termes de rang 0 et 1. La troisième dit que pour $N$ plus grand que 1, le terme de rang $N$ est la somme des termes de rangs $N-1$ et $N-2$.

Rappelez-vous que tout calcul doit être réalisé avec l’instruction is. Dans votre solution, il y a trois calculs :

  • le calcul de $N-1$,
  • le calcul de $N-2$,
  • le calcul de la somme des termes de rangs $N-1$ et $N-2$ (après leur production par invocation récursive du prédicat fibo).


"Indice2"

fibo(0,1).
fibo(1,1).
fibo(N,F) :- N>1, N1 is N-1, N2 is N-2, 
    fibo(..... , .....), fibo(..... , .....), F is .......... .


"Réponse"

fibo(0,1).
fibo(1,1).
fibo(N,F) :- N>1, N1 is N-1, N2 is N-2, 
    fibo(N1,F1), fibo(N2,F2), F is F1+F2.

Prêt pour la suite ?

Si vous n’avez pas bien compris certaines explications, ou des exemples, ou des solutions proposées pour les exercices de découverte, vous devez poser à une personne maîtrisant bien Prolog des questions précises qui ciblent vos difficultés.

Vous avez compris les notions et principes qui viennent d’être introduits ? Vous devez maintenant continuer votre apprentissage en réalisant les activités d’entrainement B.ent.