Dossier sur PROLOG La programmation logique

PROLOG est un langage qui, comme son nom l’indique (PROgrammation LOGique), utilise un mode de programmation dit
‘logique’. Ce mode de programmation a vu le jour grâce à John Robinson qui a posé en 1965 les bases de la logique. Le
développement de PROLOG a commencé en 1972 à l’université de Marseille dans le Groupe d’Intelligence Artificielle de
Lumigny dirigé par A. Colmerauer. Il a été poursuivi principalement à Marseille et à Edimbourg. Aujourd’hui, PROLOG est un
langage mûr ; pourtant il ne possède toujours pas de norme.
Nous allons voir dans un premier temps ce qu’est la programmation logique afin de mieux comprendre la ‘philosophie’ des
programmes PROLOG. Ensuite, nous nous intéresserons à ce que permet de faire PROLOG. Enfin, nous essaierons de
comprendre sa méthode de recherche de solutions.

I. La programmation logique

I.1. Un mode de programmation à part

Il est important avant d’expliquer ce qu’est PROLOG et d’étudier son utilisation de bien voir ce qu’il n’est pas ; c’est à dire de
comprendre sa ‘philosophie’. Pour cela, il faut décrire ce qu’est la programmation logique et la comparer aux autres modes de
programmation.

I.1.1. Les autres modes de programmation

I.1.1.1. La programmation impérative
Cette programmation s’inscrit dans une démarche algorithmique qui décrit la façon de traiter les données pour atteindre un
résultat par une série d’actions. Celles-ci sont toujours de trois types : le test, l’ordre (chaque instruction par laquelle le
programme passe est impérative) et l’itération (obtenue grâce aux branchement).
Le déroulement du programme est parfaitement déterministe.
Exemple de langages : Fortran, Pascal, C …
I.1.1.2. La programmation fonctionnelle
Le résultat est ici comme la composition de fonctions. Pratiquement, elle est proche de la programmation impérative ; cependant
ses fondements (λ-calcul) ainsi que l’absence de branchement et d’affectation (du moins dans sa forme théorique) en fait un mode
de programmation à part.
Rem : Dans la programmation fonctionnelle, on distingue deux grandes familles :
- les langages fortement typés : ML (ex : Caml)
- les langages non typés : LISP (ex : Scheme)

I.1.2. La programmation logique

Les modes de programmation décrits juste au-dessus sont dits procéduraux car ils cherchent à obtenir le résultat grâce à une
procédure (qui peut être une suite d’actions ou une composition de fonctions). A cela on oppose la programmation logique qui est
dite déclarative. En effet, ici on ne s’occupe pas de la manière d’obtenir le résultat ; par contre, le programmeur doit faire la
description du problème à résoudre en listant les objets concernés, les propriétés et les relations qu’ils vérifient.
Ensuite, le mécanisme de résolution (pris entièrement en charge par le langage) est général et universel. Il parcourt de façon non
déterministe (cela sera détaillé au chapitre I) toutes les possibilités du problème et peut donc retourner plusieurs solutions.

I.1.3. La programmation orientée objet

Ce mode de programmation a été mis à part car il regroupe en fait tous les modes précédemment vus en utilisant à la fois des
techniques déclaratives et d’autres procédurale.
Exemple de langages : C++, Java …

1
Dossier sur PROLOG La programmation logique

I.2. Constitution d’un programme PROLOG

Nous avons vu que le principe de la programmation logique est de décrire le problème à résoudre. Dans le cas de PROLOG,
cela est formalisé grâce à un langage dérivé du calcul des prédicats (ou calcul du premier ordre). Les prédicats servent à qualifier
(donner les caractéristiques de) les objets du problème et à décrire les relations dans lesquelles ils sont impliqués.

I.2.1. Les faits

Les faits sont des données élémentaires qu’on considère vraies. Ce sont des formules atomiques constituées du nom d’un
prédicat (c’est à dire d’une relation (au sens mathématique du terme)) (pour plus de renseignement sur le calcul des prédicat, voir
la première partie du cour de Génie Logiciel) suivi entre parenthèse d’une liste ordonnée d’arguments qui sont les objets du
problème principal ou d’un sous-problème.
Un programme PROLOG est au moins constitué d’un ou plusieurs fait(s) car c’est à partir de lui (d’eux) que PROLOG va
pouvoir rechercher des preuves pour répondre aux requêtes de l’utilisateur (voir chapitre III.1.3.2 page 27 pour comprendre
comment fonctionne un programme PROLOG) ; ce sont en quelque sorte ses hypothèses de travail.
Ex : Henri IV est le père de Louis XIII se traduit par : pere(henri4,louis13).
Marie de Médicis est la mère de Henri IV se traduit par : mere(marie-medicis,henri4).
Adam est l’ancêtre de tout le monde se traduit par : ancetre(Adam,X).
Superman est plus fort que tout le monde se traduit par : plusfort(superman,X).
0 ! = 1 se traduit par : factorielle(O,1).
Rem : Généralement, on place toutes les déclarations de faits au début du programme même si ce n’est pas obligatoire.

I.2.2. Les règles

