Prolog est un langage extraordinaire, pas tant par ses possibilités 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 5ème génération. Ce qui est phénoménal, c'est qu'en Prolog, il nous suffit de décrire 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 décrit notre problème, Prolog va nous le résoudre, sans qu'on n'ait à lui dire comment faire !
Ce petit cours ne va pas détailler parfaitement tout le langage, il n'est prévu que pour vous montrer (progressivement) les possibilités de Prolog, et donc des possibilités 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 département 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).
Remarquejanvier 2004 : j'ai l'impression que la dernière version de SWI Prolog ne gère plus le not, il faut utiliser \+
Le "programme" se compose d'un ensemble de règles (sous la forme : conclusion IF conditions) et de faits (en général des affirmations : on précise ce qui est vrai, tout ce qui n'est pas précisé est faux ou inconnu).
Le langage gère des variables simples (entiers, réels,...) et des listes (mais pas les tableaux).
Les variables simples sont les entiers, les réels, les chaînes de caractères (entre " ") et les constantes symboliques (chaînes sans espace ni caractères spéciaux, commençant par une minuscule, mais ne nécessitant 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 "liée" ou "instanciée", 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 complément */ est_le_père_de(marc,jean).
est_un_homme est un "prédicat". Il sera soit vrai, soit faux, soit inconnu. Dans le "programme", toutes les règles concernant le même prédicat doivent être regroupées ensemble.
Pour exécuter 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 "exécuter" le programme, en fait on fait une requête :
?- 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 règles, et considère comme faux tout ce qu'il n'a pas pu prouver. Quand le but contient une variable libre, Prolog la liera à toutes les possibilités :
?- 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 opérations logiques et (,) , ou (;) et non (not). Le but défini ci-dessus nous permet de trouver la mère de jean. Mais on peut également créer une règle en rajoutant :
est_la_mere_de(Mere,Enfant) :-
est_le_mari(Pere,Mere),
est_le_pere_de(Pere,Enfant).
Désormais le but : est_la_mere_de(Mere,jean) (réponse : Mere=anne) permet de rechercher la mère d'un individu, mais la même règle permet de répondre également à une recherche d'enfants : est_la_mere_de(anne,X) (réponse : X=jean). On peut aussi vérifier une affirmation (est_la_mere_de(anne,jean)) ou afficher tous les couples de solutions à la requête : est_la_mere_de(M,X). On ne trouvera ici qu'une solution, pour véritablement tester ceci il faut augmenter notre base de connaissances. Le comportement de Prolog est donc différent suivant que les variables soient liées (il cherche alors à prouver la véracité) ou libres (il essaie alors de les lier à des valeurs plausibles). Ceci démontre une différence capitale entre un langage déclaratif (on dit simplement ce que l'on sait) et les langages procéduraux classiques (on doit dire comment l'ordinateur doit faire, en prévoyant tous les cas).
Exercice : compléter les données pour respecter :
On définira également les règles définissant : est_le_fils, est_la_fille, est_la_belle_mere,....
Pour effectuer un ou, on peut utiliser le OU (;) ou utiliser plusieurs règles:
est_la_belle_mere_de(BelleMere,Gendre) :-
est_le_mari_de(Gendre,Epouse),
est_la_mere_de(BelleMere,Epouse). /*Belle-mère d'un homme*/
est_la_belle_mere_de(BelleMere,Bru) :-
est_le_mari_de(Epoux,Bru),
est_la_mere_de(BelleMere,Epoux). /*Belle-mère d'une femme*/
On peut également définir les femmes par :
est_une_femme(F) :- not(est_un_homme(F)).
Cette règle marche pour des variables liées (dira Yes s'il ne l'a pas trouvé parmi les hommes) mais pas pour une variable libre (en effet, toute combinaison de caractères pourrait répondre à la requête). Pour qu'une règle puisse s'appliquer à une variable libre, il faut que l'on permette à Prolog de trouver toutes les possibilités (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 intéresse 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 père, puis on élimine les hommes. On peut remarquer qu'anne et betty ne seront pas considérées comme femme. Il suffit pour résoudre ce problème de rajouter une seconde règle, 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
traités par la règle précédente */
le but : est_une_femme(X) nous donne maintenant toutes les femmes que nous avons définies.
Exercice : rajouter tantes, cousins, grand mères...
Pour simplifier la gestion des hommes par exemple, on peut utiliser une liste (voir détails plus loin) :
hommes([marc, luc, jean, jules, léon, 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.
En Prolog, l'écriture : X=Y peut avoir différents résultats :
Par contre l'écriture X=Y+1 (qui est équivalent à Y+1=X) va poser quelques problèmes. 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 compliquée). 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 opérateurs sont définis :
exemple : écrire un programme qui pour un but "affiche(10)." affiche les nombres de 10 à 0 : (on utilise le prédicat prédéfini write) :
affiche(X) :-
write(X), write(' '),
X>0, /* condition de fin */
Y is X-1,
affiche(Y).
Rq1 : il faut obligatoirement utiliser une variable intermédiaire (Y ici).
Rq2 : évidement, là je triche quand même : c'est plus procédural que déclaratif.
Exo : afficher désormais dans l'ordre croissant .
Truc : il suffit d'inverser l'ordre des instructions, mais il répond false (comme d'ailleurs aussi dans le cas précédent) mais avant les affichages. Il suffit de donner le fait : affiche(0).
Pour les autres comparaisons, les opérateurs (qui évaluent à droite et à gauche) sont : =:= =\= (différent) < > =< >= , les opérateurs arithmétiques : + - * / mod ** , sin, cos, log,....
chaque lettre représente 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 décris l'ensemble des possibilités 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 détaille ici exactement et précisément ce que l'on veut (le "quoi"), mais on ne donne aucune indication sur la méthode de résolution du problème, pas d'algorithme (le "comment"), on laisse Prolog se débrouiller.
On peut évidement se faciliter la description de ce type de problèmes en préparant quelques règles (en utilisant en particulier les listes), entre autres un prédicat "tous différents". Je vous donne ici ma proposition. Attention, certains de ces problèmes comportent un très grand nombre de solutions !
En prolog, il n'y a pas possibilité d'utiliser de tableaux (par exemple pour accéder directement à la 50ème valeur). Par contre, il est très facile de les remplacer par des listes. L'avantage des listes est que leur longueur est dynamique. Leur utilisation est récursive (on ne peut accéder à la 50ème qu'après avoir accédé aux 49 précédentes).
Une liste constante est représentée entre crochets ([ ] signifiant ensemble vide) :
equipe(ulp,[jean,lucie,yves,anne,alain,julie,marc,luc]). equipe(ushs,[jo,cathy,ahmed,louis,paul,eve,marie,rose]).
Lorsque l'on représente une liste par une variable, deux écritures sont possibles : soit par un nom de variable (commençant par une majuscule), soit par [Tete|Queue], où Tete (du type élément) est le premier de la liste, et Queue (de type liste d'éléments) le reste de la liste.
exemple :
afficher([T|Q]) :-
writeln(T),nl,
afficher(Q).
afficher([]).
essayez le but afficher([jean,jacques,jules]).
autre exemple, très utile :
appartient_à(X,[X|_]). appartient_à(X,[_|Queue]) :- appartient_à(X,Queue).
Les listes peuvent servir à représenter des ensembles (les éléments appartiennent ou non à différents ensembles, que l'on peut combiner par l'union ou l'intersection), mais aussi être ordonnée (et entre autres pourront être triées). Je vous propose ici un certain nombre de règles pour tester les listes.
SWI Prolog (sous Linux ou windows) est disponible gratuitement (licence GPL) département 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'interprétant interactivement, soit en le compilant au préalable.
pour l'aide (doc en ligne) :
Pour déboguer, on utilise le mode trace : au goal je donne : trace,ma_question(MesParametres). A chaque pas on appuie sur entrée (h pour l'aide des autres options). voir help(2-6).
listing. réécrit les règles à l'écran, ou listing(predicat). pour toutes celles limitées à un prédicat.
Petites particularités SWI Prolog :
Pour les chaînes de caractères, les mettre entre simples cotes (elles seront affichées par write et writef). Entre doubles cotes elles sont transformées en listes d'entiers (d'après les codes ascii). Elles seront affichées en liste d'entiers par write mais en chaine de caractères par writef. Entre " elles peuvent être traitées comme toute autre liste.
Comment lui demander TOUTES les solutions : taper ; après chaque réponse 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),ListeDeTousLesPeres). crée la liste de tous les X vérifiant 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 réponses par ordre alpha et vire les doublons.
Nous disposons également d'une vielle version de TURBO PROLOG (sous DOS), qui nécessite de déclarer à l'avance les prédicats. La section predicates correspond aux déclarations, la section clauses correspond à la base de faits et aux règles. 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 complément */ est_le_père_de(marc,jean).
Les listes sont déclarées dans une section nommée "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, léon, 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 numériques, Turbo Prolog accepte le signe = pour tous les cas d'égalité (instanciation, évaluation, comparaison, donc les opérateurs =, 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,integer,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.
Depuis le le 15/2/2002, vous êtes le
ème lecteur de cette page
|
Copyright P. Trau - IPST-ULP - Janvier 2002. Utilisation non commerciale de ce document autorisée, à condition de citer son auteur et conserver les liens ci-dessus. |
|
