Nous allons à présent passer à une étude plus détaillée de Prolog. Nous mettrons l'accent sur le

traitement du langage naturel, mais nous nous permettrons des incursions dans d'autres domaines pour

expliquer plus simplement certains points fondamentaux. Nous commencerons par une diversion

mathématique.

L'unification :

Nous allons étudier le programme Magique, qui va nous permettre d'approfondir notre

compréhension du mécanisme d'unification.

Nous étudierons ici deux relations. La première est représentée par le prédicat magique, prédicat à

un seul argument. Cette relation sera vraie pour tout entier qui possédera la propriété d'être magique.

Un nombre entier est dit magique si la série d'opérations suivantes conduit inexorablement à 1:

1) si le nombre (ou le résultat obtenu par l'opération 2) est pair, on le divise par 2;

2) si le nombre (ou le résultat obtenu par l'opération 1) est impair, on le multiplie par 3 et on ajoute 1.

Par exemple, 13 est magique en vertu de la séquence d'opérations:

a) (13 * 3) +1 = 40 (opération 2)

b) 40 / 2 = 20 (opération 1)

c) 20 / 2 = 10 (opération 1)

d) 10 / 2 = 5 (opération 1)

e) (5 * 3) + 1 = 16 (opération 2)

b) 16 / 2 = 8 (opération 1)

c) 8 / 2 = 4 (opération 1)

d) 4 / 2 = 2 (opération 1)

e) 2 / 2 = 1 (opération 1).

La deuxième relation sera représentée par le prédicat divisible, d'arité 2. Elle sera vraie si le

premier argument est divisible par le second.

Rappelons que c'est le concepteur de programme qui donne le sens voulu aux prédicats qu'il définit.

Par exemple, je pourrais définir le prédicat divisible de telle sorte que la relation soit vraie si le second

argument est divisible par le premier. Il me suffirait de donner la définition adéquate.

Considérons tout d'abord le prédicat divisible, dont la définition est très simple. Dividende est

divisible par Diviseur, si le reste de la division de Dividende par Diviseur est 0. Arity Prolog offre comme

prédéfini l'opérateur mod (modulo), qui permet précisément d'obtenir le reste de la division de deux entiers.

Il suffit donc de tester si Dividende mod Diviseur est égal à 0 pour savoir si Dividende est divisible par

Diviseur. Nous obtenons donc :

divisible(Dividende,Diviseur) :- (Dividende mod Diviseur) =:= 0.