Un programme PROLOG contient presque toujours des règles, cependant ce n’est pas une obligation. Si les faits sont les
hypothèses de travail de PROLOG, les règles sont des relations qui permettent à partir de ces hypothèses d’établir de nouveaux
faits par déduction (si on a démontré F1 et F1⇒F2 alors on a démontré F2).
Ex : La relation telle que si on est invincible, alors on est plus fort que tout le monde se traduit par la règle :
plusfort(X,Y):-invincible(X).
Les relations qui se traduisent en règle sont de la forme : H1 ? H2 ? … Hn ⇒ C
Où :
• ? peut être soit une disjonction (∨) soit une conjonction (∧)
• H1, H2,… Hn sont des formules atomiques ou des directives de contrôle
• C est une formule atomique.
Ex : La relation telle que si on est le père du père ou de la mère de quelqu’un alors on est son grand-père se traduit par :
grandpere(X,Y):-pere(X,Z),pere(Z,Y).
grandpere(X,Y):-pere(X,Z),mere(Z,Y).
ou encore par :
grandpere(X,Y):-pere(X,Z),(pere(Z,Y);mere(Z,Y)).
Par contre, la relation telle que si on est grand-parent alors on est grand-père ou grand-mère n’est pas traduisible par :
(grandpere(X,Y);grandmere(X,Y)):-grandparent(X,Y);
Les variables utilisées dans une règle sont universellement quantifiées par PROLOG (avec quantificateur ∀). Ainsi, il interprète
H1 ? H2 ? … Hn ⇒ C par ∀ X1, X2, … Xm (H1 ? H2 ? … Hn ⇒ C) si X1, X2, … Xm sont les variables des Hk.
Ex : grandpere(X,Y):-pere(X,Z),mere(X,Y). est quantifié
- soit par : ∀X ∀Y ∀Z (pere(X,Z) & mere(X,Y))⇒grandpere(X,Y)
- soit par : ∀X ∀Y ,∃Z / (pere(X,Z) & mere(X,Y))⇒grandpere(X,Y)
plusintelligent(X,Y):-genie(X). est quantifié
- soit par : ∀X ∀Y genie(X)⇒plusintelligent(X,Y)
- soit par : ∀X genie(X) ⇒ ∀Y plusintelligent(X,Y)

2
Dossier sur PROLOG La programmation logique

I.2.3. Les conventions de SWI-PROLOG©

Il existe plusieurs éditeur/débuggeur PROLOG. Nous utiliserons ici SWI-PROLOG© développé par Jan Wielemaker à
l’université d’Amsterdam et qui est distribué gratuitement.
Pour pouvoir fonctionner, un programme SWI-PROLOG© doit obéir à certaines conventions :
• Tous les faits et règles doivent se terminer par un « . ».
• Les variables utilisées dans les faits ou les règles commencent toujours par une majuscule ou « _ ».
Rem : Mieux vaut faire commencer les variables classiques par des majuscules. En effet, cela permet de différencier sans
ambiguïté dans le mode débuggage les variables du programme, des variables internes générées dynamiquement par
PROLOG qui commencent par « _ ».
• A l’inverse, tout le reste commence par une minuscule.
• Il ne faut pas mettre d’espace entre le prédicat et la parenthèse ouvrante qui l’accompagne.
• Les commentaires sont mis entre « /* » et « */ » ou commencent par « % » et se terminent sur la même ligne.
Rem : Ces conventions s’appliquent également au requêtes faites par l’utilisateur dans l’interpréteur de commande de
SWI-PROLO©

II. Utilisations de PROLOG

II.1. Interrogation de bases de données relationnelles

Il est très facile d’utiliser PROLOG pour programmer une base de données et l’interroger. En effet, il suffit de déclarer en tant
que faits toutes les données de la base.
Rem : Il existe en fait une extension de PROLOG appelée DATALOG qui est justement orientée base de données.
Grâce aux règles, on peut obtenir des sous-tables ou établir des relations entre les tables.
Rem : C’est ce qui fait la puissance d’un langage comme PROLOG ou DATALOG par rapport à SQL où toutes les données
de la base doivent être explicitement énoncées.
Rem : Les bases de données sont un exemple où le programme peut ne contenir que des faits sans aucune règle même si cela
fait perdre une partie de l’intérêt de PROLOG.

II.1.1. Programmation de la base de données

Programme 1 : Biographie des rois de France

% < ! >Attention : pas d'accent dans les programmes

/***************** Les faits *******************/

/*
Arguemnts du predicat ‘bio’ :
bio(enfant, sexe, annee_naissance, annee_mort, pere, mere)
*/
bio(louis13, h, 1601, 1643, henri4, marie_medicis).
bio(elisabeth_France, f, 1603, 1644, henri4, marie_medicis).
bio(marie_therese_Autriche, f, 1638, 1683, philippe4, elisabeth_france).
bio(louis14, h, 1638, 1715, louis13, anne_autriche).
bio(grand_dauphin, h, 1661, 1711, louis14, marie_therese_autriche).
bio(louis_bourbon, h, 1682, 1712, grand_dauphin, marie_anne_baviere).
bio(philippe5, h, 1683, 1746, grand_dauphin, marie_anne_baviere).
bio(louis15, h, 1710, 1774, louis_bourbon, marie_adelaide_savoie).
bio(louis_dauphin, h, 1729, 1765, louis15, marie_leczcynska).
bio(louis16, h, 1754, 1793, louis_dauphin, marie_josephe_saxe).
bio(louis18, h, 1755, 1824, louis_dauphin, marie_josephe_saxe).
bio(charles10, h, 1757, 1836, louis_dauphin, marie_josephe_saxe).
bio(clotilde, f, 1759, 1802, louis_dauphin, marie_josephe_saxe).
bio(louis17, h, 1785, 1795, louis16, marie_antoinette).
bio(philippe1, h, 1640, 1701, louis13, anne_autriche).
bio(philippe2, h, 1674, 1723, philippe1, charlotte_baviere).
bio(louis_orleans, h, 1703, 1752, philippe, francoise_marie_bourbon).

