19-03-2009, 07:09 PM
  #1
monarque
VIP_MEMBRE
   monarque
 
: 01-12-2008
:
: 1,237
monarque   monarque   monarque   monarque   monarque   monarque   monarque   monarque   monarque
11 Petite prsentation de PROLOG


Petite prsentation de PROLOG

0) prsentation

Prolog est un langage extraordinaire, pas tant par ses possibilits effectives, mais parce qu'il nous montre qu'il peut exister d'autres moyens de programmer un ordinateur. Prolog (PROgrammation LOGique) est n en France (Marseille) et a servi de base aux programmes de recherche japonais sur les ordinateurs de 5me gnration. Ce qui est phnomnal, c'est qu'en Prolog, il nous suffit de dcrire ce que l'on sait sur le domaine tudi, en vrac, dans l'ordre o a nous vient (en Intelligence Artificielle, on appelle cela une base de connaissances). Puis on dcrit notre problme, Prolog va nous le rsoudre, sans qu'on n'ait lui dire comment faire !

Ce petit cours ne va pas dtailler parfaitement tout le langage, il n'est prvu que pour vous montrer (progressivement) les possibilits de Prolog, et donc des possibilits de programmation qu'aucun langage classique n'aurait pu vous faire imaginer.

Vous cherchez un Prolog ? je vous conseille SWI Prolog (sous Linux ou windows), disponible gratuitement (licence GPL) au dpartement informatique de l'Universit de Psychologie d'Amsterdam (http://www.swi-prolog.org/ ou http://www.swi.psy.uva.nl/projects/SWI-Prolog/). Il y a galement visual prolog, disponible en version commerciale mais aussi gratuite pour un usage priv (mais je ne l'ai pas test, c'est sous Windows). Et il en existe d'autres, en particulier GNU-Prolog (par l'INRIA).

D'autres liens sur Prolog ? testez la WWW Virtual Library (en anglais)



Remarquejanvier 2004 : j'ai l'impression que la dernire version de SWI Prolog ne gre plus le not, il faut utiliser \+
1) rgles sur constantes et variables symboliques

Le "programme" se compose d'un ensemble de rgles (sous la forme : conclusion IF conditions) et de faits (en gnral des affirmations : on prcise ce qui est vrai, tout ce qui n'est pas prcis est faux ou inconnu).

Le langage gre des variables simples (entiers, rels,...) et des listes (mais pas les tableaux).

