Cours de PROLOG

Cours de PROLOG, tutoriel & guide de travaux pratiques en pdf.

Le langage Prolog pur

Les structures :

Prolog permet de représenter des objets contenant des informations, par une seule entité du langage, les structures, cette entité contenant toutes ces informations.
Ainsi, la date du 21 mai 1982 peut se représenter par la structure : date(21,mai,1982).
Le nom de la structure est date, ces arguments sont des valeurs du jour, du mois, de l’année ; la syntaxe des noms de structures est celle des atomes.
L’accès aux composantes de la structure date (jour, mois, année) peut se faire à l’aide des faits suivants :
jour(date(X,Y,Z),X).
mois(date(X,Y,Z),Y).
annee(date(X,Y,Z),Z).
En général, l’accès aux composantes d’une structure ne nécessite pas l’usage de faits et se fait le plus souvent de manière implicite.
Le livre « Les mots » de Jean-Paul Sartre, peut se représenter par la structure livre(les_mots,jean_paul,sartre)
Le livre est perçu comme un objet à trois composantes : un titre, le nom et le prénom de l’auteur.
Une autre représentation possible est la structure
livre(les_mots,auteur(jean_paul,sartre))
Ici, un livre est perçu comme une structure à deux arguments, un titre et un auteur ; un auteur est une structure à deux arguments, un prénom et un nom.
Donc, les arguments d’une structure peuvent être des structures.
Dans Prolog pur, on dispose de trois moyens pour représenter des objets : des noms d’objets dont la syntaxe est celle des atomes ou des entiers, des noms de variables et des structures.
On appelle termes ces différents éléments du langage.

Définition des termes :

a) tout nom d’objet (atome, entier) est un terme.
b) toute variable est un terme.
c) Si s est un nom de structure à n arguments (n>=1), et si t1, t2, …, tn sont des termes, alors s(t1, t2, …, tn) est un terme.
La définition des termes est récursive. Les termes de type c) sont des structures. Un nom de structure a la syntaxe d’un atome.
Exemples :
Soit f est un nom de structure à deux arguments, alors jean, paul, X sont des termes d’après a) et b).
f(jean, paul), f(jean, X) sont des termes d’après c).
f(f(jean,paul),jean), f(f(jean,X),f(jean, paul)) sont aussi des termes d’après c).
Le nombre d’arguments d’une structure est l’arité de la structure.

Définition du langage Prolog pur :

a) Une formule atomique ou fait est une expression de la forme r(t1,t2, …, tn), ou r est un nom de prédicat d’arité n (n>=1) et les ti (1<=i<=n) sont des termes.
Si n=0, une formule atomique est un nom de proposition.
b) Une clause est une expression de la forme :
A. ou A:-B1, B2, …, Bn. (n>=1), où les Bi et A sont des formules atomiques.
Le Prolog pur ne se différencie du langage du chapitre 1 que par la définition des arguments possibles d’une relation ; ces arguments sont les termes, qui comprennent outre les noms d’objets et de variables, les structures.
Quoique la syntaxe des structures soit celle des formules atomiques, nous avons affaire à deux concepts très différents.
Une formule atomique est une relation entre des objets ; on peut parler de sa valeur de vérité, vraie ou fausse, contrairement aux structures qui elles représentent des objets.
La distinction entre les formules atomiques et les structures se fait en utilisant le contexte.
Par exemple, soit la clause : p(X,Y) :-h(X,v(X,Y)).
p(X,Y) est une formule atomique et non une structure, car c’est la conclusion d’une clause. De même h(X,v(X,Y)) est une formule atomique, car c’est la prémisse d’une clause ; v(X,Y) étant un argument de la formule atomique h(X,v(X,Y)), est une structure : en effet, une formule atomique ne peut être un argument d’une autre formule atomique.
On peut de la même manière faire la distinction entre :
a) un atome servant à nommer un objet.
b) un atome servant à nommer une relation.
c) un atome servant à nommer une structure.
Ex : a:-b(c,d(e,f)),h.
utilise les atomes a, b, c, d, e, f et h.
a et h sont des formules atomiques, donc des noms de propositions, b est un nom de relation binaire, c, e et f sont des noms de d’objets et d est un nom de structure d’arité 2.
Toutes les définitions du chap.1 (sémantique d’un programme, réponses correctes aux questions, etc…) restent valables dans le cas de Prolog pur.

Exemples de structures.