3
Dossier sur PROLOG Utilisations de PROLOG

bio(louis_philippe, h, 1725, 1785, louis_orleans, augusta_marie_bade).

bio(philippe_egalite, h, 1747, 1793, louis_philippe, louise_henriette_bourbon_conti).
bio(louis_philippe1, h, 1773, 1850, philippe_egalite,
louise_marie_adelaide_bourbon_penthievre).

/***************** Les regles *******************/

/*enfant(enfant,parent)*/
/*R1*/ enfant(X,Y):-bio(X,_,_,_,Y,_).
/*R2*/ enfant(X,Y):-bio(X,_,_,_,_,Y).
/*ptenfant(petit-enfant,grand-parent)*/
/*R3*/ ptenfant(X,Y):-enfant(X,Z),enfant(Z,Y).
/*descendant(descendant,ancetre)*/
/*R4*/ descendant(X,Y):-enfant(X,Y).
/*R5*/ descendant(X,Y):-enfant(X,Z),descendant(Z,Y).
Ce programme définit avec les faits une table ‘bio’ dont les attributs sont le nom du fils, son sexe, son année de naissance, de
mort, le nom de son père et de sa mère.
Grâce aux règles il définit également trois sous-tables : ‘enfant’, ‘ptenfant’ et ‘descendant’ qui ont comme attributs :
• enfant(NomEnfant, NomParent)
• ptenfant(NomPetitEnfant, NomGrandParent)
• descendant(NomDescendant, NomAncetre)

II.1.2. Interrogation de la base de données

La base de données étant en place, nous allons l’interroger grâce à des requêtes PROLOG. Il est possible de l’interroger de
nombreuses manières. En voici quelques exemples.
II.1.2.1. Vérification de la présence d’une donnée dans la table
Il est bien sûr possible de savoir si une donnée existe bien dans la base.
Ex : Regardons si Louis XIII qui a vécu entre 1601 et 1643 est le fils de Henri IV et Marie de Médicis :
?- bio(louis13, h, 1601, 1643, henri4, marie_medicis).
Yes
C’est bien le cas.
Ex : Regardons si Louis XVII qui a vécu entre 1785 et 1795 est le fils de Louis XVI et Marie de Médicis :
?- bio(louis17, h, 1785, 1795, louis16, marie_medicis).
No
Ce n’est pas le cas car sa mère est Marie-Antoinette.
II.1.2.2. Recherche d’une liste simple
On peut extraire de la table ‘bio’ une sous-table à un seul attribut.
Cela correspond à l’opération : ΠX (σConditions (bio) ) où
• X est un (et un seul) attribut de la table ‘bio’
• Conditions est un ensemble de conjonctions et de disjonctions
Ex : Quelles sont les femmes qui figurent comme enfant ?
C’est à dire que contient ΠNomEnfant (σSexe=f (bio) ) ?
?- bio(Qui,f,_,_,_,_).
Qui = elisabeth_france ;
Qui = marie_therese_autriche ;
Qui = clotilde ;
No
Il y a donc trois filles dans la table.
Ex : Qui sont les enfants de Henri IV ?
?- bio(Qui,_,_,_,henri4,_).
Qui = louis13 ;
Qui = elisabeth_france ;
No
Henri IV a eu 2 enfants.
La sous-table retournée par PROLOG est complète dans le sens où les possibilités solution de la requête sont affichées autant de
fois qu’elles répondent au problème.

4
Dossier sur PROLOG Utilisations de PROLOG

Ex : Quelles sont les femmes qui figurent comme mère ?

