3. Chapitre 3 - Programmation logique : prolog▲
3-1. Présentation▲
prolog est né d'un pari : créer un langage de très haut niveau, même inefficace au sens des informaticiens de l'époque. L'efficacité consistait alors à faire exécuter très rapidement par une machine des programmes écrits laborieusement. Le pari était donc de pouvoir écrire rapidement des programmes, quitte à ce que la machine les exécute laborieusement. prolog signifie PROgrammation en LOGique. Le nom du langage est significatif.
Programmer en prolog, c'est exprimer sous forme de relations logiques les différentes propriétés d'un système. Une fois le problème formalisé, le langage sera, le plus souvent, capable de fournir les réponses aux questions posées par l'utilisateur en utilisant une méthode de résolution automatique.
La programmation en prolog est assez différente de la programmation dans un language classique. prolog est un language dit déclaratif, en ce sens qu'on ne décrit pas comme dans les langages traditionnels (dits procéduraux) une méthode (ou algorithme) de résolution, mais que l'on déclare les propriétés du problème, le système se chargeant lui-même d'appliquer une méthode de résolution.
Les formules logiques que prolog peut utiliser sont les clauses de Horn de la logique des prédicats tels que nous les avons décrits au chapitre 1Chapitre 1 - Logique des propositions. prolog met en application les techniques de résolution et d'unification de la logique des prédicats (nous n'avons pas abordé ces techniques pour la logique des prédicats, mais nous avons vu la résolution en logique des propositions).
prolog a vu le jour en 1971 sur une idée d'Alain Colmerauer qui travaillait alors aux problèmes de traduction automatique au Groupe Intelligence Artificielle de Marseille- Luminy. Le premier langage prolog a été créé par Alain Colmerauer avec l'aide de Philippe Roussel dans le cadre d'un contrat de communication homme-machine.
Nous nous basons pour présenter prolog sur le système swi-prolog (http://www.swi.psy.uva.nl/projects/SWI-Prolog/).
3-2. Terminologie▲
L'objet de cette section est de décrire rapidement l'emploi de certains termes dans le contexte prolog.
Base de faits - On appelle base de fait l'ensemble des faits relatifs au problème que l'utilisateur formalise en prolog. « Médor est un chien » peut se représenter par un fait. Formellement, les faits sont des clauses de Horn positives.
Base de règles - On appelle base de règles l'ensemble des règles relatives au problème que l'utilisateur formalise en prolog. « Un chien est un mammifère » peut se représenter par une règle. Les règles sont des clauses de Horn strictes.
Question - La question est ce que l'utilisateur demande au système. C'est une clause de Horn négative.
Moteur d'inférence de prolog - Le moteur d'inférence de prolog est la partie du système qui réalise les inférences logiques sur les faits et la question posée par l'utilisateur, de façon à donner une (ou plusieurs) réponse(s). Il opère sur un ensemble de faits et de règles, donc un ensemble de clauses de Horn négatives ou strictes. Sur un plan théorique, le moteur prolog fait une preuve d'inconsistance sur la base de clauses de Horn.
3-3. Syntaxe▲
Nous allons ici présenter la syntaxe du swi-prolog de manière informelle et simplifiée.
Les variables - Une variable commence par une majuscule ou le signe « _ ». Par exemple, X, XA, A123, _a sont des symboles de variables autorisés en swi-prolog tandis que ab, a1b, r2d2 sont invalides.
Les symboles de prédicats - un symbole de prédicat est un mot commencent par une minuscule. Il peut avoir des arguments, auquel cas il est suivi d'une parenthèse ouvrante, de la liste des arguments séparés par des virgules et d'une parenthèse fermante. Les arguments peuvent être des variables comme X ou des symboles de constantes comme toto par exemple. Les symboles de fonctions et de constantes ont la même structure syntaxique que les prédicats, ambiguïté qui peut parfois porter à confusion. Par exemple, chien(X), toto(A,B,C), truc(fop(X), Y) sont des utilisations de symboles de prédicats correctes.
Les listes - une liste est une suite d'objets entre « [] » séparés par des « , ». Les parenthèses sont utilisées pour délimiter les sous-listes. Par exemple, les listes [a,b,toto,2,] et [a,(b,c),d,] sont des listes syntaxiquement correctes.
Les faits - Un fait s'écrit predicat_tete.. Un exemple de fait correctement exprimé est chien(fido). pour signifier que fido est un chien.
Les règles - Une règle s'écrit predicat_tete :- predicat_1, predicat_2 … Un exemple de prédicat correctement exprimé est mammifere(X) :- chien(X) .. Ce prédicat peut signifier « pour tout X, si X est un chien alors X est un mammifère ».
Attention, le signe :-, qui s'écrit souvent -> sur d'autres interpréteurs prolog, n'est pas un signe d'implication ! Il peut s'interpréter comme un signe de réécriture. En logique nous écririons la dernière clause chien(X) → mammifere(X). Là encore, la syntaxe du langage peut induire en erreur.
3-4. Premier programme (swi-prolog)▲
Voici un premier exemple de programme prolog :
chien(fido).
mammifere(X) :- chien(X).La première ligne est un fait qui déclare que fido est un chien. La seconde ligne est une règle qui déclare que tout chien est un mammifère.
Une question que l'on pourrait poser serait :
?- mammifere(fido).La réponse serait : Yes
Il faut interpréter cette réponse comme vraie. On pourrait poser la question :
> mammifere(X).La réponse serait : X = fido
3-5. Travaux pratiques (Arbre généalogique)▲
Le but de ce TP est de représenter en prolog un arbre généalogique, puis d'écrire des relations qui permettront d'interroger cette base de données.
L'arbre généalogique à représenter est celui de la figure 3.1.
Complétez la base de faits suivante pour que l'intégralité de l'arbre généalogique soit représentée :
homme(elton).
homme(gaston).
...
femme(eva).
femme(simone).
femme(magali).
...
parent(elton,edouard).
parent(elton,magali).
parent(eva,edouard).
parent(eva,magali).
...Dans ce programme homme(X) signifie que X est un homme, femme(X) signifie que X est une femme et parent(X,Y) signifie que X est un parent de Y.
En utilisant la convention d'écriture relation(X,Y) signifiant « X est relation de Y », établir les règles suivantes :
- enfant(X,Y) ;
- fils(X,Y) ;
- fille(X,Y) ;
- pere(X,Y) ;
- mere(X,Y) ;
- grand_parent(X,Y) ;
- grand_pere(X,Y) ;
- grand_mere(X,Y) ;
- petit_enfant(X,Y) ;
- petit_fils(X,Y) ;
- petite_fille(X,Y) ;
- frere(X,Y) ;
- sœur(X,Y) ;
- oncle(X,Y) ;
- tante(X,Y).
Pensez à tester vos règles au fur et à mesure !
3-6. Travaux pratiques (Règles syntaxiques en prolog)▲
3-6-1. Microgrammaire en prolog▲
Micro grammaire
Voici un exemple de microgrammaire pour décrire quelques phrases simples en français :
phrase --> syntagme_nominal, syntagme_verbal.
syntagme_nominal --> article, nom_commun.
syntagme_verbal --> verbe, syntagme_nominal.
syntagme_verbal --> verbe.
article --> [le].
article --> [la].
nom_commun --> [souris].
nom_commun --> [chat].
verbe --> [mange].
verbe --> [guette].Avec cette grammaire on peut générer des phrases comme :
le chat guette la souris.
le chat mange.En prolog
Dans un premier temps, on aimerait avoir un programme en prolog qui accepte des phrases et nous dit si elles sont correctes d'après la grammaire spécifiée.
Si on convient que phrase_correcte(X) signifie X est une liste de mots formant une phrase syntaxiquement correcte d'après la grammaire spécifiée, alors nous aurions :
?- phrase_correcte([le, chat, mange, la, souris]).
Yes
?- phrase_correcte([le, chat, mange, souris]).
NoCela pourrait être fait de la manière suivante :
- soit append(X, Y, Z) un prédicat prédéfini qui est vrai quand la liste Z peut s'unifier avec la concaténation des listes X et Y ;
- soit syntagme_nominal(X) un prédicat vrai si X est un syntagme nominal ;
- soit syntagme_verbal(X) un prédicat vrai si X est un syntagme verbal.
La règle phrase_correcte(X) qui ferait exactement ce que l'on aimerait pourrait s'écrire en prolog :
phrase_correcte(P) :-
append(GN, GV, P),
syntagme_nominal(GN),
syntagme_verbal(GV).Écrivez la suite du programme en prolog.
Testez votre programme avec les requêtes suivantes :
?- phrase_correcte([le, chat, mange, la, souris]).
?- phrase_correcte([le, chat, mange, souris]).
?- phrase_correcte([la, chat, mange, le, souris]).
?- phrase_correcte([la, souris | R]).
?- phrase_correcte(P).Quelles sont vos remarques ?
Problèmes
Comme vous l'avez peut-être remarqué, notre programme est fortement perfectible. Il pose, à l'état actuel, trois problèmes que nous allons essayer de corriger dans les sections qui suivent.
Problème de performance : notre programme n'est absolument pas performant en analyse et totalement inutilisable en génération.
Décomposition syntaxique : le programme se contente de dire si une phrase est syntaxiquement correcte ou pas, mais dans le cas où une phrase est correcte, il ne donne pas sa décomposition.
Accords en genre : les accords en genre ne sont pas gérés.
3-6-2. Problème de performance▲
Examinons de plus près comment fonctionne notre prédicat phrase_correcte(X).
En analyse (i.e. lorsque l'on soumet une phrase à analyser au prédicat), le prédicat append(GN, GV, P) va générer toutes les décompositions possibles de la liste P en deux sous-listes GN et GV. On fait ici un grand nombre de décompositions inutiles pour n'en utiliser que très peu par la suite.
En génération (i.e. lorsque le prédicat doit lui-même générer des phrases, ou des portions de phrases), le prédicat append(GN, GV, P) peut être amené à générer des listes GN et GV au hasard ce qui conduit ici à une inefficacité catastrophique.
La bonne méthode consiste à laisser le prédicat syntagme_nominal décider lui-même de la sous-liste dont il a besoin. Ainsi nous définirons une règle
syntagme_nominal(Phrase, RestePhrase)signifiant :
- il y a un syntagme nominal en tête de la phrase Phrase, et
- ce qui reste de la phrase après ce syntagme nominal est RestePhrase.
Nous devrions alors avoir :
?- syntagme_nominal([le, chat, mange, la, souris], RestePhrase).
RestePhrase = [mange, la, souris]
YesPar souci d'homogénéité, toutes nos règles, hormis phrase_correcte(X), seront de la forme :
règle(Portion, RestePortion)La règle phrase_correcte(X) qui ferait exactement ce que l'on aimerait pourrait s'écrire en prolog :
phrase_correcte(X) :-
syntagme_nominal(X, R1),
syntagme_verbal(R1, []).La liste vide [] dans syntagme_verbal(R1, [])signifie que, pour que Xsoit une phrase correcte, il faut qu'il ne reste rien une fois enlevés le syntagme nominal et le syntagme verbal.
Écrivez la suite du programme en prolog.
Testez votre programme avec les requêtes suivantes :
?- phrase_correcte([le, chat, mange, la, souris]).
?- phrase_correcte(P).3-6-3. Décomposition syntaxique▲
Quand une phrase est correcte, il serait intéressant d'avoir sa décomposition syntaxique.
Par exemple :
?- phrase_correcte([le, chat, mange, la, souris], DecompositionSyntaxique).
DecompositionSyntaxique = ph(sn(art([le]), nc([chat])),
sv(manger([mange]),sn(art([la]),
nc([souris]))))
YesLa règle phrase_correcte(X) qui ferait exactement ce que l'on aimerait pourrait s'écrire en prolog :
phrase_correcte(X, ph(TRGN,TRGV)) :-
syntagme_nominal(X, R1, TRGN),
syntagme_verbal(R1, [], TRGV).Ici ph(TRGN,TRGV) est un terme où ph(x,y) est une fonction à laquelle on passe deux arguments : la décomposition syntaxique du syntagme nominal (TRGN) et la décomposition syntaxique du syntagme verbal (TRGV).
Écrivez la suite du programme en prolog puis testez-le.
3-6-4. Accords en genre▲
Modifiez le dernier programme écrit pour prendre en compte l'accord en genre. À vous de décider, voici le résultat :
?- phrase_correcte(Ph, Dec).
Ph = [le, chat, mange, le, chat]
Dec = ph(sn(art([le]), nc([chat])), sv(manger([mange]),sn(art([le]), nc([chat])))) ;
Ph = [le, chat, mange, la, souris]
Dec = ph(sn(art([le]), nc([chat])), sv(manger([mange]), sn(art([la]), nc([souris])))) ;
Ph = [le, chat, guette, le, chat]
Dec = ph(sn(art([le]), nc([chat])), sv(guetter([guette]), sn(art([le]), nc([chat])))) ;
Ph = [le, chat, guette, la, souris]
Dec = ph(sn(art([le]), nc([chat])), sv(guetter([guette]), sn(art([la]), nc([souris])))) ;
Ph = [le, chat, mange]
Dec = ph(sn(art([le]), nc([chat])), sv(manger([mange]))) ;
Ph = [le, chat, guette]
Dec = ph(sn(art([le]), nc([chat])), sv(guetter([guette]))) ;
Ph = [la, souris, mange, le, chat]
Dec = ph(sn(art([la]), nc([souris])), sv(manger([mange]), sn(art([le]), nc([chat])))) ;
Ph = [la, souris, mange, la, souris]
Dec = ph(sn(art([la]), nc([souris])), sv(manger([mange]), sn(art([la]), nc([souris])))) ;
Ph = [la, souris, guette, le, chat]
Dec = ph(sn(art([la]), nc([souris])), sv(guetter([guette]), sn(art([le]), nc([chat])))) ;
Ph = [la, souris, guette, la, souris]
Dec = ph(sn(art([la]), nc([souris])), sv(guetter([guette]), sn(art([la]), nc([souris])))) ;
Ph = [la, souris, mange]
Dec = ph(sn(art([la]), nc([souris])), sv(manger([mange]))) ;
Ph = [la, souris, guette]
Dec = ph(sn(art([la]), nc([souris])), sv(guetter([guette]))) ;