Les variables simples sont les entiers, les rels, les chanes de caractres (entre " ") et les constantes symboliques (chanes sans espace ni caractres spciaux, commenant par une minuscule, mais ne ncessitant pas de ")

Les noms de variables commencent obligatoirement par une majuscule (contrairement aux constantes symboliques), puis comme dans les autres langages est suivi de lettres, chiffres, et _ . Un variable "contenant" une valeur est dite "lie" ou "instancie", une variable de valeur inconnue est dite "libre".

Exemple de programme simple :
est_un_homme(marc). /* l'argument est pour moi le sujet */
est_un_homme(jean).
est_le_mari_de(marc,anne)./* 1er arg: sujet, puis complment */
est_le_pre_de(marc,jean).

est_un_homme est un "prdicat". Il sera soit vrai, soit faux, soit inconnu. Dans le "programme", toutes les rgles concernant le mme prdicat doivent tre regroupes ensemble.

Pour excuter ce programme sous SWI-Prolog, il suffit de l'enregistrer dans un fichier texte (nomfic.pl), puis d'appeler pl, charger le fichier par "consult(nomfic)." (n'oubliez pas le .).

On peut alors "excuter" le programme, en fait on fait une requte :
?- est_un_homme(marc).
Yes
?- est_un_homme(anne).
No
?- est_un_homme(luc).
No

Prolog cherche prouver que le but (goal) demand est vrai. Pour cela, il analyse les rgles, et considre comme faux tout ce qu'il n'a pas pu prouver. Quand le but contient une variable libre, Prolog la liera toutes les possibilits :
?- est_un_homme(X).
X=marc (entrez ; pour demander la solution suivante)
X=jean
?- est_le_pere_de(Pere,jean).
Pere=marc
?- est_le_mari(Pere,Mere), est_le_pere_de(Pere,jean).
Pere=marc, Mere=anne

On peut combiner les buts l'aide des oprations logiques et (,) , ou (;) et non (not). Le but dfini ci-dessus nous permet de trouver la mre de jean. Mais on peut galement crer une rgle en rajoutant :
est_la_mere_de(Mere,Enfant) :-
est_le_mari(Pere,Mere),
est_le_pere_de(Pere,Enfant).



Dsormais le but : est_la_mere_de(Mere,jean) (rponse : Mere=anne) permet de rechercher la mre d'un individu, mais la mme rgle permet de rpondre galement une recherche d'enfants : est_la_mere_de(anne,X) (rponse : X=jean). On peut aussi vrifier une affirmation (est_la_mere_de(anne,jean)) ou afficher tous les couples de solutions la requte : est_la_mere_de(M,X). On ne trouvera ici qu'une solution, pour vritablement tester ceci il faut augmenter notre base de connaissances. Le comportement de Prolog est donc diffrent suivant que les variables soient lies (il cherche alors prouver la vracit) ou libres (il essaie alors de les lier des valeurs plausibles). Ceci dmontre une diffrence capitale entre un langage dclaratif (on dit simplement ce que l'on sait) et les langages procduraux classiques (on doit dire comment l'ordinateur doit faire, en prvoyant tous les cas).

Exercice : complter les donnes pour respecter :




On dfinira galement les rgles dfinissant : est_le_fils, est_la_fille, est_la_belle_mere,....

Pour effectuer un ou, on peut utiliser le OU (;) ou utiliser plusieurs rgles:
est_la_belle_mere_de(BelleMere ,Gendre) :-
est_le_mari_de(Gendre,Epouse),
est_la_mere_de(BelleMere,Epous e). /*Belle-mre d'un homme*/
est_la_belle_mere_de(BelleMere ,Bru) :-
est_le_mari_de(Epoux,Bru),
est_la_mere_de(BelleMere,Epoux ). /*Belle-mre d'une femme*/

On peut galement dfinir les femmes par :
est_une_femme(F) :- not(est_un_homme(F)).

Cette rgle marche pour des variables lies (dira Yes s'il ne l'a pas trouv parmi les hommes) mais pas pour une variable libre (en effet, toute combinaison de caractres pourrait rpondre la requte). Pour qu'une rgle puisse s'appliquer une variable libre, il faut que l'on permette Prolog de trouver toutes les possibilits (et donc qu'elles soient en nombre limit). Exemple:
est_une_femme(F) :-
est_le_pere_de(_,F), /* _ est le nom (impos) d'une variable
dont la valeur ne nous intresse pas, Prolog n'a
donc pas besoin de la lier */
not (est_un_homme(F)).

Ici, on cherche recherche d'abord ceux et celles qui ont un pre, puis on limine les hommes. On peut remarquer qu'anne et betty ne seront pas considres comme femme. Il suffit pour rsoudre ce problme de rajouter une seconde rgle, traitant des pouses. Mais pour qu'il ne nous affiche pas deux fois celles qui sont la fois pouses et filles, on pourra l'crire ainsi :
est_une_femme(F) :-
est_le_mari_de(_,F)
and not (est_un_homme(F))
and not (est_le_pere_de(_,F)) /* pour ne pas reprendre les cas
traits par la rgle prcdente */

le but : est_une_femme(X) nous donne maintenant toutes les femmes que nous avons dfinies.

Exercice : rajouter tantes, cousins, grand mres...

Pour simplifier la gestion des hommes par exemple, on peut utiliser une liste (voir dtails plus loin) :
hommes([marc, luc, jean, jules, lon, loic, gerard, herv, jacques, paul]).
appartient_(X,[X|_]).
appartient_(X,[_|Queue]) :- appartient_(X,Queue).
est_un_homme(X) :-
hommes(Liste),
appartient_(X,Liste).

J'ai cr une petite base, pour mes tests. Vous pouvez la voir (et sauvegarder) ici.
2) variables numriques