?- bio(_,_,_,_,_,Mere).
Mere = marie_medicis ;
Mere = marie_medicis ;
Mere = elisabeth_france ;
Mere = anne_autriche ;
Mere = marie_therese_autriche ;
Mere = marie_anne_baviere ;
Mere = marie_anne_baviere ;
Mere = marie_adelaide_savoie ;
Mere = marie_leczcynska ;
Mere = marie_josephe_saxe ;
Mere = marie_josephe_saxe ;
Mere = marie_josephe_saxe ;
Mere = marie_josephe_saxe ;
Mere = marie_antoinette ;
Mere = anne_autriche ;
Mere = charlotte_baviere ;
Mere = francoise_marie_bourbon ;
Mere = augusta_marie_bade ;
Mere = louise_henriette_bourbon_conti ;
Mere = louise_marie_adelaide_bourbon_penthievre ;
No
II.1.2.3. Recherche d’une liste multiple
On peut aussi extraire de la table ‘bio’ une sous-table ayant plus d’un seul attribut.
Cela peut correspondre à l’opération : ΠX1,X2,…Xn (σConditions (bio) ) où
• X1, X2, …Xn sont des attributs de la table ‘bio’
• Conditions est un ensemble de conjonctions et/ou de disjonctions
Ex : Qui sont les parents de Louis XIV ?
?- bio(louis14,_,_,_,Papa,Maman).
Papa = louis13
Maman = anne_autriche ;
No
Le père de Louis XIV est Louis XIII et sa mère est Anne d’Autriche.
Mais cela peut aussi correspondre à une jointure : ΠX1 (σConditions (bio) ) >< Π X2,…Xn (σConditions (bio) )
Ex : Qui sont les parents de Louis XIV ?
?- bio(louis14,_,_,_,Pere,_),bio(louis14,_,_,_,_,Mere).
Pere = louis13
Mere = anne_autriche ;
No
Rem : Si les deux buts de la requête ne sont pas réunis par une conjonction mais par une disjonction, on obtient un tout autre
résultat :
?- bio(louis14,_,_,_,Pere,_);bio(louis14,_,_,_,_,Mere).
Pere = louis13
Mere = _G481 ;
Pere = _G473
Mere = anne_autriche ;
No
En effet, on obtient une sous-table avec deux attributs contenant non pas une réponse mais deux. _G481 et _G473 sont
deux variables internes utilisées par SWI-PROLOG© ; si elles apparaissent dans le résultat cela signifie que le résultat
est bon quelles que soient leurs valeurs.
Ce résultat peut donc s’interprète par :
- Si le père de Louis XIV est Louis XIII, sa mère peut être n’importe qui.
- Si la mère de Louis XIV est Anne d’Autriche, son père peut être n’importe qui.
Ce qui est bien sûr incorrect.
Par rapport à cette dernière remarque, il faut ajouter qu’il est quand même possible d’employer une disjonction dans la requête.
Cependant, ce connecteur étant équivalent à l’opération de réunion (∪) dans l’algèbre relationnelle, il supprime un attribut à la
sous-table résultat.

5
Dossier sur PROLOG Utilisations de PROLOG

Ex : Qui sont les parents de Louis XIV ?

?- bio(louis14,_,_,_,Parent,_);bio(louis14,_,_,_,_,Parent).
Parent = louis13 ;
Parent = anne_autriche ;
No
On obtient ici une sous-table à un seul attribut avec deux données. De ce fait, on perd l’information sur le sexe des
parents puisqu’ils sont tous les deux réunis sous le même attribut.
II.1.2.4. Recherche dans un intervalle de valeurs
PROLOG peut gérer un intervalle de valeurs.
Ex : Quels sont les personnages nés entre 1750 et 1800 ?
?- bio(Qui,_,N,_,_,_),1750=<N,N=<1800.
Qui = louis16
N = 1754 ;
Qui = louis18
N = 1755 ;
Qui = charles10
N = 1757 ;
Qui = clotilde
N = 1759 ;
Qui = louis17
N = 1785 ;
Qui = louis_philippe1
N = 1773 ;
No
Il y a six enfants qui sont nés entre 1750 et 1800.
La recherche de solutions dans un intervalle de valeur fait apparaître quelques caractéristiques intéressantes de PROLOG :
• L’implémentation de PROLOG ne respecte pas complètement la logique du premier ordre : une requête n’est pas
traitée comme une formule complète mais elle est divisée en formules atomiques (les buts) reliées par des disjonctions
et/ou des conjonctions et ces sous-formules sont traitées les unes après les autres dans l’ordre où elles se trouvent sur
la ligne (de gauche à droite).
• PROLOG considère à priori toute variable numérique comme faisant parti des réels.
Ex : Quels sont les personnages nés entre 1750 et 1800 ?
?- 1750=<N,N=<1800,bio(Qui,_,N,_,_,_).
ERROR: Arguments are not sufficiently instantiated
Par rapport au premier exemple, nous n’avons fait qu’inverser les formules de la requête ce qui en logique ne change rien
puisque l’opérateur ∧ est commutatif. Mais comme nous l’avons dit juste au-dessus, PROLOG découpe les requêtes en
formules atomiques. Il va donc d’abord s’attacher à résoudre le but 1750=<N. Or N étant à priori un réel, il y a une
infinité de solution à ce but. Il arrive à le détecter et alors il s’arrête.
Rem : Nous venons de voir dans cet exemple un des rares cas où PROLOG effectue un contrôle. Sans cela, il chercherait tous
les N (réels) ≤ 1750 avant de passer à la formule atomique suivante. Donc il ne terminerait jamais.
Pour contourner ces deux difficultés (les règles sont découpées en formules atomiques et les variables numériques sont
considérées comme des réels) dans le cas d’une recherche dans un intervalle de valeurs, PROLOG introduit le mot clé
between(debut,fin,X) où X est une variable considérée comme un entier et comprise entre ‘debut’ et ‘fin’.
Ex : Quels sont les personnages nés entre 1750 et 1800 ?
?- between(1750,1800,N),bio(Qui,_,N,_,_,_).
N = 1754
Qui = louis16 ;
N = 1755
Qui = louis18 ;
N = 1757
Qui = charles10 ;
N = 1759
Qui = clotilde ;
N = 1773
Qui = louis_philippe1 ;
N = 1785
Qui = louis17 ;

