Nous allons étudier le programme NOTES, qui va nous faire découvrir la manière dont Prolog gère la

LISTE, une structure de données extrêmement intéressante.

Le propos du programme NOTES est de déterminer, sur base des notes d'un étudiant, si ce dernier

réussit sans délibération.

Pour rendre le programme abordable et quelque peu facétieux, nous conviendrons des conditions de

réussite ci-dessous.

Un étudiant réussit sans délibération si :

1) il obtient 12 de moyenne et n'a pas d'échec (pas de note inférieure à 10)

ou si :

2) il obtient 16 ou plus en informatique.

De plus, nous présenterons sous forme de FAITS (au sens prologien du terme) la réussite de certains

étudiants, pour bien montrer les interactions entre faits et règles.

Nous aurons trois types de faits, qui constitueront la base de données de notre programme:

1) qui a réussi d'office (faits pour le prédicat reussit),

2) quelle est la note pour un étudiant donné dans un cours donné (trois arguments: nom de l'étudiant, libellé

du cours, note obtenue, faits pour le prédicat note, le paquet de clauses pour ce prédicat ne contient que des

faits, pas de règles, on dit qu'il s'agit d'un prédicat de base de données).

3) qui sont les étudiants (également un prédicat de base de données).

Voici un exemple de chaque type de faits:

1) reussit(pierre).

2) note(jean,informatique,16).

3) etudiant(jean).

Citons ici en vrac les règles que nous utiliserons. Nous les examinerons en détail par la suite :

reussit(Etudiant):-etudiant(Etudiant),notemoyenne(Etudiant,Moyenne),Moyenne >=

12,not(echoue(Etudiant)).

reussit(Etudiant):-etudiant(Etudiant),note(Etudiant,informatique,Note),Note >= 16.

echoue(Etudiant):-etudiant(Etudiant),note(Etudiant,_,Note),Note<10.

echoue(Etudiant):-etudiant(Etudiant),notemoyenne(Etudiant,Moyenne),Moyenne < 12.

notemoyenne(Etudiant,Valeur):-

findall(Note,note(Etudiant,_,Note),Listedenotes),

total(Listedenotes,Somme,Nombredenotes),

Valeur is Somme / Nombredenotes.

total([],0,0).

total([Tete|Queue],Somme,Nombre_el):-

total(Queue,Nouvelle_Somme,Nouveau_Nombre_el),

Somme is Nouvelle_Somme+Tete,

Nombre_el is Nouveau_Nombre_el+1.

On utilisera dans ce programme une structure de données très utile, à savoir la liste. Rappelons

qu'une liste se représente en Prolog comme suit: les éléments de la liste apparaissent séparés les uns des

autres par des virgules. Toute la liste est pincée entre parenthèses carrées. Une liste de notes pourrait être

par exemple [ 6, 5, 20, 9.5, 3, 16, 12 ].

Rappelons également qu'on dispose d'un opérateur très puissant (pas à première vue!) pour faciliter

l'exploration des

Listes : |. Ce signe sépare un certain nombre d'éléments en tête de liste du reste de la liste, la queue. La

queue de la liste est elle-même toujours une liste, bien qu'elle puisse être vide, auquel cas elle sera notée [].

Par exemple, si on unifie [X,Y|Reste] avec la liste donnée en exemple ci-dessus, on obtiendra les

appariements suivants X=6, Y=5, Reste=[20, 9.5, 3, 16, 12]. On constate que Reste, la queue de liste, est elle-

même une liste. Si on a la liste à un élément [5] et qu'on tente l'unification avec [X|Y] on obtient X=5, Y=[]

(la liste vide).

On remarquera le prédicat total. Il prend comme argument une liste de notes et renvoie le total des

notes dans son deuxième argument, et le nombre de notes à totaliser dans son troisième argument. Par

exemple, le but :

total([12,13,11],Total,Nombre_de_Notes) sera satisfait par les valeurs suivantes des variables:

Total=36, Nombre_de_Notes=3.

Essayez ce but. A l'exécution, on peut soumettre comme but n'importe quel prédicat. Cette propriété

aide grandement la mise au point des programmes, car on peut tester chaque prédicat séparément, et donc

adopter la méthode des "boîtes noires": une fois qu'un prédicat a été bien mis au point, on peut lui faire