En Prolog, l'criture : X=Y peut avoir diffrents rsultats :
Si X et Y lies, rpondra Yes si elles sont gales, No sinon.
Si X libre et Y li, proposera comme solution X valant la valeur de Y.
Si X li et Y libre, proposera comme solution Y valant la valeur de X.
Si X et Y libres, erreur (car infinit de solutions)

Par contre l'criture X=Y+1 (qui est quivalent Y+1=X) va poser quelques problmes. Il est tout d'abord obligatoire, dans cette criture, qu'Y soit li (Prolog ne sait pas inverser une quation, qu'elle soit simple comme ici ou plus complique). Mais ce n'est pas tout : = va simplement recopier l'quation (en ayant instanci les variables) : Y=23,X=Y+1,write(X). affichera 23+1, et pas 24. C'est pourquoi deux autres oprateurs sont dfinis :
is calcule (on dit aussi "value") la valeur droite (toujours lie) et instancie le rsultat la variable (libre) gauche, ou la compare la valeur lie de gauche. Par exemple X is 10+15 met 25 dans X, ou dit Yes si X vaut 25 (parce que avant on a dit X is 30-5 ou mme X=25). Certains Prolog utilisent aussi l'oprateur :=
=:= value les expressions droite et gauche et regarde si les rsultats sont gaux (les deux arguments doivent tre lis)

exemple : crire un programme qui pour un but "affiche(10)." affiche les nombres de 10 0 : (on utilise le prdicat prdfini write) :
affiche(X) :-
write(X), write(' '),
X>0, /* condition de fin */
Y is X-1,
affiche(Y).

Rq1 : il faut obligatoirement utiliser une variable intermdiaire (Y ici).
Rq2 : videment, l je triche quand mme : c'est plus procdural que dclaratif.

Exo : afficher dsormais dans l'ordre croissant .
Truc : il suffit d'inverser l'ordre des instructions, mais il rpond false (comme d'ailleurs aussi dans le cas prcdent) mais avant les affichages. Il suffit de donner le fait : affiche(0).

Pour les autres comparaisons, les oprateurs (qui valuent droite et gauche) sont : =:= =\= (diffrent) < > =< >= , les oprateurs arithmtiques : + - * / mod ** , sin, cos, log,....
3) exercices amusants

chaque lettre reprsente un chiffre et un seul. Trouver la ou les solutions :
MOT
FORTY
NEUF

+ MOT
+ TEN
+ UN
UNE
CHIEN

+ MOT
+ TEN
+ UN
+ UNE
+ CHASSE

= BLA
= SIXTY
= ONZE
=DEUX
= GIBIER


proposition de solution (la plus simple possible), pour le premier :
/* je dcris l'ensemble des possibilits envisageables */
chiffre(0).
chiffre(1).
chiffre(2).
chiffre(3).
chiffre(4).
chiffre(5).
chiffre(6).
chiffre(7).
chiffre(8).
chiffre(9).

/* je dis ce que je veux */
solution([M,O,T,B,L,A]) if
chiffre(M),M=\=0,
chiffre(O),O=\=M,
chiffre(T),T=\=O,T=\=M,
chiffre(B),B=\=0,B=\=T,B=\=O,B =\=M,
chiffre(L),L=\=B,L=\=T,L=\=O,L =\=M,
chiffre(A),A=\=L,A=\=B,A=\=T,A =\=O,A=\=M,
3*(M*100+O*10+T)=:=B*100+L*10+ A.

Remarque (importante) : on dtaille ici exactement et prcisment ce que l'on veut (le "quoi"), mais on ne donne aucune indication sur la mthode de rsolution du problme, pas d'algorithme (le "comment"), on laisse Prolog se dbrouiller.