6
Dossier sur PROLOG Utilisations de PROLOG

No
Cette fois PROLOG veut bien s’exécuter car il y a un nombre fini d’entiers compris entre 1750 et 1800. On retrouve bien
les même résultats qu’avec le premier exemple
PROLOG permet également de façon tout à fait naturelle de rechercher des solutions n’appartenant pas à un ensemble de
valeurs.
Ex : Quels sont les personnages qui ne sont pas nés entre 1750 et 1800 ?
?- bio(Qui,_,N,_,_,_),(1750>N;N>1800).
Qui = louis13
N = 1601 ;
Qui = elisabeth_France
N = 1603 ;
Qui = marie_therese_Autriche
N = 1638 ;
Qui = louis14
N = 1638 ;
Qui = grand_dauphin
N = 1661 ;
Qui = louis_bourbon
N = 1682 ;
Qui = philippe5
N = 1683 ;
Qui = louis15
N = 1710 ;
Qui = louis_dauphin
N = 1729 ;
Qui = philippe1
N = 1640 ;
Qui = philippe2
N = 1674 ;
Qui = louis_orleans
N = 1703 ;
Qui = louis_philippe
N = 1725 ;
Qui = philippe_egalite
N = 1747 ;
No
Rem : Ici non plus on ne peut pas inverser l’ordre des formules atomiques de la requête.
?- (1750>N;N>1800),bio(Qui,_,N,_,_,_).
ERROR: Arguments are not sufficiently instantiated
On obtient le même type d’erreur que lorsqu’on recherchait des solutions dans un intervalle de valeurs.
II.1.2.5. Utilisation des sous-tables
Lorsque nous avions programmé la base de données, en plus de la table ‘bio’, nous avions également déclaré trois autres sous
tables : ‘enfant’, ‘ptenfant’ et ‘descendant’ par l’intermédiaire de règles. Il est tout à fait possible d’interroger ces dernières
comme nous l’avons fait avec ‘bio’.
Ex : Quels sont les descendants de Louis XIV ?
?- descendant(X,louis14).
X = grand_dauphin ;
X = louis_bourbon ;
X = philippe5 ;
X = louis15 ;
X = louis_dauphin ;
X = louis16 ;
X = louis18 ;
X = charles10 ;
X = clotilde ;
X = louis17 ;
No
Louis XIV a 10 descendants dans la base de données.
Ex : Quels sont les ancêtres de Louis XVII ?
?- descendant(louis17,X).

7
Dossier sur PROLOG Utilisations de PROLOG

X = louis16 ;
X = marie_antoinette ;
X = louis_dauphin ;
X = marie_josephe_saxe ;
X = louis15 ;
X = marie_leczcynska ;
X = louis_bourbon ;
X = marie_adelaide_savoie ;
X = grand_dauphin ;
X = marie_anne_baviere ;
X = louis14 ;
X = marie_therese_autriche ;
X = louis13 ;
X = anne_autriche ;
X = henri4 ;
X = marie_medicis ;
X = philippe4 ;
X = elisabeth_france ;
X = henri4 ;
X = marie_medicis ;
No
Louis XVII a 19 ancêtres dans la base de données. Pourtant, on obtient 20 réponses. En effet, Henri IV apparaît deux fois
car deux liens de parenté différents les relient.

II.2. Formalisation de systèmes experts

II.2.1. PROLOG et les systèmes experts

PROLOG est parfaitement adapté pour formaliser des systèmes experts. En effet, un système expert est un programme
informatique simulant l'intelligence humaine dans un champ particulier de la connaissance ou relativement à une problématique
déterminée. Or PROLOG a justement été conçu dans cette optique là puisqu’il a été fait par des chercheurs en intelligence
artificielle.
Un système expert a trois composantes essentielles :
• une base de connaissances, formée des énoncés relatifs aux faits de tous ordres constitutifs du domaine
• un ensemble de règles de décision, consignant les méthodes, procédures et schémas de raisonnement utilisés dans le
domaine
• un moteur d'inférence, sous-système qui permet d'appliquer les règles de décision à la base de connaissances.
Or ces trois points sont extrêmement simples à implémenter dans programme PROLOG :
• la base de connaissances est constituée par les faits et quelques règles pour éviter l’énumération exhaustive de tous les
faits
• les règles de décision sont des règles (au sens de PROLOG)
• le moteur d’interface est l’interpréteur PROLOG lui-même.

II.2.2. Constitution de la base de connaissance

En guise d’exemple de système expert, nous allons formaliser le problème de coloriage de région. Les règles de ce problème
sont les suivantes :
• Une surface est découpée en un certain nombre de régions de surfaces et de formes variables
• Chaque région doit être coloriée
• Deux régions adjacentes doivent avoir deux couleurs différentes
Nous essaierons de colorier les régions suivantes :

8
Dossier sur PROLOG Utilisations de PROLOG

2
1 3 5