(=:= est prédéfini et infixe, il teste l'égalité de deux valeurs numériques)

Dividende et Diviseur sont des variables. On se souvient qu'en Prolog les noms de variables

doivent commencer par une majuscule ou un blanc souligné (_).

On peut considérer le prédicat divisible sous deux aspects: le procédural et le déclaratif.

Aspect procédural: pour découvrir si Dividende est divisible par Diviseur, effectuer la division, et

examiner le reste: s'il est égal à 0, conclure que la propriété est vraie.

Aspect déclaratif: Dividende est divisible par Diviseur si le reste de la division de Dividende par

Diviseur est égal à 0.

Considérons à présent le paquet de clauses définissant le prédicat magique. Le paquet de clauses

d'un prédicat est l'ensemble des clauses qui ont un appel à ce prédicat pour tête. Il y a trois clauses qui se

rapportent à ce prédicat. Commençons par les citer:

/* Clause 1 */

magique(1).

/* Clause 2 */

magique(Nombre):- divisible(Nombre,2),Reduction is Nombre//2,write(Reduction),tab(1),/* tab(1)

insère un blanc */

magique(Reduction).

/*Clause 3 */

magique(Nombre):- Augmentation is

(Nombre*3)+1,write(Augmentation),tab(1),magique(Augmentation).

La première est un fait: magique (1). On peut le paraphraser par: c'est un fait que 1 a la propriété

magique. C'est ce fait qui est rencontré lors de la terminaison de l'algorithme. Mais il faut dire ici qu'il n'y a

aucune garantie de terminaison de l'algorithme. En effet, si l'opération 1 rapproche la séquence de 1,

l'opération 2 l'en éloigne. On ne peut que soupçonner que tous les entiers positifs sont magiques, on ne sait

pas le prouver.

Les deux autres clauses pour le prédicat magique sont, comme la clause pour le prédicat divisible

examinée plus haut, des règles.

Examinons la première.

magique(Nombre):- divisible(Nombre,2),Reduction is Nombre // 2,write(Reduction), tab(1), /*

tab(1) insère un blanc */

magique(Reduction).

Elle nous dit qu'un nombre Nombre est magique si les cinq éléments du corps de la règle sont tous

satisfaits comme buts, en effet on se souvient que la virgule qui les sépare est la notation Prolog pour

l'opérateur logique AND.

Le premier but teste la divisibilité de Nombre par 2. C'est tout naturellement un appel au prédicat

divisible avec comme arguments le nombre Nombre et le diviseur 2 :

divisible(Nombre,2) qui sera satisfait si Nombre est divisible par 2.

Pour établir la vérité de cette assertion, la machine abstraite Prolog fera appel à la clause définissant

le prédicat divisible. Cet appel se fera en établissant une relation entre les objets Nombre et 2 dans l'appel à

la clause, et Dividende et Diviseur dans la définition de la clause. Nous verrons dans quelques instants

comment cette correspondance s'établit.

Les variables ont pour domaine (SCOPE) la clause dans laquelle elles sont employées. Il n'y a donc

aucune obligation d'utiliser le même nom de variable dans la clause d'appel et la clause de définition. On

aurait pu avoir:

magique(Nombre):- divisible(Nombre,2) ... et divisible(X,Y):-(X mod Y) =:= 0.

C'est la position des variables qui permet la liaison entre les clauses. On aurait donc eu liaison entre

Nombre et X d'une part, et 2 et Y d'autre part.

Le deuxième but est satisfait par l'affectation à une variable Reduction du résultat de la division

entière de Nombre par 2: Reduction is Nombre // 2 (// est l'opérateur de division entière).

D'où provient cette variable Reduction? Elle n'existe pas lors de l'appel à la clause magique

(Nombre). Elle est créée par l'équation elle-même. Il y a donc ici un aspect procédural clair: diviser

Nombre par 2 et verser le résultat dans la variable Reduction (rappelons que l'opérateur prédéfini is

réalise l'opération d'assignation d'une valeur à une variable). Toutefois, on sait que le prédicat is renvoie

néanmoins la valeur de vérité vraie pour indiquer qu'il est satisfait.

Le but suivant a une interprétation encore plus procédurale. En fait, il n'a pas de sens déclaratif. En

quoi l'écriture du contenu de la variable Reduction contribue-t-elle à la valeur de vérité (TRUTH VALUE)

de la clause magique(Nombre)? En rien. Ce prédicat prédéfini d'écriture, write, est toujours vrai. On lui

affecte cette valeur de vérité simplement pour qu'il ne vienne pas perturber la valeur de vérité de l'ensemble

du corps de la règle, en d'autres termes pour qu'il ne perturbe pas le processus de satisfaction de la règle.

Un prédicat tel que write est donc intéressant pour l'opération qu'il effectue, et non pour sa valeur de

vérité (vrai/faux). On dit de ces prédicats qu'ils sont importants pour leurs effets de bord (SIDE

EFFECTS), plutôt que leur valeur de vérité.

La même remarque s'applique à tab(1), qui écrit un blanc sur le périphérique de sortie, et réussit

trivialement.

Le dernier but est un appel récursif au prédicat magique. Pour que Nombre soit magique, il faut

que Reduction le soit également: magique(Reduction).

La clause qui nous permet de sortir des appels récursifs est bien sûr la première, le fait qui établit que

1 est magique.

Considérons la troisième clause magique:

magique(Nombre):- Augmentation is (Nombre*3)+1,

write(Augmentation),tab(1), magique(Augmentation).

Augmentation prend ici la valeur de (Nombre*3)+1. Pour le reste, la clause est semblable à la

précédente.

Pour bien comprendre le programme, il faut se rappeler comment la machine abstraite explore les

faits et applique les règles. Elle le fait dans l'ordre normal de la lecture, c'est-à-dire de haut en bas et de

gauche à droite.

Pour interroger la machine abstraite sur la valeur de vérité d'une relation (ou pour obtenir d'elle

toutes les valeurs des variables qui rendent cette relation vraie), on a vu qu'on lui soumettait la relation sous

forme de but (GOAL), c'est-à-dire en réponse à l'invite (?-) de l'interpréteur Prolog.

Si le but ne comporte pas de variable, la machine abstraite renseignera sur sa valeur de vérité. Elle

renverra la valeur yes ou no selon le cas.

Si le but comporte des variables, on pourra obtenir de la machine abstraite Prolog toutes les valeurs