On peut videment se faciliter la description de ce type de problmes en prparant quelques rgles (en utilisant en particulier les listes), entre autres un prdicat "tous diffrents". Je vous donne ici ma proposition. Attention, certains de ces problmes comportent un trs grand nombre de solutions !
4) listes

En prolog, il n'y a pas possibilit d'utiliser de tableaux (par exemple pour accder directement la 50me valeur). Par contre, il est trs facile de les remplacer par des listes. L'avantage des listes est que leur longueur est dynamique. Leur utilisation est rcursive (on ne peut accder la 50me qu'aprs avoir accd aux 49 prcdentes).

Une liste constante est reprsente entre crochets ([ ] signifiant ensemble vide) :
equipe(ulp,[jean,lucie,yves,anne,alain,jul ie,marc,luc]).
equipe(ushs,[jo,cathy,ahmed,louis,paul,eve, marie,rose]).

Lorsque l'on reprsente une liste par une variable, deux critures sont possibles : soit par un nom de variable (commenant par une majuscule), soit par [Tete|Queue], o Tete (du type lment) est le premier de la liste, et Queue (de type liste d'lments) le reste de la liste.

exemple :
afficher([T|Q]) :-
writeln(T),nl,
afficher(Q).
afficher([]).

essayez le but afficher([jean,jacques,jules]).

autre exemple, trs utile :
appartient_(X,[X|_]).
appartient_(X,[_|Queue]) :- appartient_(X,Queue).

Les listes peuvent servir reprsenter des ensembles (les lments appartiennent ou non diffrents ensembles, que l'on peut combiner par l'union ou l'intersection), mais aussi tre ordonne (et entre autres pourront tre tries). Je vous propose ici un certain nombre de rgles pour tester les listes.
5)Utilisation de SWI PROLOG

SWI Prolog (sous Linux ou windows) est disponible gratuitement (licence GPL) dpartement informatique de l'Universit de Psychologie d'Amsterdam (http://www.swi-prolog.org/ ou http://www.swi.psy.uva.nl/projects/SWI-Prolog/). J'ai not ci-dessous quelques unes de mes remarques sur son utilisation.

On peut tester un programme en l'interprtant interactivement, soit en le compilant au pralable.
Solution interactive : appeler pl, puis donner comme but : consult(nomfic). Ne pas oublier le point, il est inutile d'ajouter le .pl qui est ajout par dfaut au nom du fichier.
Solution compile : je cre mon programme (xxx.pl) et je le compile par pl -o xxx -c xxx.pl (-c en dernier !). Puis j'appelle xxx, il me propose de donner des buts (je dois les terminer par .), je quitte par halt. (le point compris !) ou CTRL D.

pour l'aide (doc en ligne) :
help. : toute l'aide
help(1). : intro gnrale Rq : voir www.swi.psy.uva.nl/projects/xcpe
help(2). : options de ligne de commande, historique, mode trace/spy (2-6), compilation et options (2-7) ,caractres spciaux (2-12)
help(3). : tous les prdicats prdfinis, les types (3-4), comparaisons (3-5) fail et ! (3-6) assert (3-10) fichiers (3-13) E/S sur cran (3-15) string (3-19) oprateurs (3-20) arithmtique (3-21) listes (3-24) write (3-30) shell commands (3-32) fichiers (3-33), commandes break, trace, debug (3-34) appels DDE windows (3-40)
help(4). : les modules (pas encore lu)
help(5). : interface C
help(6). : runtime
help(7). : spcial hackers (donc pas pour moi)
help(8). : index de TOUS les mots dfinis avec quelques mots d'explication


Pour dboguer, on utilise le mode trace : au goal je donne : trace,ma_question(MesParametre s). A chaque pas on appuie sur entre (h pour l'aide des autres options). voir help(2-6).
listing. rcrit les rgles l'cran, ou listing(predicat). pour toutes celles limites un prdicat.

Petites particularits SWI Prolog :

Pour les chanes de caractres, les mettre entre simples cotes (elles seront affiches par write et writef). Entre doubles cotes elles sont transformes en listes d'entiers (d'aprs les codes ascii). Elles seront affiches en liste d'entiers par write mais en chaine de caractres par writef. Entre " elles peuvent tre traites comme toute autre liste.

Comment lui demander TOUTES les solutions : taper ; aprs chaque rponse au lieu de <CR>.
Un tel but le fait aussi :
affiche :- homme(X),write('Homme : '),write(X),nl,fail.
On peut peut-tre aussi utiliser findall ou bagof : voir help(3-27). Le but bagof(X,pere(X),ListeDeTousLes Peres). cre la liste de tous les X vrifiant pere(X) (X et ListeDeTousLesPeres sont normalement libres). bagof(X,pere(P,X),Enfants) donne dans Enfants la liste des enfants de P si P li, ou tous les couples P,Enfants si P libre, alors que bagof(X,P^pere(P,X),Y) met dans une seule liste Y tous les enfants existants (^ signifie "tel que"). setof est comme bagof mais trie les rponses par ordre alpha et vire les doublons.
6) utilisation de TURBO PROLOG