confiance et le considérer comme une "boîte noire", qui accomplit de manière fiable ce qu'on lui demande de

faire (si on adopte une vue procédurale des choses).

Examinons le prédicat reussit, défini par les clauses suivantes:

/* des faits */

reussit(pierre).

reussit(paul).

/* des règles */

/* 1 */

reussit(Etudiant):-

etudiant(Etudiant),

notemoyenne(Etudiant,Moyenne),

Moyenne >= 12,

not(echoue(Etudiant)).

/* 2 */

reussit(Etudiant):-

etudiant(Etudiant),

note(Etudiant,informatique,Note),

Note >= 16.

Le prédicat reussit est un paquet de 4 clauses, dont les deux premières sont des faits: c'est un fait

que pierre a réussi, et c'est un fait que paul a réussi.

Voyons nos deux règles.

La première fait un appel au prédicat notemoyenne, qui, pour un étudiant donné, renvoie la

moyenne de ses notes. Nous y reviendrons. La moyenne est stockée dans la variable Moyenne. La deuxième

condition nous indique que cette moyenne doit être égale ou supérieure à 12, et la troisième condition nous

indique que l'étudiant ne peut pas avoir d'échec.

Cette troisième condition est intéressante. Examinons-la:

not(echoue(Etudiant))

not est un prédicat prédéfini. Il réussit si son argument échoue. En d'autres termes, si la machine

