Prolog : "crash course" (4)

Nous reviendrons encore aux structures incomplètes (listes différentielles et similaires), car ceci montre la formidable puissance sémantique du langage, mais la section suivante passe à la description de quelques éléments du langage lui-même.

Liberté syntaxique/sémantique ; opérateurs.

Dans presque tous les langages, on a des expressions infixes et le parenthésage, par ex. (a+X)*n-7/(z+1), etc. En Prolog les opérateurs existent aussi, mais par défaut ce sont des constructeurs des termes, sans une sémantique calculatoire. Nous pouvons écrire X=a+8., et Prolog répond X = a+8 ; ceci, d'ailleurs, est équivalent à X = +(a,8). La variable X a été unifiée avec le terme a+8, c'est tout. Nous avons vu la forme : X is P+1 ou similaire ; l'opérateur is est une "calculatrice", capable d'évaluer les expressions algébriques, selon la signification habituelle des opérateurs arithmétiques. Prolog possède plusieurs autres, par ex. "=", l'opérateur d'unification, qui n'est pas un simple constructeur, ou "\+" – la négation.

Mais nous pouvons modifier cette sémantique, définir des nouveaux opérateurs, et leurs attribuer un sens relationnel, définir des opérateurs qui font quelque chose, qui agissent comme des prédicats, comme "is" ou "=", ou "\==", etc. Certains opérateurs agissent entre les termes, comme l'égalité, ou "<", d'autres comme ":-", ou "->" – entre prédicats. Il ne faut pas se tromper : il n'est pas possible de définir "+" comme une opération d'addition, qui retourne un résultat, car c'est un opérateur infixe, donc prend deux arguments ; ici nous aurions besoin de trois : deux données et le résultat. Un opérateur infixe peut seulement spécifier une relation entre deux données. L'opérateur is est essentiel.

Comme un exemple artificiel, essayons de définir un "calculateur" non pas arithmétique, mais sur les listes, par exemple que X :: L1+L2 signifie la même chose que append(L1,L2,X). Il y a deux choses à faire :

La forme qui définit les propriétés syntaxiques : la précédence et l'associativité d'un opérateur infixe, c'est op, un prédicat à 3 paramètres.

op(Precedence,AssocType,Nom).
Attention. Si nous voulons exécuter op(...) dans le fichier source, avec un programme, nous ne pouvons simplement écrire op(...), ceci signifierait la rédéfinition de ce prédicat. Il faut insérer
?-op(...)
donc :
?-op(710,xfx,::).
R::(A+B) :- append(A,B,R).
est la solution de notre problème. Nous aurons :
 P::[1,2]+[3,8].
P = [1, 2, 3, 8].

La forme d'un programme Prolog peut donc être très, très variée, selon les formes opérationnelles que l'on définit.

Notre opérateur - exécuteur "::" est très faible, il ne réagit qu'à la présence de "+", mais il est très facile de faire des choses plus universelles.

Structures de contrôle et méta-prédicats.

L'utilisateur a également une grande liberté sémantique, pas seulement syntaxique en Prolog. Nous pouvons définir des nouveaux protocoles d'exécution, et modifier les existants. Par ex., pour l'instant nous n'avons ni les conditionnelles if - then - else ni les boucles "classiques", permettant d'itérer automatiquement une activité, similaires à ces constructions dans d'autres langages. On a le mécanisme conditionnel piloté par l'échec, mais le non-déterminisme fonctionne un peu différemment que le "if...". Nous avons des itérations pilotées par l'échec (backtracking) et la récursivité, mais il nous manque un peu d'organisation, afin de concevoir les structures de contrôle "plus classiques".

Négation

Si P est un prédicat quelconque, la forme \+ P est sa négation. Cet opérateur lance le prédicat, et "inverse" la décision succès/échec. Si P unifie une variable, la négation l'invalide, donc cette forme est incapable d'unifier quoi que ce soit. Notez que l'opérateur agit sur un prédicat, non pas sur un terme quelconque.

Attention, logiquement ceci est vraiment un opérateur permettant de constater, qu'une vérité ne peut pas être prouvé, non pas une "preuve de fausseté".