5 4 3
4
que nous représenterons plutôt par
La deuxième représentation permet de s’abstraire de toute géométrie :
• Un sommet représente une région
• Une arête reliant deux sommets signifie que les régions équivalentes sont adjacentes
C’est cela qu’on va traduire dans le programme PROLOG par le prédicat adjacent
1 2
Ex : adjacent(1,2). signifie
ce qui n’est pas exactement « La région 1 est adjacente à la région 2. »
II.2.2.1. Enumération exhaustive
La première solution pour constituer la base de connaissance est de faire une énumération exhaustive des régions adjacentes.
Programme 2 : Base de connaissances exhaustive
%Liste exhaustive des regions adjacentes
adjacent(1,2). adjacent(2,1).
adjacent(1,3). adjacent(3,1).
adjacent(1,4). adjacent(4,1).
adjacent(1,5). adjacent(5,1).
adjacent(2,3). adjacent(3,2).
adjacent(2,4). adjacent(4,2).
adjacent(3,4). adjacent(4,3).
adjacent(4,5). adjacent(5,4).
Cette base de connaissance fonctionne parfaitement.
Ex : Les régions 1 et 2 sont adjacentes :
?- adjacent(1,2) ,adjacent(2,1).
Yes
La région 2 n’est pas adjacente à la région 11 (qui n’existe pas)
?- adjacent(2,11).
No
La région 2 n’est pas adjacente à la région 5
?- adjacent(2,5).
No
Cependant, on voit très bien que ce genre de base de connaissances est limité : si le problème devient trop complexe, on ne peut
pas saisir à la main toutes les possibilités. De plus cette écriture sous-exploite le potentiel de PROLOG qui grâce aux règles peut
grandement alléger cette écriture.
II.2.2.2. Ecritures condensées
Nous allons condenser l’écriture exhaustive en remplaçant certains faits par des règles ce qui comme nous le verrons n’est pas
sans danger.
II.[Link]. Règle de commutation
Essayons tout d’abord d’introduire une règle de commutativité. En effet, cette règle si naturelle pour nous quand on parle de
coté adjacent fait cruellement défaut à PROLOG et permettrait de réduire de moitié le nombre de faits.
Programme 3 : Base de connaissances commutative (erronée)
%Liste des régions adjacentes 1 fois (sans commutation)
adjacent(1,2).
adjacent(1,3).
adjacent(1,4).
adjacent(1,5).
adjacent(2,3).
adjacent(2,4).
adjacent(3,4).
adjacent(4,5).

9
Dossier sur PROLOG Utilisations de PROLOG

/*La regle de commutation */

adjacent(X,Y):-adjacent(Y,X).
Cette règle de commutation fonctionne très bien dans certains cas.
Ex : Le programme détecte parfaitement les régions adjacentes :
?- adjacent(2,4).
Yes
?- adjacent(4,2).
Yes
2 et 4 sont bien deux régions adjacentes
Malheureusement, dans d’autres cas elle engendre des boucles infinies.
Ex : Le programme boucle systématiquement pour détecter des régions non adjacentes :
?- adjacent(2,5).
Action (h for help) ? abort
Execution Aborted
Ex : Enumérer toutes les régions adjacentes à 1
?- adjacent(1,X).
X = 2 ;
X = 3 ;
X = 4 ;
X = 5 ;
X = 2 ;
X = 3 ;
X = 4 ;
X = 5 ;
X = 2 ;
X = 3 ;
X = 4 ;
X = 5
…
PROLOG ne boucle pas tout seul mais il retourne toujours la même série de solutions tant que l’utilisateur lui en
demande encore : il ne s’arrête pas tout seul pour signifier qu’il n’y en a plus d’autres.
En fait, la règle de commutativité remplie parfaitement son rôle pour déterminer que deux régions sont adjacentes car soit elle
n’est jamais invoquée soit elle est utilisée une seule fois avant de trouver le fait permettant d’arrêter la recherche.
Ex : [debug] ?- adjacent(2,4).
T Call: ( 8) adjacent(2, 4)
T Exit: ( 8) adjacent(2, 4)
PROLOG trouve la preuve directement dans les faits.
[debug] ?- adjacent(4,2).
T Call: ( 8) adjacent(4, 2)
T Call: ( 9) adjacent(2, 4)
T Exit: ( 9) adjacent(2, 4)
T Exit: ( 8) adjacent(4, 2)
Cette fois il est obligé d'appliquer la règle de commutativité 1 fois (2ème call) puis il trouve un fait pour elle, il en sort et
il répond à la requête.
Par contre, si la requête porte sur deux régions non adjacentes, PROLOG va appeler une infinité de fois la règle de
commutativité.
Ex : [debug] ?- adjacent(2,5).
T Call: ( 8) adjacent(2, 5)
T Call: ( 9) adjacent(5, 2)
T Call: ( 10) adjacent(2, 5)
T Call: ( 11) adjacent(5, 2)
T Call: ( 12) adjacent(2, 5)
T Call: ( 13) adjacent(5, 2)
T Call: ( 14) adjacent(2, 5)
T Call: ( 15) adjacent(5, 2)
T Call: ( 16) adjacent(2, 5)
T Call: ( 17) adjacent(5, 2)
T Call: ( 18) adjacent(2, 5)
...

10
Dossier sur PROLOG Utilisations de PROLOG