Nous disposons galement d'une vielle version de TURBO PROLOG (sous DOS), qui ncessite de dclarer l'avance les prdicats. La section predicates correspond aux dclarations, la section clauses correspond la base de faits et aux rgles. Le premier programme devient donc :
predicates /* on ne souligne videment pas */
est_un_homme(symbol) /* forme : nom(type des arguments : symbol, integer, real ou string) */
est_le_pere_de(symbol,symbol)
est_le_mari_de(symbol,symbol)
clauses
est_un_homme(marc)./* l'argument est pour moi le sujet */
est_un_homme(jean).
est_le_mari_de(marc,anne)./*1er arg: sujet, puis complment */
est_le_pre_de(marc,jean).

Les listes sont dclares dans une section nomme "domains". le :- peut tre not if, la virgule par and :
domains
liste=symbol*
predicates
hommes(liste)
appartient_(symbol,liste)
est_un_homme(symbol)
clauses
hommes([marc, luc, jean, jules, lon, loic, gerard, herv, jacques, paul]).
appartient_(X,[X|_]).
appartient_(X,[_|Queue]) if appartient_(X,Queue).
est_un_homme(X) if
hommes(Liste)
and appartient_(X,Liste).

Pour les variables numriques, Turbo Prolog accepte le signe = pour tous les cas d'galit (instanciation, valuation, comparaison, donc les oprateurs =, is et =:=).

L'exemple "MOT+MOT+MOT=BLA" s'crit en Turbo Prolog :
domains
liste=integer*
predicates
chiffres(liste)
appartient_(integer,liste)
est_une_possibilit(integer)
solution(integer,integer,integ er,integer,integer,integer)
clauses
chiffres([0,1,2,3,4,5,6,7,8,9]).
appartient_(X,[X|_]).
appartient_(X,[_|Queue]) if appartient_(X,Queue).
est_une_possibilit(X) if
chiffres(Liste)
and appartient_(X,Liste).
solution([M,O,T,B,L,A]) if
est_une_possibilit(M),M<>0,
est_une_possibilit(O),O<>M,
est_une_possibilit(T),T<>O,T< >M,
est_une_possibilit(B),B<>0,B< >T,B<>O,B<>M,
est_une_possibilit(L),L<>B,L< >T,L<>O,L<>M,
est_une_possibilit(A),A<>L,A< >B,A<>T,A<>O,A<>M,
3*(M*100+O*10+T)=B*100+L*10+A.


__________________
L'accs est mieux que la paresse

...
monarque    

« | »



exercices corriges prolog 102 10 11-12-2015 02:08 PM
programmation logique en prolog * 10 23-12-2013 04:56 PM
prolog 16 01-11-2012 03:04 PM
Prsentation de lIRM para 22 04-07-2012 12:10 PM
Compilateurs PROLOG 3 lmd achraf.mouni 13 27-12-2008 01:29 PM


10:02 AM.
Powered by vBulletin® Copyright ©2000 - 2018, Jelsoft Enterprises Ltd. , TranZ By Almuhajir