Conditionnelle classique

Ceci dans quelques implémentations n'est pas défini, et l'utilisateur doit le faire soi-même, mais en SWI nous avons un opérateur prédéfini "->", appliqué dans un contexte particulier. La forme P -> Q lance P, et s'il réussit, lance Q. La différence par rapport à P,Q est, qu'il n'y a pas de backtracking sur P si Q échoue, ou si l'utilisateur force l'échec. C'est similaire à P,!,Q.

Alors P -> Q;R est la forme avec une alternative, si P échoue, on passe à R. Si Q échoue, R n'est pas lancé, c'est ce que l'on attend de if-then-else.

- 3<7 ->  write(yo),fail;perm([xx,yy],Z).
yo
false.

La sémantique intuitive de cette construction est équivalente (+/-) avec :

If -> Then; _Else :- If, !, Then.
If -> _Then; Else :- !, Else.
If -> Then :- If, !, Then.
Ceci pourrait inspirer tout le monde à concevoir ses propres structures de contrôle décisionnelles spécifiques, parfois même exotiques.

Boucles

Rappelons, qu'il y a deux variantes de répétitions en Prolog : les itérations récursives, et les itérations via backtracking. Construisons un prédicat qui répète le lancement d'un autre prédicat plusieurs fois. Commençons cependant par un sous-problème ponctuel : comment lancer un prédicat passé en paramètre, depuis le programme utilisateur?. Ceci :
lance(P,X):-P(X).
ne marchera pas. Un terme (exécutable ou non) ne peut avoir le nom variable. Il faut d'abord construire une liste [P,X] et la convertir en terme fonctionnel grâce à l'opérateur – constructeur de termes "=..". Voici la solution :
lance(P,X):-Pred =..[P,X],Pred.
Ainsi, comme ça on engendre toutes les permutations d'une liste fixe. On définit : tperm(X):-perm([1,2,3],X)., et on lance :
 lance(tperm,A).
Voici la boucle qui affiche un certain nombre de carrés des nombres entiers.
square(X):-Y is X*X,writeln(Y).

loop(Xin,Xin,Pr):-lance(Pr,Xin).
loop(Xin,Xlim,Pr):-Xin<Xlim, lance(Pr,Xin), X is Xin+1,loop(X,Xlim,Pr).
On le lance par ex. comme : loop(0,14,square).
0
1
4
9
16
25
36
49
64
81
100
121
144
169
196
true 

Ceci était la solution récursive, "classique". Le non-déterminisme sert ici seulement comme la conditionnelle permettant de passer à l'autre clause. Passons aux boucles pilotées par le backtrack. Elles sont un peu similaires aux précédentes, mais l'organisation du contrôle des prédicats qui "font quelque chose" est différente, ils ne font pas partie de la structure récursive. Voici le générateur de la boucle "nu" :

bloop(Xin,Xin).
bloop(Xin,X):-Xnxt is Xin+1,bloop(Xnxt,X).
et son appel :
 bloop(0,X),square(X).
0
X = 0 ;
1
X = 1 ;
4
X = 2 ;
9
X = 3 ;
16
X = 4 ;
25
X = 5 
...
Ici le relancement n'est pas automatique, mais manuel, on force explicitement la reprise. Si on ajoute des filtres qui arrêtent la génération, on peut ramasser toutes les réponses via findall. Il faut faire attention !!. Ceci :
 findall(X,(bloop(0,X),X<15,square(X)),LL).
affichera la séquence, et ensuite se bloquera dans une boucle infinie morte, car l'échec du filtrage n'empêche bloop de continuer la génération. Le résultat LL ne sera jamais visualisé. Il faut incorporer le filtre dans bloop, si on veut coder la boucle de cette manière. Voici une autre solution :
 findall(X,(bloop(0,X),(square(X);X>13,!,fail)),LL).