abstraite ne parvient pas à prouver echoue(Etudiant) (l'étudiant a au moins un échec) elle conclura à la

vérité de not(echoue(Etudiant)) (l'étudiant n'a pas d'échec).

Cette manière de concevoir la négation doit être bien assimilée. Elle se base sur la conception d'un

UNIVERS CLOS: le programme renseigne la machine abstraite sur tout ce qu'elle doit savoir pour se

prononcer sur la vérité des relations.

La règle suivante (/* 2 */) interroge le prédicat note, prédicat à trois arguments. L'appel à ce prédicat

se fait avec le deuxième argument (le cours) lié à la valeur informatique, puisque c'est le cours

d'informatique qui permet de faire réussir un étudiant tout à fait nul ailleurs (rappelons qu'un étudiant

réussit sans délibération s'il obtient 16 ou plus en informatique: c'est cette condition que la deuxième règle

pour le prédicat reussit tente de saisir). Etudiant est une variable désignant l'étudiant sur la réussite

duquel on s'interroge. Le troisième argument, Note, servira à stocker la note renvoyée par les faits qui

définissent le prédicat note. Par exemple, le but reussit(jean), unifié avec la tête de la deuxième règle,

conduira au but note(jean, informatique, Note) qui sera unifié avec le fait note(jean, informatique, 16)

pour donner la liaison (l'instanciation): Note = 16, et conduire à la satisfaction du but Note >= 16, après

quoi la machine abstraite pourra conclure que jean a réussi.

Examinons à présent les clauses pour le prédicat echoue:

echoue(Etudiant):-

etudiant(Etudiant),

note(Etudiant,_,Note),

Note < 10.

echoue(Etudiant):-

etudiant(Etudiant),

notemoyenne(Etudiant,Moyenne),

Moyenne < 12.

On a ici un appel au prédicat note. Le premier argument sera instancié au nom de l'étudiant

(Etudiant). Le second est désigné par la variable anonyme ou muette, marquée par un blanc souligné.

Rappelons que nous indiquons par-là que la valeur de cette variable ne nous intéresse pas. Dans le cas précis

qui nous occupe, je cherche à savoir si un étudiant donné à un échec, et je ne me soucie pas de savoir dans

quelle branche: d'où l'utilisation de la variable anonyme.

Comment l'appel à ce prédicat note va-t-il me permettre de découvrir si un étudiant a un échec ou s'il

n'en a pas? Il convient de se rappeler ici la propriété cruciale de la machine abstraite Prolog: elle recherche

TOUTES les solutions possibles, elle essaie TOUTES les valeurs possibles avant de conclure à l'échec du

prédicat. Donc, si un étudiant a une note déficiente, Prolog la trouvera, car il ne conclura à l'échec du

prédicat echoue que si aucune valeur de Note ne satisfait la relation Note < 10.

On voit donc combien le mécanisme de recherche des solutions en Prolog est puissant. La définition

du prédicat echoue est élégante et simple. Elle accomplit le travail d'une dizaine d'instructions au moins

dans d'autres langages de programmation de haut niveau.

Considérons à présent le prédicat total, pour revenir ensuite au prédicat notemoyenne, qui y fait

appel.

total([],0,0).

total([Tete|Queue],Somme,Nombre_el):-

total(Queue,Nouvelle_Somme,Nouveau_Nombre_el),

Somme is Nouvelle_Somme+Tete,

Nombre_el is Nouveau_Nombre_el+1.

Le prédicat total est basé sur le principe du parcours récursif d'une liste. Ce procédé peut paraître

déroutant au premier abord, il est pourtant extrêmement puissant et élégant.

La première clause est la clause d'arrêt (STOPPING CLAUSE), celle qui nous permet de sortir du

parcours récursif défini par la seconde clause. Comme c'est toujours le cas pour les clauses d'arrêt, elle est

très simple. Ce n'est pas une règle, mais un fait:

total([],0,0).

C'est un fait que le total des éléments d'une liste vide est 0, et que le nombre d'éléments y est

également 0. C'est sur ce fait que l'on tombera lorsqu'on arrivera en fin de parcours de la liste, lorsque sa

queue sera la liste vide (on se rappelle qu'une queue de liste est toujours une liste, et on commence à

comprendre pourquoi).

La deuxième clause est une règle: elle nous dit que si on a totalisé tous les éléments de la liste à

l'exception du premier (totalisation qui se fait à l'aide du prédicat total appliqué à la queue de la liste), il

suffit d'ajouter la valeur du premier élément au total et 1 au nombre d'éléments pour avoir le total de la liste

et son nombre d'éléments.

La liste est divisée en deux parties, tête et queue, à l'aide de l'opérateur |. L'application récursive du

prédicat total à cette queue donne les résultats Nouvelle_Somme et Nouveau_Nombre_el, auxquels il

suffit d'ajouter la valeur de la tête (contenue dans la variable Tête) et le nombre d'éléments qu'elle

représente, à savoir 1.

Comment la machine abstraite s'en sort-elle lorsqu'elle est confrontée à des prédicats récursifs, qui se

définissent en faisant appel à eux-mêmes? Elle maintient une pile de tous les buts en attente qui sont

générés par les appels récursifs, jusqu'au moment où elle peut appliquer (par unification) la clause non

récursive: dans notre cas, il s'agit du fait qui concerne le total d'une liste vide. Fort de ce premier résultat,

Prolog reprend un après l'autre tous les appels en attente. Dans notre cas, il pourra bâtir sur la base des

deux 0 renvoyés par l'unification du but avec le fait.

Il nous reste à examiner le prédicat notemoyenne.

notemoyenne(Etudiant,Valeur):-

findall(Note,note(Etudiant,_,Note),Listedenotes),

total(Listedenotes,Somme,Nombredenotes),

Valeur is Somme / Nombredenotes.

Notemoyenne fait appel à un prédicat prédéfini très puissant, à savoir findall. Findall prend trois

arguments:

1) une variable.

2) un prédicat dans lequel cette variable apparaît comme argument.

3) une liste qui va lui permettre de stocker toutes les valeurs de la variable qui satisfont le prédicat donné en

deuxième argument.

La machine abstraite réunit donc en une liste toutes les valeurs que peut prendre la variable Note

dans le prédicat note, c'est-à-dire toutes les notes de l'étudiant Etudiant.

Le prédicat notemoyenne appelle le prédicat total pour qu'il totalise la liste et en renvoie le nombre

d'éléments: il s'agit des variables Somme et Nombredenotes. Finalement, la moyenne, renvoyée dans la

variable Valeur, est calculée par Valeur is Somme/Nombredenotes (/ est l'opérateur de division, on se

souvient que // est réservé à la division entière).

Le programme se termine par une série de faits qui servent à définir le prédicat note. Ce prédicat n'a

pas de règles. C'est donc purement un prédicat de base de données, destiné à stocker toutes les valeurs des

relations qui sont connues d'entrée de jeu. On verra plus tard que ce n'est pas le seul type de base de

données que Prolog connaisse. Pour l'heure, on en a dit assez et il est temps de présenter le programme

NOTES en entier.