Les zone 2 et 5 n'étant pas adjacentes, ni adjacent(2,5), ni adjacent(5,2) ne fait partis des faits.
La première action de PROLOG est de regarder si la requête est un fait. Puisque ce n’est pas le cas, il applique la règle de
commutation en espérant que cela lui permet de conclure. Il reparcourt donc les faits mais il ne trouve encore aucune
preuve pour répondre à la requête. Donc il applique une nouvelle fois la règle de commutation.
Dans le cas d’une énumération de zones adjacentes à une autre, la règle de commutation crée en quelque sorte une infinité de
faits en répétant les faits une fois à l’endroit, une fois en commutant les paramètres et ceci une infinité de fois.
Ex : [debug] ?- adjacent(1,X).
T Call: ( 7) adjacent(1, _G304)
T Exit: ( 7) adjacent(1, 2)
X = 2 ;
T Exit: ( 7) adjacent(1, 3)
X = 3 ;
T Exit: ( 7) adjacent(1, 4)
X = 4 ;
T Exit: ( 7) adjacent(1, 5)
X = 5 ;
T Redo: ( 7) adjacent(1, _G304)
T Call: ( 8) adjacent(_G304, 1)
T Redo: ( 8) adjacent(_G304, 1)
T Redo: ( 8) adjacent(_G304, 1)
T Call: ( 9) adjacent(1, _G304)
T Exit: ( 9) adjacent(1, 2)
T Exit: ( 8) adjacent(2, 1)
T Exit: ( 7) adjacent(1, 2)
X = 2
…
Au 1er passage, PROLOG trouve tous les faits correspondant à la requête (les régions 2, 3, 4 et 5 sont adjacentes à la 1).
Ensuite il appelle la règle de commutation adjacent(X,Y):-adjacent(Y,X)et relit les faits. Cette fois aucun ne
convient mais il arrive de nouveau à la règle de commutation. Il l’applique et recommence à lire les faits. Après deux
commutations, il est revenu (malheureusement il ne le sait pas) à l’état initial ; il trouve donc les mêmes solutions qu’au
premier passage…
Rem : Il existe des méthodes pour prévenir ces boucles, cependant pour des raisons d’efficacité, elle ne sont pas utilisées dans
PROLOG.
II.[Link]. Enumération par variables
Une autre façon de condenser l’écriture est de faire l’énumération des quatre premiers faits (et leurs images commutées) par
l’intermédiaire d’une variable. En effet, on remarque que ces faits sont tous de la forme adjacent(1,x) avec 2 ≤ x ≤ 5.
Programme 4 : Base de connaissances avec énumération par variable (erronée)
% Liste des regions adjacentes autres que la 1
adjacent(2,3).
adjacent(2,4).
adjacent(3,4).
adjacent(4,5).
adjacent(3,2).
adjacent(4,2).
adjacent(4,3).
adjacent(5,4).

% Regles concernant la region 1

adjacent(1,X):-X>=2,X=<5.
adjacent(X,1):-X>=2,X=<5.
Ce programme marche très bien avec des requêtes simples
Ex : On peut savoir que les régions 3 et 1 sont adjacentes :
?- adjacent(1,3),adjacent(3,1).
Yes
ou que les régions 5 et 2 ne le sont pas :
?- adjacent(5,2).
No
Par contre, une erreur peut apparaître lorsqu’on emploie des requêtes un peu plus complexes.
Ex : Enumérer toutes les régions adjacentes à 2
?- adjacent(2,X).

11
Dossier sur PROLOG Utilisations de PROLOG

X = 3 ;
X = 4 ;
X = 1 ;
No
La région 2 est bien adjacente aux régions 1, 3 et 4.
Ex : Enumérer toutes les régions adjacentes à 1
?- adjacent(1,X).
ERROR: Arguments are not sufficiently instantiated
^ Exception: (7) _G158>=2 ? abort
% Execution Aborted
PROLOG refuse d’exécuter la requête. En effet, il s’agit d’un des rares contrôle de PROLOG. Sans ce contrôle, il
regarderait adjacent(1,X) pour tous les X ≥ 2 puis pour tous les X ≤ 5 ; or il y en a une infinité dans les deux cas et
il entrerait donc dans une boucle infinie.
Il existe une solution à ce problème. PROLOG fournit un système pour borner une variable entière : between.
Ainsi, il faut remplacer les deux règles concernant la région 1 par :
% Regles concernant la region 1
adjacent(1,X):-between(2,5,X).
adjacent(X,1):-between(2,5,X).

II.[Link]. Relations entre paramètres

On remarque que concernant les régions (2,3), (3,4) et (4,5) les deux paramètres X et Y du prédicat adjacent sont liés par la
relation Y=X+1. On pourrait donc écrire explicitement cette relation.
Programme 5 : Base de connaissances avec relation entre paramètres (erronée)
% Regions adjacentes explicitement declarees
adjacent(2,4).
adjacent(4,2).

% Regles concernant la region 1

adjacent(1,X):-between(2,5,X).
adjacent(X,1):-between(2,5,X).

% Regles concernant les couples (2,3), (3,4) et (4,5)

