Création de programmes

Pour creer une base de faits et de regles, on ecrit normalement un chier dont on demande le chargement par l’interprete ou le compilateur. Cette operation est appelee consultation d’un chier et se commande en faisant executer le but consult(fichier) qui va interpreter le contenu de chier comme une suite de clauses a ajouter a la banque de faits et regles du systeme. Il est souvent pratique de pouvoir remplacer un jeu de clauses par d’autres du m^eme nom : c’est ce qui arrive lorsqu’on decouvre une erreur dans un chier, qu’on la corrige avec l’editeur et fait interpreter le programme en s’attendant a ce que la nouvelle version des clauses remplace les anciennes au lieu de s’ajouter aux anciennes qui sont erronees. Cette operation de remplacement est commandee par reconsult(fichier)
On peut ajouter des commentaires dans un chier en les faisant preceder par le caractere % ; le commentaire s’etend jusqu’a la n de la ligne.

Arithmetique

Les foncteurs permettent d’exprimer toutes les valeurs, mais dans ce cas l’arithmetique devient encombrante et ine cace car pour representer par exemple 3, il faudrait ecrire succ(succ(succ(0))). Heureusement, on peut e ectuer des operations en utilisant le fonc-teur is qui evalue son deuxieme argument et l’uni e avec le premier. Ainsi is(X, +(*(3,7),8)) uni era X avec 29, car le deuxieme argument est consider comme un arbre dont les noeuds sont soit des valeurs soit des operations a e ectuer sur les branches. C’est deja beaucoup plus pratique mais l’arithmetique sous forme pre xe n’est pas tres habituelle (a moins d’^etre un lispien convaincu…). C’est pourquoi la plupart de ces foncteurs peuvent aussi s’ecrire sous forme in xe (pour les foncteurs binaires) et sous forme pre xe ou su xe pour les foncteurs unaires. L’utilisateur peut egalement declarer certain de ses propres foncteurs comme etant in xe, pre xe ou su xe. A chaque operateur sont associees une priorite et une associativite, ce qui permet de rendre les programmes plus lisibles et reproduire ainsi les priorites ren-contrees habituellement dans les langages de programmation. L’exemple precedent devient donc :
X is 3*7+8
qui n’est pas sans rappeler l’a ectation classique, mais c’est une illusion car ceci n’est qu’une autre facon de denoter l’arbre suivant :
is
X +
* 8
Ce n’est que lorsqu’on tente de resoudre is(X,+(*(3,7),8)) que l’uni cation de X avec l’evaluation du deuxieme operande est e ectuee. Cette evaluation est egalement commandee par les operations de comparaison : >=,=<,<,>,==,\== les deux derniers denotant l’egalit ou l’inegalit mais forcant l’evaluation des arguments.

Les listes

