Upload
vanthuy
View
217
Download
0
Embed Size (px)
Citation preview
Concepts des langages de
programmationprogrammation
Introduction à la programmation logique avec Prolog
Programmation logique
� Paradigme de programmation déclarative � Basé sur la déclaration des relations existantes entre
différentes entités
� Basé sur la logique des prédicat (logique mathématique du � Basé sur la logique des prédicat (logique mathématique du premier ordre)
� Principal représentant de ce type de langages : Prolog
2
Langage logique vs. Langage fonctionnel
� Les langages fonctionnels manipulent les relations qui sont des fonctions
� Les langages logiques peuvent manipuler n’importe quelle � Les langages logiques peuvent manipuler n’importe quelle relation� "Une généralisation des langages fonctionnels"
� Avantage : permet d’aller “dans les 2 sens”
3
Relations
� Fonction de X1 vers X2
� Relation binaire où chaque élément de l'ensemble de départ X1
est associé avec au plus un élément de X2
� La fonction peut être représenter par les couples (x1, x2)
� Relation n-aire� Relation n-aire sur les ensembles X1,...,Xn : ensemble des tuples
de la forme (x1, ..., xn) où xi est un élément de Xi
4
Relations (suite)
� Propriété qui lie un certain nombre d’objets� Exemple : posséder lie le propriétaire et l’objet possédé
� Leur nom commence par une minuscule
� Utilité des relations :
� Liens entre les objets
� Propriétés d’un objet
5
Les faits
� Affirmation de l’existence d’une relation entre certains objets� La chèvre est un animal herbivore
� Le loup est un animal cruel� Le loup est un animal cruel
� Pierre est un homme
� Formule vraie à priori
� Constitue une partie des données d’un problème
6
Les faits (suite)
� Supposons que nous voulions exprimer que “Pierre est un homme”. Nous écrirons simplement :� homme(pierre).� Le prédicat est : homme()
7
� homme(pierre) est appelée un fait et traduit que le prédicat homme est vrai si son argument est égal à "pierre"
� On dira que homme est un prédicat d’arité1 (c’est-à-dire à 1 argument), et on le notera homme/1.
Les faits (suite)
� Il est possible maintenant de poser la question “Pierre est-il un homme ?” dans la fenêtre de “dialogue” de Prolog :
� > homme(pierre).
8
� > homme(pierre).
Ou bien :
� > -? homme(pierre).
� Prolog répond par l’affirmative :
� > true
Hypothèse de monde clos
� Posons maintenant la question :
� > homme(paul) .
� Que vous aurez traduit par "Paul est-il un homme?"
9
� Que vous aurez traduit par "Paul est-il un homme?" Prolog ne répond rien, ce qui signifie qu'il n'a pas su prouver que paul est un homme => paul n'est pas un homme
� Hypothèse de monde clos : tout ce qui n’est pas connu est faux
Variables
� Les variables commencent par une majuscule, les constantes par une minuscule. Leur affectation est unique et définitive
� Complétons donc le programme :� homme(pierre) .� homme(pierre) .
� homme(paul).
� Si maintenant on veut savoir “Qui est un homme ?”, il faut utiliser une variable :� homme(X) .
� X = pierre;
� X = paul
10
Variables (suite)
� La réponse de Prolog signifie que pierre et paul sont des hommes
� En termes de logique, on peut dire aussi que homme(X) est vrai si on substitue la variable X par pierre ou par paul
11
Variables (suite)
� Un fait à plusieurs arguments traduit une relation entre ces arguments :� pere(pierre, paul). : Traduit une relation pere entre pierre et paul. On peut
interpréter cette relation par la phrase "pierre est le père de paul"
� /* pere(X,Y) */
� /* X est le père de Y */
� pere(pierre, paul) .� pere(pierre, paul) .
� pere(pierre, jean) .
� Ceci peut être écrit :� pere(pierre, X) :- X = paul; X = jean.
12
Variables (suite)
� Définition d’une variable anonyme : "_"
� a_un_salaire(X) :-
employeur(Y,X). employeur(Y,X).
� Peut s’écrire :
a_un_salaire(X) :-
employeur(_,X).
13
Variables (suite)
� Affectations :� On utilise le mot clé is pour effectuer une affectation
� -? X is 4.
� -? Y is 2 * 8.
� Quelques fonctions prédéfinies :� -, +, *, /, ^, mod, abs, min, max, random, sqrt, sin, cos, tan, log, …
� Opérateurs de comparaison :� <, >, >=, =<, =:=, =\=
14
Règles Prolog
� Enoncent la dépendance d’une relation entre objets par rapport à d’autres relations
� Forme d'une règle :� conclusion si conditions
� Exemple de règle en Prolog� Exemple de règle en Prolog� Fait :
� fille(helene)
� Règle : � "si X est une fille alors X aime les poupées" s'écrit :
� aime(X,poupees) :- fille(X).
� Le "si" s’écrit ":-" en Prolog
15
Règles Prolog (suite)
� Il peut y avoir plusieurs conditions derrière le ":-", séparées par des opérateurs logiques :� Et : virgule (,)
� Ou : point virgule (;) � Ou : point virgule (;)
� Négation : not
� Exemple : � "un animal qui n'est pas un mammifère et qui vole ou un qui est un
pingouin est un oiseau" s'écrit :� oiseau(X) :- animal(X), not(mammifere(X)) , (vol(X) ; pingouin(X)).
16
Portée des variables
� En Prolog, une même variable représente le même objet à l'intérieur d'une règle ou un fait
17
� Il n’existe pas de variables globales en Prolog. Toutes les variables sont locales à une règle ou un fait
Programme en Prolog
� Programme = ensemble de relations (faits ou règles) + requête
� Exécution d’un programme = recherche d’une preuve de � Exécution d’un programme = recherche d’une preuve de la requête, étant données les relations existantes
� Prolog lit le programme de haut en bas et de gauche à droite
18
Programme en Prolog (suite)
� Comment exécuter un programme ? � Enregistrer les règles et faits dans un fichier
� Charger ce fichier avec l'instruction consult
� Entrer une requête pour que le programme s'exécute
19
Requêtes : exemple 1
� Considérons l’énoncé� Socrate est un homme
� Tout homme est mortel
� Requête � Socrate est-il mortel ?
Le langage
20
homme(socrate).
mortel(X) :- homme(X).
?- mortel(socrate).
Requêtes : exemple 2� masculin(tom).
� masculin(tim).
� masculin(bob).
� masculin(jim).
� feminin(pam).
� feminin(liz).
� feminin(ann).
Le langage
Famille :� feminin(pat).
� enfant(bob,pam).
� enfant(bob,tom).
� enfant(liz,tom).
� enfant(ann,bob).
� enfant(pat,bob).
� enfant(tim,liz).
� enfant(jim,pat).
Famille :
21
Requêtes : exemple 2 (suite)
� Requêtes :Est-ce que pat est un enfant de bob ?
?- enfant(pat,bob).
Yes
Quels sont les enfants de tom ?
?- enfant(X,tom).
X = bob;
X = liz;
No
22
Requêtes : exemple 2 (suite)
� Qui est le père de bob ?� ?- enfant(bob,X), masculin(X).
� X=tom
X=pam
Le langage
� Écriture d'une nouvelle relation : � pere(X,Y) :-
enfant(Y,X),
masculin(X).
23
Requêtes : exemple 3
� "qui est le père de paul ?" :� ?- pere(X, paul) .� X = pierre
� "de qui pierre est-il le père ?" :� ?- pere(pierre, Y) .
pere(pierre, paul) .
pere(pierre, jean) .
24
� ?- pere(pierre, Y) .� Y = jean;� Y= paul
� "qui est le père de qui ?" :� ?- pere(X, Y) .� X = pierre , Y = paul;� X = pierre , Y = jean
Principe de récurrence
� Comment définit-on une suite un par récurrence en mathématiques ? � Il suffit de deux étapes :
� Définir le cas de base uk pour un entier k (souvent 0 ou 1)
25
k
� Définir un pour n > k en supposant connu um pour m < n (souvent m = n-1 suffit)
� Le principe de récurrence permet alors d’affirmer que un
est bien définie pour tout n > k
Définition d'un prédicat récursif
� Dans le cas de la définition d’un prédicat récursif, il y a une difficulté supplémentaire : � l’entier n n’est pas toujours explicite
� On procédera donc en trois phases :
26
� On procédera donc en trois phases :
� Trouver un entier n associé au prédicat, qu’on appellera l’ordre de récurrence
� Définir le prédicat à l’ordre k (souvent 0 ou 1)
� Définir le prédicat à l’ordre n en le supposant connu pour les ordres inférieurs à n
Exemple : ancêtre
� Définition d’un prédicat ancetre(X,Aieul) pour la base de données généalogique :
� Choisir comme ordre de récurrence le nombre de générationsentre X et Aieul
27
entre X et Aieul
� À l’ordre1, un ancêtre est simplement un parent
� Un ancêtre de X à l’ordre n est le parent d’un ancêtre à l’ordre n-1
Exemple : ancêtre (suite)
� On traduit aisément cette définition en Prolog :
� ancetre(X, P) :- /* une génération entre X et P */
28
ancetre(X, P) :- /* une génération entre X et P */
parent(X, P).
� ancetre(X, Aieul) :- /* n générations entre X et Aieul */
parent(X, P) /* une génération entre X et P */
ancetre(P, Aieul). /* n-1 génération entre P et Aieul */
Exemple : ancêtre (suite)
� Il est à rappeler que Prolog lit les règles de gauche à droite. Si on écrit :
� ancetre(X, P) :-
parent(X, P).
29
parent(X, P).
� ancetre(X, Aieul) :- /* INCORRECT */
ancetre(P, Aieul), parent(X, P).
� On ne peut plus affirmer qu’il y a n-1 générations entre P et Aieul, puisque la résolution de parent(X,P) est faite après la résolution de ancetre(P, Aieul).
Exemple : chemin
� Sachant les liens suivants :� lien(a,b).
� lien(a,c).
� lien(c,d).
� lien(c,e).
lien(d,e).� lien(d,e).
� Chemin entre deux points� chemin(Z,Z).
� chemin(X,Y) :- lien(X,I), chemin(I,Y).
� Requête : est ce qu'il existe un chemin entre a et e ?� ?- chemin(a,e).
30
Unification
� Définition : � L'unification est le procédé par lequel on essaie de rendre � L'unification est le procédé par lequel on essaie de rendre
deux formules identiques en affectant des valeurs aux variables qu’elles contiennent
31
Unification (suite)
� Résultat : c’est un unificateur (ou substitution), un ensemble d’affectations de variables� Exemple :
� frere(X,Y) :- homme(X), enfant(X,Z), enfant(Y,Z), X=\=Y. � où =\= représente le prédicat de différence
� frere(patrick,qui) : tentative d’unification avec la tête de la clause � frere(patrick,qui) : tentative d’unification avec la tête de la clause frere(X,Y)
� Résultat : {X=patrick, Y=qui}
� Le résultat n’est pas forcément unique, mais représente l’unificateur le plus général
� L’unification peut réussir ou échouer� e(X,X) et e(2,3) ne peuvent être unifiés
32
Unification (suite)
� Prédicat d’unification : "="� a(B,C) = a(2,3). donne pour résultat :
� YES {B=2, C=3}
� a(X,Y,L) = a(Y,2,carole). donne pour résultat :� YES {X=2, Y=2, L=carole}
� a(X,X,Y) = a(Y,u,v). donne pour résultat :NO
33
Pas de démonstration
� Si l’unification échoue : � situation d'échec sur la règle considérée pour démontrer la
formule
� Si l’unification réussit : � substitution des variables présentes dans la queue de la clause
(le reste des relations de la classe) par les valeurs correspondantes des variables de l ’unificateur
34
Pas de démonstration (suite)
� Exemple :
frere(patrick,Qui) Unification avec frere(X,Y)
X=patrick et qui=Y
homme(patrick)enfant(patrick,Z)
enfant(qui,Z)patrick=\=qui
X=patrick et qui=Y
35
Listes en Prolog
� Liste vide : � [].
� Liste non vide : � Liste non vide : � Une suite finie d’éléments (constantes, variables, nombres,
listes, ...)
� Exemples :� [a, A, B, C, D]
� [p(A,V), p(a, V)]
36
Listes en Prolog (suite)
� Une liste non vide est constituée d’un élément, appelé tête, et d’une liste appelée reste (qui est exactement la liste moins la tête)tête)
� En Prolog, on peut écrire une telle liste :� [Tete | Reste]
37
Listes en Prolog (suite)
� Pour y voir plus clair, testons directement des unifications de listes :
� ?- [X,2,3] = [1,Y,Z].� {X = 1, Y = 2, Z = 3}
38
� {X = 1, Y = 2, Z = 3}
� ?- [X|Y] = [1,2,3].� X = 1, Y = [2,3]
� ?- [1,[2,X],Y] = [X|[[Y,1],2]].� X = 1, Y = 2
Listes en Prolog (suite)
� Exemple de prédicat avec les listes
� Retrouver le premier élément d'une liste : � premier_de_liste(L, X) est vrai si X est le premier élément de L� premier_de_liste(L, X) est vrai si X est le premier élément de L
� Solution :
� premier_de_liste([X|_],X).
39
Listes en Prolog (suite)
� Exemple de prédicat avec les listes
� Afficher le premier élément d'une liste : � premier_de_liste2(L) est vrai si le premier élément de la liste L est � premier_de_liste2(L) est vrai si le premier élément de la liste L est
affiché (et aucun autre).
� Solution :
� premier_de_liste2([X|_]) :- write(X), nl.
40
write(X) : afficher Xnl : saut de ligne
Quelques prédicats utiles
� Comment exprimer qu'on veut calculer la somme de deux nombres ?
� somme(X,Y,S) :- S is X+Y.
� Requête :� ?- somme(10, 34, S).
� Résultat :� Yes
� S = 44
41
Quelques prédicats utiles (suite)
� Trouver la factorielle d'un nombre. (Où : fact(N,X) est vrai si X vaut N!.)
� fact(0,1). � fact(0,1).
� fact(N,X) :-
N>0,
N1 is N-1,
fact(N1,X1),
X is N*X1.
42
Quelques propriétés
� la recherche réalisée par Prolog est une recherche en profondeur d’abord
� On peut obtenir plusieurs solutions pour une même requête
Le langage
requête� On appelle cela le non-déterminisme de Prolog
� Les seuls résultats possibles : yes ou no� Pas de fonction, les réponses sont obtenues par unification
uniquement
43