On se propose d’écrire un programme permettant de donner des informations sur un ensemble de cours. Chaque cours est caractérisé par sa matière, par le nom et prénom d’enseignant, par son horaire et la salle où le cours a lieu.
On a donc un ensemble d’assertions telles que : « le cours d’intelligence artificielle » est fait par Paul Durand et il a lieu les lundis de 9 à 11 dans le bâtiment Ampère, salle D », à représenter.
Voici 2 représentations possibles d’une telle assertion :
1) existe_cours(ia,paul,durand,lundi,9,11,ampere,d).
2) existe_cours(ia,enseignant(paul,durand),horaire(lundi,9,11),local(ampere,d)).
La deuxième est meilleure.
Prenons un ensemble de faits :
existe_cours(ia,enseignant(paul,durand),horaire(lundi,9,11),local(ampere,d)).
existe_cours(algo,enseignant(jean,dupont),horaire(mercredi,1,12),local(cochy,a)).
…
Cet ensemble de faits peut être perçu comme une base de données.
Voici quelques exemples de questions possibles :
Qui enseigne le cours d’IA ?
?-existe_cours(ia,Enseignant,Horaire,Local).
Enseignant=enseignant(paul,durand)
Horaire=horaire(lundi,9,11)
Local=local(ampere,d)
yes
Quels sont les jours où Paul Durand enseigne ?
?-existe_cours(Cours,enseignant(paul,durand),horaire(Jour,Hd,Hf),Local).
Cour=ia
Jour=lundi
Hd=9
Hf=11
Local=local(ampere,d)
yes
Les réponses aux questions ci- dessus contiennent l’information désirée, mais aussi des informations supplémentaires. Si on ne désire pas ces dernières, on peut poser les questions en utilisant des variables anonymes :
?-existe_cours(ia,Enseignant,_,_).
Enseignant=enseignant(paul,durand)
yes
?- existe_cours(_,enseignant(paul,durand),horaire(Jour,_,_),_).
Jour=lundi
yes
En général, on utilise des variables anonymes dans une clause, lorsqu’une variable a une seule occurrence dans la clause et qu’on ne s’intéresse pas à l’instanciation de cette variable.
Les entiers naturels sont habituellement nommés 0, 1, 2, …
La classe des entiers admet une construction récursive : un entier est l’entier 0 ou le successeur d’un entier.
Soit s un successeur, alors 0, s(0), s(s(0)), … représentent la suite des entiers.
Le prédicat entier(X) est vrai si l’objet X est un entier.
Définir ce prédicat revient à dire à quelle condition un objet X est un entier.
Un objet est un entier s’il est successeur d’un entier ou s’il est 0.
entier(0).
entier(s(Y)):-entier(Y).
A la question, quels sont les entiers naturels :
?-entier(X).
X=0
yes
X=s(0)
yes
X=s(s(0))
yes
etc…
Comme il y a une infinité des réponses possibles, Prolog les fournit. Le programmeur est obligé d’interrompre l’exécution du programme.
On peut définir l’addition de façon récursive :
voici la définition du prédicat(X,Y,Z) (X+Y=Z)
plus(0,Y,Y).
plus(s(X),Y,s(Z)):-plus(X,Y,Z).
?-plus(s(s(0)),s(0),X).
X=s(s(s(0))).

Représentation graphique des structures et des formules atomiques :

Une formule atomique r(t1,t2,…,tn) (respectivement une structure s(t1,t2,…,tn)) est représentée graphiquement par un arbre de racine r (respectivement s) ; les sous-arbres de la racine sont les représentations graphiques des termes t1, t2, …, tn.
Du point de vue syntaxique, il n’y a pas de différence entre les formules atomiques et les structures ; d’ailleurs, dans la terminologie usuelle Prolog, les formules atomiques sont qualifiées de termes. Cette terminologie est regrettable, car un terme représente un objet alors qu’une formule atomique est une relation entre des objets, ayant une valeur de vérité vraie ou fausse.
Un autre abus de langage que l’on fait consiste à identifier les concepts de noms de structure et de noms de relations avec leur syntaxe, c.à.d, des atomes.
Avec cette terminologie, le langage Prolog pur se définit comme suit :

Définition des termes :

a) Un atome ou un entier est un terme.
b) Une variable est un terme.
c) Si s est un atome et si t1, t2, …, tn sont des termes, alors s(t1,t2,…, tn) est un terme.
Les termes c) sont dit structures (ces structures recouvrent ce que nous avons appelé structures ainsi que les formules atomiques).
Une clause est une expression de la forme :
A. ou A :- B1, B2, …, Bn. (n>0) où A et les Bi sont des atomes ou des structures.

Les listes :

Une liste est une suite ordonnée de termes ; ces termes sont les éléments de la liste. Un cas particulier : la liste vide.
Ex :
L1=[]
L2 = [[]]
L3 = [jean,[paul,[pierre,eric]]]
L4 = [toto,titi]
La tête d’une liste non vide est le premier élément de la liste.
Ex :
[[a,b],c,d] : [a,b]
[X]:X
La queue d’une liste non vide est la liste obtenue en supprimant le premier élément de la liste.
La queue d’une liste est toujours une liste.
Ex :
[[a,b],c,d] : [c,d]
[X] : []

Notation [X|Xs] des listes :

