Programmation logique. Chap.1 Klouche-Djedid A.
Dpt Informatique IGMO/USTO
Introduction à la programmation logique
Le langage Prolog.
1. Origine :
Le langage Prolog a été conçu par Alain Colmerauer. C’est un langage de très haut niveau, dit
de cinquième génération, il a été consacré en 1982, comme langage de support du projet
japonais de 5ème génération
Prolog est un démonstrateur de théorèmes.
L’idée de base de la création de prolog :
¾ Mise en forme de la logique sous forme de clauses
¾ Introduction d’une règle d’inférence.
Les domaines d’applications de Prolog sont :
9 automatisation des preuves de théorèmes,
9 pour résoudre les problèmes d’analyse et de compréhension de la langue naturelle.
9 Son application s’est étendue à l’intelligence artificielle,
9 pour la représentation des connaissances et des systèmes experts.
9 Prototypage, BD, BC etc ….
Prolog est un langage conversationnel, son code source est plus concis que Pascal, mais il
consomme plus de temps et de mémoire.
Le langage Prolog est le plus souvent interprété, mais certaines versions Prolog disposent de
compilateurs
Programmer en Prolog consiste à [CM]:
¾ Déclarer des faits ou assertions sur des objets et leurs interactions
¾ Définir des règles sur des objets et leurs interactions
¾ Poser des questions (requêtes) sur des objets et leurs interactions.
La question ∃x (Q) but
Le programme P Résolution SLD
{Ensemble des (Sélectionné, linéaire, défini)
clauses définies}
Non, n’∃ pas de x dans T L’ensemble des x dans T,
/Q est conséquence tels que Q est conséquence
logique de P. logique de P
Schématique d’exécution Prolog
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
Programmation logique. Chap.1 Klouche-Djedid A. Dpt Informatique IGMO/USTO
2. Structure d’un programme Prolog :
Un programme ≡ des axiomes et des règles.
On se restreint aux sous-ensembles des clauses de Horn, définies dans Chap0. on n’admet
que des formules du type :
(lp1 ∧ lp2 ∧ lp3 ….∧ lpn ) Æ lp
¬lp1 ∧ ¬lp2 ∧ ¬lp3…∧ ¬lpn ∨ lp
Qu’on écrit en syntaxe Prolog
lp Å lp1, lp2, …., lpn.
lp :- lp1, lp2, …., lpn. Syntaxe d’une clause
Où lpi représente un littéral positif ou formule atomique, lpi = pi (t1, t2,…tn) pi : prédicat.
Autrement, une conjonction d’hypothèses entraîne une seule conclusion.
Faits
p1(t1,t2,…tk) Å
p2(t1,t2,…tk). Å
lp Å lp1, lp2, ,lpn
Règles
……Å ………
…….Å ………
…….Å ………
Å q(v1,v2,…vn) But
Å ……. En prolog Å s’écrit :-
Structure d’un programme Prolog
2.1. Les faits (assertions) :
Un fait (formule atomique) est la représentation d’une connaissance exprimant une propriété
d’objet ou une relation entre des objets.
Exemple :
fille(jamila) est la connaissance « jamila est une fille » qu’on écrit en Prolog
fille(jamila) Å ou bien fille(jamila).
pere(ali, jamila) représente la connaissance « ali est le père de jamila » en prolog
pere(ali,jamila) Å ou bien pere( ali, jamila).
mere(fatma, jamila)
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
Programmation logique. Chap.1 Klouche-Djedid A. Dpt Informatique IGMO/USTO
Les prédicats sont pere , mere, fille et les termes sont jamila ali.
2.2. Les règles :
Les règles permettent de définir des relations à partir d’autres relations.
lp Å lp1, lp2, ,lpn est une connaissance exprimée en logique mathématique par :
« ∀x1,x2,..xn , (lp1 et lp2 et…lpn ⇒ lp) »
En prolog standard la règle s’écrit :
lp :- lp1, lp2, ,lpn
tête de clause :- corps de la clause
lp1, lp2, ,lpn les prémisses
les quantificateurs universels sont omis, implicites, la conjonction « et » est remplacée par la
virgule.
Exemple :
parent(X,Y) :- pere(X,Y).
grand_parent( X,Z) :- parent(X,Y) , parent (Y,Z).
Soit la connaissance suivante :
« un parent d’une personne est son père ou sa mère »
Comment la représenter en logique mathématique ? Puis en prolog ?
∀ x, ∀y (parent(x, y) ⇔ ((père(X,Y) ou mere(X,Y) ).
Equivaut à 2 énoncés :
1- si x parent de y, alors alors x est père de y ou x est mere de y.(non repr en prolog
,conclu contient ou)
2- si x est père de y ou x est mere de y alors x parent de y.(contient ou en prémisses)
En prolog 2- équivaut à:
parent(X,Y) :- pere(X,Y).
parent(X,Y) :- mere(X ,Y).
On peut ainsi définir de nouvelles règles telles que la règle « sœur » et enrichir ainsi la base
des connaissances.
2.3. Les questions (requêtes) ou résolution de but :
Une fois que nous avons défini la base de connaissance, on peut lancer une requête
q(v1,v2,…,vn).
Les buts peuvent être simple ou composés (conjonctions d’atomes).
La requête provoque l’exécution du programme prolog qui va :
¾ Chercher un axiome qui convient
¾ Chercher si une règle peut être appliquée, c'est-à-dire si sa conclusion convient
(Chercher une assertion qui correspond à l’assertion de la question, deux assertions ont
identiques si leurs prédicats sont identiques et si leurs arguments sont les mêmes dans
l’ordre)
Si ça marche prolog répond yes sinon il répond no
Exemples de requête :
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
Programmation logique. Chap.1 Klouche-Djedid A. Dpt Informatique IGMO/USTO
« Est-ce que ali est un parent de jamila » s’écrit en prolog par
?- parent(ali,jamila) ÆYes
« Quels sont les parents de jamila ? »
?- parent(X, jamila) Æ X =ali ÆX= fatma
2.5. Conclusion :
Un programme logique est un ensemble (conjonction) fini de définition de prédicats.
3. Syntaxe des objets Prolog :
Les noms d’objets et de relations doivent suivre une syntaxe précise : en général un objet a
une syntaxe alphanumérique, et il est recommandé d’utiliser des noms mnémoniques afin de
reconnaître et nous rappeler le sens des objets. Ex pere au lieu de p.
9 Les noms de relations et des objets doivent commencer par une lettre minuscule.
9 Les faits doivent toujours se terminer par un point.
9 La relation est écrite en premier, et les objets sont entre ( ).
9 Les noms des variables doivent être une majuscule ou commencer par le blanc
souligné « _ » (tiret du 8) X _som Flene …
9 les commentaires multilignes, comme en C, compris entre /* et */
sur une seule ligne, introduits par le symbole %
9
3.1. Un exemple de programme Prolog :
F1 mere(fatema, soraya).
F2 mere(fatema,jamila).
F3 mere(zohra, ali).
F4 pere(ali,jamila).
F5 pere(ali,kader).
F6 pere(hadj,ali).
F7 pere(houari,fatema).
R1 grandpere(X,Z) :- pere(X,Y), pere(Y,Z).
R2 grandpere(X,Z) :- pere(X,Y), mere(Y,Z).
R3 grandmere(X,Z) :- mere(X,Y), pere(Y,Z).
R4 grandmere(X,Z) :- mere(X,Y), mere(Y,Z).
………………...................................................
Déterminer les termes, prédicats,
On se propose de rajouter la nouvelle relation « frere » décrire la règle :
frere(X,Y) :- pere(Z,X),pere(Z,Y) , mere(Z,X), mere(Z,Y).
Les questions :
?-grandpere(hadj,kader). Æyes
?-grandpere(X,jamila). Æ X=houari Æ X=hadj
?-frere(jamel,Y).
Autre règle : cousin
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
Programmation logique. Chap.1 Klouche-Djedid A. Dpt Informatique IGMO/USTO
cousin(X,Y) :- pere(T,X), frere(T,U), pere(U,Y).
4. Exécution d’un programme Prolog. Résolution de but.
Soit l’écriture généralisée d’un programme P :
p1(t1,t2,…tk) .
p(t1,t2,…tk) :- p1(t1,t2,…tk), p2(t1,t2,…tk),… pn(t1,t2,…tk).
On exécute le programme P par la soumission d’une requête q(v1,v2,…,vn) ;
La réponse de Prolog à la question q(v1,v2,…,vn) est Æ yes , s’il peut déduire que
q(v1,v2,…,vn) est vraie à partir de la connaissance du programme P constituée des faits et
des règles.
q(v1,v2,…,vn) sera donc une conséquence logique de P.
Ex - ?grandpere(hadj,kader). Peut être déduit des faits F5 et F6 plus la règle R1.
La résolution de but est basée sur le principe d’Unification, qui fait appel à la
substitution.
4.1. Définition substitution S
C’est un ensemble fini de paires de la forme Xi = ti où les Xi sont des variables et les ti sont
des objets, termes.
Par ex S={X = ali , Y = fatema } est une substitution.
La substitution vide (Identité) est { } où l’ensemble des couples est vide (aucune variable à
remplacer ou à instancier).
4.2. Le principe d’Unification.
Consiste à mettre en correspondance q(v1,v2,…,vn) et p(t1,t2,…,tn) on unifie les deux
termes sachant qu’ un prédicat est identifié à la fois par son nom et par le nombre de ses
arguments.
Le principe d'« unification » affecte une valeur à une variable.
Une fois qu'une valeur est affectée à une variable, on dit « variable liée ».
L’unification calcule une substitution S qui rend les termes égaux. On fait « une
résolution d’équations symboliques »
q(v1,v2,…,vn) = p(t1,t2,…,tn)
Exemples d’unifications des deux termes :
p(X,a,c) = p(a,a,Z) Æ substitution solution S ={X=a,Z=c}
f (X, g(a, d)) et f (h(c, Z), g(a,Y )) Æ S={X= h(c, Z)), Y ,=d}
f (g(X)) et f (h(Y )): S = φ
pere(X, jamila) et pere(ali,jamila) Æ S ={X = ali}
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
Programmation logique. Chap.1 Klouche-Djedid A. Dpt Informatique IGMO/USTO
Conclusion requête solution .
c(X, Y ) c(f (a), g(a, b)) X = f (a), Y = g(a, b)
c(f (a), g(a, b)) c(X, Y ) X = f (a), Y = g(a, b)
f (T, c(e), d) f (a, X, d) T = a, X = c(e)
f (a, b, X) f (Y , c, d) echec
c(X, Y ) c(Z,T) X = Z, Y = T (ou T = Y, ou Z = X. . . )
c(X, a, b) c(c, X, b) problème mal pose
f (a) f (a) oui
p(X, c, X) p(a, Y , a) X = a, Y = c
f (X, g(X)) f (Z, Z) ´ échec
4.3. Exemples de résolutions de buts.
Revenons au programme prolog famille.
Ex1 Soit la requête ?-grandpere(hadj,kader).
Comment procède Prolog pour la résolution de ce but ?
1. La requête correspond à la tête de la règle grandpere la var X sera instanciée à hadj
et Z à kader
2. Prolog doit satisfaire les deux sous buts de la règle grandpere , qui sont pere(X, Z,) et
pere(Z,Y) avec les instanciations de X et Z égales à hadj et kader.
3. prolog recherche pere(hadj,Z) et pere(Z, kader) dans les faits , la variable Z sera
instanciée à ali par conséquent :
4. Prolog répond Æ yes.
5. la substitution S est vide (Identité) car pas de variable à calculer.
Ex2 soit la requête ?-grandpere(X,jamila). Æ grandpere(hadj, jamila)
grandpere(houari, jamila)
Prolog procède par les étapes suivantes :
1. cette requête correspond (sera unifiée) à la conclusion de la règle grandpere, la var X
de la question est libre comme la variable X de la règle R1 grandpere Æ ces 2
variables sont unifiées.
2. on passe à la résolution des sous buts : pere(X,Z) et pere(Z,jamila) engendrés par la
règle grandpere pour construire progressivement la substitution solution)
3. pour le premier sous but de la règle pere (X,Z) comme on ne connait pas Z , le second
sous but est pere (Z,jamila) et va correspondre à pere(ali,jamila) donc Z est
instancié par ali
4. on revient au 1èr but pere(X, ali) ce qui correspond à pere(hadj, ali) pour X= hadj.
Unifier ces deux sous termes revient à engendrer des substitution(s) solution(s) S qui les
rendent égaux.
S1= {X = hadj}
La résolution du but se poursuivra de la même manière avec la seconde règle R2 de
grandpere qui permettra d’engendrer la substitution S2 = {X= houari}
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
Programmation logique. Chap.1 Klouche-Djedid A. Dpt Informatique IGMO/USTO
Le parcours de l’unification est arborescent, du fait qu’on part d’un but à résoudre pour
remonter à des sous buts résolus. Ceci est la décomposition du problème en sous problèmes et
ainsi de suite…
Prolog fonctionne en retour arrière (backtracking)! Un mécanisme qui permet de remonter
dans l’arbre pour trouver d’autres solutions.
De ce fait il existe plusieurs algorithmes d’unifications.
grandpere(X,jamila).
pere(X,Z), pere(Z,jamila)
pere(X,ali) pere(ali,jamila)
Z=ali
pere(hadj, ali)
X =hadj
Mécanisme de backtracking.
Autre exemple : représenter à l’aide de faits les connaissances suivantes :
6 est pair
6 est le double de 3
Le cours de PL a lieu le mardi de 13h à 14h30.
3.4. Exemple :
0 est un nombre naturel
Si N est un nombre naturel alors succ(N) est naturel
Natural(0).
Natural(S(N)) :- natural(N).
?- natural (s(s(s(0))).
Yes
?-natural(mardi)
No
?-natural(X)
Æ X=0
Æ X= S(0)
Æ X= S(S(0))
………..
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
Programmation logique. Chap.1 Klouche-Djedid A. Dpt Informatique IGMO/USTO
5. Les outils :
Il existe différents outils pour vous permettre de programmer en Prolog :
• SWI Prolog
Possède un débuggeur graphique ainsi que plusieurs solveurs de contraintes
www.swi-prolog.org
• GNU Prolog
Propose un solveur de contraintes sur domaine fini
http://gnu-prolog.inria.fr
5.1. Installation
• Sous Windows :
Télécharger l'un des programmes mentionnés précédemment et l'installer
5.2. Edition
Tout éditeur de texte :Bloc notes, Wordpad, ou Word l’extension d’un programme Prolog
est : .pro ou .pl
Lister le programme :
Avec le prédicat listing.
Avec argument : permet d’éditer la liste de définition du prédicat argument
Sans arguments : permet de lister tout le programme tout le programme.
3 ?- listing('pere').
pere(ali, jamila).
pere(ali, med).
pere(med, sam).
true.
Editer permet d’ouvrir la fenêtre d’édition de l’interpréteur Prolog.
?- edit(famille).
true.
5.3. Exécution.
Lancez votre interpréteur Prolog :
Chargez votre programme grâce à la commande consult :
Utilisez le prédicat consult avec comme argument le chemin d'accès du programme, sous
forme d'une chaîne :
| ?- consult('le_nom_de_votre_programme.pro').
Tous les prédicats sont alors évalués et on peut alors les exécuter
On peut visualiser le contenu suivant :
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.62)
Copyright (c) 1990-2008 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
Programmation logique. Chap.1 Klouche-Djedid A. Dpt Informatique IGMO/USTO
1 ?- consult('famille.pl').
% famille.pl compiled 0.00 sec, 1,484 bytes
true.
2 ?- pere(ali,X).
X = jamila ;
Pour passer à la solution suivante tapez la touche « ; »
X = med.
Fenêtre d’exécution et d’édition SWI-Prolog
Références :
Programmer en Prolog. Jonhatan Elbaz Ellipses.
Programmer en Prolog. W.F. Clocksin C.S. Mellish. Eyrolles.
http://prolog.developpez.com/cours/
Signature numérique de Klouche-Djedid
Klouche-Djedid Afaf
ID : CN = Klouche-Djedid Afaf, C = <a
Motif : Je suis l'auteure de ce document
Afaf Lieu : Oran
Date : 2009.03.27 18:07:55 +01'00'
Mise en ligne : http://klouche-djedid.com http://klouche.iquebec.com www.klouche.tk