Dans nos exemples precedents, notre syntagme etait represent par un foncteur a n ar-guments pour n mots, mais la longueur des suites de mots est inconnue a priori ; il est donc important de trouver une representation pour exprimer des listes d’elements. Ceci est fait a l’aide d’un foncteur special . a deux arguments dont le premier indique un element et le deuxieme la suite de la liste. Donc la liste de deux elements a et b est representee comme suit :
.(a,b)
cette notation est un peu encombrante et on utilise normalement l’abreviation in xe suivante ou la liste est indiquee entre crochets et le debut est separ de la suite par une barre verticale.
[a | b]
Ceci est particulierement pratique lorsqu’il y a plusieurs elements dans la liste. Comparez :
.(a, .(.(c,d),e)) et [a |[[c|d]|b]]
.( .( .(c,d), e),a) et [[[c|d]|b]|a]
Pour eviter des niveaux de crochets, on peut remplacer .[ par une virgule (et enlever le crochet correspondant). Par exemple le premier exemple devient :
[a,[c|d]|b]
La n de liste est habituellement indiquee par [] et on permet de ne pas indiquer le dernier element vide (i.e.|[] ) ; ceci permet de simpli er encore plus, comparez :
.(a, .(b, .(c,[]))) [a|[b|[c|[]]]] [a,b,c]
qui representent tous le m^eme objet ; evidemment la troisieme possibilite est la plus pra-tique a utiliser mais elle n’est qu’une abreviation pour les deux autres ; la premiere etant la representation \logique ». La notation avec une barre verticale est habituellement utilisee lorsqu’on veut indiquer que le \reste » d’une liste est une variable. Ainsi [a,b | X] equivaut a .(a,.(b,X)) et represente une liste dont les deux premiers elements sont a et b mais dont on ne conna^t pas la suite (qui peut ^etre []). [X|Y] equivaut a .(X,Y) et donc X est le premier element et Y le reste ; ceci correspond au car et cdr de Lisp. Voyons mainte-nant quelques predicats utiles sur les listes. Nous n’en donnons que la de nition et quelques exemples d’utilisation. On pourra consulter (Clocksin et Mellish 84) (Sterling et Shapiro 86) pour apprendre a deriver ces predicats. Nous allons les utiliser ici regulierement et les supposer prede nis.
%%%
%%% outils de manipulations de listes
%%% fichier « listes.pro »
%%%
% concatenation concat([],L,L). concat([X|Xs],Y,[X|Z]):-concat(Xs,Y,Z).
% verification d’appartenance dans(X,[X|Xs]). dans(X,[_|Xs]):-dans(X,Xs).
% donner le nieme element nieme([H|T],1,H):-!. nieme([H|T],N,H1):-N1 is N-1, nieme(T,N1,H1).
% trouver le nombre d’elements longueur([],0).
longueur([H|T],N):-longueur(T,N1),N is N1+1.
% renverser l’ordre des elements renverse(L,R):-renverse(L,[],R). renverse([H|T],L1,L):-renverse(T,[H|L1],L). renverse([],L,L).
Voyons maintenant quelques exemples d’utilisation de ces predicats :
| ?- concat([l,e],[c,h,a,t],X). X = [l,e,c,h,a,t]
| ?- concat(Radical,[e,r],[a,i,m,e,r]). Radical = [a,i,m]
| ?- concat(Debut,Fin,[j,e,u,n,e]). Debut = []
Fin = [j,e,u,n,e] ;
Debut = [j]
Fin = [e,u,n,e] ;
Debut = [j,e]
Fin = [u,n,e] ;
Debut = [j,e,u]
Fin = [n,e] ;
Debut = [j,e,u,n]
Fin = [e] ;
Debut = [j,e,u,n,e]
Fin = [] ;
no
| ?- dans(h,[c,h,a,t]).
yes
| ?- dans(X,[c,h,a,t]). X = c ;
X = h ; X = a ; X = t ;
no
| ?- nieme([c,h,a,t],3,X).
X = a
| ?- longueur([c,h,a,t],L). L = 4
| ?- renverse([e,t,a,l,e,r],X). X = [r,e,l,a,t,e]
On remarque qu’on peut utiliser le m^eme predicat de plusieurs facons di erentes selon que l’on instancie ou non certains parametres : ainsi concat sert aussi bien a coller deux listes bout a bout qu’a en decomposer une en deux morceaux. dans permet d’obtenir tous les elements d’une liste.

Predicats extra-logiques

Si Prolog est base sur la logique, on a quelquefois besoin d’un contr^ole ou d’operations qui sortent du cadre de la logique. Nous allons ici decrire tres brievement les outils extra-logiques dont nous aurons besoin pour le traitement de la langue naturelle.

Le coupe-choix

Si le non-determinisme est souvent pratique, il y a des cas ou il est interessant de le limiter. L’outil le plus utile en Prolog est le \coupe-choix » cut notee par un point d’exclamation qui, lorsqu’il est \prouve », a pour e et d’enlever tous les choix en attente dans le groupe de clauses ou il appara^t. Il est utilise pour eviter des tests dont on est certain qu’ils vont echouer ou pour s’assurer que certaines operations ne vont ^etre e ectuees qu’une seule fois. Par exemple,
max(X,Y,X):- X>=Y.
max(X,Y,Y):- X<Y.
pourrait ^etre reecrit comme
max(X,Y,X):- X>=Y,!.
max(X,Y,Y).
Ainsi, si le test de la premiere clause reussit, il est inutile de tenter la deuxieme et s’il echoue, alors il est s^ur que le deuxieme reussit et nous n’avons pas besoin d’un autre test.
Le coupe-choix permet egalement de forcer l’echec d’un predicat m^eme s’il reste d’autres possibilites a explorer. Un cas particulier mais tres utile de ce cas de gure est la de nition de not(P) qui reussit lorsque P echoue et echoue lorsque P reussit. Il est de ni comme suit :
not(P) :- call(P), !, fail.
not(P).
ou call est tout simplement une demande de resolution du predicat P. Le coupe-choix assure que la seconde clause ne sera pas tentee (pour reussir) apres le succes de P. Si P echoue, alors le coupe-choix n’est pas essay et on tente la deuxieme possibilite qui renvoie un succes car il n’y a rien a prouver. En Sicstus, ce predicat est prede ni sous la forme de l’operateur pre xe \+.

Decomposition de litteraux

On a quelquefois besoin de manipuler les litteraux eux-m^emes, en particulier lorsqu’on calcule un but a resoudre. Comme en C-Prolog il n’est pas possible d’ecrire le but X(Y) ou X aurait et instancie dans la clause ou il appara^t, il faut d’abord composer le foncteur avant de l’appeler. Ceci peut ^etre fait en utilisant l’operateur =.. (nomme univ depuis la premiere version de Prolog). Ainsi
f(a,b,c) =.. X
uni era X a [f,a,b,c]. On obtient donc une liste dont le premier element est le foncteur et les autres ses arguments. Donc pour construire X(Y,Z) et l’evaluer, on fera plut^ot
P =.. [X,Y,Z], call(P).

Decomposition d’un identicateur

On peut \exploser » ou \imploser » le nom d’un identi cateur avec name ; par exemple : name(chat,X)
uni era X a la liste [99,104,97,116] ou chaque element correspond au code ASCII du caractere correspondant de l’identi cateur donne comme premier argument. Cette operation est reversible en ce sens que si on donne une liste de codes ASCII comme deuxieme argument et une variable comme premier, alors on recompose un identi cateur. Comme la manipulation de codes ASCII est assez malcommode et rend les programmes di ciles a lire, nous de nirons a la section suivante un autre predicat nom qui ne travaille qu’en terme d’identi cateur (mais il utilise name de facon interne).

Modification de la base de faits

On peut ajouter et retrancher dynamiquement des clauses a un programme : ainsi assert(c(p1,p2)).
ajoute la clause c(p1,p2) au programme et retract(c(X1,X2)) enleve la premiere clause qui s’uni e avec c(X1,X2). Ce mecanisme est utilise pour transfor-mer des programmes ou pour conserver des informations entre plusieurs executions de clauses car normalement toutes les liaisons de variables sont brisees lors de la n de la preuve.
Nous donnons maintenant une illustration de l’arithmetique et de la modi cation de la base de faits en de nissant un predicat permettant de tirer des nombres au hasard ; ceci nous sera utile dans certains exemples des prochains chapitres.
%% ce qu’il faut pour generer au hasard
%% c’est le fichier « hasard.pro »
% tirage au sort via un generateur congruentiel lineaire
% donne X un nombre reel dans [0,1]
hasard(X):-
retract(germe_hasard(X1)), X2 is (X1*824) mod 10657, assert(germe_hasard(X2)), X is X2/10657.0
% donne X un nombre entier dans [1,N] hasard(N,X) :-
hasard(Y),
X is floor(N*Y)+1.
% initialisation du germe (a la consultation du fichier) :- abolish(germe_hasard,1), X is floor(cputime*1000), assert(germe_hasard(X)).

Entrees-Sorties

Comme nous voulons traiter la langue naturelle et que ces applications impliquent souvent l’ecriture d’interfaces, il est important d’avoir des outils commodes d’entree et de sortie de mots et de phrases. Nous allons passer rapidement en revue les predicats de lecture et d’ecriture de C-Prolog et ensuite nous montrerons la programmation de predicats de plus haut niveau.

Entree de caracteres

Voici les predicats permettant l’entree de caracteres :
get0(X) uni e X avec le code ASCII du prochain caractere sur le terminal.
get(X) comme get0 mais ignore tous les caracteres de contr^ole.
skip(X) ou X doit ^etre instancie a un code ASCII, saute tous les caracteres en entree en s’arr^etant au premier dont la valeur est egale a X.

Ecriture

Voici les predicats permettant l’ecriture de caracteres :
put(X) ecrit sur le terminal le caractere dont le code ASCII est X.
write(X) ecrit le terme X selon la syntaxe standard y compris les operateurs in xe
nl ecrit une n de ligne
tab(I) ecrit I blancs sur la ligne courante. I peut ^etre une expression a evaluer.

 Entree de mots et de listes de mots

Nous de nissons maintenant des predicats qui permettent de lire une suite de mots separes par des blancs et terminee par un point, un point d’interrogation ou une n de ligne et qui retourne une liste d’identi cateurs. Ainsi
| ?- lire_les_mots(X).
|: bonjour les degats
X = [bonjour,les,degats]
| ?- lire_les_mots(X).
|: Salut, les grands copains .
X = [Salut,les,grands,copains]
Ce programme n’est qu’un exemple de traitement de listes de mots et il est facile de le modi-er pour traiter autrement certains caracteres. On y remarque egalement la transformation des codes ASCII en identi cateurs.
%%%
%%% Les utilitaires de lecture
%%% fichier « entree.pro »
%%%
%% transformation de la ligne lue en une suite d’atomes lire_les_mots(Ws):-lire_car(C),lire_les_mots(C,Ws).
lire_les_mots(C,[W|Ws]):- % ajoute un mot
car_mot(C),!,
lire_mot(C,W,C1),lire_les_mots(C1,Ws).
lire_les_mots(C,[]):- % fin de phrase
car_fin_des_mots(C),!.
lire_les_mots(C,Ws):- % on oublie ce
lire_car(C1),lire_les_mots(C1,Ws). % caractere
lire_mot(C,W,C1):-
cars_des_mots(C,Cs,C1),nom(W,Cs).
% construit un mot
cars_des_mots(C,[C|Cs],C0):-
car_mot(C),!,lire_car(C1),cars_des_mots(C1,Cs,C0).
cars_des_mots(C,[],C):- \+(car_mot(C)).
%% classes des caracteres car_mot(C):- a @=< C, C @=< z. car_mot(C):-‘A’ @=< C,C @=< ‘Z’. car_mot( » »).
%% une liste de mots est terminee par un point un
%% un point d’interrogation ou une fin de ligne
car_fin_des_mots(‘.’):-skip(10). % sauter jusqu’a la
car_fin_des_mots(‘?’):-skip(10). % fin de ligne
car_fin_des_mots(X) :-name(X,[10]). % le « newline »
%%% predicats necessaires en C-Prolog pour eviter
%%% la manipulation de codes ascii
%% lecture d’un caractere et
%% transformation en l’atome correspondant lire_car(X) :- get0(X1), name(X,[X1]).
%% nom explose un identificateur en
%% une liste d’identificateurs d’une lettre
%% appel: nom(aimer,[a,i,m,e,r])
%%
nom(X,Xl) :- % explose
var(Xl),!, name(X,Codes), nom1(Codes,Xl).
nom(X,Xl) :- % compose
var(X),!, nom1(Codes,Xl), name(X,Codes).
nom1([],[]).
nom1([X|Xs],[X1|X1s]):- name(X1,[X]), nom1(Xs,X1s).

Ecriture de listes de mots et d’arbres

Prolog nous fournit les outils de base pour l’ecriture de termes, mais dans une interface nous aimerions souvent pouvoir ecrire une liste d’identi cateurs comme une liste de mots separes par un blanc et terminee par une n de ligne. Le predicat ecrire-les-mots permet de faire cette operation. De plus, nous montrons un predicat un peu plus complexe qui permet de faire ressortir la structure d’un terme compose en utilisant l’indentation des di erentes lignes. Cette operation est communement appel \pretty-print » d’ou le nom de pp pour ce predicat. Sa principale particularite etant qu’il est possible de contr^oler les termes qui seront ecrits sur plusieurs lignes.