Une liste non vide est caractérisée par sa tête et sa queue. Le terme [X|Xs] représente une liste de tête X et de queue Xs.
Donc, [a,b,c,d]=[a|[b,c,d]]

Définition d’une liste :

liste([]).
liste([X|Xs]:-liste(Xs).
Les listes non vides sont des structures.
La syntaxe des listes non vides ne respecte pas la définition des termes Prolog. Cependant, de manière interne à l’interprète, les listes non vides sont des structures.
Une liste [X|Xs] est équivalente de point de vue logique à une structure d’arité 2 avec le premier argument X et le deuxième Xs et le nom ‘.'(un objet à deux composantes – sa tête et sa queue). ‘.'(X,Xs).
Pour obtenir une représentation graphique d’une liste il faut l’écrire sous forme de structure.

Traitement de listes :

Comme nous disposons d’une représentation des listes ([X|Xs]) de nature récursive, on peut programmer de manière récursive les relations sur les listes.
• La relation élément :
element(X,Xs) qui signifie que X est un élément de Xs.
Formulation : X est élément de [Y|Ys] si X est le premier élément de la liste, soit X=Y, ou si X est élément de la queue de la liste, soit element(X,Ys).
Cette connaissance peut s’exprimer par les clauses :
element(X,[X|Xs]).
element(X,[Y|Xs]):-element(X,Xs).
Question : element(a,[b,d,a]).
yes
• Concaténation :
concatener([],Xs,Xs).
concatener([X|Xs],Ys,[X|Zs]) :-concatener(Xs,Ys,Zs).
• Le dernier élément :
dernier([X],X).
dernier([X,Y|Zs],T) :- dernier([Y|Zs],T).
• Inverser la liste :
inverse([],[]).
inverse([X|Xs],Zs):-inverse(Xs,Ys),concatener(Ys,[X],Zs).
concatener([],Xs,Xs).
concatener([X|Xs],Ys,[X|Zs]) :-concatener(Xs,Ys,Zs).
• Longueur de liste
longueur([],0).
longueur([X|Xs],s(N)):-longueur(Xs,N).
• Suppression de la liste :
Le programme suivant définit la relation supprimer(X,Xs,Ys), où Ys est la liste obtenue à partir de Xs en supprimant toutes les occurrences de X dans Xs.
supprimer(X,[],[]).
supprimer(X,[X|Xs],Ys):-supprimer(X,Xs,Ys).
supprimer(X,[Y|Ys],[Y|Zs]):-differents(X,Y),supprimer(X,Ys,Zs).

Chap.1 Un sous-ensemble de Prolog : les clauses de Horn sans symbole de fonction
1. Un premier programme Prolog
2. Chargement d’un programme
3. Utilisation d’un programme : les questions (on dit aussi résolution d’un but)
• Questions ou buts simples
• Questions composées
4. Les faits
5. Les variables :
6. Les formules atomiques
7. Les règles
8. Les questions
• Les réponses correctes aux questions simples et closes
• Questions simples non closes
• Questions ou buts composés
9. Les règles récursives
10. Sémantique d’un programme
Chap.2 Le langage Prolog pur
1. Les structures
2. Définition des termes
3. Définition du langage Prolog pur
4. Exemples de structures
5. Représentation graphique des structures et des formules atomiques
6. Définition des termes
7. Les listes
8. Notation [X|Xs] des listes
9. Définition d’une liste
10. Traitement de listes
Chap.3 Sémantique opérationnelle de Prolog pur
1. Importance
2. Interprétation procédurale des clauses, unification
3. Interprétation procédurale de la clause
4. Une autre façon de voir les choses
5. Exemples :
6. Recherche des preuves : le retour-arrière
7. Algorithme d’unification
8. Théorème
9. Les preuves Prolog
10. Théorème :
11. Un algorithme non déterministe de recherche des preuves
12. Le retour-arrière
13. Arbre Prolog d’un but
14. Résumé
15. Semi-décidabilité
16. Réponses d’un interprète Prolog à une question (profondeur d’abord)
Chap.4 Arithmétique et Syntaxe Prolog
1. Les opérateurs
2. Les opérateurs prédéfinis
3. Arithmétique
4. Exemples
5. Exemples de programmes
6. Egalité et inégalité
Chap.5 Contrôler le retour-arrière : la coupure
1. Introduction
2. Sémantique de la coupure
3. Déterminisme et modes d’utilisation d’une relation
4. La négation par l’échec
Chap.6 Les prédicats extra-logiques
1. Prédicats d’écriture
2. Prédicats de lecture
3. Les prédicats prédéfinis « repeat » et « fail »
4. Construction et accès aux arguments d’une structure
5. Le prédicat « call »
6. Exemple sur la base de données
Chap.7 Les fichiers
1. Introduction
2. Re-direction temporaire
Chap.8 Applications
1. Analyser un langage rationnel
2. Les problèmes à transition d’états
• Problème typique