des variables qui satisfont la relation présentée comme but, c'est-à-dire la rendent vraie.

Lors de l'entrée d'un but tel que magique(345), la machine teste d'abord la première clause, qui est

le fait: magique(1). Ce fait ne s'applique pas. Qu'est-ce qu'il faut entendre par là au juste?

Le mécanisme fondamental de Prolog est l'UNIFICATION. Pour établir la vérité d'un but, Prolog

tente de l'unifier avec les faits et les têtes des règles qui se rapportent à ce but. Il faut savoir aussi que:

1) une constante ne peut être unifiée qu'avec elle-même

Cette propriété est responsable de l'échec de l'unification de magique(345) (le but à évaluer par la

machine abstraite) et magique(1) (le premier fait).

2) une variable peut s'unifier à n'importe quoi

Mais une fois qu'une variable est liée à une valeur par unification, on dit qu'elle est instanciée ou

liée (INSTANTIATED / BOUND) et elle a alors cette valeur partout où elle apparaît dans sa clause (qui,

rappelons-le, est son domaine). Nous verrons plus tard comment elle peut perdre cette valeur.

Revenons à notre but: magique(345). L'unification avec la première clause ayant échoué, la machine

abstraite se tourne vers la seconde clause du paquet de clauses pour le prédicat magique. C'est également

l'unification qui est responsable de ce choix: magique(345) s'unifie avec magique(Nombre) car les deux

prédicats magique s'unifient: même nom (foncteur), et même nombre d'arguments qui s'unifient chacun à

leur tour, ici il n'y en a qu'un: la variable Nombre va s'unifier avec la constante 345).

La machine abstraite va donc tenter de satisfaire le but magique(345) à l'aide de la première règle.

Pour satisfaire un but à l'aide d'une règle, il faut que le but et la tête de règle soient unifiables et que

tous les éléments du corps de la règle (considérés à leur tour comme des buts à satisfaire) soient satisfaits:

ici encore, l'exploration se fera de haut en bas et de gauche à droite, et le mécanisme fondamental sera

l'unification.

La machine abstraite tentera donc de satisfaire le but divisible(345,2), puisqu'il s'agit du premier

but dans la règle à satisfaire.

Par unification, la machine abstraite portera son attention vers la clause qui définit le prédicat

divisible, et par unification, Dividende y vaudra 345 et Diviseur 2. Ce but échouera. Cet échec forcera

l'échec de la première règle de magique pour la valeur concernée, puisque un des éléments du corps de la

règle n'a pas pu être satisfait.

Toutefois, l'unification du but de départ (magique(345)) est aussi possible avec la deuxième règle, qui

sera à présent tentée, conformément au mécanisme d'exploration de haut en bas et de gauche à droite.

La satisfaction de cette règle conduit à la création d'une variable Augmentation, qui vaudra:

345 * 3 + 1, à savoir 1036. Le nouveau but à satisfaire (après l'écriture de 1036 à l'écran, but qui réussira de

manière triviale) sera à présent magique(Augmentation), avec Augmentation liée à la valeur 1036.

Le procédé reprend dès lors au début pour ce nouveau but, l'unification avec le fait échouera, la

satisfaction de la première règle conduira à un nouveau but, à savoir magique(518) et ainsi de suite

jusqu'au but magique(1), qui réussira par unification avec le fait.

Tous les buts ayant été satisfaits, Prolog indiquera la satisfaction du but de départ en annonçant yes.

On trouvera ci-dessous le programme magique dans sa totalité :

/* MAGIQUE */

/* le fait */

magique(1).

/* les deux règles */

/* on se rapproche de 1 */

magique(Nombre):- divisible(Nombre,2),Reduction is Nombre//2, write(Reduction),tab(1), /* tab(1) insère un

blanc */

magique(Reduction).

/* on s'éloigne de 1 */

magique(Nombre):-Augmentation is (Nombre*3)+1,write(Augmentation),tab(1),magique(Augmentation).

/* la clause pour le deuxième prédicat, il s'agit d'une règle */

divisible(Dividende,Diviseur):-(Dividende mod Diviseur) =:= 0.

/* =:= teste l'égalité de deux valeurs numériques */

Exemples d'invocation et résultats obtenus (en gras)

?- magique(17).

52 26 13 40 20 10 5 16 8 4 2 1

True

*Veuillez consulter le fichier [Exemples/Fichier8.pl] du CD.