0
1
4
9
16
25
36
49
64
81
100
121
144
169
196
LL = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14].
(Bien sûr, au lieu d'afficher, on pourrait simplement récupérer le carré dans une variable, et ramasser toutes.) Ces exemples montrent que – si en Prolog on peut faire tout ce que l'on veut, le codage des structures non-triviales demande une bonne expérience. Ceci ne s'apprend pas en quelques jours ! Il y a des prédicats prédéfinis qui bouclent ad infinitum via backtracking :
repeat.
repeat:-repeat.
mais leur usage :
repeat,p1(...),p2(...),...
demande une solide connaissance de la sémantique de Prolog.


Première rencontre avec les DCG (Definite Clause Grammars)

Les DCG constituent une sorte de "langage dans le langage" ; on a vu que Prolog facilite la construction des extensions syntaxiques via les opérateurs, et sémantiques, grâce à l'universalité du non-déterminisme et les méta-prédicats. Son usage typique est l'analyse (parsing) des textes, mais elles peuvent inspirer l'utilisateur à traiter de cette manière plusieurs autres structures. Elles profitent des dispositifs genre listes différentielles de manière assez intense.

Les exemples ci-dessous seront en anglais, car la langue anglaise est plus simple, "moins contextuelle". Voici un exemple de "grammaire" en DCG-Prolog, une construction qui a la forme de grammaire, mais qui est effectivement un programme Prolog en déguisement. Ceci est une très simple grammaire des phrases en langue naturelle.

phrase --> noun_phrase, verb_phrase.
noun_phrase --> det, noun.
verb_phrase --> verb, noun_phrase.

det --> [the].
det --> [a].

noun --> [cat].
noun --> [bat].

verb --> [eats].
Le "déguisement" cache des arguments. L'équivalent Prolog serait :
phrase(S1,S3) :- noun_phrase(S1,S2), verb_phrase(S2,S3).
...
verb([eats|X], X).
L'argument du prédicat compatible avec DCG est une liste différentielle ! Le premier élément est la liste totale, le second – sa queue. Une grammaire DCG peut être utilisée pour la reconnaissance des formes syntaxiques :
 phrase([a, X, eats, the, Y, on, the, roof],Q).
X = Y, Y = cat,
Q = [on, the, roof] ;
X = cat,
Y = bat,
Q = [on, the, roof] ;
X = bat,
Y = cat,
Q = [on, the, roof] ;
X = Y, Y = bat,
Q = [on, the, roof] 
... et aussi pour la synthèse pure.
 phrase(A,B).
A = [the, cat, eats, the, cat|B] ;
A = [the, cat, eats, the, bat|B] ;
A = [the, cat, eats, a, cat|B] ;
A = [the, cat, eats, a, bat|B] ;
A = [the, bat, eats, the, cat|B] ;
A = [the, bat, eats, the, bat|B] ;
A = [the, bat, eats, a, cat|B] ;
A = [the, bat, eats, a, bat|B] ;
A = [a, cat, eats, the, cat|B] ;
A = [a, cat, eats, the, bat|B] ;
A = [a, cat, eats, a, cat|B] ;
A = [a, cat, eats, a, bat|B] ;
A = [a, bat, eats, the, cat|B] ;
A = [a, bat, eats, the, bat|B] ;
A = [a, bat, eats, a, cat|B] ;
A = [a, bat, eats, a, bat|B].

Dans ces exemples nous travaillons avec les listes, non pas avec les chaînes, qu'il faudrait d'abord "tokeniser", séparer les sous-chaînes qui correspondent aux entités lexicales. Pour un vrai travail d'analyse des textes, il faut d'abord tokeniser la chaîne. Mais les outils pour cela existent.

Construisons une grammaire qui représente les expressions algébriques, genre (a+b)*7-s/(5*u+t), avec les quatre opérations, atomes et parenthèses. Une expression peut être un atome (numérique ou non, ici la signification des éléments ne nous concerne pas). Sinon, en accord avec les règles de précédence des opérateurs, c'est une somme [ou différence] de termes, où chaque terme est le produit (et/ou quotient) de facteurs, un terme par définition n'a pas d'opérateurs additifs. Un facteur peut être atomique, mais aussi une sous-expression parenthésée. Ainsi nous aurons des expressions de longueur et de profondeur quelconque.

== == To be continued... == ==


Suivant
Retour à l'index