adjacent(X,X+1).
adjacent(X+1,X).
Ce programme présente plusieurs défauts :
• D’abord, il est syntaxiquement incorrect. En effet, PROLOG ne reconnaît pas « X+1 » comme étant la valeur de X
augmenté de 1. Pour cela, il dispose du mot clé is :
adjacent(X,Y):-Y is X+1.
adjacent(X,Y):-Y is X+1.
• Ensuite, comme nous l’avons vu au chapitre précédent, il faut spécifie que X est un entier borné en utilisant between
adjacent(X,Y):-between(2,4,X), Y is X+1.
adjacent(X,Y):-between(2,4,X), Y is X+1.
Finalement, nous avons pu condenser la base de connaissances en :
Programme 6 : Base de connaissances condensée (finale)
% Regions adjacentes explicitement declarees
adjacent(2,4).
adjacent(4,2).

% Regles concernant la region 1

adjacent(1,X):-between(2,5,X).
adjacent(X,1):-between(2,5,X).

% Regles concernant les couples (2,3), (3,4) et (4,5)

adjacent(X,Y):-between(2,4,X),Y is X+1.
adjacent(Y,X):-between(2,4,X),Y is X+1.
Cette écriture condensée est exactement équivalente au programme exhaustif page 9.

12
Dossier sur PROLOG Utilisations de PROLOG

Ex : Test sur deux régions adjacentes

?- adjacent(1,2),adjacent(2,1).
Yes
1 et 2 sont bien adjacentes
Ex : Test sur deux régions non adjacentes
?- adjacent(2,5).
No
2 et 5 ne sont effectivement pas adjacentes
Ex : Enumération de régions adjacentes
?- adjacent(1,X).
X = 2 ;
X = 3 ;
X = 4 ;
X = 5 ;
No
1 est adjacente exactement à 2, 3, 4 et 5

II.2.3. Mise en place des règles de décision

Pour les règles de décision, on introduit deux nouveaux prédicats :

• conflit(Coloriage) qui permet de voir si un coloriage des régions respecte les contraintes que nous nous
sommes fixées
• conflit(X,Y,Coloriage) qui permet de savoir quelles régions adjacentes ont la même couleur
Un coloriage des régions est une fonction qui à chaque région associe une couleur. Elle est réalisée par le prédicat :
color(Region,Couleur,Coloriage)
Trois coloriages ont été définis directement dans le programme :
coloriage1 coloriage2 coloriage3

2 2 2
1 3 1 3 1 3

5 4 5 4 5 4
Programme 7 : Formalisation d'un système expert (complète)
% Description des zones
adjacent(2,4).
adjacent(4,2).
adjacent(1,X):-between(2,5,X).
adjacent(X,1):-between(2,5,X).
adjacent(X,Y):-between(2,4,X),Y is X+1.
adjacent(Y,X):-between(2,4,X),Y is X+1.

% Règles de décisions
conflit(Coloriage):-adjacent(X,Y),color(X, Couleur, Coloriage),color(Y, Couleur, Coloriage).
conflit(X,Y,Coloriage):-adjacent(X,Y),color(X, Couleur, Coloriage),color(Y, Couleur,
Coloriage).

% Exemples de coloriages possibles

/* Coloriage sans conflit */
color(1,bleu,coloriage1).
color(2,rouge,coloriage1).
color(3,vert,coloriage1).
color(4,jaune,coloriage1).
color(5,rouge,coloriage1).

/* Coloriage avec conflit */

color(1,vert,coloriage2).
color(2,rouge,coloriage2).
color(3,vert,coloriage2).
color(4,jaune,coloriage2).

13
Dossier sur PROLOG Utilisations de PROLOG

color(5,vert,coloriage2).

/* Coloriage avec conflit */

color(1,bleu,coloriage3).
color(2,bleu,coloriage3).
color(3,bleu,coloriage3).
color(4,bleu,coloriage3).
color(5,bleu,coloriage3).
Nous pouvons maintenant vérifier si un coloriage est valide et dans le cas contraire, connaître les régions adjacentes qui ont la
même couleur.
Ex : Un coloriage sans conflit
?- conflit(coloriage1).
No
Le coloriage 1 ne possède effectivement pas de régions adjacentes de même couleur.
Ex : Un coloriage avec conflit
?- conflit(coloriage2).
Yes
Les régions adjacentes de même couleur sont :
?- conflit(X,Y,coloriage2),between(X,5,Y).
X = 1
Y = 3 ;
X = 1
Y = 5 ;
No
La région 1 a la même couleur que la région 3 et la région 5.
Ex : Toutes les régions de la même couleur
?- conflit(coloriage3).
Yes
Toutes les régions adjacentes entrent en conflit
?- conflit(X,Y,coloriage3),between(X,5,Y).
X = 2
Y = 4 ;
X = 1
Y = 2 ;
X = 1
Y = 3 ;
X = 1
Y = 4 ;
X = 1
Y = 5 ;
X = 2
Y = 3 ;
X = 3
Y = 4 ;
X = 4
Y = 5 ;
No
Effectivement, il s’agit bien là de toutes les régions adjacentes.

II.3. Calculs

PROLOG permet évidemment d’effectuer des calculs numériques. C’est ce que nous allons voir en essayant de programmer la
factorielle. Pour cela, plusieurs approches sont possibles.

II.3.1. Utilisation d’une pile

Il s’agit probablement de la façon la plus intuitive de programmer la factorielle. En effet, on définit mathématiquement cette
fonction par : fact : NÆN
0Æ1
n Æ n × (n-1)!

14