INTRODUCTION A PROLOG

 ET AU TRAITEMENT DU LANGAGE NATUREL

 

 

 

 

 

A. Michiels

 Université de Liège, Liège


Table des matières

Avant-propos
Introduction: notions d'algorithme et de programme

Chapitre 1 L'unification

Chapitre 2 La gestion des listes

Chapitre 3 Les structures de données

Chapitre 4 Listes et récursivité

Chapitre 5 Les réseaux sémantiques

Chapitre 6 Automates non déterministes à nombre fini d'états

Chapitre 7 Réseaux de transition récursifs

Chapitre 8 Analyse syntaxique descendante

Chapitre 9 Méta-interprètes et analyse ascendante

Chapitre 10 Analyse et génération de variantes morphologiques

Chapitre 11 Utilisation de macros pour la gestion du vocabulaire

Chapitre 12 Le traitement des dépendances de longue distance

Annexe 1 De la chaîne de caractères à la liste de mots

Annexe 2 Le pretty-printer PRPR

Annexe 3 La notation DCG

Notes bibliographiques

 


Avant-propos

                Ces toutes dernières années, un consensus semble se dégager quant aux outils à utiliser dans la recherche en traitement automatique du langage naturel (NLP: Natural Language Processing). Il s'articule autour de la notion de grammaire d'unification. Au coeur de cette notion on trouve bien sûr le processus d'unification, et il est donc naturel que Prolog, dans lequel le mécanisme d'unification est central, soit très fréquemment utilisé comme langage pour le développement de prototypes dans ce domaine.

            Le linguiste intéressé par le traitement informatique du langage naturel voudra donc tout naturellement se familiariser avec ce langage de programmation, d'autant plus qu'il s'agit d'un langage très ouvert, qui permet assez aisément l'écriture de méta-interprètes (voir Chapitre 9), grâce auxquels on peut enrichir le langage pour en faire un outil particulièrement bien adapté à la formulation et la mise à l'épreuve d'hypothèses linguistiques.

            Il existe déjà un certain nombre d'introductions à Prolog, en anglais mais aussi en français. Il existe également des introductions à Prolog et au traitement du langage naturel, dont deux excellentes, Pereira et Shieber 1987 et Gazdar et Mellish 1989 (voir Notes bibliographiques).

            Cet ouvrage n'est donc pas original par le sujet qu'il aborde. Il l'est peut-être par son approche, que j'ai voulue très didactique. En effet, il se base sur les notes que j'utilise dans mon enseignement à l'université de Liège, dans le cadre du cours intitulé Traduction automatique et traduction assistée par ordinateur, dont il représente un volet. Il ne s'agit pas ici de faire le tour des applications de Prolog dans le domaine du traitement du langage naturel, mais bien plutôt d'exposer de manière claire les concepts, stratégies et mécanismes fondamentaux pour pouvoir utiliser Prolog dans l'analyse linguistique.

            Je n'ai donc pas non plus tenté d'illustrer tous les aspects de Prolog. J'ai préféré m'en tenir à ceux que j'estime cruciaux dans le domaine choisi, et même si les exemples de programme ne concernent pas tous le traitement du langage naturel, ce dernier a toujours servi de pierre de touche dans le choix de la matière à exposer, et des endroits où placer les accents.

 

Introduction: notions d'algorithme et de programme

            L'ordinateur est une machine à traiter l'information, et celle-ci, quelle que soit sa représentation dans les registres de la machine, n'est pas nécessairement de nature numérique, même s'il y a une tendance naturelle à associer informatique et calcul. Si au niveau le plus profond, l'information (données ET programme) se présente sous la forme d'une série de BITS (Binary Digits), c'est-à-dire de 0 et de 1, d'ON/OFF, d'OUVERT/FERME, en deux mots de distinctions binaires, rien ne force l'utilisateur à adopter cette vue très réductionniste de l'information (on pourrait aussi bien considérer le cerveau humain uniquement sous l'angle des réactions physico-chimiques qui s'y déroulent, et tenter de faire l'économie du mot pensée...).

            En fait, l'utilisateur est débarrassé de la nécessité de voir les choses en termes binaires par toute une série de couches protectrices (en fait du logiciel, des programmes) qui permettent une perception beaucoup plus abstraite (dégagée des contraintes du matériel) des données et du processus de transformation que le programme va leur faire subir.

            Traiter l'information, c'est donc appliquer un programme (de l'information) à des données (également de l'information). Ce qui fait la force des ordinateurs, c'est la capacité à considérer les programmes et données comme essentiellement la même chose, c'est-à-dire de l'information. C'est ce qui permet à l'ordinateur d'être une machine universelle: pour autant qu'on puisse lui communiquer des programmes "de l'extérieur" (c'est-à-dire que son savoir ne soit pas entièrement câblé - HARD-WIRED -, inscrit dans ses circuits), on pourra lui faire exécuter toute tâche qui consiste à transformer de l'information (toute tâche intellectuelle).

            C'est là bien sûr une vue très optimiste des possibilités d'exploitation de la machine par l'homme. La difficulté provient du fait que la transformation de l'information envisagée doit être minutieusement décrite, d'une manière qui ne laisse aucune place à des interprétations diverses. En d'autres termes, on dira que la transformation de l'information doit être spécifiée dans un ALGORITHME et qu'ensuite cet algorithme doit être programmé dans un langage de programmation (PROGRAMMING LANGUAGE) que la machine est à même de comprendre, c'est-à-dire de traduire en une suite d'instructions élémentaires de l'exécution desquelles elle peut se charger. Nous nous intéresserons ici uniquement aux langages évolués (HIGH LEVEL LANGUAGES) dont les primitives représentent l'agencement d'un grand nombre d'instructions machine, c'est-à-dire directement exécutables par la machine.

            Il existe de nombreux langages de programmation, même si l'on s'en tient aux langages évolués. Dans cet ouvrage, nous étudierons PROLOG, qui est le premier langage déclaratif (il date des années soixante-dix). On oppose langage déclaratif et langage procédural. Que recouvre cette distinction?

            Dans un langage procédural, un programme est une série d'instructions qui indiquent à la machine COMMENT elle doit procéder pour résoudre un problème. Quel que soit le niveau d'abstraction que permet la machine abstraite définie par le langage de programmation, c'est toujours en termes d'opérations à effectuer que le programmeur raisonne.

            Dans un langage déclaratif, le programmeur ne se préoccupe plus - ou plus précisément, plus exclusivement - de la marche à suivre pour résoudre le problème. Il se préoccupe surtout de définir les objets manipulés par son programme, et les relations qui existent entre ces objets, ou dont il veut prouver l'existence. Le mécanisme d'exécution d'un langage déclaratif passera en revue toutes les solutions du problème, c'est-à-dire toutes les configurations d'objets qui satisfont la ou les relations  recherchées.

            Bien sûr, il existe des problèmes qui se pensent plus aisément en termes procéduraux, et d'autres qui se conçoivent mieux en termes déclaratifs. Toutefois, on peut dire d'une manière générale que l'approche déclarative est très fructueuse dans les applications qui relèvent de l'intelligence artificielle, et notamment le traitement du langage naturel. Dans la suite de cet ouvrage, nous tenterons de le montrer à l'aide de petits programmes rédigés en Prolog.

            Nous avons choisi Arity Prolog, développé par Arity Corporation[1]. Arity Prolog est disponible sous DOS et sous OS/2, et il respecte la syntaxe standard de Prolog, dite d'Edimbourg, qui est celle exposée et exemplifiée dans Clocksin et Mellish 1981.

            Revenons à la notion d'algorithme, tout à fait capitale pour notre propos. Algorithmiser une tâche, c'est  la décomposer en sous-tâches, et ces sous-tâches en sous-sous-tâches, et ainsi de suite, de manière à obtenir des instructions élémentaires (que l'on peut accomplir sans intuition ni grande intelligence) dont l'agencement est parfaitement explicite et dépourvu de toute ambiguïté. Il est bien entendu que l'utilisateur peut faire usage des couches protectrices mentionnées ci-dessus: élémentaire ne veut pas dire DIRECTEMENT exécutable par la machine. En fait, le niveau de spécification de détail requis par l'algorithme dépendra en partie du langage de programmation dans lequel on se propose de traduire cet algorithme. Mais une chose est certaine: une description de tâche qui convient à un être humain convient rarement à la machine, car elle laisse en général beaucoup trop de choses dans le vague, se fiant aux facultés d'intelligence et d'intuition dont les humains sont normalement dotés.

            Par exemple, le langage que nous utilisons pour décrire des tâches aux autres membres de notre espèce, à savoir le langage dit naturel (NATURAL LANGUAGE), par opposition aux langages artificiels (ARTIFICIAL LANGUAGES) comme les langages de programmation, est  entaché de nombreuses ambiguïtés que nous ne percevons même pas, car elles sont levées par le contexte situationnel ou linguistique sans que nous en ayons conscience. Ce sont des entreprises telles que la traduction automatique et le développement d'interfaces en langage naturel pour la consultation de bases de données (NATURAL LANGUAGE FRONT ENDS) qui nous ont rendus sensibles à l'ambiguïté dont le langage naturel est chargé. Dans la deuxième partie de cette introduction, nous examinerons plus en détail certains des problèmes associés au traitement du langage naturel, et nous esquisserons des ébauches de solution à certains d'entre eux.

            Qu'on ne se méprenne pas: si l'algorithme spécifie la tâche à exécuter d'une manière si univoque et détaillée qu'il peut être mis en oeuvre sans faire appel à l'intuition ou à l'intelligence, sa conception même requiert elle un haut degré d'intelligence. Les plus beaux algorithmes sont merveilleusement simples, mais c'est une simplicité et une élégance qui ne doivent pas laisser croire qu'ils s'écrivent sur un coin de table entre la poire et le fromage...

            Le décomposition d'une tâche complexe en sous-tâches plus simples est au coeur même de la caractérisation de l'algorithme. La métaphore des poupées russes est bien à sa place ici, surtout si l'on considère des algorithmes récursifs (souvent les plus élégants), c'est-à-dire des algorithmes qui font appel à eux-mêmes dans leur propre définition.

            Nous commencerons par un algorithme tout simple et connu depuis longtemps (la paternité en est attribuée à Euclide). Il s'agit du calcul du plus grand commun diviseur à deux nombres.

            Soit à calculer le pgcd d de deux nombres entiers x et y.

1) si x et y sont égaux, d est égal à x

2) si x est plus petit que y, alors d est le pgcd de x et de y-x

3) si x est plus grand que y, intervertir x et y (x prend la valeur de y et y prend l'ancienne valeur de x) et calculer leur pgcd.

 Exemples:

pgcd (8,8) >> d=8

pgcd (12,16) >> pgcd (12,4) >> pgcd (4,12) >> pgcd (4,8) >> pgcd (4,4) >> d=4

pgcd (3,7) >> pgcd (3,4) >> pgcd (3,1) >> pgcd (1,3) >> pgcd (1,2) >> pgcd (1,1) >> d=1

Etudions brièvement la traduction de cet algorithme en Prolog (voir Bratko 1990, p.91-92) :

/* PGCD */

/* clause 1 */

   pgcd(X,X,X).

/* clause 2 */

   pgcd(X,Y,D):-
      X<Y,
      Nouvel_y is Y-X,
      pgcd(X,Nouvel_y,D).

/* clause 3 */

   pgcd(X,Y,D):-
      X>Y,
      pgcd(Y,X,D).

Exemples d'invocation et résultats obtenus (en gras) 

?- pgcd(15,255,Pgcd).

            Pgcd = 15

?- pgcd(15,255,15).

            yes

On constate que le programme PROLOG est très proche de l'algorithme. Mais bien sûr il s'agit d'un algorithme très simple.

            Quelques paragraphes d'explication suffiront pour éclaircir la structure du programme. Nous reviendrons sur la plupart des points que nous introduisons ici.

            Le programme se compose de trois clauses, chaque clause correspondant à un des cas de figure étudiés dans l'algorithme. Voyons la structure interne d'une clause.

            Notons tout d'abord que:- peut se lire IF (si).  C'est le signe qui sépare la tête de la clause de son corps.  Quant à la virgule qui sépare les différents éléments du corps de la clause, elle joue le rôle de l'opérateur booléen AND (et logique).  Notons aussi que toute clause se termine par un point (.). Nous appelerons faits les clauses qui n'ont pas de corps, et règles celles qui en ont.

            La tête de la clause et son corps sont composés de prédicats accompagnés de leurs arguments. La syntaxe est la suivante: le prédicat est suivi de ses arguments, lesquels apparaissent séparés par des virgules. L'ensemble des arguments est placé entre parenthèses. Ainsi, dans

      pgcd(X,Y,D)

pgcd est le nom du prédicat, et (X,Y,D) est l'ensemble de ses arguments. L'arité du prédicat est son nombre d'arguments; on dira donc que pgcd est ici un prédicat d'arité 3.

            Le prédicat est la représentation en Prolog de la notion de relation[2]. Le prédicat pgcd représente la relation plus grand commun diviseur, relation qui lie trois nombres, à savoir les deux nombres dont on recherche le plus grand commun diviseur, et ce plus grand commun diviseur lui-même.

            Les clauses qui n'ont pas de corps (et où n'intervient donc pas le signe:-) seront interprétés comme des faits. Quelle que soit leur valeur de vérité dans le monde réel, Prolog les tiendra pour vrais. Par exemple, la clause

      verbe(aimer).

peut être interprétée comme suit: c'est un fait que aimer est un verbe.  Si le prédicat a une arité supérieure à 1, l'interprétation qui sera donnée du fait est entièrement affaire de convention. Par exemple, pour indiquer que aimer est un verbe de la première conjugaison, je pourrais envisager d'écrire soit

a)    verbe(1,aimer).

soit

b)    verbe(aimer,1).

1 désigne le numéro de la conjugaison. Bien sûr, ce que je ne peux pas faire, c'est écrire tantôt a, tantôt b  à l'intérieur du même programme. Je ne peux pas tabler sur un hypothétique bon sens de Prolog. La charge sémantique des prédicats résulte d'une interprétation que je leur donne, et Prolog n'en a cure. Donc, si j'écris

      verbe(aimer,1).
      verbe(1,aider).

je vais au-devant des pires ennuis. La même convention d'interprétation doit gouverner tous les usages d'un même prédicat à l'intérieur d'un programme donné. Un programme se définit lui-même comme l'ensemble de clauses que je soumets comme un tout à l'interpréteur ou au compilateur Prolog.

            Les clauses qui ont un corps (les règles) reçoivent l'interprétation suivante: la tête recevra la valeur de vérité VRAI seulement si le corps reçoit cette valeur. Le corps ne recevra cette valeur que si chacun des prédicats qui le constituent reçoit cette valeur (en effet, nous avons vu que la virgule qui sépare les éléments du corps devait être interprétée comme l'opérateur logique ET).

            On dira que Prolog tente de satisfaire un but lorsqu'il essaie de le rendre vrai. C'est ce que l'interpréteur Prolog fera avec tout but qui lui est soumis à son invite (le signe?-). Donc, lorsqu'on lui soumet  pgcd(15,255,15), il tente de prouver que la relation plus grand commun diviseur (représentée par le prédicat pgcd) relie les trois arguments 15, 255 et 15. S'il existait une clause pgcd(15,255,15) dans la base de données, Prolog conclurait immédiatement à la vérité du but, puisqu'il tient tous les faits de sa base de données pour vrais. Mais on constate que la base de données ne contient pas un tel fait. Les clauses de la base de données ont chacune une tête où apparaissent des variables (X,Y,D, etc.) et non des constantes (15, 255,15, etc.). Penchons-nous quelques instants sur cette distinction.

            Les arguments des prédicats peuvent donc être des constantes ou des variables. Les constantes ne peuvent changer de valeur en cours de programme, comme leur nom l'indique. Les variables, au contraire, peuvent prendre toutes les valeurs que l'on veut.

            Les variables doivent débuter par une majuscule (ou le signe du souligné, à savoir _), alors que les constantes doivent commencer par une minuscule.

            Le domaine d'une variable est la clause dans laquelle elle apparaît. A l'intérieur de son domaine, une variable désigne toujours la même valeur. Par exemple, dans la clause 2 de notre programme, les deux occurrences de la variable D désignent la même valeur, quelle qu'elle soit. Seule la variable muette (notée par le blanc souligné, _) n'est pas tenue de désigner une valeur unique dans son domaine. Nous y reviendrons.

            Pour satisfaire un but qui contient des variables, Prolog va donner à ces variables les valeurs qui rendent le but vrai. Notons tout de suite qu'il sera possible de lui faire trouver toutes les valeurs des variables qui rendent le but vrai.

            Examinons notre programme clause par clause. On se souvient que dans le prédicat pgcd les deux premiers arguments représentent les deux nombres dont on recherche le pgcd et le troisième argument est le pgcd lui-même.

/* clause 1 */

   pgcd(X,X,X).

            Il s'agit d'un fait. Les arguments sont tous la même variable, à savoir X. Comme nous sommes dans un seul domaine pour la variable X, ses trois instances doivent désigner la même valeur.

            Considérée du point de vue de la logique, la première clause stipule que le prédicat  pgcd est vrai quand ses trois arguments sont identiques. Vue d'une manière plus procédurale, elle stipule que si X et Y sont égaux (pour l'indiquer on utilise la même variable, à savoir X)[3] alors le pgcd (le troisième argument de la relation) est égal aux deux premiers (c'est donc aussi X).

/* clause 2 */

   pgcd(X,Y,D):-
      X<Y,
      Nouvel_y is Y-X,
      pgcd(X,Nouvel_y,D).

            Il s'agit d'une règle. Pour satisfaire un but qui y correspond (nous étudierons plus en détail cette notion de correspondance entre but et tête de règle), Prolog doit satisfaire (rendre vrai) chacun des éléments du corps de la règle, qu'il va donc considérer à leur tour comme des buts à satisfaire.

            Donnons d'abord une paraphrase rapide de cette deuxième clause: elle indique que le pgcd de X et de Y sera donné par le pgcd de X et de Nouvel_y, pour autant que X soit plus petit que Y et que le nouvel Y (Nouvel_y) soit le résultat de la soustraction Y-X. D'une manière procédurale: pour trouver le pgcd de X et de Y, si X est plus petit que Y, chercher le pgcd de X et de la différence entre Y et X.

            On a vu qu'en général les arguments d'un prédicat se plaçaient à la suite du nom du prédicat, l'ensemble étant pincé entre parenthèses, et les arguments séparés les uns des autres par des virgules. Il existe toutefois des prédicats qui prennent la forme d'opérateurs, et certains de ces opérateurs sont infixes, c'est-à-dire se placent entre leurs arguments. Nous avons un exemple ici: < est un opérateur infixe qui représente le prédicat plus_petit_que. On pourrait donc définir plus_petit_que de la manière suivante:

      plus_petit_que(X,Y):- X<Y.

            Notons que < est défini pour nous: c'est un prédicat dit prédéfini. La  nature et le nombre des prédicats prédéfinis diffèrent d'une implantation de Prolog à l'autre, mais les prédicats représentés par les opérateurs arithmétiques sont toujours disponibles.

            L'opérateur is est particulier: il joue le rôle de l'opérateur d'affectation d'une valeur à une variable, comme le fait := en Pascal ou = en C, par exemple. Il convient de ne pas le confondre en Prolog avec l'opérateur infixe =, qui lui teste l'égalité de ses deux opérandes, et renvoie donc une valeur de vérité. Donc,

      X is Y+3

affectera à X  le résultat de l'opération d'addition du contenu de la variable Y et de la constante numérique 3,

alors que

      X=3

testera si X a la valeur 3, et renverra VRAI ou FAUX selon le cas.

            Notons que dans le schéma d'interprétation que nous avons donné, X is Y+3 doit lui aussi renvoyer une valeur de vérité. Après avoir versé le résultat de l'opération Y+3 dans la variable X, il renvoie la valeur VRAI, c'est-à-dire réussit en tant que but, et l'interpréteur Prolog peut passer au but suivant.

/* clause 3 */

   pgcd(X,Y,D):-
      X>Y, pgcd(Y,X,D).

            Il s'agit ici aussi d'une règle. On peut la paraphraser de la manière suivante: le pgcd de X et de Y est le même que le pgcd de Y et de X, pour autant que X soit plus grand que Y. Ici, l'interprétation procédurale est plus claire (car c'est elle qui met en valeur l'importance de l'ordre des arguments): pour trouver le pgcd de deux nombres X et Y, si X est plus grand que Y, calculer le pgcd de Y et de X.

            Ce qui caractérise aussi bien les définitions logiques que les définitions procédurales, c'est l'usage de la récursivité, c'est-à-dire l'usage dans la définition du pgcd d'appels au prédicat  pgcd lui-même. (En d'autres termes, il apparaît à la fois dans la tête et dans le corps d'une même règle). Une telle définition ne conduit pas à un cercle vicieux: en effet, les cas où la récursivité est mise en oeuvre font évoluer les données vers le cas non récursif, c'est-à-dire ici la première clause. On veillera à ne pas donner aux prédicats des définitions récursives qui conduiraient bel et bien à un cercle vicieux, soit parce qu'il n'y aurait pas progression vers le cas non récursif, soit parce que le cas non récursif aurait été omis de la définition. Exemple:

      frere(X,Y):- frere(Y,X).

essai infructueux de définir la relation frère en se basant sur sa propriété de réflexivité.

            Pour notre deuxième exemple d'algorithme (et de programme), quittons le domaine du numérique pour nous tourner vers le traitement de chaînes de caractères (CHARACTER STRINGS). Il s'agit de déterminer l'algorithme qui permet de calculer la valeur de vérité (vrai ou faux) du prédicat prec_dans_dic (qui représente la relation précède dans le dictionnaire) dont les deux arguments sont des mots (au sens typographique: suite de caractères délimitée par un signe de ponctuation ou un blanc).

Par exemple: 

prec_dans_dic(albert,michel,vrai)
prec_dans_dic(paul,marie,faux)
prec_dans_dic(paul,pauline,vrai)
prec_dans_dic(paul,paul,faux)

            Comme le montre le dernier exemple, on conviendra que la relation n'est pas satisfaite pour deux mots identiques.

            Exactement comme dans le cas précédent, nous partirons de la prémisse qu'il existe des relations élémentaires que nous n'avons plus à définir (pensez aux opérations de soustraction et de comparaison de valeurs numériques dans le cas du calcul du pgcd). Ici, on supposera connue la relation de précédence entre les caractères de la chaîne, c'est-à-dire les lettres de l'alphabet. Par exemple, on pourra se baser sur la relation de précédence entre a et b, d et l, etc. En fait, cette relation est bel et bien une primitive des langages de programmation. En effet, chaque caractère reçoit un code numérique standard (CODE ASCII: American Standard Code for Information Interchange) et il suffit d'utiliser les opérateurs de comparaison numérique pour établir la relation de précédence entre caractères (le code ASCII de a est plus petit que le code ASCII de b; les complications proviennent du fait que les majuscules précèdent en bloc les minuscules: nous négligerons le problème en nous limitant aux minuscules).

            Notons au passage que la plupart des langages de programmation offrent comme primitive la relation de précédence, non seulement entre caractères, mais aussi entre chaînes. En d'autres termes, nous allons nous intéresser à un problème qui est déjà résolu! Il serait d'ailleurs étonnant que notre deuxième algorithme aborde un problème dont on cherche encore la solution dans les meilleurs laboratoires d'intelligence artificielle...

            On peut formuler l'algorithme comme suit.

Soit x le premier mot et y le deuxième.
Si x et y sont identiques, renvoyer la valeur FAUX.
Si la première lettre de x précède la première lettre de y, renvoyer la valeur VRAI.
Si la première lettre de x suit la première lettre de y, renvoyer la valeur FAUX.
Si la première lettre de x est identique à la première lettre de y, renvoyer la valeur de vérité qui est renvoyée par la relation prec_dans_dic entre x privé de sa première lettre et y également privé de sa première lettre.          

            A première (et même peut-être deuxième) vue, cet algorithme est correct. Et pourtant, il n'est pas à même de traiter le cas suivant:

      prec_dans_dic(albert,albertine,Solution).

EXERCICE: déterminer pourquoi. Pensez à la nécessité de sortir du cas récursif (le dernier) en faveur d'un des autres.

            Pour simplifier le problème de la traduction de cet algorithme en Prolog, nous conviendrons d'utiliser des listes de caractères pour représenter les mots en Prolog. Une liste en Prolog est un ensemble d'éléments de liste séparés par des virgules et compris entre deux crochets:

[ 'a', 'l', 'b', 'e', 'r', 't' ]

est la liste de caractères correspondant au mot albert.

            Une liste est tout simplement une suite ordonnée d'objets. Ces objets peuvent être tous les objets usuels de l'univers Prolog: nous avons rencontré jusqu'à présent les constantes et les variables. Nous aborderons des objets plus complexes dans la suite de cet ouvrage. Notons dès à présent que la longueur d'une liste n'a pas à être prédéterminée (déclarée avant l'utilisation de la liste) et que ses éléments ne doivent pas nécessairement être de même nature. Par exemple, on peut mêler constantes et variables, et une liste peut contenir des sous-listes comme éléments. Dans la liste que nous venons de mentionner, les éléments sont tous du même type, à savoir la constante caractère, dont la notation est le caractère pincé entre simples guillemets.

            Prolog dispose en standard d'un opérateur qui divise la liste en deux parties: le premier élément et la liste constituée par les autres éléments (une liste peut être vide). Cet opérateur est le signe |[4].

            Si on applique le schéma [X|Y] à la liste mentionnée ci-dessus, on obtiendra les valeurs suivantes pour les variables:

X='a'
Y=['l','b','e','r','t']

            On gardera présent à l'esprit le fait que le deuxième opérande de | désigne toujours une liste. Si on applique l'opérateur de divison de liste à une liste qui ne contient qu'un seul élément, on obtient d'une part le premier et unique élément de la liste, et d'autre part une liste qui ne contient plus rien, donc une liste vide, que l'on note tout naturellement [].

            Ainsi, appliqué à  la liste à un élément ['t'], le schéma [X|Y] donnera:

X='t'
Y=[]

            C'est donc ce type de configuration des variables que l'on obtiendra en fin de parcours de liste, par exemple lorsqu'on aura isolé le dernier caractère de la liste ['a','l','b','e','r','t'].

            Nous en savons assez pour examiner le programme Prolog qui traduit notre algorithme.

 

/* PRECDIC: l'ordre lexicographique */

/* un mot ne se précède pas lui-même */

   prec_dans_dic(X,X,faux):-!.

/* il est vrai qu'un mot X précède un autre mot Y si la première lettre de X

     précède la première lettre de Y */

   prec_dans_dic(X,Y,vrai):-
      premlettre(X,Xprem),
      premlettre(Y,Yprem),
      Xprem @< Yprem.

/* il est faux qu'un mot X précède  un autre mot Y si la première lettre de X

     suit la première lettre de Y */

   prec_dans_dic(X,Y,faux):-
      premlettre(X,Xprem),
      premlettre(Y,Yprem),
      Xprem @> Yprem.

/* si deux mots X et Y commencent par la même lettre, alors il faut comparer leurs restes respectifs pour savoir si X précède Y */

    prec_dans_dic(X,Y,Valeur):-
      premlettre(X,Xprem),
      premlettre(Y,Yprem),
      Xprem=Yprem,
      reste(X,ResteX),
      reste(Y,ResteY),
      prec_dans_dic(ResteX,ResteY,Valeur).

/* la liste vide précède n'importe quelle liste */

    prec_dans_dic([],_,vrai).

/* prédicats utilitaires */

  /* isoler le premier élément d'une liste */

    premlettre([Prem|_],Prem).

/* obtenir une liste privée de son premier élément */

    reste([_|Reste],Reste).

 

            Notons tout d'abord que l'opérateur infixe @< désigne la relation de précédence dans l'ordre alphabétique. Son inverse est bien sûr @>.

            Pour bien comprendre ce programme, il faut être très attentif à la distinction entre CONSTANTES et VARIABLES.  On distinguera donc très clairement les valeurs vrai et faux (des constantes) de la variable Valeur, telle qu'elle est utilisée dans la quatrième clause du prédicat prec_dans_dic. Valeur est une variable qui recevra une des deux valeurs vrai/faux.

     Examinons tout d'abord prec_dans_dic à l'oeuvre.

Exemples d'invocation et résultats obtenus (en gras) 

?- prec_dans_dic([o,i,s,e,a,u],[o,s,e],Quid).

            Quid = vrai

Ici, l'appel à prec_dans_dic contient la variable Quid. Pour satisfaire le but, l'interpréteur Prolog lui attribue la valeur vrai et nous communique cette liaison.

?- prec_dans_dic([o,i,s,e,a,u],[o,s,e],faux).

            no

Ici, l'appel ne contient pas de variable: faux est une constante. L'interpréteur Prolog fonctionne ici comme vérificateur. Il répond no car la valeur du troisième argument devrait être vrai pour que la relation prec_dans_dic soit vraie, comme le montrait le premier exemple d'invocation. Lorsque Prolog échoue dans sa tentative de satisfaire un but, il répond no. (= Il n'y a pas/plus de solution).

?- prec_dans_dic([a,l,b,e,r,t],[a,l,b,e,r,t,i,n,e],Solution).

            Solution = vrai

On voit ici que le nom de la variable importe peu: Solution est interchangeable avec Quid.

            Le prédicat central prec_dans_dic a trois arguments: les deux premiers sont les deux mots à comparer, c'est-à-dire deux chaînes de caractères, ou, pour être plus précis, deux listes de caractères, en conformité avec le schéma de liste que nous avons décrit plus haut.

            Le prédicat premlettre a pour fonction de renvoyer la première lettre (son deuxième argument) d'une liste de lettres (son premier argument). Quant au prédicat reste, il prend comme argument deux listes de caractères: son deuxième argument est la liste constituée par son premier argument privé de sa tête.

            Ces choses étant dites, on peut plus aisément constater que le programme, ici encore, est assez proche de l'algorithme. On notera l'utilisation du blanc souligné comme variable: c'est ce qu'on appelle la variable muette ou variable anonyme (DON'T CARE VARIABLE / ANONYMOUS VARIABLE), c'est-à-dire une variable dont la valeur ne nous intéresse pas.

            Examinons la clause

     prec_dans_dic ([],_,vrai).

            Elle nous dit en fait que la liste vide précède n'importe quelle autre liste. Cette autre liste n'a pas d'intérêt pour nous. Nous ne nous donnons pas la peine de la nommer.

            On aura compris que la clause que nous venons d'examiner permet précisément de traiter le cas albert-albertine. Lorsque la comparaison lettre par lettre arrivera à la fin du mot albert, il restera la liste vide, et celle-ci précède la queue du mot albertine à ce stade, à savoir ine.

            Enfin, on remarquera la grande simplicité de l'expression - en Prolog - des deux manipulations de liste spécifiées par premlettre et reste.

            Bien que l'algorithme et le programme qui permettent de calculer la valeur de vérité de la relation de précédence lexicographique soient très simples, ils laissent entrevoir le niveau de complexité que peuvent atteindre des algorithmes et programmes qui visent l'informatisation de tâches infiniment plus complexes, comme la traduction par exemple.

            Et cependant, la stratégie de parcellisation des tâches permet de grandes choses. Le problème plus fondamental auquel se heurte la traduction automatique est qu'on ne connaît pas d'algorithme satisfaisant de l'opération de traduction pour les langues naturelles. On travaille donc par approximation, en utilisant des algorithmes dont on sait qu'ils ne sont pas à la hauteur de la tâche, car ils négligent des facteurs importants, mais que précisément on ne parvient pas à encapsuler dans une procédure univoque et libre de tout appel à l'intuition et à l'intelligence.

            Pour montrer le fossé qui sépare des algorithmes simples de traduction de ceux qu'il faudrait mettre en oeuvre pour automatiser la traduction d'une langue naturelle vers une autre, nous prendrons comme exemple la traduction mot à mot, qui conviendrait si les mots ne déterminaient en aucune façon l'environnement grammatical et lexical dans lequel ils s'insèrent.

            On a parfois l'impression que pour des phrases très simples, on peut faire du mot à mot. Prenons l'exemple bien connu du chat et du paillasson:

            the cat is on the mat

            On a les équivalences suivantes répertoriées dans un 'dictionnaire':

the = le
cat = chat
is = est
on = sur
mat = paillasson

            Le mot à mot donne donc:

            le chat est sur le paillasson

            L'algorithme est simple à énoncer. Soient deux listes de mots x et y. y est la traduction de x si elle est le résultat d'un parcours de x avec traduction de chaque élément de x en accord avec un dictionnaire qui apparie à chaque mot de x sa traduction dans la langue cible, à savoir celle de y.

            La mise en oeuvre de l'algorithme en PROLOG est immédiate (cf. Sterling et Shapiro 1986, p.115-116). Nous dirons qu'il existe une relation traduire(Chaîne1, Chaîne2) s'il existe une relation traduire_mot(Mot1, Mot2) pour tous les mots de Chaîne1 et si Chaîne2 est la concaténation de tous les Mot2 obtenus par traduire_mot.

            En Prolog:

   /* CATMAT */

/* on traduit le premier mot à l'aide de traduire_mot et on fait un appel récursif à traduire pour traduire le reste */

   traduire([First|Remainder],[Premier|Reste]):-
      traduire_mot(First,Premier),
      traduire(Remainder,Reste).

/* rien se traduit par rien; ou encore, la liste vide se traduit par la liste vide */

   traduire([],[]).

/* le dictionnaire bilingue est un ensemble de faits construits autour du prédicat traduire_mot */

   traduire_mot(the,le).
   traduire_mot(cat,chat).
   traduire_mot(is,est).
   traduire_mot(on,sur).
   traduire_mot(mat,paillasson).

   /* Tout ce qui est compris entre barre oblique - astérisque et astérisque - barre oblique est un commentaire et est négligé par Prolog. Nous allons donc utiliser cette possibilité pour introduire dans le programme d'autres traductions pour certains mots de la phrase. Il suffit de faire disparaître les indications de commentaire -UNCOMMENT- pour que le programme les prenne en compte */

   /* traduire_mot(the,la).
      traduire_mot(cat,chatte).
      traduire_mot(mat,carpette). */

Exemples d'invocation et résultats obtenus (en gras) 

?- traduire([the,cat,is,on,the,mat],French).

            French = [le,chat,est,sur,le,paillasson]

?- traduire([the,cat,is,on,the,mat],[le,chat,est,sur,le,paillasson]).

            yes

Il n'y a pas de variable dans ce but. Le rôle de Prolog est donc uniquement de nous renseigner sur une valeur de vérité: est-il bien vrai que [the, cat, is, on, the, mat] et [le, chat, est, sur, le, paillasson] sont liés par la relation de traduction représentée par le prédicat traduire? La réponse est yes.

?- traduire(English, [le, chat, est, sur, le, paillasson]).

            English = [the, cat, is, on, the, mat]

 

            Quelques mots d'explication.

            Le prédicat traduire s'applique à deux phrases, alors que le prédicat traduire_mot s'applique à deux mots. On se persuadera que les noms des variables n'ont pas d'importance en  intervertissant l'anglais et le français dans la définition de la relation traduire.

            On remarquera la clause de traduire qui stipule que la traduction d'une liste vide est une liste vide. C'est elle qui s'applique lorsqu'on arrive au bout des listes.

            On découvrira avec plaisir que le programme traduit aussi bien (!!!) du français vers l'anglais que vice-versa. Telle qu'elle est définie ici, la traduction est une relation logique et son application est bi-directionnelle.

EXERCICE: essayer de déterminer ce qui se passe lorsqu'on libère les clauses traduire_mot additionnelles de leur appartenance à un champ commentaires. Vérifier ou infirmer les hypothèses en les libérant réellement.


 

PROLOG ET LA PROGRAMMATION LOGIQUE

 

 

            Nous allons à présent passer à une étude plus détaillée de Prolog. Nous mettrons l'accent sur le traitement du langage naturel, mais nous nous permettrons des incursions dans d'autres domaines pour expliquer plus simplement certains points fondamentaux. Nous commencerons par une diversion mathématique.

Chapitre 1 L'unification

            Nous étudierons ici deux relations. La première est représentée par le prédicat magique, prédicat à un  seul argument. Cette relation sera vraie pour tout entier qui possédera  la propriété d'être magique.

            Un nombre entier est dit magique si la série d'opérations suivantes conduit inexorablement à 1:

1) si le nombre (ou le résultat obtenu par l'opération 2) est pair, on le divise par 2;

2) si le nombre (ou le résultat obtenu par l'opération 1) est impair, on le multiplie par 3 et on ajoute 1.

            Par exemple, 13 est magique en vertu de la séquence d'opérations:

a)         (13 * 3) +1 = 40          (opération 2)
b)         40 / 2 = 20                   (opération 1)
c)         20 / 2 =  10                  (opération 1)
d)         10 / 2 = 5                     (opération 1)
e)         (5 * 3) + 1 = 16           (opération 2)
b)         16 / 2 = 8                     (opération 1)
c)         8 / 2 =  4                      (opération 1)
d)         4 / 2 = 2                       (opération 1)
e)         2 / 2 = 1                       (opération 1).

            La deuxième relation sera représentée par le prédicat divisible, d'arité 2. Elle sera vraie si le premier argument est divisible par le second.

            Rappelons que c'est le concepteur de programme qui donne le sens voulu aux prédicats qu'il définit. Par exemple, je pourrais définir le prédicat  divisible de telle sorte que la relation soit vraie si le second argument est divisible par le premier. Il me suffirait de donner la définition adéquate.

            Considérons tout d'abord le prédicat divisible, dont la définition est très simple. Dividende est divisible par Diviseur, si le reste de la division de Dividende par Diviseur est 0. Arity Prolog offre comme prédéfini l'opérateur mod (modulo), qui permet précisément d'obtenir le reste de la division de deux entiers. Il suffit donc de tester si  Dividende mod Diviseur est égal à 0 pour savoir si Dividende est divisible par Diviseur. Nous obtenons donc:

divisible(Dividende,Diviseur):-
             (Dividende mod Diviseur)  =:= 0. 

(=:= est prédéfini et infixe; il  teste l'égalité de deux valeurs numériques)

            Dividende et Diviseur sont des variables. On se souvient qu'en Prolog les noms de variables doivent commencer par une majuscule ou un blanc souligné (_).

            On peut considérer le prédicat divisible sous deux aspects: le procédural et le déclaratif.

            Aspect procédural: pour découvrir si Dividende est divisible par Diviseur, effectuer la division, et examiner le reste: s'il est égal à 0, conclure que la propriété est vraie.

            Aspect déclaratif: Dividende est divisible par Diviseur si le reste de la division de Dividende par Diviseur est égal à 0.

            Considérons à présent le paquet de clauses définissant le prédicat magique. Le paquet de clauses d'un prédicat est l'ensemble des clauses qui ont un appel à ce prédicat pour tête. Il y a trois clauses qui se rapportent à ce prédicat. Commençons par les citer:

/* Clause 1 */

  magique(1).

/* Clause 2 */

  magique(Nombre):-
       divisible(Nombre,2),
       Reduction is Nombre//2,
       write(Reduction),
       tab(1),                   /* tab(1) insère un blanc */
       magique(Reduction).

/*Clause 3 */

  magique(Nombre):-
       Augmentation is (Nombre*3)+1,
       write(Augmentation),
       tab(1),
       magique(Augmentation).

            La première est un fait: magique (1). On peut le paraphraser par: c'est un fait que 1 a la propriété magique. C'est ce fait qui est rencontré lors de la terminaison de l'algorithme. Mais il faut dire ici qu'il n'y a aucune garantie de terminaison de l'algorithme. En effet, si l'opération 1 rapproche la séquence de 1, l'opération 2 l'en éloigne. On ne peut que soupçonner que tous les entiers positifs sont magiques; on ne sait pas le prouver.

            Les deux autres clauses pour le prédicat magique sont, comme la clause pour le prédicat divisible examinée plus haut, des règles.

            Examinons la première.

  magique(Nombre):-
       divisible(Nombre,2),
       Reduction is Nombre // 2,
       write(Reduction),
       tab(1),                   /* tab(1) insère un blanc */
       magique(Reduction).

            Elle nous dit qu'un nombre Nombre est magique si les cinq éléments du corps de la règle sont tous satisfaits comme buts; en effet on se souvient que la virgule qui les sépare est la notation Prolog pour l'opérateur logique AND.

            Le premier but teste la divisibilité de Nombre par 2. C'est tout naturellement  un appel au prédicat divisible avec comme arguments le nombre Nombre et le diviseur 2:

divisible(Nombre,2) qui sera satisfait si Nombre est divisible par 2.

            Pour établir la vérité de cette assertion, la machine abstraite Prolog fera appel à la clause définissant le prédicat divisible. Cet appel se fera en établissant une relation entre les objets Nombre et 2 dans l'appel à la clause, et Dividende et Diviseur dans la définition de la clause. Nous verrons dans quelques instants comment cette correspondance s'établit.

            Les variables ont pour domaine (SCOPE) la clause dans laquelle elles sont employées. Il n'y a donc aucune obligation d'utiliser le même nom de variable dans la clause d'appel et la clause de définition. On aurait pu avoir:

magique(Nombre):-
            divisible(Nombre,2)
            ...

et

divisible(X,Y):-        (X mod Y) =:= 0.

            C'est la position des variables qui permet la liaison entre les clauses. On aurait donc eu liaison entre Nombre et X d'une part, et 2 et Y d'autre part.

            Le deuxième but est satisfait par l'affectation à une variable Reduction du résultat de la division entière de Nombre par 2: Reduction  is Nombre // 2 (// est l'opérateur de division entière).

            D'où provient cette variable Reduction? Elle n'existe pas lors de l'appel à la clause magique (Nombre). Elle est créée par l'équation elle-même. Il y a donc ici un aspect procédural clair: diviser Nombre par 2 et verser le résultat dans la variable Reduction (rappelons que l'opérateur prédéfini is réalise  l'opération d'assignation d'une valeur à une variable). Toutefois, on sait que le prédicat is renvoie néanmoins la valeur de vérité vrai pour indiquer qu'il est satisfait.

            Le but suivant a une interprétation  encore plus procédurale. En fait, il n'a pas de sens déclaratif. En quoi l'écriture du contenu de la variable Reduction contribue-t-elle à la valeur de vérité (TRUTH VALUE) de la clause magique(Nombre)? En rien. Ce prédicat prédéfini d'écriture, write, est toujours vrai. On lui affecte cette valeur de vérité simplement pour qu'il ne vienne pas perturber la valeur de vérité de l'ensemble du corps de la règle, en d'autres termes pour qu'il ne perturbe pas le processus de satisfaction de la règle.

            Un prédicat tel que write  est donc intéressant pour l'opération qu'il effectue, et non pour sa valeur de vérité (vrai/faux). On dit de ces prédicats qu'ils sont importants pour leurs effets de bord (SIDE EFFECTS), plutôt que leur valeur de vérité.

            La même remarque s'applique à tab(1), qui écrit un blanc sur le périphérique de sortie, et réussit trivialement.

            Le dernier but est un appel récursif au prédicat magique. Pour que Nombre soit magique, il faut que Reduction le soit également: magique(Reduction).

           La clause qui nous permet de sortir des appels récursifs est bien sûr la première, le fait qui établit que 1 est magique.

            Considérons la troisième clause magique:

  magique(Nombre):-

       Augmentation is (Nombre*3)+1,
       write(Augmentation),
       tab(1),
       magique(Augmentation).

             Augmentation prend ici la valeur de (Nombre*3)+1. Pour le reste, la clause est semblable à la précédente.

            Pour bien comprendre le programme, il faut se rappeler comment la machine abstraite explore les faits et applique les règles. Elle le fait dans l'ordre normal de la lecture, c'est-à-dire de haut en bas et de gauche à droite.

            Pour interroger la machine abstraite sur la valeur de vérité d'une relation (ou pour obtenir d'elle toutes les valeurs des variables qui rendent cette relation vraie), on a vu qu'on lui soumettait la relation sous forme de but (GOAL), c'est-à-dire en réponse à l'invite (?-) de l'interpréteur Prolog.

    

            Si le but ne comporte pas de variable, la machine abstraite renseignera sur sa valeur de vérité. Elle renverra la valeur yes ou  no selon le cas.

            Si le but comporte des variables, on pourra obtenir de la machine abstraite Prolog toutes les valeurs des variables qui satisfont la relation présentée comme but, c'est-à-dire la rendent vraie.

 

            Lors de l'entrée d'un but  tel que magique(345), la machine teste d'abord la première clause, qui est le fait: magique(1). Ce fait ne s'applique pas. Qu'est-ce qu'il faut entendre par là au juste?

            Le mécanisme fondamental de Prolog est  l'UNIFICATION. Pour établir la vérité d'un but, Prolog tente de l'unifier avec les faits et les têtes des règles qui se rapportent à ce but. Nous aurons l'occasion de revenir sur le mécanisme d'unification. Pour le moment, il faut savoir que:

1) une constante ne peut être unifiée qu'avec elle-même

            Cette propriété est responsable de l'échec de l'unification de magique(345) (le but à évaluer par la machine abstraite) et magique(1) (le premier fait).

2) une variable peut s'unifier à n'importe quoi

            Mais une fois qu'une variable est liée à une valeur par unification, on dit qu'elle est instanciée ou liée (INSTANTIATED / BOUND) et elle a alors cette valeur partout où elle apparaît dans sa clause (qui, rappelons-le, est son domaine). Nous verrons plus tard comment elle peut perdre cette valeur.

            Revenons à notre but: magique(345). L'unification avec la première clause ayant échoué, la machine abstraite se tourne vers la seconde clause du paquet de clauses pour le prédicat magique. C'est également l'unification qui est responsable de ce choix: magique(345) s'unifie avec magique(Nombre) car les deux prédicats magique s'unifient: même nom, et même nombre d'arguments qui s'unifient chacun à leur tour - ici il n'y en a qu'un: la variable Nombre va s'unifier avc la constante 345).

             La machine abstraite va donc tenter de satisfaire le but magique(345) à l'aide de la première règle.

            Pour satisfaire un but à l'aide d'une règle, il faut que le but et la tête de règle soient unifiables et que tous les éléments du corps de la règle (considérés à leur tour comme des buts à satisfaire) soient satisfaits: ici encore, l'exploration se fera de haut en bas et de gauche à droite, et le mécanisme fondamental sera l'unification.

            La machine abstraite tentera donc de satisfaire le but divisible(345,2), puisqu'il s'agit du premier but dans  la règle à satisfaire.

            Par unification, la machine abstraite portera son attention vers la clause qui définit le prédicat divisible, et par unification, Dividende y vaudra 345 et Diviseur 2. Ce but échouera. Cet échec forcera l'échec de la première règle de magique pour la valeur concernée, puisque un des éléments du corps de la règle n'a pas pu être satisfait.

            Toutefois, l'unification du but de départ (magique(345)) est aussi possible avec la deuxième règle, qui sera à présent tentée, conformément au mécanisme d'exploration de haut en bas et de gauche à droite.

            La satisfaction de cette règle conduit à la création d'une variable Augmentation, qui vaudra: 345 * 3 + 1, à savoir 1036. Le nouveau but à satisfaire (après l'écriture de 1036 à l'écran, but qui réussira de manière triviale) sera à présent magique(Augmentation), avec Augmentation liée à la valeur 1036.

            Le procédé reprend dès lors au début pour ce nouveau but; l'unification avec le fait échouera, la satisfaction de la première règle conduira à un nouveau but, à savoir magique(518) et ainsi de suite jusqu'au but magique(1), qui réussira par unification avec le fait.

            Tous les buts ayant été satisfaits, Prolog indiquera la satisfaction du but de départ en annonçant yes.

            On trouvera ci-dessous le programme magique dans sa totalité, pour faciliter les références.  

 

/*   MAGIQUE */

/* le fait */

  magique(1).

/* les deux règles */

/* on se rapproche de 1 */

  magique(Nombre):-
       divisible(Nombre,2),
       Reduction is Nombre//2,
       write(Reduction),
       tab(1),                   /* tab(1) insère un blanc */
       magique(Reduction).

/* on s'éloigne de 1 */

  magique(Nombre):-
       Augmentation is (Nombre*3)+1,
       write(Augmentation),       tab(1),
       magique(Augmentation).

/* la clause pour le deuxième prédicat; il s'agit d'une règle */

  divisible(Dividende,Diviseur):-
         (Dividende mod Diviseur) =:= 0.

      /* =:= teste l'égalité de deux valeurs numériques */

    

Exemples d'invocation et résultats obtenus (en gras) 

?- magique(17).

            52 26 13 40 20 10 5 16 8 4 2 1
            yes

 

Chapitre 2 La gestion des listes

            Nous allons étudier le programme NOTES, qui va nous permettre d'approfondir notre compréhension du mécanisme d'unification, et va nous faire découvrir la manière dont Prolog gère la LISTE, une structure de données extrêmement intéressante.

            Le propos du programme NOTES est de déterminer, sur base des notes d'un étudiant, si ce dernier réussit sans délibération.

            Pour rendre le programme abordable et quelque peu facétieux, nous conviendrons des conditions de réussite ci-dessous.

            Un étudiant réussit sans délibération si

1) il obtient 12 de moyenne et n'a pas d'échec (pas de note inférieure à 10)

ou si  

2) il obtient 16 ou plus en informatique.

            De plus, nous présenterons sous forme de FAITS (au sens prologien du terme) la réussite de certains étudiants, pour bien montrer les interactions entre faits et règles.

            Nous aurons trois types de faits, qui constitueront la base de données de notre programme:

1) qui a réussi d'office (faits pour le prédicat reussit);
2) quelle est la note pour un étudiant donné dans un cours donné (trois arguments: nom de l'étudiant, libellé du cours, note obtenue; faits pour le prédicat note; le paquet de clauses pour ce prédicat ne contient que des faits, pas de règles; on dit qu'il s'agit d'un prédicat de base de données);
3) qui sont les étudiants (également un prédicat de base de données).

            Voici un exemple de chaque type de faits:

1)  reussit(pierre).
2)  note(jean,informatique,16).
3)  etudiant(jean).

            Citons ici en vrac les règles que nous utiliserons. Nous les examinerons en détail dans le reste de ce chapitre:

  reussit(Etudiant):-
                  etudiant(Etudiant),
                  notemoyenne(Etudiant,Moyenne),
                  Moyenne >= 12,
                  not(echoue(Etudiant)).

  reussit(Etudiant):-
                  etudiant(Etudiant),
                  note(Etudiant,informatique,Note),
                  Note >= 16.

  echoue(Etudiant):-
                  etudiant(Etudiant),
                  note(Etudiant,_,Note),Note<10.

  echoue(Etudiant):-
                 etudiant(Etudiant),
                 notemoyenne(Etudiant,Moyenne),
                 Moyenne < 12.

  notemoyenne(Etudiant,Valeur):-
                 findall(Note,note(Etudiant,_,Note),Listedenotes),
                 total(Listedenotes,Somme,Nombredenotes),
                 Valeur is Somme / Nombredenotes.

  total([],0,0).

  total([Tete|Queue],Somme,Nombre_el):-
        total(Queue,Nouvelle_Somme,Nouveau_Nombre_el),
        Somme is Nouvelle_Somme+Tete,
        Nombre_el is Nouveau_Nombre_el+1.

            On utilisera dans ce programme une structure de données très utile, à savoir la liste. Rappelons qu'une liste se représente en Prolog comme suit: les éléments de la liste apparaissent séparés les uns des autres par des virgules. Toute la liste est pincée entre parenthèses carrées. Une liste de notes pourrait être par exemple [ 6, 5, 20, 9.5, 3, 16, 12 ].

            Rappelons également qu'on dispose d'un opérateur très puissant (pas à première vue!) pour faciliter l'exploration des listes:  |. Ce signe sépare un certain nombre d'éléments en tête de liste du reste de la liste, la queue. La queue de la liste est elle-même toujours une liste, bien qu'elle puisse être vide, auquel cas elle sera notée [].

            Par exemple, si on unifie [X,Y|Reste] avec la liste donnée en exemple ci-dessus, on obtiendra les appariements suivants X=6, Y=5, Reste=[20, 9.5, 3, 16, 12]. On constate que Reste, la queue de liste, est elle-même une liste. Si on a la liste à un élément [5] et qu'on tente l'unification avec [X|Y] on obtient X=5, Y=[] (la liste vide).

            On remarquera le prédicat total. Il prend comme argument une liste de notes et renvoie le total des notes dans son deuxième argument, et le nombre de notes à totaliser dans son troisième argument. Par exemple, le but

total([12,13,11],Total,Nombre_de_Notes)

sera satisfait par les valeurs suivantes des variables:

Total=36, Nombre_de_Notes=3.

            Essayez ce but. A l'exécution, on peut soumettre comme but n'importe quel prédicat. Cette propriété aide grandement la mise au point des programmes, car on peut tester chaque prédicat séparément, et donc adopter la méthode des "boîtes noires": une fois qu'un prédicat a été bien mis au point, on peut lui faire confiance et le considérer comme une "boîte noire", qui accomplit de manière fiable ce qu'on lui demande de faire (si on adopte une vue procédurale des choses).

            Examinons le prédicat  reussit, défini par les clauses suivantes:

/* des faits */

  reussit(pierre).
  reussit(paul).

/* des règles */

/* 1 */

  reussit(Etudiant):-
                  etudiant(Etudiant),
                  notemoyenne(Etudiant,Moyenne),
                  Moyenne >= 12,
                  not(echoue(Etudiant)).

/* 2 */

  reussit(Etudiant):-
                  etudiant(Etudiant),
                  note(Etudiant,informatique,Note),
                  Note >= 16.

            Le prédicat reussit est un paquet de 4 clauses, dont les deux premières sont des faits: c'est un fait que pierre a réussi, et c'est un fait que paul a réussi (pourquoi pas de majuscules?). Ici, en quelque sorte, je ne me soucie pas des raisons de leur réussite, et Prolog ne s'en souciera pas non plus. A l'examen du but reussit(paul) il conclura à la vérité du but en unifiant but et fait: il s'agit du même prédicat (reussit) et leurs arguments s'unifient: un seul argument de chaque côté, et il s'agit d'une constante, et il s'agit de la même constante. Prolog renverra donc la valeur yes, même si, comme on va le voir dans un instant, pierre a 2 en russe et 7 en anglais!

            Voyons nos deux règles.

            La première fait un appel au prédicat notemoyenne, qui, pour un étudiant donné, renvoie la moyenne de ses notes. Nous y reviendrons. La moyenne est stockée dans la variable Moyenne. La deuxième condition nous indique que cette moyenne doit être égale ou supérieure à 12, et la troisième condition nous indique que l'étudiant ne peut pas avoir d'échec.

            Cette troisième condition est intéressante. Examinons-la:

not(echoue(Etudiant))

            not est un prédicat prédéfini. Il réussit si son argument échoue. En d'autres termes, si la machine abstraite ne parvient pas à prouver echoue(Etudiant) (l'étudiant a au moins un échec) elle conclura à la vérité de not(echoue(Etudiant)) (l'étudiant n'a pas d'échec).

            Cette manière de concevoir la négation doit être bien assimilée. Elle se base sur la conception d'un UNIVERS CLOS: le programme renseigne la machine abstraite sur tout ce qu'elle doit savoir pour se prononcer sur la vérité des relations.

            La règle suivante (/* 2 */) interroge le prédicat note, prédicat à trois arguments. L'appel à ce prédicat se fait avec le deuxième argument (le cours) lié à la valeur informatique, puisque c'est le cours d'informatique qui permet de faire réussir un étudiant tout à fait nul ailleurs (rappelons qu'un étudiant réussit sans délibération s'il obtient 16 ou plus en informatique: c'est cette condition que la deuxième règle pour le prédicat reussit tente de saisir). Etudiant est une variable désignant l'étudiant sur la réussite duquel on s'interroge. Le troisième argument, Note, servira à stocker la note renvoyée par les faits qui définissent le prédicat note. Par exemple, le but reussit(jean), unifié avec la tête de la deuxième règle, conduira au but note(jean, informatique, Note) qui sera unifié avec le fait note(jean, informatique, 16) pour donner la liaison (l'instanciation): Note = 16, et conduire à la satisfaction du but Note >= 16, après quoi la machine abstraite pourra conclure que jean a réussi.

            Examinons à présent les clauses pour le prédicat echoue:

echoue(Etudiant):-
              etudiant(Etudiant),
                    note(Etudiant,_,Note),
                    Note < 10.

echoue(Etudiant):-
                    etudiant(Etudiant),
                    notemoyenne(Etudiant,Moyenne),
                    Moyenne < 12.

            On a ici un appel au prédicat note. Le premier argument sera instancié au nom de l'étudiant (Etudiant). Le second est désigné par la variable anonyme ou muette, marquée par un blanc souligné. Rappelons que nous indiquons par là que la valeur de cette variable ne nous intéresse pas. Dans le cas précis qui nous occupe, je cherche à savoir si un étudiant donné a un échec, et je ne me soucie pas de savoir dans quelle branche: d'où l'utilisation de la variable anonyme.

            Comment l'appel à ce prédicat note va-t-il me permettre de découvrir si un étudiant a un échec ou s'il n'en a pas? Il convient de se rappeler ici la propriété cruciale de la machine abstraite Prolog: elle recherche TOUTES les solutions possibles, elle essaie TOUTES les valeurs possibles avant de conclure à l'échec du prédicat. Donc, si un étudiant a une note déficiente, Prolog la trouvera, car il ne conclura à l'échec du prédicat echoue que si aucune valeur de Note ne satisfait la relation  Note < 10.

            On voit donc combien le mécanisme de recherche des solutions en Prolog est puissant. La définition du prédicat echoue est élégante et simple. Elle accomplit le travail d'une dizaine d'instructions au moins dans d'autres langages de programmation de haut niveau.

            Considérons à présent le prédicat total, pour revenir ensuite au prédicat notemoyenne, qui y fait appel.

  total([],0,0).

  total([Tete|Queue],Somme,Nombre_el):-
        total(Queue,Nouvelle_Somme,Nouveau_Nombre_el),
        Somme is Nouvelle_Somme+Tete,
        Nombre_el is Nouveau_Nombre_el+1.

            Le prédicat total est basé sur le principe du parcours récursif d'une liste. Ce procédé peut paraître déroutant au premier abord, il est pourtant extrêmement puissant et élégant.

            La première clause est la clause d'arrêt (STOPPING CLAUSE), celle qui nous permet de sortir du parcours récursif défini par la seconde clause. Comme c'est toujours le cas pour les clauses d'arrêt, elle est très simple. Ce n'est pas une règle, mais un fait:

 total([],0,0).

            C'est un fait que le total des éléments d'une liste vide est 0, et que le nombre d'éléments y est également 0. C'est sur ce fait que l'on tombera lorsqu'on arrivera en fin de parcours de la liste, lorsque sa queue sera la liste vide (on se rappelle qu'une queue de liste est toujours une liste, et on commence à comprendre pourquoi).

            La deuxième clause est une règle: elle nous dit que si on a totalisé tous les éléments de la liste à l'exception du premier (totalisation qui se fait à l'aide du prédicat total appliqué à la queue de la liste), il suffit d'ajouter la valeur du premier élément au total et 1 au nombre d'éléments pour avoir le total de la liste et son nombre d'éléments.

            La liste est divisée en deux parties, tête et queue, à l'aide de l'opérateur |. L'application récursive du prédicat total à cette queue donne les résultats Nouvelle_Somme et Nouveau_Nombre_el, auxquels il suffit d'ajouter la valeur de la tête (contenue dans la variable Tête) et le nombre d'éléments qu'elle représente, à savoir 1.

            Comment la machine abstraite s'en sort-elle lorsqu'elle est confrontée à des prédicats récursifs, qui se définissent en faisant appel à eux-mêmes?  Elle maintient une pile de tous les buts en attente qui sont générés par les appels récursifs, jusqu'au moment où elle peut appliquer (par unification) la clause non récursive: dans notre cas, il s'agit du fait qui concerne le total d'une liste vide. Fort de ce premier résultat, Prolog reprend un après l'autre tous les appels en attente. Dans notre cas, il pourra bâtir sur la base des deux 0 renvoyés par l'unification du but avec le fait.

            Il nous reste à examiner le prédicat notemoyenne.

  notemoyenne(Etudiant,Valeur):-
           findall(Note,note(Etudiant,_,Note),Listedenotes),
           total(Listedenotes,Somme,Nombredenotes),
           Valeur is Somme / Nombredenotes.

Notemoyenne fait appel à un prédicat prédéfini[5] très puissant, à savoir findall. Findall prend trois arguments:

1) une variable;

2) un prédicat dans lequel cette variable apparaît comme argument;

3) une liste qui va lui permettre de stocker toutes les valeurs de la variable qui satisfont le prédicat donné en deuxième argument.

            La machine abstraite réunit donc en une liste toutes  les valeurs que peut prendre la variable Note dans le prédicat note, c'est-à-dire toutes les notes de l'étudiant Etudiant.

            Le prédicat notemoyenne appelle le prédicat total pour qu'il totalise la liste et en renvoie le nombre d'éléments: il s'agit des variables Somme et Nombredenotes. Finalement, la moyenne, renvoyée dans la variable Valeur, est calculée par Valeur is Somme/Nombredenotes (/ est l'opérateur de division; on se souvient que // est réservé à la division entière).

            Le programme se termine par une série de faits qui servent à définir le prédicat note. Ce prédicat n'a pas de règles. C'est donc purement un prédicat de base de données, destiné à stocker toutes les valeurs des relations qui sont connues d'entrée de jeu. On verra plus tard que ce n'est pas le seul type de base de données que Prolog connaisse. Pour l'heure, on en a dit assez et il est temps de présenter le programme NOTES en entier.

 

/* NOTES: à méditer avant les examens ...  */

/* des faits */

  reussit(pierre).
  reussit(paul).

/* des règles */

  reussit(Etudiant):-
                  etudiant(Etudiant),
                  notemoyenne(Etudiant,Moyenne),
                  Moyenne >= 12,
                  not(echoue(Etudiant)).

  reussit(Etudiant):-
                  etudiant(Etudiant),

                  note(Etudiant,informatique,Note),
                  Note >= 16.

  echoue(Etudiant):-
                  etudiant(Etudiant),
                  note(Etudiant,_,Note),Note<10.

  echoue(Etudiant):-
                  etudiant(Etudiant),
                  notemoyenne(Etudiant,Moyenne),
                  Moyenne < 12.

  /* calcul de la moyenne */

  notemoyenne(Etudiant,Valeur):-
           findall(Note,note(Etudiant,_,Note),Listedenotes),
           total(Listedenotes,Somme,Nombredenotes),
           Valeur is Somme / Nombredenotes.

  total([],0,0).

    total([Tete|Queue],Somme,Nombre_el):-
        total(Queue,Nouvelle_Somme,Nouveau_Nombre_el),
        Somme is Nouvelle_Somme+Tete,
        Nombre_el is Nouveau_Nombre_el+1.

  /* les notes */

  note(jean,anglais,16).
  note(jean,espagnol,13).
  note(jean,droit,6).                 
  note(jean,informatique,16).

  note(richard,droit,11).
  note(richard,anglais,11).
  note(richard,russe,12).
  note(richard,informatique,10).

  note(camille,droit,5).
  note(camille,informatique,15).
  note(camille,russe,18).

  note(pierre,russe,2).
  note(pierre,anglais,7).
  note(pierre,informatique,5).

/* qui sont les étudiants? */

  etudiant(jean).
  etudiant(richard).
  etudiant(camille).
  etudiant(pierre).
  etudiant(paul).

Exemples d'invocation et résultats obtenus (en gras) 

?- reussit(X).

            X = pierre
            X = paul
            X = jean

?- notemoyenne(jean,X).

            X = 12.75

?- total([12,16,14,15,17],Somme,Nombre_elements).

            Somme = 74
            Nombre_elements = 5

 Chapitre 3 Les structures de données

            Nous allons examiner plus en détail le mécanisme d'unification en étudiant LEX, un programme très simple, dont toute la puissance provient précisément du mécanisme d'unification.

            Mis à part les sélecteurs et prédicats utilitaires d'impression, sur lesquels nous allons revenir, LEX ne comporte qu'un seul prédicat, à savoir dic. De plus, le paquet de clauses pour ce prédicat ne comporte pas de règles, mais simplement un ensemble de faits.

            LEX montre comment on pourrait organiser un petit dictionnaire en Prolog. Chaque entrée de dictionnaire est une structure de type lex, qu'on peut définir par le schéma suivant:

lex (Hw, Hn, Pos, Defnu, Grcode, Def, Exlist)

            On rencontre ici la possibilité d'utiliser des STRUCTURES, c'est-à-dire des objets complexes, à plusieurs niveaux. lex est une telle structure.

            On voit tout de suite la similitude avec le concept de prédicat. Si lex était utilisé comme tête de clause ou comme élément du corps on concluerait à l'existence d'un prédicat lex, prédicat à 7 arguments.

            En fait, il ne s'agit pas d'un prédicat, mais d'une structure de données complexe. Bien sûr, le mécanisme d'unification sera exactement le même que pour les prédicats. En d'autres termes, deux structures seront unifiables si:

1) elles ont le même FONCTEUR (équivalent du nom de prédicat: ici lex);

2) elles ont le même nombre d'OBJETS (équivalents des arguments: ici Hw, Hn, etc.);

3) ces objets sont unifiables entre eux, c'est-à-dire: le premier objet de la première structure est unifiable avec le premier objet de la seconde structure, le deuxième objet de la première structure est unifiable avec le deuxième objet de la seconde structure, et ainsi de suite.

            On voit que cette définition est récursive: elle fait appel au prédicat unifiable. Donc, on ne sera pas étonné de voir des structures complexes dans lesquelles les objets sont eux-mêmes des structures complexes.

            En fait, les objets de la structure lex ne sont pas tous des objets simples. Considérons-les l'un après l'autre:

1) Hw désignera une variable du type atomique (une chaîne de caractères). 

            Il s'agit d'un objet simple, destiné à recevoir le HEADWORD, ou mot vedette, par exemple ABANDON dans notre petite base de données.

2) Hn sera du type integer (un nombre entier). C'est donc aussi un objet simple.

            Il s'agit de l'HOMOGRAPH NUMBER, numéro d'homographe. Cette information est utile pour les mots qui possèdent plusieurs homographes. Par exemple, dans notre petit dictionnaire, nous distinguerons ABANDON verbe et ABANDON nom.

3) Pos désignera un objet simple, du type atomic.

            Il s'agit du PART OF SPEECH, partie du discours, par exemple v, n, adj, adv, etc.

4) Defnu désignera également un objet simple, du type integer.

            Il s'agit du numéro de la définition, utile pour les homographes qui possèdent plusieurs définitions.

5) Grcode désignera  le dernier objet simple de la liste d'objets du foncteur lex.

            Il s'agit du code grammatical, destiné à refléter l'environnement syntaxique dans lequel l'item s'insère. Ces codes (comme d'ailleurs tout le reste du mini-dictionnaire) sont repris au LONGMAN DICTIONARY OF CONTEMPORARY ENGLISH[6] (t1=transitif avec un groupe nominal comme objet; t1to: idem mais avec en plus un deuxième complément introduit par la préposition TO; u: uncountable, indénombrable)

6) Def désignera un objet complexe. Il sert à stocker la définition d'une acception donnée d'un homographe donné d'un item donné. Il s'agit d'une liste de mots. Il va sans dire qu'un programme plus sophistiqué que LEX permettrait la saisie des informations à inclure dans la base de données sous une forme qui correspond mieux au travail du lexicographe. Celui-ci n'aurait pas à entrer une liste de mots, mais bien une chaîne, et cette chaîne serait convertie en liste par le programme (nous verrons bientôt qu'on peut réaliser cette opération de conversion en Prolog).

Un exemple de la structure représentée par la variable Def:

             def([to,leave,completely])

Le nom du foncteur est ici def. def a un objet, qui est une liste d'atomes: [to,leave,completely].

7) Exlist désignera une liste d'objets complexes; il s'agit en fait de la liste des exemples qui illustrent une acception donnée.

Voici un exemple d'une structure désignée par Exlist:

  [ex([the,sailors,abandoned,the,burning,ship]),
   ex([they,abandoned,the,town])]

Il s'agit donc d'une liste de structures du type ex. Chaque structure du type ex a un foncteur de nom ex suivi d'une liste d'atomes, par exemple:

ex([they,abandoned,the,town])

            On se souvient de la souplesse que permet la définition d'objets du type liste: il n'est pas nécessaire de déterminer le nombre d'éléments à l'avance (ni même le nombre maximal d'éléments: contrainte typique des sgbd, c'est-à-dire des systèmes de gestion de bases de données). On peut avoir une définition de trois mots suivie d'une autre de trente mots. On peut avoir une liste de deux longs exemples suivie d'une liste de dix petits.

 

            Le programme, on l'a dit, ne comporte pas de règles. Le seul prédicat est le prédicat dic (pour dictionary) qui prend un seul argument, une structure complexe du type lex.

            On examinera soigneusement toutes les clauses (tous les faits) repris dans le programme lex, pour se persuader qu'ils sont bien conformes au schéma de la structure complexe.

            Que peut-on faire avec une telle base de données lexicale (car c'est bien de cela qu'il s'agit: la taille extrêmement restreinte n'altère pas la nature de l'entreprise)? Tout ce que l'on peut faire avec un sgbd classique, et d'une manière bien plus élégante. On s'en persuadera en exécutant les exemples d'appel, et en en inventant d'autres. On peut donc aisément, comme dans les exemples d'appel donnés en commentaires au programme:

1) sortir tout le dictionnaire
2) sortir tous les exemples d'ABANDON
3) sortir toutes les entrées qui ont exactement deux exemples
4) sortir toutes les définitions des verbes
5) cf.4, mais en testant la présence de TO comme premier mot de la définition
6) sortir tous les exemples des verbes qui ont le mot LEAVE en deuxième position dans leur définition.

            Tout cela sans programmation proprement dite, par la simple puissance du mécanisme d'unification.

            Pourquoi donc développer des sgbd quand Prolog fait si bien l'affaire? On réfléchira aux contraintes suivantes:

1) toute la base de données se trouve en mémoire centrale (contrainte typique de bon nombre d'implantations Prolog, mais pas de toutes; Arity Prolog, par exemple, y échappe);

2) le processus d'unification est séquentiel: il explore toute la base de données de haut en bas et de gauche à droite.

            Les sgbd sont faits précisément pour échapper à de telles contraintes: ils permettent le passage rapide de la mémoire auxiliaire vers la mémoire centrale, et vice-versa; ils utilisent des techniques d'indexation sophistiquées pour accélérer le mécanisme d'accès aux données.

            Il n'en reste pas moins vrai que Prolog peut servir d'interface avec un sgbd (aussi grâce à ses possibilités de traitement du langage naturel), et qu'il représente une approche conceptuellement élégante du modèle relationnel. Nous ne poursuivrons pas ces points dans cette introduction.

            En examinant les exemples de buts cités dans la première partie du programme, on peut se dire que, même s'il n'y a pas de programmation, il faut néanmoins connaître à fond la structure de l'objet complexe lex pour pouvoir récupérer l'information que ses instances comportent. Une erreur est très aisée à commettre, comme par exemple l'oubli d'un blanc souligné. Pour résoudre ce problème, on peut développer des prédicats, dits sélecteurs, qui ont pour rôle d'aller chercher dans la structure complexe les éléments qui nous intéressent. Supposons que nous voulions accéder aisément à la définition correspondant à une certaine acception d'un certain homographe d'un certain lexème. Par exemple, nous aimerions pouvoir faire exécuter le but

            definition(abandon,1,4,Def)

pour obtenir dans Def la définition associée à l'acception 4 du premier homographe de l'item abandon.

            Pour ce faire, il nous suffit de définir le sélecteur definition, prédicat à 4 places. C'est chose aisée:

definition(Word,Homograph_number,Definition_number,Definition):-
dic(lex(Word,Homograph_number,_,Definition_number,_,Definition,_)),
printdef(Definition).

On voit que definition extrait par unification l'information pertinente de la structure dic. Nous verrons dans quelques instants le rôle et la définition de printdef.

Supposons que nous voulions toutes les définitions associées à un item, en invoquant par exemple

      definitions(abandon,Liste_de_def).

Le sélecteur definitions fait appel à findall pour collecter dans une liste les définitions liées à toutes les acceptions de tous les homographes du lexème:

definitions(Word,Deflist):-
      findall(Definition_list,
            dic(lex(Word,_,_,_,_,Definition_list,_)),
            Deflist),
      printdeflist(Deflist).

            On aura des sélecteurs très semblables pour example (les exemples liés à une acception) et examples (tous les exemples liés à un item).

            Voyons à présent les prédicats d'impression, tels que printdef et printdeflist dans les sélecteurs cités. Ce qu'ils font est très simple: ils lisent l'information contenue dans les termes complexes tels que def et ex. Cette information est elle-même présentée sous la forme de liste, donc le prédicat d'impression auquel ils font tous appel est printlist, dont la définition suit:

       printlist([]).
       printlist([H|T]):- write(H),tab(1),printlist(T).

Printlist parcourt la liste passée en argument. Elle en écrit tous les éléments, chaque élément étant séparé du suivant par un espace (tab(1)).

L'impression d'une définition est tout simplement l'impression de la liste de mots qui est l'argument du foncteur def:

       printdef(def(List)):-
                printlist(List).


Si on a une liste de définitions, comme celle construite par findall dans definitions, on utilise le prédicat printdeflist, qui imprime successivement chaque définition de la liste:

       printdeflist([]).         

       printdeflist([Head|Tail]):-
                printdef(Head),nl,
                printdeflist(Tail).

On procède de même pour les exemples, où on a toutefois un niveau de structure en plus, puisque chaque définition peut être associée à une liste d'exemples. Le findall du prédicat examples créera donc une liste de liste d'exemples.

Finalement, on peut aussi prévoir des prédicats qui vérifient la cohérence des données lexicographiques. On n'en construira qu'un ici, à savoir celui qui serait chargé de vérifier que toutes les définitions des verbes commencent par la particule TO. Ce travail est réalisé par checkto. Checkto réussit si tout le dictionnaire est conforme. Sinon, il s'arrête sur le premier item déviant, dont il cite la forme, le numéro d'homographe et le numéro de définition. Voici checkto:

 checkto:-
     not (dic(lex(Verb,Homograph_number,v,
            Definition_number,_,def([First|Defrest]),_)),
      First \= to,
      write(Verb),tab(1),write(Homograph_number),
      tab(1),write(Definition_number),nl).

On constate que checkto se sert de not. Le premier mot de la définition de chaque verbe viendra occuper la variable First. On testera ensuite que First n'est pas différent de to, à l'aide du prédicat prédéfini \=, qui s'utilise comme opérateur infixe, c'est-à-dire pincé entre ses deux arguments. \= réussit si ses arguments ne peuvent s'unifier. On se rappelle qu'ici on est toujours dans la portée de not, donc le définition ne sera admise que si elle ne contient pas un premier mot différent de to.

 

/* LEX: la puissance de l'unification... */

/* PREMIERE PARTIE: PAS DE REGLES ... */

dic(lex(abandon,1,v,1,t1,
             def([to,leave,completely]),
           [ex([the,sailors,abandoned,the,burning,ship]),
             ex([they,abandoned,the,town])])).

dic(lex(abandon,1,v,2,t1,
             def([to,leave,a,relation,or,friend,in,
                  a,thoughtless,and,cruel,way]),
         [ex([he,abandoned,his,wife,and,went,away,with,all,
                 their,money])])).  

dic(lex(abandon,1,v,3,t1,
             def([to,give,up]),
         [ex([the,search,was,abandoned,when,night,came])])).

dic(lex(abandon,1,v,4,t1to,
                def([to,give,oneself,up,
              completely,to,a,feeling,desire,etc]),
           [ex([he,abandoned,himself,to,grief]),
                 ex([abandoned,behaviour] )] )).

dic(lex(abandon,2,n,1,u,
                    def([freedom,from,control]),
               [ex([the,people,were,so,excited,that,
                    they,jumped,and,shouted,with,abandon ]),
                 ex([in,gay,abandon]) ] )).

          /* Exemples de buts:

          dic(X)
          dic(lex(abandon,_,_,_,_,_,EX))
          dic(lex(LEX,_,_,_,_,_,[ex(X),ex(Y)]))
          dic(lex(Verb,_,v,_,_,def(DEF),_))
          dic(lex(Verb,_,Pos,_,_,def([to | DEF ],_))
          dic(lex(Verb,_,v,_,_,def([_,leave|_]),EX ))
          */

/* DEUXIEME PARTIE: SELECTEURS ET UTILITAIRES */

/* les sélecteurs */

example(Word,Homograph_number,Definition_number,
                                                            Example_list):-
dic(lex(Word,Homograph_number,_,Definition_number,
                                                          _,_,Example_list)),
printexlist(Example_list).

definition(Word,Homograph_number,Definition_number,
                                                                   Definition):-
dic(lex(Word,Homograph_number,_,Definition_number,
                                                               _,Definition,_)),
printdef(Definition).

examples(Word,Exlist):-
      findall(Example_list,
            dic(lex(Word,_,_,_,_,_,Example_list)),
            Exlist),
      printallexlist(Exlist).

definitions(Word,Deflist):-
      findall(Definition_list,
            dic(lex(Word,_,_,_,_,Definition_list,_)),
            Deflist),
      printdeflist(Deflist).

/* vérifier que les définitions des verbes commencent par TO */

 checkto:-
     not (dic(lex(Verb,Homograph_number,v,
            Definition_number,_,def([First|Defrest]),_)),
      First \= to,
      write(Verb),tab(1),write(Homograph_number),
      tab(1),write(Definition_number),nl).

/* les impressions */

printlist([]).

printlist([H|T]):- write(H),tab(1),printlist(T).

printallexlist([]).

printallexlist([H|T]):- printexlist(H),nl,
            printallexlist(T).

printexlist([]).         

printexlist([ex(List)|Tail]):-
                printlist(List),nl,
                printexlist(Tail).

printdeflist([]).         

printdeflist([Head|Tail]):-
                printdef(Head),nl,
                printdeflist(Tail).

printdef(def(List)):-
                printlist(List).

Exemples d'invocation et résultats obtenus (en gras) 

/* PREMIERE PARTIE */

?- dic(lex(Verb,_,Pos,_,_,def([to|DEF]),_)).

            Verb = abandon
            Pos = v
            DEF = [leave,completely]
            Verb = abandon
            Pos = v
            DEF = [leave,a,relation,or,friend,in,a,thoughtless,and,cruel,way]
            Verb = abandon
            Pos = v
            DEF = [give,up]
            Verb = abandon
            Pos = v
            DEF = [give,oneself,up,completely,to,a,feeling,desire,etc]

/* DEUXIEME PARTIE */

?- definition(abandon,1,2,_).

            to leave a relation or friend in a thoughtless and cruel way
            yes

?- example(abandon,1,2,_).

            he abandoned his wife and went away with all their money
            yes

?- definitions(abandon,_).

            to leave completely
            to leave a relation or friend in a thoughtless and cruel way
            to give up
            to give oneself up completely to a feeling desire etc
            freedom from control

?- examples(abandon,_).

            the sailors abandoned the burning ship
            they abandoned the town
            he abandoned his wife and went away with all their money
            the search was abandoned when night came
            he abandoned himself to grief
            abandoned behaviour
            the people were so excited that they jumped and shouted with abandon.
            in gay abandon
            yes

?- checkto.

               yes                      

 

Chapitre 4 Listes et récursivité

            Notre prochain exemple de programme en Prolog vise essentiellement à approfondir notre compréhension de la récursivité et de son emploi dans l'exploration des listes.

            Ce programme s'appelle LIBRARY et se présente effectivement comme une petite bibliothèque de prédicats utilitaires.

            Avant de nous pencher plus en détail sur certains des prédicats définis dans LIBRARY, nous allons tous les passer en revue, en indiquant ce qu'ils sont censés faire.

            DELETE enlève son premier argument de la liste donnée en second argument pour renvoyer en troisième argument la liste ainsi privée d'un élément.

            APPEND concatène ses deux premiers arguments (des listes) pour former son troisième argument (une liste aussi, bien sûr).

            MEMBER recherche si son premier argument est un élément de son second, qui est une liste.

            LAST renvoie dans son premier argument le dernier élément de son second argument, qui est une liste.

            ORDER réussit si son premier argument précède son second dans l'ordre lexicographique, ou lui est identique.

            CARD renvoie dans son second argument le nombre d'éléments de son premier, qui est une liste.

            SPLIT fragmente son deuxième argument, qui est une liste, en son troisième et quatrième arguments, qui sont également tous deux des listes. La fragmentation s'opère de telle manière que tous les éléments qui précèdent le premier argument dans l'ordre lexicographique (ou lui sont identiques) se retrouvent dans le troisième argument, alors que tous les autres éléments se retrouvent dans le quatrième argument.

            QUISORT trie la liste donnée en premier argument et la renvoie dans son second argument.

            NTHMEMBER renvoie dans son dernier argument le membre de son second argument (une liste), dont la position dans la liste est donnée en premier argument.

            ADD ajoute son premier argument à son second (une liste) pour donner son troisième. L'ajout ne se fait toutefois pas si la liste donnée en second argument contient déjà l'élément donné en premier argument.

            REMDUP enlève tous les duplicata dans son premier argument (une liste) pour donner son second (une liste également).

            Toutes ces définitions souffrent d'un grave défaut: elles sont toutes procédurales, et ne rendent pas justice à Prolog, qui ne force pas le concepteur à déterminer à l'avance quelles seront les variables instanciées lors de l'appel d'un prédicat.

            Le lecteur se souvient du programme de 'traduction' donné en exemple dans l'introduction à cet  ouvrage. La traduction pouvait aussi bien s'opérer de l'anglais vers le français que du français vers l'anglais. Tout dépend de la variable qui n'est pas liée lors de l'appel de ce prédicat. Si c'est l'argument qui correspond à la phrase française, la traduction se fait de l'anglais vers le français, et vice-versa si la variable libre (FREE) est la phrase anglaise. En outre, les variables peuvent être toutes deux instanciées lors de l'appel du prédicat. Notre système de traduction fonctionne alors comme vérificateur. L'appel de but renvoie yes si les deux arguments sont la traduction l'un de l'autre, et no dans les autres cas. Cette propriété de la machine abstraite Prolog contribue grandement à sa puissance.

            Nous pouvons l'illustrer ici à l'aide du prédicat member.

member(paul,[pierre,paul,jean,jacques]) renvoie yes

member(X,[pierre,paul,jean,jacques]) renvoie les solutions:

                        X = pierre,X = paul, X = jean, X = jacques.

            MEMBER peut donc être utilisé pour tester l'appartenance d'un élément à une liste (comme le faisait comprendre la définition que nous en avions donnée), mais également pour obtenir un à un tous les éléments d'une liste.

            De même, CARD peut être utilisé pour obtenir ou pour vérifier la longueur d'une liste:

card([pierre, paul,jean],3) renvoie yes

card([pierre,paul,jean],Longueur) renvoie Longueur = 3.

            Cette grande souplesse des prédicats ne peut pas toujours être maintenue. Elle est détruite par l'emploi de la coupure (coupe-choix, CUT), que l'on indique par un point d'exclamation (!), et qui peut s'avérer très utile. L'effet de la coupure est d'empêcher la remontée (retour-arrière, BACKTRACKING) au-delà (à gauche) du point marqué par la coupure. Nous allons voir comment.

            On sait que l'on peut demander à Prolog de rechercher TOUTES les solutions possibles, toutes les valeurs des variables qui satisfont un prédicat donné en but. Comment Prolog procède-t-il?

            Dès qu'il a trouvé une solution, Prolog est prêt à forcer l'échec du prédicat, et à réessayer de le satisfaire d'une autre manière. Pour ce faire, il se reporte à la dernière unification qu'il a réalisée, la défait (il rend libres les variables que cette unification l'avait amené à lier) et essaye d'unifier autrement (par exemple, en considérant la clause suivante d'un prédicat donné). Pour pouvoir se reporter à cette dernière unification, ne pas réessayer plusieurs fois les mêmes valeurs, et ne pas tomber plusieurs fois sur les mêmes solutions, Prolog maintient un pointeur à l'endroit auquel il est arrivé dans sa lecture des clauses (qu'il accomplit, on le sait, de haut en bas et de gauche à droite). Lorsqu'il force l'échec, Prolog REMONTE (de bas en haut, de droite à gauche) dans son exploration des clauses, et c'est ce mécanisme qu'on appelle REMONTEE en français et BACKTRACKING en anglais (revenir sur ses pas). Lorsque toutes les valeurs ont été essayées, le but échoue, mais dans l'entretemps les valeurs qui satisfont le but ont été communiquées à l'utilisateur.

            Le rôle de la coupure est d'empêcher la remontée au-delà (à gauche) de la coupure. Pourquoi faire cela? Pour diverses raisons, notamment pour empêcher Prolog de chercher des solutions qui ne nous intéressent pas.

            Considérons la définition du prédicat DELETE.

  delete(_,[],[]).
  delete(X,[X|R],R):-!.
  delete(X,[Y|R],[Y|R2]):- delete(X,R,R2).

            La première clause est la clause d'arrêt: peu importe ce que j'enlève à une liste vide, j'ai toujours une liste vide.

            La deuxième nous dit que si l'élément à enlever est en tête de liste, il suffit de renvoyer la queue de la liste, et le tour est joué. Pour que Prolog s'arrête de chercher des solutions, on donne comme corps à la règle la seule coupure. Le prédicat coupure est un prédéfini. Comme but, il réussit immédiatement, et empêche la machine abstraite de considérer d'autres solutions pour le but parent de la coupure, dans notre exemple DELETE. La machine abstraite n'essayera plus de satisfaire d'une autre manière le but DELETE, et ne renverra donc qu'une solution.

            La troisième clause ne sera donc essayée que si la seconde a échoué (car l'item à enlever n'était pas en tête de liste). Dans ce cas, on maintient la tête de liste, et on essaye d'enlever l'élément de la queue de liste, ce qui se fait en utilisant DELETE.

            Donc, grâce à la coupure, seule la première occurrence de l'élément dans la liste sera retranchée. Sans la coupure, DELETE renverrait autant de solutions qu'il y a d'occurrences de l'élément dans la liste. Chaque nouvelle solution serait découverte lors de la remontée, lorsque Prolog essaie de resatisfaire l'appel au prédicat DELETE.

           

            La coupure est assez délicate à utiliser. Nous n'en analyserons pas tous les usages dans cette introduction. Il suffit de retenir que c'est un moyen d'augmenter l'efficacité du programme, mais souvent au détriment de sa lisibilité, et de la souplesse d'emploi des prédicats qui contiennent des coupures.

            MEMBER est très souvent le premier prédicat récursif auquel on soumet le débutant en Prolog. Sa définition est en effet extrêmement simple. Examinons-la un instant.

            La première clause, qui est la clause d'arrêt, nous dit qu'un élément est membre d'une liste si c'est la tête de cette liste. Cette propriété peut être communiquée sous forme de fait, puisque nous disposons d'un opérateur qui divise la liste en deux parties, tête et queue. On a donc

member(Head,[Head|Tail]).

            Si l'élément n'est pas la tête, il est peut-être dans la queue. Comment explorer la queue, sinon à l'aide de member lui-même:

member(Element,[_|Tail]):- member(Element,Tail).

            On peut rendre ce prédicat déterministe (c'est-à-dire à une seule solution) en utilisant la coupure. Il suffit que la machine abstraite s'arrête de chercher des solutions dès qu'elle a trouvé l'élément dans la liste. On placera donc une coupure dans la première clause, qui devient dès lors une règle:

detmember(Head,[Head|Tail]):-!. (ne pas oublier le point après la coupure)

            Detmember ne pourra pas, contrairement à member, être utilisé pour obtenir un à un tous les éléments d'une liste, puisque la coupure empêchera la remontée dès que le premier élément aura été trouvé.

            La coupure apporte donc ici un gain d'efficacité si on veut utiliser member pour tester l'appartenance d'un élément à une liste. Mais ce gain se paie par une perte de souplesse, le prédicat ne pouvant plus être utilisé comme générateur d'éléments de liste.

            APPEND est aussi un bel exemple de prédicat récursif. On remarquera surtout le 'transfert' de la tête de la première liste en tête de la troisième, transfert qui garantit, grâce à la récursivité, le passage complet de la première liste en tête de la troisième. La première clause assurera le transfert de la deuxième liste lorsque la première liste aura été entièrement parcourue.

  append([],X,X).

  append([U|X],Y,[U|Z]):-
                    append(X,Y,Z).

            QUISORT est la programmation en Prolog d'un des meilleurs algorithmes de tri, QUICKSORT, algorithme dû à Hoare.

            Le principe de QUICKSORT est très simple. Pour trier une liste, divisez-la en deux sous-listes, de telle manière que la première contienne tous les éléments qui sont égaux à ou plus petits qu'un élément arbitraire de la liste (dans quisort, on prend tout simplement l'élément de la liste auquel on a le plus facilement accès, à savoir la tête), et la deuxième tous les éléments qui sont plus grands. Triez ensuite ces sous-listes à l'aide de QUICKSORT. Arrêtez-vous lorsque les listes sont dégénérées au point de ne plus contenir qu'un seul élément, ou rien du tout.

quisort([H|T],S):-
          split(H,T,A,B),
          quisort(A,A1),
          quisort(B,B1),
          append(A1,[H|B1],S),!.

quisort([],[]).

quisort([X],[X]).

 

split(H,[A|X],[A|Y],Z):- order(A,H),
                            split(H,X,Y,Z).

split(H,[A|X],Y,[A|Z]):- order(H,A),
                            split(H,X,Y,Z).

split(_,[],[],[]).

            Cet algorithme est fondamentalement récursif, et sa programmation en Prolog est donc assez simple. Voyons d'abord les clauses d'arrêt, les cas des listes dégénérées:

quisort([X],[X]).: une liste d'un seul élément est triée.

quisort([],[]).: une liste vide est également triée.

            Le prédicat split accomplit la division de la liste en deux sous-listes, conformément aux conditions exposées ci-dessus. L'élément en tête de liste est transféré vers la liste des "petits", ou vers la liste des "grands", selon le résultat de la comparaison avec le guide de tri (la tête de la liste à trier par QUISORT).

            QUISORT s'applique récursivement aux deux listes renvoyées par split, la liste des petits et la liste des grands.

            Ensuite, la liste triée est recomposée par un appel au prédicat append.

            Voici à présent le programme LIBRARY dans son intégralité.

 

/* LIBRARY: quelques prédicats  utiles ... */

  delete(_,[],[]).
  delete(X,[X|R],R):-!.
  delete(X,[Y|R],[Y|R2]):- delete(X,R,R2).

  append([],X,X).
 
append([U|X],Y,[U|Z]):-
     append(X,Y,Z).

  member(X,[X|T]).
  member(X,[_|T]):- member(X,T).

  last(X,[X]).
  last(X,[_|Y]):- last(X,Y).

  order(A,B):- A=<B.
  order(A,B):- A@=<B.  
/* @=< signifie: précède ou est égal */

  card([],0).
  card([X|Y],N):- card(Y,N1), N is N1+1.
 

  split(H,[A|X],[A|Y],Z):- order(A,H),
                            split(H,X,Y,Z).
  split(H,[A|X],Y,[A|Z]):- order(H,A),
                            split(H,X,Y,Z).
  split(_,[],[],[]).

  quisort([H|T],S):-
          split(H,T,A,B),
          quisort(A,A1),
          quisort(B,B1),
          append(A1,[H|B1],S),!.
 
quisort([],[]).
  quisort([X],[X]).

  nthmember(1,[X|L],X).
  nthmember(N,[Y|L],X):-  N1 is N-1, nthmember(N1, L, X ).

 add(X,L,L):- member(X,L),!.
 add(X,L,[X|L]).

 remdup([X|Y],L):-  member(X,Y), remdup(Y,L),!.
 remdup([],[]).
 remdup([X|Y],[X|Y1]):- not(member(X,Y)),
                         remdup(Y,Y1),
                        !.

 Exemples d'invocation et résultats obtenus (en gras) 

?- delete(two,[one,three,two,five],X).

            X = [one,three,five]

?- append([one,two],[three,four,five],X).

            X = [one,two,three,four,five]

?- append(X,[three,four,five],[one,two,three,four,five]).

            X = [one,two]

?- member(three,[one,two,three,four,five]).

            yes

?- member(X,[one,two,three,four,five]).

            X = one
            X = two
            X = three
            X = four
            X = five

?- card([one,two,three,four,five],Combien).

            Combien = 5

?- card([one,two,three,four,five],4).

            no

?- quisort([one,two,three,four,five,six,seven,eight,nine,ten],Sorted).

            Sorted = [eight,five,four,nine,one,seven,six,ten,three,two]

?- quisort([5,6,3,9,8,1,1,0,7,4,2],Sorted).

            Sorted = [1,2,3,4,5,6,7,8,9,10]

?- nthmember(2,[one,two,three],X).

            X = two

?- nthmember(1,[one,two,three],one).

            yes

?- add(three,[one,four,five],New).

            New = [three,one,four,five]

?- add(three,[one,two,three,four],New).

            New = [one,two,three,four]

?- remdup([a,b,b,c,c,c,d,e],Clean).

            Clean = [a,b,c,d,e]                   

 

Chapitre 5 Les réseaux sémantiques

            Il existe en intelligence artificielle plusieurs formalismes pour la représentation des connaissances. Nous nous intéresserons ici à un des plus simples, les réseaux sémantiques, et nous étudierons leur implantation en Prolog.

            Dans un réseau sémantique, on trouve:

1.         des individu
2.         des classe
3.         des propriétés, attribuées à des individus ou à des classes.

            Nous avons choisi comme exemple un domaine que le lecteur de cet ouvrage connaît certainement bien, à savoir les objets informatiques. Nous en restreignons ici le champ aux répertoires et aux fichiers[7]. Concrètement on a les individus suivants dans notre micro-monde:

1.         root, le répertoire racine
2.         asoft et prolog, des sous-répertoires
3.         notes, pgcd et magique, des programmes écrits en Prolog
4.         cap et install, des programmes écrits en C
5.         manual, un texte ASCII
6.         cours, un texte produit avec Word Perfect
7.         find, un fichier exécutable d'extension .exe
8.         wp, un fichier exécutable d'extension .bat (fichier de commandes)
9.         format, un fichier exécutable d'extension .com

            On travaillera avec les classes suivantes:

1.         prolog_pro, la classe des programmes Prolog, sous-classe de program
2.         c_pro, la classe des programmes C, sous-classe de program
3.         program, la classe des programmes, sous-classe de document
4.         document, la classe des documents, sous-classe de file
5.         file, la classe des fichiers, sous-classe de object
6.         object, la classe universelle pour notre domaine (elle n'est sous-classe d'aucune classe)
7.         directory, la classe des répertoires, sous-classe d'object
8.         child_dir, la classe des sous-répertoires, sous-classe de directory
9.         ascii_text, la classe des textes ASCII, sous-classe de text
10.       text, la classe des textes, sous-classe de document
11.       wp_text, la classe des textes produits avec Word Perfect, sous-classe de word_processed_text
12.       word_processed_text, la classe des textes produits par traitement de texte, sous-classe de text
13.       exe, la classe des fichiers d'extension .exe, sous-classe de exe_file
14.       exe_file, la classe des fichiers exécutables, sous-classe de file
15.       bat, la classe des fichiers d'extension .bat, sous-classe de exe_file et de ascii_text
16.       com, la classe des fichiers d'extension .com, sous-classe de exe_file.

            On remarquera la double appartenance des fichiers batch (fichiers de commandes, d'extension .bat): ce sont à la fois des textes ASCII et des fichiers exécutables.

            On attribuera aux individus et aux classes de notre domaine les propriétés suivantes:

1.         erasable, pour les objets qui peuvent être détruits
2.         creatable, pour les objets qui peuvent être créés
3.         interpretable, pour les objets qui peuvent être traités par un interpréteur
4.         compilable, pour les objets qui peuvent être transformés en code objet par un compilateur
5.         understandable, pour les objets qui peuvent être compris par tout le monde (!!!)
6.         printable, pour les objets qui peuvent être imprimés
7.         executable, pour les objets qui peuvent être exécutés
8.         can_contain_directories, pour les objets qui peuvent contenir des répertoires
9.         can_contain_files, pour les objets qui peuvent contenir des fichiers
10.       in_directory, pour les objets qui sont contenus dans un répertoire

            L'appartenance est une propriété fondamentale. On distingue l'appartenance d'un individu à une classe de l'appartenance d'une sous-classe à une classe. Cette distinction est nécessaire pour éviter l'incohérence dans l'héritage des propriétés. De quoi s'agit-il?

            Nous émettrons l'hypothèse qu'en l'absence d'informations indiquant que ce n'est pas le cas, un individu hérite des propriétés de la classe à laquelle il appartient. Par exemple, si asoft est un child_dir, et que les child_dir ont la propriété in_directory, il est normal de conclure que asoft a la propriété in_directory. Mais l'héritage de propriétés ne s'arrête pas là: une sous-classe hérite également des propriétés associées à la classe à laquelle elle appartient. Par exemple, puisque la classe child_dir est une sous-classe de la classe  directory, et que la classe directory possède la propriété can_contain_files, on en conclut que la classe child_dir possède la propriété can_contain_files. De plus, et c'est le point crucial, cette notion d'héritage est transitive (si X rel Y et Y rel Z alors X rel Z); c'est ainsi qu'en remontant la hiérarchie des classes, on conclut que asoft possède également la propriété can_contain_files.

            Il est clair que certaines propriétés attribuées aux classes ne peuvent pas être héritées par les individus qui appartiennent à cette classe, et donc que l'on doit pouvoir distinguer entre appartenance d'un individu à une classe et appartenance d'une sous-classe à une classe. Considérez la propriété "est une espèce en voie de disparition". Il est clair que quelle que soit la classe à laquelle cette propriété est attribuée, elle ne peut pas être héritée automatiquement par les membres de cette classe. En effet, supposez que Moby soit une baleine à bosse, et que baleine à bosse désigne une espèce en voie de disparition, il ne s'ensuit pas que Moby elle-même est une espèce en voie de disparition.

            Etant donné une hiérarchie de classes, et la notion d'héritage de propriétés esquissée ci-dessus, le niveau d'attribution d'une propriété est assez aisé à déterminer: afin d'éviter les répétitions, on attribuera la propriété à la classe la plus élevée possible dans la hiérarchie. Par exemple, nous associons can_contain_files à la classe directory, plutôt qu'à la classe child_dir, car c'est une propriété qui vaut également pour le membre de directory qui n'est pas membre de child_dir, à savoir root, qui symbolise le répertoire racine.  Si on attache can_contain_files directement à child_dir, il faudra également l'attacher directement à root, ce qui est une contravention au principe d'économie.

            De même, on associera les individus à la plus petite classe possible, de telle sorte que l'héritage de propriétés puisse jouer à fond. Si par exemple je déclarais que asoft est un individu de la classe object, je ne pourrais plus conclure qu'il possède la propriété can_contain_files, puisque cette propriété n'est pas attribuée  à la classe universelle de notre domaine, à savoir object. En effet, object a comme sous-classe file, classe à laquelle la propriété can_contain_files n'est pas applicable. On devrait dès lors se résigner à attribuer la propriété can_contain_files à asoft lui-même, et bien sûr à tous les autres objets qui sont en fait des directory, des répertoires. Ici encore, c'est le principe d'économie qui gère le niveau d'attribution de la propriété d'appartenance.

            Nous avons écrit que l'héritage des propriétés s'appliquait uniquement en l'absence d'indications contraires. Il faut en effet pouvoir énoncer des exceptions. Par exemple, dans notre domaine, root est un directory, et donc normalement il devrait être erasable et creatable. On sait que ce n'est pas le cas. On associera donc la propriété non-erasable et non-creatable à root, et on donnera priorité aux propriétés locales par rapport aux propriétés héritées.

            Nous pouvons à présent passer à l'étude de l'implantation de notre petit réseau sémantique en Prolog.

            Les deux propriétés privilégiées, à savoir l'appartenance d'un individu à une classe et l'appartenance d'une sous-classe à une classe, seront  matérialisées respectivement par les prédicats à deux places isa (isa = is a = est un) et  ako (a kind of = une sorte de). Ces appellations sont communes. On aura donc par exemple:

isa(root,directory).
isa(asoft,child_dir).
isa(prolog,child_dir).

et

ako(child_dir,directory).
ako(directory,object).

            Le lien entre ces deux relations, et leur transitivité (remontée dans la hiérarchie) sont exprimés par les prédicats  is_instance et subclass, définis comme suit:

 is_instance(X,Y):- isa(X,Y).
 is_instance(X,Y):- isa(X,Z),  subclass(Z,Y).

 subclass(X,Y):- ako(X,Y).
 subclass(X,Y):- ako(X,Z), subclass(Z,Y).

            On remarque la récursivité de subclass, exploitée aussi par is_instance, ce qui assure le lien entre les deux relations.

            Pour les autres propriétes, nous nous servirons du prédicat prop à trois places: l'objet, la propriété elle-même, et une polarité (yes/no) qui indique si l'objet est ou n'est pas détenteur de la propriété, par exemple:

prop(object,erasable,yes).
prop(object,creatable,yes).
prop(directory,can_contain_directories,yes).
prop(directory,can_contain_files,yes).
prop(child_dir,in_directory,yes).
prop(root,erasable,no).
prop(root,creatable,no).

            Pour déterminer si un objet possède une propriété, on interroge d'abord le prédicat prop. Si on n'a pas de réponse, on explore la hiérarchie pour hériter la propriété, mais on ne franchit pas la barre d'une propriété  locale, c'est-à-dire obtenue directement via prop. On a les deux clauses suivantes:

has_property(Entity,Property,Polarity):-
      prop(Entity,Property,Polarity).

    has_property(Entity,Property,Polarity):-
             is_instance(Entity,Class),
             has_property(Class,Property,Polarity),
       notlocal(Entity,Property).

            Le prédicat notlocal (cf. Gazdar et Mellish 1989, p.354) s'assure que Property n'est pas lié à Entity via prop. On écrit:

notlocal(X,Y):- prop(X,Y,_),!, fail.
notlocal(_,_).                       

            Il faut comprendre ce prédicat comme suit. Si prop(X,Y) existe, notlocal doit être mis en échec, et la remontée ne peut pas remettre cet échec en cause. On a donc la coupure pour empêcher la remontée, et le prédéfini fail pour forcer l'échec (fail est un prédicat prédéfini: il échoue automatiquement, et provoque donc l'échec du but auquel il est associé, ici notlocal). Si la propriété n'a pas été trouvée, elle n'est pas locale, et notlocal peut réussir: c'est ce qu'assure la deuxième clause. On utilise des blancs soulignés car les valeurs d'instanciation sont sans importance ici.

            On comprend maintenant pourquoi l'appel à notlocal est placé à la fin de la deuxième clause définissant has_property: l'échec de notlocal ne doit pas empêcher l'exploration de la hiérarchie par is_instance. Si l'appel à notlocal  précédait l'appel à has_property, ce dernier ne serait jamais atteint dans le cas où une propriété est attribuée localement. En effet, l'appel à prop dans la première clause de notlocal réussirait, et le prédicat notlocal serait mis en échec permanent. En conséquence, la deuxième clause de notlocal ne serait jamais invoquée et la barrière ainsi constituée par l'appel à notlocal dans has_property ne pourrait jamais être franchie.

            Il y aura des cas où on désirera savoir quelle est la relation qui lie deux objets. Pour obtenir cette information, il faudrait en quelque sorte que nos prédicats eux-mêmes puissent être considérés comme des variables, que l'on puisse écrire, par exemple:

X(asoft,directory).                              * syntaxiquement incorrect!!!

pour obtenir la nature de la relation qui lie asoft et directory. Mais on ne peut pas utiliser des variables en lieu et place des prédicats. La solution consiste à réifier[8] le prédicat, c'est-à-dire le placer en position d'argument dans un super-prédicat et lier les deux par une définition appropiée du super-prédicat. On aura par exemple:

relation(X,Y,isa):- isa(X,Y).
relation(X,Y,ako):- ako(X,Y).

            Très simplement, X et Y sont liés par la relation isa si le but isa(X,Y) réussit. Cette technique est simple et puissante.

            On trouvera ci-dessous le programme semnet.ari en entier, ainsi que des exemples d'appel et de résultats obtenus.

 

/* SEMNET:  Un réseau sémantique élémentaire  */

/* individu appartient à classe */

    isa(notes,prolog_pro).
    isa(pgcd,prolog_pro).
    isa(magique,prolog_pro).
    isa(cap, c_pro).
   
isa(install, c_pro).
   
isa(root,directory).
    isa(asoft,child_dir).
    isa(prolog,child_dir).
    isa(manual,ascii_text).
   
isa(cours,wp_text).
    isa(find,exe).
   
isa(wp,bat).
    isa(format,com).

    /* sous-classe appartient à classe */

    ako(child_dir,directory).
    ako(directory,object).
    ako(prolog_pro,program).
    ako(c_pro,program).
   
ako(program,document).
   
ako(document,file).
    ako(file,object).
    ako(ascii_text,text).
    ako(wp_text,word_processed_text).
    ako(word_processed_text,text).
   
ako(text,document).
    ako(exe,exe_file).
    ako(bat,exe_file).
    ako(bat,ascii_text).
    ako(com,exe_file).
    ako(exe_file,file).

   /* propriétés des individus et des classes */   

    prop(object,erasable,yes).
    prop(object,creatable,yes).
    prop(directory,can_contain_directories,yes).
    prop(directory,can_contain_files,yes).
    prop(child_dir,in_directory,yes).
    prop(root,erasable,no).
    prop(root,creatable,no).
    prop(prolog_pro,interpretable,yes).
    prop(program,compilable,yes).
    prop(text,understandable,yes).
    prop(document,printable,yes).
    prop(file,in_directory,yes).
    prop(exe_file,executable,yes).

    /* remontée de la hiérarchie */

    is_instance(X,Y):- isa(X,Y).
    is_instance(X,Y):- isa(X,Z),  subclass(Z,Y).

    subclass(X,Y):- ako(X,Y).
    subclass(X,Y):- ako(X,Z), subclass(Z,Y).

    /* héritage de propriétés */

    has_property(Entity,Property,Polarity):-
      prop(Entity,Property,Polarity).

    has_property(Entity,Property,Polarity):-
                  is_instance(Entity,Class),
                  has_property(Class,Property,Polarity),
        notlocal(Entity,Property).

    notlocal(X,Y):- prop(X,Y,_),!, fail.
    notlocal(_,_).                       

   /* réification des relations */

    relation( X,Y,isa):- isa(X,Y).
    relation( X,Y,ako):- ako(X,Y).
    relation(X,Y,prop):- prop(X,Y,_).
    relation( X,Y,is_instance):- is_instance(X,Y).
    relation( X,Y,has_property):- has_property(X,Y,_).
    relation(X,Y,subclass):- subclass(X,Y).

Exemples d'invocation et résultats obtenus (en gras) 

-? is_instance(root,directory).

            yes

-? is_instance(asoft,directory).

            yes

-? is_instance(root,X).

            X = directory
            X = object

-? is_instance(asoft,X).

            X = child_dir
            X = directory
            X = object

-? subclass(bat,X).

            X = exe_file
            X = ascii_text
            X = file
            X = object
            X = text
            X = document

-? has_property(root,erasable,Quid).

            Quid = no

-? has_property(asoft,erasable,Quid).

            Quid = yes

-? has_property(wp,Property,Polarity).

            Property = executable
            Polarity = yes
            Property = in_directory
            Polarity = yes
            Property = erasable
            Polarity = yes
            Property = creatable
            Polarity = yes
            Property = understandable
            Polarity = yes
            Property = printable
            Polarity = yes

-? notlocal(root,erasable).

            no

-? notlocal(asoft,erasable).

            yes

-? relation(asoft,directory,X).

            X = is_instance

Chapitre 6 Automates non déterministes à nombre fini d'états

            Prolog est de plus en plus utilisé pour l'analyse du langage naturel (interface système-utilisateur dans les systèmes experts et sgbd, traduction automatique), et les  programmes que nous étudierons dans la suite de cet ouvrage s'y rattachent.

            Le premier s'appelle NDFA: non-deterministic finite automaton, automate non déterministe à nombre fini d'états. De quoi s'agit-il?

            Nous savons déjà ce qu'il faut entendre par non déterministe: s'il y a une solution, elle sera découverte; s'il y a plusieurs solutions, elles seront toutes découvertes. Le non-déterminisme de notre automate est dû entièrement à Prolog, à son mécanisme d'unification et de remontée.

            Un automate à nombre fini d'états est une machine abstraite caractérisée par:

1) un nombre fini d'ETATS (STATES) dans lequel l'automate peut se trouver; certains de ces états sont spéciaux car on leur attribue le prédicat INITIAL ou TERMINAL (FINAL).

2) un nombre fini de TRANSITIONS, c'est-à-dire de passages d'un état dans un autre. La condition pour qu'une transition puisse s'accomplir est la présence d'un élément sur la chaîne d'entrée; on peut toutefois prévoir des transitions qui s'accomplissent sans lecture sur la chaîne d'entrée (SILENT MOVES). Une transition se caractérise donc par trois arguments: l'état de départ, l'état d'arrivée, le mot lu.

            De tels automates peuvent servir à établir si une phrase est licite par rapport à une grammaire donnée exprimée sous forme d'ensemble de transitions. S'il y a un moyen de passer d'un état initial à un état final (un chemin dans le graphe que représente la grammaire), la phrase soumise fait partie du langage reconnu par la grammaire.

            Essayons d'expliquer tout cela à l'aide d'un exemple concret.

            Supposons que nous voulions développer un système capable de reconnaître des phrases telles que:

1) a silly man is buying a hamburger
2) mary likes the pie
3) the silly black cat is eating the pie
4) the cat is eating the pie
5) john is buying a hamburger
6) the silly man likes the hamburger
7) mary hates the pie
8) a large dog is buying a hamburger

            Plutôt que de lister toutes les phrases licites (1 à 8 ne sont que des exemples), je peux définir une machine qui me dira si la phrase est correcte.

            Voyons tout de suite comment réaliser cela en Prolog. J'établis tout d'abord un dictionnaire qui me dit à quelle(s) catégorie(s) grammaticale(s) appartient un item donné. Dans notre programme, il s'agit de la relation assoc qui lie un mot à une partie du discours. La relation assoc se définira par un paquet de clauses qui sont toutes du type fait. Nous aurons:

assoc (a, art).: a est un art, c'est-à-dire un article.

Similairement:

assoc(the, art).
assoc(large, adj).
assoc(black, adj).
assoc(silly, adj).
assoc(cat, nsgsubj).
(nsgsubj: nom singulier qui peut remplir le rôle de sujet)
assoc(dog, nsgsubj ).
assoc(man, nsgsubj ).
assoc(is, bethird ).
(bethird: troisième personne sg de BE)
assoc(john, proper ).
(proper: nom propre )
assoc(mary, proper ).
assoc(eating, ving ).
(ving: forme en -ing d'un verbe)
assoc(buying, ving ).
assoc(likes, vthird ).
(vthird: troisième personne du singulier d'un verbe)
assoc (hates, vthird ).
assoc(hamburger, nsgobj).
(nsgobj: nom singulier qui peut apparaître en position objet)
assoc(pie, nsgobj ).

            On détermine ensuite un nombre d'états. Nous les désignerons par la lettre q suivie d'un numéro d'ordre: q0, q1, q2, ... qn. Pour le petit exemple que nous considérons ici, 7 états suffisent: q0, q1, q2, ...q6.

            On affecte un ou plusieurs états de l'attribut INITIAL, et un ou plusieurs états de l'attribut FINAL. Dans notre exemple, nous aurons:

initial(q0).
final(q6).

            Nous définissons ensuite un certain nombre de transitions t, à trois arguments (état de départ, état d'arrivée, catégorie) telles que la machine abstraite peut passer de l'état de départ à l'état d'arrivée si le mot qu'elle lit sur la chaîne d'entrée relève de la catégorie prévue par la transition.

            On aura: t(q0,q1,art): la lecture d'un élément de catégorie art sur la chaîne d'entrée permet à la machine de passer de l'état q0 à l'état q1.

            De même:

t(q1, q2, nsgsubj ).
t(q2,q3, bethird ).
t(q3,q4,ving ).
t(q4,q5,art).
t(q5,q6,nsgobj ).

Avec les transitions citées ci-dessus, on pourrait reconnaître comme licites:

1) a cat is eating a pie
2) the dog is buying the hamburger
3) the man is eating the pie

et d'autres phrases encore, mais toutes de six mots, et de structure unique, à savoir:

art - nsgsubj - bethird - ving - art - nsgobj.

            Pour introduire une plus grande diversité, on peut prévoir un ensemble de transitions, et pas seulement une transition unique, d'un état x à un état y. De plus, ces deux états ne doivent pas nécessairement être adjacents. Par exemple, comme sujet de la phrase, on peut avoir un nom propre au lieu du groupe art - nsgsubj.

            Cette nouvelle possibilité s'exprime par la transition

t(q0, q2, proper).

            On remarquera que l'état q1 est "sauté". On pourra donc à présent reconnaître aussi:

4) john is eating a pie
5) mary is buying the hamburger

            De même, on peut prévoir des formes simples aussi bien que des formes progressives: le verbe à la troisième personne du singulier (likes, hates) prend la place du groupe bethird - ving (is buying, is eating):

t(q2,q4,vthird).

            La machine abstraite peut maintenant reconnaître:

6) the man likes the hamburger
7) mary hates the pie

            Finalement, on peut prévoir des éléments optionnels: il s'agit d'éléments qui, lorsqu'ils sont lus dans la chaîne d'entrée, provoquent une transition d'un état x vers le même état x: on ne progresse pas dans le graphe qui représente la grammaire.

            Par exemple, on peut avoir

t(q1,q1,adj).

qui permet l'adjonction d'un nombre quelconque d'adjectifs entre l'article et le nom dans le groupe sujet. Seront donc maintenant reconnues:

8) the silly big cat is eating a pie 
9) a black man likes a hamburger
10) the large silly black dog is buying a pie

            Notez qu'il n'y a pas de relation d'ordre entre les éléments qui peuvent satisfaire une transition optionnelle:

11) the black large silly dog is buying a pie

sera également reconnu comme appartenant à la grammaire décrite par l'automate.

            D'un point de vue plus général, on se convaincra aisément que l'automate est incapable de rendre compte de relations entre transitions. Il n'y a pas moyen de lui dire: n'acceptez la transition z entre les états c et d que si vous êtes passé de a à b en utilisant la transition x. En conséquence, les automates à nombre fini d'états ne peuvent pas rendre compte de manière élégante de bon nombre de contraintes respectées par les langages naturels. Ils ont une vue myopique des relations entre les éléments d'une phrase.

            Il nous reste à expliquer comment d'une part notre automate progresse dans la chaîne d'entrée, et d'autre part comment il peut nous donner plus d'informations qu'un pur vérificateur, qui ne pourrait nous dire que yes (la phrase appartient au langage décrit par la grammaire) ou  no (ce n'est pas le cas).

            Nous représenterons en Prolog la chaîne d'entrée comme une liste de symboles. L'automate se servira de la relation assoc pour passer de la chaîne d'entrée à la chaîne de sortie, une liste de catégories.

            Une chaîne est acceptée par l'automate s'il y a un parcours du graphe représenté par la grammaire tel que:

1) on part d'un état déclaré initial (prédicat initial(X))

2) on aboutit à un état déclaré final (prédicat final(X))

3) il existe une transition entre chaque état du parcours tel que l'élément lu sur la chaîne d'entrée est associé à la catégorie spécifiée comme troisième argument de la transition.

            Le parcours de la chaîne d'entrée se fait de manière récursive. La clause d'arrêt est constituée par une chaîne d'entrée vide. A ce moment-là, l'état atteint doit être du type final:

accepte1(Q,[],[]):- final(Q).

            Au point de départ, par contre, on doit être dans un état initial. On part d'un prédicat à deux arguments (chaîne d'entrée - des mots - et chaîne de sortie - des catégories) pour passer à un prédicat à trois arguments: état atteint, chaîne d'entrée, chaîne de sortie. Au premier appel de ce nouveau prédicat, l'état doit être un des états déclarés initiaux:

accepte(X,Y):- initial(Q), accepte1(Q,X,Y).

            Il nous reste à examiner la clause récursive. Une chaîne sera acceptée si son premier élément est accepté, et si le reste de la chaîne est accepté. Pour qu'un élément soit accepté, il faut qu'il existe une transition entre l'état dans lequel on se trouve et un autre état, et que cette transition ait comme troisième argument une catégorie qui est associée à l'élément (relation assoc). En partant de ce nouvel état, on doit pouvoir accepter le reste de la chaîne. On a donc:

accepte1(Q,[Tete|Queue],[Cat | Autres_Cat ]):-
      t(Q,Nouveletat,Cat ),
      assoc(Tete,Cat),
      accepte1(Nouveletat,Queue,Autres_Cat ).

            Nous avons décrit l'automate comme s'il ne pouvait faire que de l'ANALYSE (transformer une chaîne de mots en une chaîne de catégories si la chaîne de mots est licite dans la grammaire représentée par le graphe). Comme le programme ne contient ni coupure ni opérateurs arithmétiques ou de comparaison, ses prédicats sont réversibles. On peut donc soumettre au programme une chaîne de catégories (représentant un parcours dans le graphe) pour qu'il renvoie toutes les chaînes de mots qui y correspondent (GENERATION ou SYNTHESE).

            Le programme NDFA, que l'on trouvera ci-dessous, comporte quatre graphes. Nous n'avons analysé que le premier (état initial: q0, état final: q6). Le deuxième graphe va de l'état q7 à q10, le troisième de q11 à q15, et le quatrième de q16 à q20.

 

/* NDFA: automate non déterministe à nombre fini d'états */

/* cf. Sterling and Shapiro 1986, p.225 ; Bratko 1990, p.104 et suivantes */

/* prédicat de test */

 test(String,Parses):- accepte(String,Parses). 

/* accepter une chaîne de mots ou de catégories */

 accepte(X,Y):- initial(Q), accepte1(Q,X,Y).

 accepte1(Q,[X|Xs],[Pos|Qs]):-
         t(Q,Q1,Pos),assoc(X,Pos),
         accepte1(Q1,Xs,Qs).

 accepte1(Q,[],[]):- final(Q).

/* les transitions */

 t(q0,q1,art).
 
t(q1,q1,adj).
 t(q1,q2,nsgsubj).       
 t(q2,q3,bethird).
 
t(q0,q2,proper).
 t(q3,q4,ving).
 t(q4,q5,art).
 
t(q5,q6,nsgobj).
 t(q7,q8,nplsubj).
 t(q8,q9,bepl).
 t(q8,q9,beplsyn).
 t(q9,q9,degreeadv).
 t(q9,q10,adj).
 t(q2,q4,vthird).
 t(q11,q12,whword).
 t(q12,q13, plop).
 t(q13,q14,prpl).
 t(q14,q15,vtr).
 t(q16,q17,whword).
 t(q17,q17,expletive).
 t(q17,q18, sgop).
 t(q18,q19,prthird).
 t(q19,q20,vtr).

/* association entre mot et catégorie grammaticale */

 assoc(a, art).
 assoc(the,art).
 assoc(large, adj).
 assoc(black, adj).
 assoc(silly,adj).
 assoc( cat,nsgsubj).
 assoc(likes, vthird).
 assoc(hates, vthird).
 assoc(john, proper).
 assoc(mary, proper).
 assoc(he, prthird ).
 assoc(she, prthird).
 assoc( know, vtr).
 assoc(mean,vtr).
 assoc(propose, vtr).
 assoc(you, prpl ).
 assoc(we, prpl).
 assoc(the_hell, expletive).
 assoc(the_devil, expletive).
 assoc( man, nsgsubj).
 assoc( dog, nsgsubj).
 assoc( is, bethird ).
 assoc( eating, ving).
 assoc( buying, ving ).
 assoc( hamburger, nsgobj).
 
assoc( pie, nsgobj).
 assoc( cats, nplsubj).
 assoc( people, nplsubj).
 assoc( are, bepl).
 assoc( look, beplsyn).
 assoc( very, degreeadv).
 assoc( extremely, degreeadv).
 assoc( who, whword).
 assoc( what, whword).
 assoc( did, plop).
 assoc( do, plop).
 assoc( does, sgop).
 assoc( did, sgop ).

/* états initiaux et finals */

 initial(q0).
 initial(q7).
 initial(q11).
 initial(q16).

 final(q6).
 final(q10).
 final(q15).
 
final(q20).

Exemples d'invocation et résultats obtenus (en gras) 

?- test([the,silly,man,is,eating,a,hamburger],Cats).

            Cats = [art,adj,nsgsubj,bethird,ving,art,nsgobj]

?- test(String,[art,adj,nsgsubj,bethird,ving,art,nsgobj]).

            String = [a,large,cat,is,eating,a,hamburger]
            String = [a,large,cat,is,eating,a,pie]
            String = [a,large,cat,is,eating,the,hamburger]
            String = [a,large,cat,is,eating,the,pie]
            String = [a,large,cat,is,buying,a,hamburger]
            ...
            String = [the,silly,dog,is,buying,the,pie]

Chapitre 7 Réseaux de transition récursifs

            Nous avons vu que le problème principal de NDFA est sa vue myopique de l'analyse. Il ne domine que les rapports entre mots adjacents. Nous allons remédier à ce problème en  permettant  comme transition d'un noeud du réseau au suivant le parcours d'un sous-réseau. Nous obtenons ainsi un réseau de transition récursif (RECURSIVE TRANSITION NETWORK - RTN). Ce réseau est implémenté par le programme TRADRTN. Tradrtn est une légère adaptation de rtrans.pl, qui est dû à Gazdar et Mellish 1989 (p.459-461).

            Pour chaque sous-réseau nous pouvons définir des états initiaux et finals. Par exemple, le graphe du groupe verbal aura comme état initial one et comme état final two. On comprend donc que la déclaration des états initiaux et finals soit ici implémentée par des prédicats à deux places, la première stipulant le nom du graphe et la deuxième le nom de l'état. On aura donc par exemple, pour le groupe verbal:

initial(vp,one).          et

final(vp,two).

            Les transitions d'état à état sont représentées par les clauses du prédicat transition, pour lequel nous ouvrons quatre positions, à savoir:

a) le nom du graphe
b) l'état de départ
c) l'état d'arrivée
d) le mot (1) ou le graphe (2) à traverser

            Prenons d'abord le cas (d(1)) où le dernier argument de transition est la spécification d'une partie du discours (ou d'une catégorie grammaticale plus précise, comme par exemple vi - verbe intransitif), c'est-à-dire la condition que doit satisfaire le mot de la chaîne pour permettre la transition. Pour indiquer que l'on peut passer, dans le graphe du groupe verbal, de l'état  one à l'état two en lisant un verbe intransitif, nous écrivons:

transition(vp,one,two,vi).

            On peut passer d'un état à un autre en traversant récursivement un sous-graphe(d(2)). C'est cette possibilité qui  permet d'éviter de fastidieuses répétitions dans la grammaire. En effet, un groupe nominal sujet et un groupe nominal objet auront la même structure, et il ne sera pas nécessaire de la spécifier en détail deux fois. On se contentera d'indiquer dans chacun des cas (sujet/objet) qu'il faut traverser un sous-graphe de type groupe nominal (np). On aura donc les deux clauses:

transition(s,one,two,np). (parcours du groupe nominal sujet)

et

transition(vp,eleven,two,np). (parcours du groupe nominal objet)

            C'est expressément qu'on a utilisé ici des noms, plutôt que des nombres, pour représenter les états.  On voit que eleven précède two: c'est une simple question de convention.

            On remarquera que les clauses pour le prédicat  assoc ont elles aussi été enrichies. En effet, on a prévu une position pour le français, pour permettre une traduction mot à mot, bidirectionnelle comme dans catmat examiné dans l'introduction. Une clause assoc aura à présent trois arguments:

a) le mot anglais
b) la partie du discours (ou catégorie grammaticale)
c) le mot français

Exemple: assoc(thinks,vi,pense).

            Il nous reste à étudier les prédicats qui permettent de parcourir un graphe et ses sous-graphes. Examinons d'abord le prédicat traverse. C'est un prédicat à cinq arguments:

a) l'élément à traverser, soit un mot, soit un graphe
b) la chaîne anglaise qui reste à traverser au moment de l'appel du prédicat traverse
c) la chaîne anglaise qui restera à traverser après exécution du prédicat
d) cf b), mais pour le français
e) cf c), mais pour le français

            Le cas simple est celui du mot à traverser. On l'enlève de la chaîne pour autant qu'il satisfasse la condition spécifiée dans le premier argument, à savoir l'appartenance à la partie du discours requise. La "traduction" est elle aussi, comme on l'a vu, la tâche du prédicat assoc. On obtient donc:

traverse(Pos,[Word|X],X,[French|Z],Z):-
        assoc(Word, Pos,French ).

 

            Il se peut que l'on doive traverser tout un sous-graphe. Pour ce faire, on s'assure qu'à partir d'un état initial du sous-graphe on peut  "accepter" la chaîne, ce qui se fera par le prédicat accept, que nous étudierons dans un instant:

  traverse(Net, En1,En2,Fr1,Fr2):-
           initial(Net, Node ),
           accept(Net, Node, En1,En2,Fr1,Fr2).

            Le prédicat accept a donc 6 arguments, à savoir:

1) le graphe à accepter
2) le noeud atteint dans le graphe
3) la chaîne anglaise de départ
4) la chaîne anglaise restante
5) la chaîne française de départ
6) la chaîne française restante

            Le cas le plus simple est celui où on a atteint un noeud final du graphe à accepter: on n'a plus rien à faire, et les chaînes ne doivent plus être parcourues:

 accept(Net,Node,X,X,Z,Z):- final(Net,Node).

 

            Si le noeud Node n'est pas final dans le graphe Net, il a un successeur, que nous appelerons Nextnode. Le passage de Node à Nextnode se fera à l'aide de transition  et de traverse. Transition indiquera la nature de l'objet à traverser, soit un simple mot, soit un sous-graphe; cette information sera versée dans la variable Label. Traverse se chargera de traverser cet élément, sous-graphe ou mot, et puis on tentera d'"accepter" le reste des deux chaînes, française et anglaise, au départ de Nextnode  dans le même graphe Net. On a donc:

  accept(Net, Node, En1,En2,Fr1,Fr2):-
         transition(Net,Node,Nextnode, Label),
         traverse(Label, En1,Entemp,Fr1,Frtemp),
         accept(Net, Nextnode,Entemp, En2,Frtemp, Fr2).

            On trouvera ci-dessous le programme tradrtn en entier. On remarquera que le prédicat test est défini avec une certaine orientation: il attend une phrase anglaise et en livre la traduction française. Il est très simple de modifier le prédicat test  pour qu'il fonctionne avec l'orientation inverse, ou encore pour qu'il s'oriente en fonction du choix de l'utilisateur. On laissera au lecteur le soin de développer ces variantes.

 

/* TRADRTN */

/* Un réseau de transition récursif avec traduction bidirectionnelle anglais-français */

/* traversée du graphe */

 accept(Net,Node,X,X,Z,Z):- final(Net,Node ).

 

  accept(Net, Node, En1,En2,Fr1,Fr2):-
         transition(Net,Node,Nextnode, Label),
         traverse(Label, En1,Entemp,Fr1,Frtemp),
         accept(Net, Nextnode,Entemp, En2,
                    Frtemp, Fr2).

  traverse(Pos,[Word|X],X,[French|Z],Z):-
           assoc(Word, Pos,French ).

traverse(Net, En1,En2,Fr1,Fr2):-
           initial(Net, Node ),
           accept( Net, Node, En1,En2,Fr1,Fr2).

/* le prédicat de test */

test(St1):-
        traverse(s,St1,[],St2,[]),nl,write(St2),nl. 

/* états initiaux et finals */

initial(s,one).
      initial(vp,one).
      initial(np,one).    
      initial(pp,one).
     
      final(s,three).
      final(vp,two).
      final(np,three).
      final(pp,three).

/* les transitions */

     

      transition(s,one,two,np).
      transition(s,two,three,vp).
      transition(vp,one,two,vi).
      transition(vp,one,eleven,vtr).
      transition(vp,eleven,two,np).
      transition(pp,one,two,prep).
      transition(pp,two,three,np).
      transition(np,one,two,detm).
      transition(np,one,eleven,detf).
      transition(np,two, three,nm).
      transition(np,eleven,three,nf).
      transition(np,three,three,pp).

/* le lien entre le mot anglais, la catégorie grammaticale et le mot français */

     

     assoc(thinks,vi,pense).
     assoc(walks, vi, marche ).
     assoc(writes, vi, écrit ).
     assoc(reads, vi,lit).
     assoc(reads, vtr, lit ).
    
assoc(writes, vtr, écrit ).
     assoc(eats, vtr, mange ).
     assoc(on,prep, sur ).
     assoc( with, prep, avec).
     assoc(in,prep, dans).
     assoc(a, detm, un ).
     assoc(a, detf, une).
     assoc( the, detm, le).
     assoc(the, detf, la).
     assoc( book,nm, livre).
     assoc(mountain, nf, montagne).
     assoc(table, nf, table ).
     assoc(pie, nf, tarte).
     assoc(letter, nf, lettre).
     assoc(boy, nm,'garçon').
     assoc(girl, nf, fille).

Exemples d'invocation et résultats obtenus (en gras) 

?- test([the,girl,reads,the,letter,on,the,table]).

            [la,fille,lit,la,lettre,sur,la,table]

?- traverse(s,St1,[],[la,fille,lit,la,lettre,sur,la,table],[]).

            St1 = [the,girl,reads,the,letter,on,the,table]

 

Chapitre 8 Analyse syntaxique descendante

            Ce programme traite également de l'analyse syntaxique. Il s'appelle PARSE et montre essentiellement comment on peut construire en Prolog un analyseur syntaxique (SYNTACTIC PARSER) basé sur une grammaire indépendante du contexte (CONTEXT FREE GRAMMAR; CFG) ou grammaire hors contexte.

            Qu'est-ce qu'une cfg? C'est un ensemble de règles de réécriture, appelées aussi productions: dans chaque règle, le symbole de gauche peut être réécrit comme la succession des symboles de droite (la gauche et la droite sont séparées par une flèche). Par exemple, je peux avoir la règle suivante:

s --> np vp

            Cette règle m'indique que le symbole s (pour sentence, phrase) peut être réécrit comme la concaténation des symboles np (noun phrase: groupe nominal) et vp (verb phrase: groupe verbal).

            Les symboles s, np, et vp sont tous trois des non-terminaux, c'est-à-dire qu'ils sont réécrits par la grammaire sous forme de succession de non-terminaux et/ou terminaux. Par contre une règle telle que

art --> the

a comme partie droite un terminal: le symbole the n'est réécrit nulle part dans la grammaire.

            Si on conçoit une cfg comme la spécification d'arbres d'analyse syntaxique, on peut dire que les terminaux sont les feuilles de l'arbre. Sa racine est un non-terminal comme np ou vp, ou, pour une phrase complète, le symbole s.

            On dira d'une phrase (liste de terminaux) qu'elle est reconnue par la cfg, s'il existe une réécriture de s qui correspond à la phrase.

            Un analyseur doit faire plus que reconnaître: il doit aussi fournir l'analyse de la phrase, dans ce cas-ci l'arbre syntaxique qui y correspond.

            Si la phrase est ambigüe (susceptible de plusieurs analyses dans la grammaire qui sert de base à l'analyseur), l'analyseur doit donner toutes les analyses (non-déterminisme: ici encore c'est Prolog lui-même qui s'en charge).

            PARSE se base sur une grammaire de type cfg qui n'a d'autre but que d'exemplifier l'analyse de telles phrases ambigües. Les structures reconnues et le vocabulaire (éléments terminaux) sont extrêmement pauvres.

            La cfg qui sous-tend PARSE est la suivante:

s --> np vp

np --> snp  (un groupe nominal peut être un groupe nominal simple: a claim/ the man: la définition suit)

np --> sentnp (sentential np: contenant une phrase en apposition: the claim that he made a claim)

np --> relnp (np avec relative: the claim he considered)

snp --> det n (det: articles, etc.)

sentnp --> det sentn s (sentn: des noms tels que claim qui peuvent avoir toute une proposition en apposition: remarquez la récursivité: the claim the man made an oversimplification the woman liked,... )

relnp --> det n relcl (relcl: relative clause)

relcl --> det n vtr (vtr: verbe transitif; cette définition des relatives est tout à fait inadéquate ailleurs que dans ce petit programme: the man read/ the woman likes)

vp --> vpi (avec verbe intransitif)

vp --> vpt (avec verbe transitif)

vp --> vpc (avec verbe complexe, c'est-à-dire requérant deux groupes nominaux: un objet direct et un attribut de l'objet direct: CONSIDER the claim an oversimplification)

vpi --> vintr

vpt --> vtr np

vpc --> vcomp np np

Le vocabulaire comprend:

det: a, the, a, some, any, zero (article zéro)
n: book, claim, computer, man, oversimplification, woman
vintr: think
vtr: buy, consider, like, make, read, see, sell
vcomp: consider
sentn: claim

            La méthode d'analyse mise en oeuvre dans PARSE en fait un analyseur que l'on peut considérer comme:

1) DESCENDANT (top down): il commence par le sommet de l'arbre, et progresse vers ses feuilles; confronté à une phrase, il essaie de montrer qu'il s'agit d'une phrase reconnue par sa grammaire en réécrivant le symbole s (contraire: partir des feuilles: ascendant - bottom up)

2) DE GAUCHE A DROITE: la progression dans les listes correspondant aux phrases soumises à l'analyseur se fait de gauche à droite

3) RECURSIF: par exemple, dans l'analyse d'un groupe nominal de type sentnp, parse retrouve s, et est prêt à réessayer toutes les réécritures de s à ce niveau

4) NON DETERMINISTE:  il débusque toutes les analyses de la phrase

            La méthode utilisée par PARSE est la méthode dite parsing with difference lists. Elle est assez simple à mettre en oeuvre. Considérons la définition du prédicat parse. Il partage avec les autres prédicats d'analyse ses trois arguments:

1) la liste des mots en entrée (elle sera désignée par la variable P0)

2) la liste des mots renvoyée (ce qui reste à analyser; cette liste sera désignée par une variable dont le nom est constitué de P suivi d'un chiffre: P1, P2, P3, etc.)

3) la structure créée

            Avec parse, nous sommes au plus haut niveau: il faut que toute une phrase ait été reconnue, et qu'il ne reste rien à analyser (donc la liste renvoyée doit être vide):

parse (P0, [],[s(Np,Vp)]):-
      sentence (P0,[], [s(Np,Vp)]) .
     

            Voyons le prédicat sentence:

sentence (P0,P2, [s(Np,Vp)]):-
      nounphrase (P0,P1, Np, Number,Semsubj),
      verbphrase (P1, P2,Vp,Number,Semverb),
            sfok(Semverb,Semsubj).

            La chaîne d'entrée est divisée par le prédicat nounphrase en deux parties (la partie reconnue - celle que le groupe nominal occupe dans la phrase - et la partie encore à analyser, P1). Le prédicat verbphrase prend comme liste d'entrée cette partie de la phrase à analyser, et renvoie le reste dans P2 (on a vu que parse allait s'assurer qu'à ce niveau-ci P2 était vide).

            Le troisième argument sert à créer l'arbre d'analyse. Au niveau de la phrase, on crée une stucture s(X,Y) et on laisse à nounphrase et verbphrase le soin de déterminer quelles sont ces structures X et Y. On sera donc bien attentif au fait que dans s(Np,Vp) Np et Vp sont des VARIABLES: les noms de Np et Vp sont choisis uniquement pour leur valeur mnémonique.

            Le quatrième argument des prédicats nounphrase et verbphrase nous permet de vérifier l'accord entre le sujet et le verbe: on voit que la variable Number, qui contiendra bien sûr la valeur sing ou  plural, doit être la même dans le groupe nominal sujet et dans le groupe verbal.

            La présence d'arguments supplémentaires transforme une grammaire cfg en grammaire dcg (definite clause grammar). Les catégories syntaxiques des cfg (tels que nounphrase et verbphrase) s'enrichissent pour devenir des prédicats à n arguments. Ces arguments sont soumis au mécanisme d'unification, et le concepteur de la grammaire dcg en fait ce que bon lui semble. En conséquence, les grammaires dcg  permettent la construction aisée d'arbres syntaxiques, et la mise en oeuvre de contrôles tels que l'accord au niveau syntaxique et les règles dites de sélection au niveau sémantique (par exemple, que le verbe démissionner exige un sujet qui porte le trait sémantique [+ humain]).

            C'est ce test sémantique qui est accompli par le prédicat sfok (semantic features are OK!). On voit qu'on lui passe en argument une variable instanciée dans le groupe nominal sujet (Semsubj) et une variable instanciée dans le groupe verbal (Semverb). Nous l'examinerons en détail dans quelques instants.

            La plupart des implantations de Prolog possèdent un mécanisme interne qui leur permet d'accepter les grammaires dcg sous une forme plus simple que celle que nous présentons ici: en bref, l'utilisateur n'a plus à se soucier des indications de progression dans la liste de mots constituée par la phrase à analyser. Dans cette introduction, nous avons préféré nous en tenir à une représentation des grammaires dcg dans la syntaxe de base de Prolog, et  laisser nos programmes eux-mêmes s'assurer que la liste est parcourue séquentiellement de gauche à droite. Toutefois, nous donnons à  l'Annexe 3 de cet ouvrage une description de la notation dcg et une version de parse dans cette notation.

            Revenons à notre grammaire. Au niveau le plus bas, on atteint les éléments terminaux, et ce sont eux qui, en fait, font progresser l'analyseur dans la liste des mots constituée par la phrase à analyser.

            Considérons une clause d'élément terminal au hasard:

  verbtr([reads|X],X,[vtr(reads)],sing,human,reading_matter).

            Cette clause nous dit que, confronté à une liste de mots dont la tête est le mot reads, le prédicat verbtr renvoie en sortie la liste privée de sa tête (elle a donc bien diminué: l'analyseur avance dans la phrase). Il construit sa partie de l'arbre syntaxique, à savoir qu'il renvoie la structure de foncteur vtr et d'argument reads (le mot qui est lu apparaît donc dans l'arbre comme feuille). Le quatrième argument renvoie la constante sing: le verbe reads est décrit comme une forme du singulier. Les deux derniers arguments ont trait à la sémantique, aux règles de sélection. Le cinquième place une restriction sur le sujet de READ et le sixième sur son objet. Ces arguments sont des traits sémantiques.

            Que trouve-t-on entre les deux niveaux, le niveau de s et le niveau des éléments terminaux? On trouve des prédicats qui décrivent leur arbre particulier, assurent le passage de la variable Number, et se chargent soit de passer les traits sémantiques du lexique vers les constructions grammaticales (comme dans l'exemple ci-dessous le passage de la variable Sem du nom, élément lexical, au groupe nominal, structure syntaxique), soit d'effectuer les vérifications sémantiques (d'imposer les règles de sélection). Considérons une clause pour nounphrase prise elle aussi au hasard:

nounphrase(P0, P3, [sentnp(Det,Sentn,S)], Number,Sem):-
      determiner(P0, P1, Det, Number),
      sentnoun(P1, P2, Sentn, Number,Sem),
      sentence(P2,P3,S).

            On remarquera le passage des restes de listes: le prédicat determiner passe P1 à sentnoun, et sentnoun passe P2 à sentence.

            On remarquera ensuite la récursivité: la troisième clause de nounphrase est un appel à sentence tout à fait semblable à celui qu'on a au niveau le plus haut (mais on n'a pas d'appel à parse: la liste restante ne doit pas être vide: on n'est pas nécessairement en fin de phrase).

            La structure bâtie par nounphrase est ici

sentnp(Det, Sentn, S)

            Le prédicat est responsable du passage d'un objet à trois arguments; on pourrait donc dire qu'il crée une partie de l'arbre, laissant à ses trois prédicats subordonnés le soin de déterminer le contenu des trois sous-arbres Det, Sentn, et S (ce dernier est de nouveau tout un arbre de phrase, mais subordonné cette fois à une structure nominale).

            Voyons maintenant le passage du paramètre Number: la structure nominale aura comme nombre celle de son determiner et de son centre constitué par le nom. Ces deux valeurs doivent être les mêmes: c'est donc la même variable Number que l'on rencontre comme argument dans determiner et dans sentnoun. Cette valeur est passée au niveau le plus haut, celui de nounphrase. Si le déterminant et son nom ne s'accordent pas quant au nombre, le prédicat nounphrase échouera car l'unification des deux valeurs de Number ne pourra se faire (deux constantes différentes).

            Au niveau le plus profond (les éléments terminaux), on peut renvoyer ou ne pas renvoyer une valeur pour le paramètre Number. Nous avons vu que makes causait le renvoi de la valeur sing. Par contre, une forme du prétérit comme thought ne renverra pas de valeur: on exprime par là la propriété que thought peut avoir n'importe laquelle des deux valeurs du paramètre nombre:

  verbintr([thought|X],X,[vintr(thought)],_,human).

            On voit que la forme thought reçoit la variable anonyme (_) comme valeur du paramètre Number. On remarque aussi qu'on lui attribue le trait sémantique human dans la position qui marque la restriction sémantique sur son sujet.

           

            Prenons à présent un exemple de règle grammaticale où s'effectue le contrôle sémantique que nous étudierons en détail ci-dessous:

  verbphrase(P0,P2,[vpt,Vtr,Np],Number,Semsubj):-
    verbtr(P0,P1,Vtr,Number,Semsubj,Semobj),
    nounphrase(P1,P2,Np,_,Sem),
    sfok(Semobj,Sem).

            La clause verbtr est une clause du lexique. C'est là que sont attribués Semsubj et Semobj, qui désignent respectivement la restriction sémantique sur le sujet et sur l'objet du verbe transitif. La restriction sur le sujet est passée au groupe verbal (à verbphrase) et sera testée par sentence, car lui aura également accès au groupe nominal sujet, que verbphrase ne connaît pas. La restriction sur l'objet peut par contre être vérifiée ici: c'est ce que fait sfok, qui teste que l'objet comporte bien le trait sémantique réclamé par le verbe pour son objet.

            Finalement, on considérera le cas d'éléments qui apparaissent dans l'analyse, mais ne font pas avancer l'analyseur dans la chaîne d'entrée. Prenons le cas de l'article zéro. On a:

determiner(X,X, [det (zero)], plural).

            La chaîne d'entrée est renvoyée telle quelle en sortie (X,X), mais une structure est créée (det (zero)) et le paramètre nombre est fixé: plural (il s'agit donc ici uniquement de l'article zéro dans des groupes nominaux pluriels, comme dans men make claims et non dans patience is a virtue).

            Examinons à présent en détail le mécanisme des tests sémantiques appliqués par PARSE. On vient de voir qu'au niveau du lexique on attribue aux verbes des traits sémantiques qui reflètent leurs règles de sélection. Pour les intransitifs, on marque la restriction sémantique sur le sujet; pour les transitifs on marque les restrictions sur le sujet et sur l'objet. Par exemple, les clauses du lexique qui décrivent READ marquent dans leurs deux dernières positions la restriction sur le sujet et celle sur l'objet. Le sujet doit porter le trait human et l'objet le trait reading_matter (on ne s'inquiétera pas trop ici du caractère tautologique de ce trait; il va essentiellement nous servir à montrer l'intérêt qu'il y a à être capable de remonter dans une hiérarchie des traits). On aura donc par exemple:

  verbtr([reads|X],X,[vtr(reads)],sing,human,reading_matter).

            Qu'en est-il des noms? Ils auront des traits sémantiques inhérents, et la vérification des règles de restriction se fera en testant la correspondance entre le trait prévu dans l'entrée lexicale du verbe (et percolée jusqu'au niveau nécessaire pour la rendre accessible à la règle de grammaire chargée d'effectuer ce contrôle) et le trait attribué au nom qui forme le centre du groupe nominal dans la fonction appropriée (pour simplifier disons sujet ou objet). Toutefois, il est préférable d'attribuer aux noms des listes de traits sémantiques. La liste se limitera parfois à un seul élément, mais la possibilité d'en avoir plusieurs nous permet de dire que le mot computer possède à la fois les traits human et thing. On n'est donc pas obligé de considérer que le mot computer est ambigu entre deux acceptions: l'une où il est [+humain] et l'autre où il est [+objet]. Il pourra donc satisfaire les règles de sélection mises en oeuvre dans les énoncés suivants:

            the computer thinks  (THINK exige un sujet [+humain])

            the man bought a computer (BUY exige un objet grammatical marqué [+objet])

            De même, on attribuant à  book la liste de traits [reading_matter, thing] on pourra rendre compte des deux énoncés:

the woman read a book (READ exige un objet portant le trait

                                      reading_matter)

the woman sold a book  (SELL exige un objet portant le trait thing).

             On se persuadera aisément que les traits doivent être organisés hiérarchiquement. En effet, un verbe comme SEE prendra un objet marqué [+concret]. Le trait [+concret] est plus haut dans la hiérarchie que [+humain] et [+objet]. En fait, il est leur hyperonyme. Nous avons vu dans notre étude des réseaux sémantiques que l'on pouvait matérialiser la relation hyperonyme / hyponyme et sa transitivité par les prédicats ako et subclass. Nous les reprenons ici. On aura donc:

 subclass(X,Y):- ako(X,Y).
 subclass(X,Y):- ako(X,Z), subclass(Z,Y).
 ako(reading_matter,abstract).
 ako(thing,concrete).
 ako(human,concrete).

           

            Il nous est maintenant possible d'aborder le prédicat sfok, chargé du test de cohérence sémantique. Sa première clause s'applique si l'une des deux variables désignant des traits sémantiques n'est pas instanciée lors de l'appel à sfok; dans ce cas, par unification, elle est instanciée à l'autre, et le test sémantique réussit:

      sfok(Sem,Sem):-!.

           

            Le test réussit également si le trait sémantique exigé par le verbe fait partie de la liste des traits sémantiques attribués au nom (et percolés au niveau du groupe nominal). sfok fait appel à inlist, qui n'est rien d'autre qu'un member tout à fait déterministe, qui réussit dès que le trait a été trouvé dans la liste:

sfok(Sem, Semlist):- inlist(Sem,Semlist),!.
inlist(Sem,[Sem|_]):-!.
inlist(Sem,[_|Remainder]):- inlist(Sem,Remainder).

            On remarque les coupures à la fin des définitions de sfok: il est utilisé comme vérificateur et peut donc s'arrêter dès qu'il a réussi.

            Il nous reste à intégrer dans sfok le parcours de la hiérarchie. Si un trait ne se trouve pas dans la liste, mais qu'un des ses hyponymes s'y trouve, le test réussit néanmoins. Le parcours de la hiérarchie se fait avec subclass.

 sfok(Sem,Semlist):- subclass(Hypo,Sem),         
                                 inlist(Hypo,Semlist),!.

Par exemple, si le contrôle doit s'établir entre un groupe verbal dont le verbe est SEE et un groupe nominal en position d'objet grammatical dont le centre est BOOK, sfok sera invoqué avec les valeurs

           

sfok(concrete,[thing,reading_matter]).
subclass(Hypo,concrete)

réussira avec Hypo instancié à thing, et ensuite

inlist(thing,[thing,reading_matter]).

réussira, conduisant à la satisfaction du but sfok initial.

            On trouvera ci-dessous le programme PARSE.               

 

/* PARSE: analyseur dcg  */

/* démarrage ... */

/* cette partie est à considérer comme une boîte noire ... */

go:-
      write($Output file name for the parses? [don't forget the dot!]$),
                 nl,
                 read(Outfile),nl,
                 create(HandleOut,Outfile),close(HandleOut),
                 open(HandleOut2,Outfile,a),    
                 create(HandleIn,'bidon'),
                 close(HandleIn),!,
                 repeat,
                 nl,
                 write($Please key in your sentence or stop. to stop$),
                 nl, 
                 read_line(0,S),
                 open(HandleIn,'bidon',w),
                 write(HandleIn,S),
                 close(HandleIn),
                 open(Handlenew,'bidon',r),
                 getsentence(Sentence,Handlenew),
   /* le prédicat getsentence est  expliqué à l'annexe 1 de cet ouvrage */
                 close(Handlenew),
                 nl,write(Sentence),
                 process(Sentence,HandleOut2).

     process(Sentence,Handle):-
                 parse(Sentence,_,Parse),nl,
                 prpr(Parse,0),get0_noecho(ZZZ),
    /* le prédicat prpr ext expliqué à l'annexe 2  de cet ouvrage */
                writeq(Handle,Sentence),nl(Handle),nl(Handle),
                 writeq(Handle,Parse),nl(Handle),nl(Handle),
                 nl,
                 fail.

process([stop],Handle):-  close(Handle),!.

/* fin de la boîte noire */

/* la grammaire */

  parse(P0,[],[s,Np,Vp]):-
    sentence(P0,[],[s,Np,Vp]) .

 

  sentence(P0,P2,[s,Np,Vp]):-
     nounphrase(P0,P1,Np,Number,Semsubj),
     verbphrase(P1,P2,Vp, Number,Semverb),
     sfok(Semverb,Semsubj).

nounphrase(P0,P2,[snp,Det,N],Number,Sem):-
     determiner(P0,P1,Det,Number),
     noun(P1,P2,N,Number,Sem).

    

  nounphrase(P0,P3,[sentnp,Det,Sentn,S],Number,Sem):-
     determiner(P0,P1,Det,Number),
     sentnoun(P1,P2,Sentn,Number,Sem),
     sentence(P2,P3,S).

nounphrase(P0,P3,[relnp,Det,N,Relcl],Number,Sem):-
     determiner(P0,P1,Det,Number),
     noun(P1,P2,N,Number,Sem),
     relclause(P2,P3,Relcl).

relclause(P0,P3,[relcl,Det,N,Vtr]):-
     determiner(P0,P1,Det,Number),
     noun(P1,P2,N,Number,Sem),
     verbtr(P2,P3,Vtr,Number,Semsubj,Semobj),
     sfok(Semsubj,Sem).      

verbphrase(P0,P1,[vpi,Vintr],Number,Semsubj):-
  verbintr(P0,P1,Vintr,Number,Semsubj).

verbphrase(P0,P2,[vpt,Vtr,Np],Number,Semsubj):-
    verbtr(P0,P1,Vtr,Number,Semsubj,Semobj),
    nounphrase(P1,P2,Np,_,Sem),
    sfok(Semobj,Sem).

verbphrase(P0,P3,[vpc,Vcomp,Np1,Np2],Number,Semsubj):-
    vcomp(P0,P1,Vcomp,Number,Semsubj,Semobj),
    nounphrase(P1,P2,Np1,_,Sem),
    nounphrase(P2,P3,Np2,_,Sem),
    sfok(Semobj,Sem).

/* le lexique */

  verbintr([thinks|X],X,[vintr(thinks)],sing,human).
  verbintr([think|X],X,[vintr(think)],plural,human).
  verbintr([thought|X],X,[vintr(thought)],_,human).

 

  verbtr([buys|X],X,[vtr(buys)],sing,human,thing).
  verbtr([buy|X],X,[vtr(buy)],plural,human,thing).
  verbtr([bought|X],X,[vtr(bought)],_,human,thing).
  verbtr([considers|X],X,[vtr(considers)],sing,human,_).
  verbtr([consider|X],X,[vtr(consider)],plural,human,_).
  verbtr([considered|X],X,[vtr(considered)],_,human,_).
  verbtr([likes|X],X,[vtr(likes)],sing,human,_).
  verbtr([like|X],X,[vtr(like)],plural,human,_).
  verbtr([liked|X],X,[vtr(liked)],_,human,_).
  verbtr([makes|X],X,[vtr(makes)],sing,_,_).
  verbtr([make|X],X,[vtr(make)],plural,_,_).
  verbtr([made|X],X,[vtr(made)],_,_,_).
  verbtr([reads|X],X,[vtr(reads)],sing,human,reading_matter).
  verbtr([read|X],X,[vtr(read)],plural,human,reading_matter).
  verbtr([read|X],X,[vtr(read)],_,human,reading_matter).
  verbtr([sees|X],X,[vtr(sees)],sing,human,concrete).
  verbtr([see|X],X,[vtr(see)],plural,human,concrete).
  verbtr([saw|X],X,[vtr(saw)],_,human,concrete).
  verbtr([sells|X],X,[vtr(sells)],sing,human,thing).
  verbtr([sell|X],X,[vtr(sell)],plural,human,thing).
  verbtr([sold|X],X,[vtr(sold)],_,human,thing).

  vcomp([considers|X],X,[vcomp(considers)],sing,human,_).
  vcomp([consider|X],X,[vcomp(consider)],plural,human,_).
  vcomp([considered|X],X,[vcomp(considered)],_,human,_).

 

  determiner([a|X],X,[det(a)], sing).
  determiner([the|X],X,[det(the)],_).
  determiner([an|X],X,[det(an)],sing).
  determiner(X,X,[det(zero)],plural).
  determiner([some|X],X,[det(some)],_).
  determiner([any|X],X,[det(any)],_).

  noun([book|X],X,[n(book)],sing,[thing,reading_matter]).
  noun([books|X],X,[n(books)],plural,[thing,reading_matter]).
  noun([claim|X],X,[n(claim)],sing,[abstract]).
  noun([claims|X],X,[n(claims)],plural,[abstract]).
  noun([computer|X],X,[n(computer)],sing,[thing,human]).
  noun([computers|X],X,[n(computers)],plural,[thing,human]).
  noun([man|X],X,[n(man)],sing,[human]).
  noun([men|X],X,[n(men)],plural,[human]).
  noun([oversimplification|X],X,[n(oversimplification)],
                                                                  sing,[abstract]). 
  noun([oversimplifications|X],X,[n(oversimplifications)],
                                                                 plural,[abstract]). 
  noun([woman|X],X,[n(woman)],sing,[human]).
  noun([women|X],X,[n(women)],plural,[human]).

  sentnoun([claim|X],X,[sentn(claim)],sing,[abstract]). 
 
sentnoun([claims|X],X,[sentn(claims)],plural,[abstract]).  

  /* hiérarchie sémantique: le prédicat subclass est repris au programme SEMNET.ARI */

 subclass(X,Y):- ako(X,Y).
 subclass(X,Y):- ako(X,Z), subclass(Z,Y).
 ako(reading_matter,abstract).
 ako(thing,concrete).
 ako(human,concrete).

/* test sur la sémantique */

 sfok(Sem,Sem):-!.
 sfok(Sem,Semlist):- inlist(Sem,Semlist),!.
 sfok(Sem,Semlist):- subclass(Hypo,Sem), inlist(Hypo,Semlist).
 inlist(Sem,[Sem|_]):-!.
 inlist(Sem,[_|Remainder]):- inlist(Sem,Remainder).

Exemples d'invocation et résultats obtenus (en gras) 

?-go.

            Please key in your sentence or stop. to stop

the man considers the claim the woman made an oversimplification
[the,man,considers,the,claim,the, woman,made,an,oversimplification]

s         

            snp

                        det(the)

                        n(man)

            vpt

                        vtr(considers)

                        sentnp

                                    det(the)

                                    sentn(claim)

                                    s

                                                snp

                                                            det(the)

                                                            n(woman)

                                                vpt

                                                            vtr(made)

                                                            snp

                                                                        det(an)

                                                                        n(oversimplification)                                                                                        


s

            snp

                        det(the)

                        n(man)

            vpc

                        vcomp(considers)

                        relnp

                                    det(the)

                                    n(claim)

                                    relcl

                                                det(the)

                                                n(woman)

                                                vtr(made)

                        snp

                                    det(an)

                                    n(oversimplification)

Chapitre 9 Méta-interprètes et analyse ascendante

            Parse est un analyseur descendant: il progresse de la racine de l'arbre (s) vers ses feuilles. On se rend facilement compte que de tels analyseurs sont mis en difficulté par des règles récursives à gauche, c'est-à-dire des règles qui se conforment au schéma suivant:

a:- a,b,c,...

Pour satisfaire a, l'analyseur descendant doit tout d'abord satisfaire a, puisque c'est la première clause du corps de la règle. Pour satisfaire cet a, il doit satisfaire a ... Il est donc pris dans un cercle vicieux.

            Une première solution consiste à éviter l'emploi de règles récursives à gauche. Mais ce procédé n'est pas toujours aisé à mettre en oeuvre, et, dans le cas du traitement du langage naturel, conduit souvent à des analyses moins naturelles. Considérons le cas du groupe nominal en anglais. On désirera analyser the man's bag comme determiner + noun, le rôle du determiner étant rempli ici par la séquence the man's. Il est clair que la séquence the man's est à son tour à analyser comme un groupe nominal (the man) suivi d'apostrophe s ('s). On est donc en présence d'un couple de règles qui, par leur interaction, conduisent au problème de la récursivité à gauche. Schématiquement,

np:- determiner,noun
determiner:- np, apostrophe-s

            Notons tout de suite que le problème n'est nullement limité à l'anglais. Toutes les langues que nous connaissons possèdent un mécanisme de coordination, qui permet d'obtenir une structure donnée par la conjonction de deux ou plusieurs structures du même type, par exemple:

np + np = np    jean et marie; le camion et la voiture que tu as vue hier
vp + vp = vp    croit en l'avenir et se moque du passé
s + s = s          il croit en l'avenir et elle se moque du passé

Il est clair que la représentation naturelle d'une telle structure fera appel aux règles suivantes:

np:- np, coordinator, np
vp:- vp, coordinator, vp
s  :- s, coordinator, s

toutes règles immédiatement récursives à gauche.

            Un analyseur (ascendant) qui part des feuilles, construit les constituants intermédiaires, et aboutit finalement à la racine, ne connaît pas ce problème. En effet, dans une structure telle que np1(Np1a, Coordinator, Np1b) les deux np à coordonner sont plus près des feuilles, et sont donc d'abord construits, avant que ne soit tentée la reconnaissance de np1.

            Dans un tel analyseur ascendant, on prévoit un lexique, auquel seront confrontées les feuilles de l'arbre (les mots de la phrase à analyser) au début de l'analyse. Dans notre programme, ce lexique est matérialisé par des règles telles que:

lex(noun, man, [n(man)], sing)

qui se conforment au schéma:

lex(Type, Chaîne, Arbre d'analyse, Nombre).

            Rappelons-nous que Parse non seulement était descendant, mais encore accomplissait l'analyse de gauche à droite. Nous allons lever ici cette restriction. Notre nouvel analyseur va pouvoir s'intéresser à tout moment à tout élément de la chaîne à analyser ou de l'arbre en train de se construire. Nous ne pouvons donc plus utiliser les  difference lists, puisque l'analyse ne donne plus nécessairement un reste à analyser sous la forme d'une chaîne d'éléments adjacents.

            Nous continuerons à travailler avec une représentation en liste de la chaîne d'entrée (on se rappelle que ce travail de conversion est confié à une boîte noire ... jusqu'à l'Annexe 1). On aura donc, pour la chaîne

the man likes the woman

la liste

[the, man, likes, the, woman]

Nous allons transformer cette liste en une série de prédicats que nous insérerons dynamiquement dans la base de données de Prolog. Ces prédicats indiqueront la position de chaque élément dans la liste. Après conversion, on aura donc:

position(0,1,the).
position(1,2,man).
position(2,3,likes).
position(3,4,the).
position(4,5,woman).
fin(5).

On voit que le prédicat fin indique la position finale dans la chaîne à analyser. Comme on détient maintenant les positions de tous les éléments, on va pouvoir s'en servir pour analyser la chaîne à tout endroit voulu.

Le travail de conversion de la liste en série de prédicats position(X,Y,Z) est réalisé par le prédicat process, repris ci-dessous:

     process([Head|Tail],Pos):-
                 Posand1 is Pos + 1,
                 recorda(pos,position(Pos,Posand1,Head),_),
                 process(Tail,Posand1).

     process([],X):-
                 recorda(fin,fin(X),_).

Le prédicat recorda est prédéfini en Arity Prolog. Il est semblable à assert, mais est plus efficace pour l'assertion de faits, c'est-à-dire de clauses sans corps. Il prend trois arguments:

1. une clé, qui permet de ranger les prédicats ajoutés à la base de données dans des 'boîtes' différentes, ce qui permet leur rappel plus rapide en cas de besoin. On voit qu'ici on crée et utilise deux de ces boîtes, à savoir pos (pour les positions) et fin (pour l'indication de la fin de chaîne).

2. le prédicat à insérer dans la base de données

3. une référence interne, de peu d'intérêt pour l'utilisateur, et donc indiquée par la variable muette.

            On voit que process prend deux arguments, une liste et une position. La position est au départ 0, mais elle augmente de 1 à chaque appel. La liste, elle, diminue d'un élément à chaque appel. Lorsqu'on arrive en bout de liste, la position est la position finale, et on ajoute à la base de données le prédicat fin.

            On sait que le mécanisme d'exécution de Prolog lui-même est descendant. C'est pourquoi on n'a pas eu trop de peine à construire parse. On a dû, bien sûr, spécifier le lexique et la grammaire, mais pour le reste on s'en est remis à Prolog. On ne peut pas procéder de même ici, puisqu'on ne veut plus d'analyse descendante.

            Nous allons devoir écrire un méta-interprète (ou méta-interpréteur) de Prolog, c'est-à-dire un programme en Prolog qui dit à Prolog comment il doit analyser certaines des clauses qu'on lui soumet. Ce sont ces clauses spéciales qui contiendront notre grammaire. On va leur donner une forme très simple, à savoir:

[liste de conditions]  opérateur  [liste d'actions]

            L'interprétation que nous proposerons à Prolog de suivre est elle aussi très simple: si toutes les conditions à gauche de l'opérateur sont satisfaites, alors il faut accomplir toutes les actions à droite de l'opérateur. On utilise un opérateur spécial pour que Prolog sache quand il est en présence de ces clauses spéciales.

            Voyons tout d'abord comment définir un opérateur. On utilise pour ce faire une directive, c'est-à-dire un prédicat spécial, précédé du signe :- . La directive pour la déclaration de notre opérateur spécial est la suivante:

 

:- op(800,xfx,--->).

            Le prédicat spécial op prend trois arguments:

1. la précédence de l'opérateur, qui indique quels éléments il lie dans une clause. Les opérateurs de basse précédence lient avant les opérateurs de plus haute précédence. C'est ainsi que l'opérateur de multiplication (*) a une précédence moins élevée que l'opérateur d'addition (+), pour que

X is 3 + 2 * 7

donne 17 (3 + (2 * 7))  et non 35 (( 3+2) * 7)  (dans Arity Prolog,  * a 400 de précédence, et + 500).

            La précédence d'un opérateur se détermine donc en fonction de celles attribuées aux autres opérateurs, à la fois les opérateurs prédéfinis (on consulte la documentation du produit) et les autres opérateurs définis par l'utilisateur dans le programme.

            La précédence de 800 rend notre opérateur plus liant que la virgule, ce qui est nécessaire pour une interprétation correcte de la clause suivante de notre programme:

run1:-  Condition ---> Action,
        test(Condition),
        execute1(Action).

L'opérateur ---> liera donc Condition et Action. Les limites posées par:- et la virgule ne seront pas franchies, car ces opérateurs ont des précédences plus élevées (dans Arity Prolog,:- a 1200 de précédence et la virgule 1000).

2. l'associativité et la place de l'opérateur. Nous n'entrerons pas dans les détails. xfx signifie que l'opérateur (f) est infixe, c'est-à-dire se place entre ses arguments (x).

3. le signe qui représente l'opérateur (ici --->).

            Revenons à notre méta-interpréteur (étroitement inspiré de Bratko, 1990, p.559). Nous voulons qu'il teste toutes les conditions reprises dans la liste Condition et, si elles sont toutes satisfaites, accomplisse toutes les actions reprises dans la liste Action. C'est ce dont se charge le prédicat run1, dont nous venons de citer la définition. Voyons à présent comment le prédicat test teste la liste des conditions:

test([]).
test([First|Rest]):-
                       call(First),
                       test(Rest).

            On a donc un parcours de la liste des conditions, chaque condition étant passée en argument au prédicat call. Ce prédicat est prédéfini. Son rôle est très simple: il exécute son argument comme s'il s'agissait d'un but à satisfaire. On voit donc que call(X) réussit si X réussit. L'intérêt de call est que les buts à satisfaire peuvent être présentés sous forme de données, comme ils le sont dans notre programme.

            Voyons l'exécution de la liste d'actions. Elle est programmée comme suit:

execute1([]):- run1.
execute1([First|Rest]):- call(First),
                                     execute1(Rest).

            La seconde clause de execute1 est tout à fait parallèle à la seconde clause du prédicat test. La première est différente, en ceci que lorsqu'il n'y a plus d'actions à accomplir, execute1 relance le processus d'interprétation défini par run1. Nous allons comprendre pourquoi si nous examinons le contenu de nos listes de conditions et d'actions, c'est-à-dire le contenu de notre grammaire.

            Réfléchissons au processus d'analyse d'une phrase. Il est aisé de comprendre qu'il s'agit d'un processus monotone[9] qui ajoute de l'information, sans jamais en retirer. Au départ, on a une liste de mots. Le lexique leur attribue à chacun une liste de parties du discours (en cas d'absence d'ambiguïté lexicale, cette liste n'a qu'un élément). Ensuite, les règles de grammaire viennent s'appliquer, pour reconnaître dans la phrase des groupes, comme les groupes nominaux et verbaux. Finalement, ces groupes s'associent pour former des propositions ou des phrases.

            Prenons un moment de l'analyse où toutes les règles du lexique et de la grammaire viennent de s'exécuter. Supposons que la règle de formation du groupe nominal ait reconnu comme groupe nominal the claim et l'ait ajouté à la base de données (ajout d'information via le prédicat recorda) et que la règle de reconnaissance des phrases ait formé un s hors du groupe nominal the man et du groupe verbal likes the woman, et l'ait aussi ajouté à la base de données. Les règles ont toutes été parcourues, mais comme elles ont ajouté de l'information, il convient de les reparcourir pour voir si elles ne s'appliquent pas à nouveau. Par exemple, lors de ce nouveau passage, une règle de reconnaissance du groupe nominal pourra s'appliquer si le groupe nominal préalablement reconnu, à savoir the claim, est suivi immédiatement du s préalablement reconnu, à savoir the man likes the woman. Cette règle combine un groupe nominal dont la tête est un nom régissant une proposition et une phrase adjacente interprétée comme le complément de ce nom: the claim the man likes the woman.

            Ce procédé qui consiste à ajouter de l'information à une base de données qui représente l'état actuel de l'analyse est aussi utilisé dans les CHART PARSERS, qui, pour des raisons d'efficacité, combinent un analyseur ascendant ou descendant avec le CHART, c'est-à-dire la structure de données représentant l'analyse à un moment donné du processus d'analyse.

            En effet, dans notre programme, on n'a fini l'analyse que lorsque plus aucune règle de la grammaire ou du lexique ne peut s'appliquer. Ce procédé, qui parcourt et reparcourt incessamment tout le lexique et la grammaire, est extrêmement coûteux en temps, comme on s'en persuadera en comparant le temps mis par parse et par ce programme-ci pour fournir les analyses d'une phrase ambigüe comme

the man considers the claim the woman made an oversimplification

            On peut améliorer un peu l'efficacité du programme en séparant, comme nous l'avons fait, lexique et grammaire. Les règles lexicales de la grammaire reconnaissent les informations à associer aux feuilles de l'arbre. Elles peuvent s'accomplir en bloc, avant que les règles de grammaire proprement dites ne commencent à s'appliquer. C'est pourquoi nous avons défini deux procédures parallèles, run1 et run2, chacune avec leur opérateur distinct:

--->: 3 traits d'union et la flèche: règles lexicales dans la grammaire

------>: 6 traits d'union et la flèche: règles grammaticales stricto sensu

Run1 accomplit son travail, et, lorsqu'il n'a plus rien à ajouter, run2 prend la relève. Cette séquence des deux programmes est matérialisée par le prédicat run, défini comme suit:

run:- run1.
run:- run2.

On voit que run2 ne commencera son travail qu'en cas d'échec de run1. Cet échec n'interviendra que quand run1 n'aura plus aucune clause susceptible de réussir. Pour comprendre pourquoi, il convient d'étudier à présent la nature des clauses spéciales de notre analyseur, à savoir les listes de conditions et d'actions séparées par les deux opérateurs ---> et ------>. Prenons une règle lexicale et une règle grammaticale au hasard:

REGLE LEXICALE

[recorded(pos,position(A,B,Vtr),_),
 lex(verbtr,Vtr,Treeverb,Number)] --->
[reconce(verbtr,verbtr(A,B,Treeverb,Number),_)].

REGLE GRAMMATICALE

[recorded(det,det(A,B,Tree1,Number),_),
 recorded(noun,noun(B,C,Tree2,Number),_)] ------>
[reconce(np,np(A,C,[np,simplenp,Tree1,Tree2],Number),_)].

            Dans la règle lexicale, les conditions sont de deux types:

1. appel au prédicat lex pour comparer une feuille (ici Vtr) à l'information y associée dans le lexique,
2. appel au prédicat recorded pour obtenir une feuille et sa position dans la chaîne.

            L'action est toujours la même. Il s'agit d'un appel au prédicat reconce, qui insère de l'information dans la base de données, si cette information n'y est pas encore.

            En effet, reconce est défini comme suit:

reconce(X,Y,Z):-
                 not(recorded(X,Y,Z)),
                 recorda(X,Y,Z).

            On se rend donc compte que reconce échoue si l'information à inclure dans la base de données s'y trouve déjà. Lorsque tous les reconce de toutes les clauses du lexique échouent, c'est que le lexique a fini son travail. Run tente alors de réussir via sa seconde clause, à savoir un appel à run2, qui lance les règles grammaticales.

            Dans une règle de grammaire, les conditions sont d'un seul type: elles vérifient que des informations sont bien présentes dans la base de données. Les actions sont elles aussi toutes du même type: ajout conditionnel d'information dans la base de données, la condition étant bien sûr l'absence de cette information dans la base.

            On remarquera l'utilisation des positions (A, B, C, D, ...) pour assurer l'adjacence des  éléments. Pour améliorer l'efficacité du programme, on met en tête des conditions celle ou celles qui a ou ont le plus de chances d'échouer[10]. Par exemple, pour la reconnaissance des structures coordonnées, on s'assurera d'abord que la chaîne comporte la conjonction de coordination.

            Voyons maintenant quand et comment les résultats de l'analyse sont transmis à l'utilisateur. Pour qu'une analyse intéresse l'utilisateur, il faut qu'elle concerne la phrase tout entière[11], c'est-à-dire que la chaîne couverte par l'analyse aille de la position 0 à la position donnée par le prédicat fin. Il faut en outre que cette analyse ne lui ait pas été déjà communiquée (test accompli par recorded).

            On présentera l'analyse sous forme d'arborescence, ce qui est accompli par notre deuxième petite boîte noire, prpr (voir Annexe 2).

            On obtient donc:

[recorded(s,s(0,B,Tree),_),
 recorded(fin,fin(B),_)] ------>
[not(recorded(tree,tree(0,B,Tree),_)),
 nl,
 prpr(Tree,0),
 recorda(tree,tree(0,B,Tree),_),
 nl,
 write($ --- ANY KEY TO GO ON ---$),nl,
 get0_noecho(_) ].

            Bien sûr, il faut nettoyer la base de données après chaque phrase. C'est le rôle joué par le prédicat clear, qui est défini comme une série d'appels au prédicat prédéfini eraseall(Key), où Key représente une clef telle que nous l'avons définie dans notre présentation de recorda.

            Clear a donc la définition suivante:

clear:-
       eraseall(pos),
       eraseall(fin),
       eraseall(tree),
       eraseall(s),
       eraseall(np),
       eraseall(vp),
       eraseall(verbintr),
       eraseall(verbtr),
       eraseall(coord),
       eraseall(det),
       eraseall(sentnoun),
       eraseall(noun),
       eraseall(vcomp),
       eraseall(relclause),
       eraseall(apo).

            Pour utiliser le programme, on lancera le but go. Go accomplira pour chaque énoncé à analyser les trois opérations suivantes:

1. invoquer gets, la boîte noire qui se charge de convertir la chaîne entrée au terminal en liste de mots, et qui fait ensuite appel à process pour insérer dans la base de données les mots accompagnés de leurs positions;

2. invoquer run, qui accomplit l'analyse et imprime les résultats;

3. invoquer clear, qui nettoie la base de données, et puis relancer go.

            Pour arrêter, on entrera stop au terminal après avoir invoqué go.

            On se convaincra que les régles récursives à gauche ne posent pas de problèmes en demandant l'analyse d'énoncés tels que:

the man and the woman like the book.
the man reads and likes the book.
the man reads the book and the woman likes the man.
the man likes the woman's book.

            On trouvera ci-dessous le programme dans sa totalité. Il porte le nom de grpd.ari.

 

/* GRPD.ARI, UN ANALYSEUR ASCENDANT */

/* déclarations d'opérateurs... */

/* pour les règles lexicales de la grammaire: 3 tirets --- */

:- op(800,xfx,--->).

/* pour les règles grammaticales proprement dites: 6 tirets ------ */

:- op(800,xfx,------>).

/* démarrage */

go:- gets,run,!,fail.
go:- clear,go.

/* obtenir une phrase de l'utilisateur */

gets:-
                 create(HandleIn,'bidon'),
                 close(HandleIn),!,
                 nl,
                 write($Please key in your sentence or stop. to stop$),
                 nl, 
                 read_line(0,S),
                 open(HandleIn,'bidon',w),
                 write(HandleIn,S),
                 close(HandleIn),
                 open(Handlenew,'bidon',r),
                 getsentence(Sentence,Handlenew),
                 /* voir annexe 1 */
                 close(Handlenew),
                 nl,write(Sentence),
                 process(Sentence,0).

/* chaque mot de la liste reçoit une position de départ et de fin dans la liste */

     process([Head|Tail],Pos):-
                 Posand1 is Pos + 1,
                 recorda(pos,position(Pos,Posand1,Head),_),
                 process(Tail,Posand1).

 

/* la position du dernier mot indique la fin de la liste */

     process([],X):-
                 recorda(fin,fin(X),_).

/* méta-interprète */

/* adapté de Bratko 1990 */

run:- run1.  /* règles lexicales de la grammaire */

run:- run2.  /* règles grammaticales  proprement dites */

run1:-  Condition ---> Action,
        test(Condition),
        execute1(Action).

run2:-  Condition ------> Action,
        test(Condition),
        execute2(Action).

test([]).

test([First|Rest]):-
                       call(First),
                       test(Rest).

execute1([]):- run1.

execute1([First|Rest]):- call(First),
                         execute1(Rest).

execute2([]):- run2.

execute2([First|Rest]):- call(First),
                         execute2(Rest).

/* utilitaire */

/* ajouter l'info à la bd si elle ne s'y trouve pas déjà */

reconce(X,Y,Z):-
                 not(recorded(X,Y,Z)),
                 recorda(X,Y,Z).

/* le lexique */

lex(verbintr,thinks,[vintr(thinks)],sing).
lex(verbintr,think,[vintr(think)],plural).
lex(verbintr,thought,[vintr(thought)],_).
lex(verbtr,reads,[vtr(reads)],sing).
lex(verbtr,read,[vtr(read)],plural).
lex(verbtr,read,[vtr(read)],_).
lex(verbtr,considered,[vtr(considered)],_).
lex(verbtr,made,[vtr(made)],_).
lex(verbtr,make,[vtr(make)],plural).
lex(verbtr,makes,[vtr(makes)],sing).
lex(verbtr,considers,[vtr(considers)],sing).
lex(verbtr,consider,[vtr(consider)],plural).
lex(verbtr,likes,[vtr(likes)],sing).
lex(verbtr,like,[vtr(like)],plural).
lex(verbtr,liked,[vtr(liked)],_).
lex(vcomp,considered,[vcomp(considered)],_).
lex(vcomp,consider,[vcomp(consider)],plural).
lex(vcomp,considers,[vcomp(considers)],sing).
lex(determiner,a,[det(a)],sing).
lex(determiner,the,[det(the)],_).
lex(determiner,an,[det(an)],sing).
lex(determiner,some,[det(some)],_).
lex(determiner,any,[det(any)],_).
 
lex(noun,man,[n(man)],sing).
lex(noun,book,[n(book)],sing ).
lex(noun,claim,[n(claim)],sing).
lex(noun,oversimplification,[n(oversimplification)],sing). 
lex(noun,woman,[n(woman)],sing).
lex(noun,men,[n(men)],plural).
lex(noun,books,[n(books)],plural).
lex(noun,claims,[n(claims)],plural).
lex(noun,oversimplifications,[n(oversimplifications)],plural). 
lex(noun,women,[n(women)],plural).
              
lex(sentnoun,claim,[sentn(claim)],sing). 
lex(sentnoun,claims,[sentn(claims)],plural).  
                                   
lex(coord,and,[coord(and)]).

 /* la grammaire */

/*  PREDICATS  LEXICAUX */

/* l'apostrophe du génitif anglo-saxon */

[recorded(pos,position(A,B,s),_)] --->
[reconce(apo,apo(A,B),_)].

/* les noms */

[recorded(pos,position(A,B,Noun),_),
 lex(noun,Noun,Tree,Number)] --->
[reconce(noun,noun(A,B,Tree,Number),_)].

/* les determiners */

[recorded(pos,position(A,B,Det),_),
 lex(determiner,Det,Tree,Number)] --->
[reconce(det,det(A,B,Tree,Number),_)].

/* les noms qui ont une proposition pour cplt */

[recorded(pos,position(A,B,Sn),_),
 lex(sentnoun,Sn,Tree,Number)] --->
[reconce(sentnoun,sentnoun(A,B,Tree,Number),_)].

/* les verbes intransitifs */

[recorded(pos,position(A,B,Vi),_),
 lex(verbintr,Vi,Tree,Number)] --->
[reconce(vp,vp(A,B,[vp,Tree],Number),_)].

/* les verbes transitifs */

[recorded(pos,position(A,B,Vtr),_),
 lex(verbtr,Vtr,Treeverb,Number)] --->
[reconce(verbtr,verbtr(A,B,Treeverb,Number),_)].

/* les verbes qui prennent un objet direct
 et un attribut de cet objet */

[recorded(pos,position(A,B,Vcomp),_),
 lex(vcomp,Vcomp,Treeverb,Number)] --->
[reconce(vcomp,vcomp(A,B,Treeverb,Number),_)].

/* la conjonction de coordination  AND */

[recorded(pos,position(A,B,And),_),
 lex(coord,And,Treeand)] --->
[reconce(coord,coord(A,B,Treeand),_)].

/*  PREDICATS  GRAMMATICAUX*/

/* DETERMINERS */

/* le génitif anglo-saxon comme determiner: the man's book */

 [ recorded(apo,apo(B,C),_),
   recorded(np,np(A,B,Tree,Number),_)] ------>
 [ reconce(det,det(A,C,[det,Tree],_),_)].

/* GROUPES NOMINAUX */

/* simples, avec determiner différent de zéro */

[recorded(det,det(A,B,Tree1,Number),_),
 recorded(noun,noun(B,C,Tree2,Number),_)] ------>
[reconce(np,np(A,C,[np,simplenp,Tree1,Tree2],Number),_)].

/* simples, avec zéro determiner */

[recorded(noun,noun(A,B,Tree,plural),_)] ------>
[reconce(np,np(A,B,[np,simplenp,det(zero),Tree],plural),_)].

/* avec une proposition comme cplt */

[ recorded(sentnoun,sentnoun(B,C,Tree2,Number),_),
  recorded(det,det(A,B,Tree1,Number),_),
  recorded(s,s(C,D,Tree3),_)] ------>
[reconce(np,np(A,D,[np,sententialnp,Tree1,Tree2,Tree3],
Number),_)].

/* avec une relative */

[recorded(det,det(A,B,Tree1,Number),_),
 recorded(noun,noun(B,C,Tree2,Number),_),
 recorded(relclause,relclause(C,D,Tree3),_)] ------>
[reconce(np,np(A,D,[np,relclausenp,Tree1,Tree2,Tree3],
Number),_)].

/* gn coordonnés */

[ recorded(coord,coord(B,C,Tree2),_),
  recorded(np,np(A,B,Tree1,Number1),_),
  recorded(np,np(C,D,Tree3,Number3),_)] ------>
[reconce(np,np(A,D,[np,Tree1,Tree2,Tree3],plural),_)].

/* GROUPES VERBAUX */

/* verbes transitifs coordonnés */

[ recorded(coord,coord(B,C,Treeand),_),
  recorded(verbtr,verbtr(A,B,Treeverb1,Number),_),
  recorded(verbtr,verbtr(C,D,Treeverb2,Number),_)] ------>
[reconce(verbtr,verbtr(A,D,
[vtr,Treeverb1,Treeand,Treeverb2],Number),_)].

/* avec verbe transitif */

[recorded(verbtr,verbtr(A,B,Treeverb,Number),_),
 recorded(np,np(B,C,Treenp,Numbernp),_)] ------>
[reconce(vp,vp(A,C,[vp,Treeverb,Treenp],Number),_)].

/* avec verbe transitif complexe (COD + attribut du COD) */

[recorded(vcomp,vcomp(A,B,Treeverb,Number),_),
 recorded(np,np(B,C,Treenp1,Numbernp),_),
 recorded(np,np(C,D,Treenp2,Numbernp),_)] ------>
[reconce(vp,vp(A,D,[vp,Treeverb,Treenp1,Treenp2],
Number),_)].

/* groupes verbaux coordonnés */

[ recorded(coord,coord(B,C,Tree2),_),
  recorded(vp,vp(A,B,Tree1,Number),_),
  recorded(vp,vp(C,D,Tree3,Number),_)] ------>
[reconce(vp,vp(A,D,[vp,Tree1,Tree2,Tree3],Number),_)].

/* PROPOSITIONS RELATIVES */

 [recorded(det,det(A,B,Tree1,Number),_),
 recorded(noun,noun(B,C,Tree2,Number),_),
 recorded(verbtr,verbtr(C,D,Tree3,Number),_)] ------>
[reconce(relclause,
         relclause(A,D,[relclause,Tree1,Tree2,Tree3]),_)].

/* PHRASES */

 [ recorded(vp,vp(B,C,Treevp,Number),_),
  recorded(np,np(A,B,Treenp,Number),_)] ------>
[reconce(s,s(A,C,[s,Treenp,Treevp]),_)].

/* coordonnées */

[ recorded(coord,coord(B,C,Tree2),_),
  recorded(s,s(A,B,Tree1),_),
  recorded(s,s(C,D,Tree3),_)] ------>
[reconce(s,s(A,D,[s,Tree1,Tree2,Tree3]),_)].

/* production des résultats ... */

 [recorded(s,s(0,B,Tree),_),
 recorded(fin,fin(B),_)] ------>
[not(recorded(tree,tree(0,B,Tree),_)),
 nl,
 prpr(Tree,0),                      /* voir Annexe 2 */
 recorda(tree,tree(0,B,Tree),_),
 nl,
 write($ --- ANY KEY TO GO ON ---$),nl,
 get0_noecho(_) ].

/* arrêt ... */

 [recorded(pos,position(0,1,stop),_)] ---> [abort].

/* abort: prédéfini qui cause le retour immédiat à l'interpréteur Prolog  */

/* Raz de la bd ... */

clear:-
       eraseall(pos),
       eraseall(fin),
       eraseall(tree),
       eraseall(s),
       eraseall(np),
       eraseall(vp),
       eraseall(verbintr),
       eraseall(verbtr),
       eraseall(coord),
       eraseall(det),
       eraseall(sentnoun),
       eraseall(noun),
       eraseall(vcomp),
       eraseall(relclause),
       eraseall(apo).
 Exemples d'invocation et résultats obtenus (en gras) 

-? go.

            Please key in your sentence or stop. to stop

the woman reads and likes the man's book.

            [the,woman,reads,and,likes,the,man,s,book]

            s

                        np

                        simplenp

                                    det(the)

                                    n(woman)

                        vp

                                    vtr

                                                vtr(reads)

                                                coord(and)

                                                vtr(likes)

                                    np

                                    simplenp

                                                det

                                                            np

                                                            simplenp

                                                                        det(the)

                                                                        n(man)

                                                n(book)

 

            Il n'est peut-être pas inintéressant de revenir sur notre méta-interprète et d'en proposer une nouvelle version. Elle nous permettra de nous assurer que nous avons bien saisi le mécanisme de satisfaction des buts, qui est au coeur même de la machine abstraite Prolog.

             Dans la première version de notre méta-interprète les opérateurs ---> et ------> séparent une liste de conditions d'une liste d'actions. Or, les conditions et les actions sont toutes deux soumises à la même opération, à savoir call. Elles sont exécutées comme des buts à satisfaire. On peut donc sans problème déplacer les conditions à la droite de nos opérateurs. En fait, la distinction condition/action n'a pas de sens ici. Si l'on maintient le caractère infixe de nos opérateurs, on pourra utiliser l'opérande de gauche pour donner un nom à la règle. Ce nom ne servira qu'à la maintenance de notre lexique et de notre grammaire: le méta-interprète Prolog n'en fera rien. Pour simplifier les choses, ne gardons qu'un des deux opérateurs, à savoir --->, qui servira donc aussi bien au lexique qu'à la grammaire. Nous aurons des règles telles que:

/* lexique */

nouns --->
[recorded(pos,position(A,B,Noun),_),
 lex(noun,Noun,Tree,Number),
not(recorded(noun,noun(A,B,Tree,Number),_)),
    recorda(noun,noun(A,B,Tree,Number),_)].

/* grammaire */

simplenps --->
[recorded(det,det(A,B,Tree1,Number),_),
recorded(noun,noun(B,C,Tree2,Number),_),
not(recorded(np,np(A,C,[np,simplenp,Tree1,Tree2],
                                                              Number),_)),
recorda(np,np(A,C,[np,simplenp,Tree1,Tree2],Number),_)].

            nouns et simplenps sont ici des noms de règle. On remarque aussi que nous ne faisons plus appel à reconce: son contenu est directement intégré dans les règles. Cette intégration rend le méta-interprète plus efficace, puisqu'un appel à un but extérieur est évité.

            Voyons maintenant comment de telles règles sont interprétées. En fait, le méta-interprète est beaucoup plus simple. Tout ce qu'il doit faire, c'est exécuter tout ce qui se trouve à droite de l'opérateur --->, et puis se relancer. On a donc:

run:-  Rulename ---> ConditionAction,
        testexec(ConditionAction),
        run.

testexec([]).

testexec([First|Rest]):-
                       call(First),
                       testexec(Rest).

            Une deuxième amélioration que l'on peut apporter à notre analyseur ascendant concerne le traitement des structures coordonnées. Dans la première version, chaque type de coordination donne lieu à une règle différente: coordination de groupes nominaux, de phrases, de verbes transitifs, etc. Il est certain que les groupes nominaux méritent un traitement particulier, vu que le nombre du groupe nominal résultant est pluriel, quelles que soient les valeurs des variables 'nombre' de ses composants:

            the man walks                                    sg
            the woman walks                    sg
            the man and the woman walk            sg+sg > pl

Par contre, les autres types de coordination se ramènent à un même schéma. C'est ce schéma que nous exploitons dans notre nouvelle règle de coordination:

coordstructures --->
[ recorded(coord,coord(B,C,Tree2),_),
  (X=verbtr;X=vcomp;X=vp;X=relclause;X=s),
  Term1 =.. [X,A,B,Tree1,Number],
  Term2 =.. [X,C,D,Tree3,Number],
  Term3 =.. [X,A,D,[X,Tree1,Tree2,Tree3],Number],
  recorded(X,Term1,_),
  recorded(X,Term2,_),
  not(recorded(X,Term3,_)),
  recorda(X,Term3,_)].

            Examinons l'opérande de droite. On vérifie tout d'abord qu'on a une conjonction de coordination AND:

      recorded(coord,coord(B,C,Tree2),_)

            Ensuite, on permet à une variable X de prendre une valeur correspondant à un des éléments que l'on peut coordonner dans notre grammaire. On convient ici que l'on peut coordonner des verbes transitifs, des verbes à objet et attribut d'objet, des groupes verbaux, des propositions relatives et des phrases entières.

            Term1 et Term2 sont les deux éléments à coordonner, et Term3 est le résultat de la coordination. On se souvient que les structures (au sens prologien) qui décrivent les structures (au sens grammatical) déjà connues s'ouvrent par une indication de la nature de la structure (au sens grammatical). Par exemple, si on a découvert une phrase (s) allant de la position A à la position C, on utilise recorda avec les arguments ci-dessous:

      recorda(s,s(A,C,[s,Treenp,Treevp],sing),_)].

La structure s(A,C,[s,Treenp,Treevp] débute bien par s, qui indique la nature de l'élément découvert.

On ne peut pas questionner directement la nature de la structure à l'aide d'un schéma comme celui-ci:

Nature(A,C,[s,Treenp,Treevp]

                                              (syntaxiquement INCORRECT!!!)

La variable Nature peut certes désigner l'ensemble; je peux avoir par exemple

Nature = s(A,C,[s,Treenp,Treevp]

mais je ne peux pas avoir le foncteur sous forme de variable et détailler les objets de ce foncteur.

Un prédicat prédéfini vient à mon secours. Il s'agit de =.. (prononcé univ). Il s'emploie comme opérateur infixe, et a pour fonction de transformer une structure dans la liste correspondante, ou une liste dans la structure correspondante, selon l'opérande qui est instancié lors de l'appel. L'opérande de gauche désigne la structure, l'opérande de droite la liste. La transformation s'opère de telle manière que le foncteur de la structure corresponde au premier élément de la liste. Par exemple:

fonc(A,B,C) =.. [fonc,A,B,C].

Donc dans

  Term1 =.. [X,A,B,Tree1,Number],
  Term2 =.. [X,C,D,Tree3,Number],
  Term3 =.. [X,A,D,[X,Tree1,Tree2,Tree3],Number],

X occupe dans la liste la position correspondant à celle du foncteur des structures Term1, Term2 et Term3. Cet élément X va aussi se retrouver dans la liste décrivant la structure coordonnée, avant les trois arbres correspondant aux deux éléments de la coordination, et à la conjonction de coordination elle-même (Tree1,Tree2,Tree3). On a donc la liste [X,Tree1,Tree2,Tree3] comme troisième argument de Term3, qui vaudra, si on coordonne des phrases:

s(A,D,[s,Tree1,Tree2,Tree3],Number)

C'est cette structure qui sera passée en argument au recorda qui termine la règle.

On trouvera ci-dessous la deuxième version de notre méta-interprète. On n'y a pas repris les prédicats dont la définition est la même que dans la version 1.

 

/* META-INTERPRETE: Version 2 */

/* déclaration d'opérateur */

:- op(800,xfx,--->).

/* démarrage */

go:- gets,run.
go:- clear, go.

/* gets: voir Version 1 */

/* coeur du méta-interprète */

run:-  Rulename ---> ConditionAction,
        testexec(ConditionAction),
        run.

testexec([]).

testexec([First|Rest]):-
                       call(First),
                       testexec(Rest).

/* lexique: voir Version 1;  pour pouvoir tester la coordination, on ajoute: */

lex(verbintr,walks,[verbintr(walks)],sing).
lex(verbintr,walk,[verbintr(walk)],plural).
lex(verbintr,walked,[verbintr(walked)],_).
  
lex(vcomp,declared,[vcomp(declared)],_).
lex(vcomp,declare,[vcomp(declare)],plural).
lex(vcomp,declares,[vcomp(declares)],sing).

/* la grammaire  */

/*PREDICATS  LEXICAUX */

apo --->
[recorded(pos,position(A,B,s),_),
not(recorded(apo,apo(A,B),_)),
    recorda(apo,apo(A,B),_)] .

nouns --->
[recorded(pos,position(A,B,Noun),_),
 lex(noun,Noun,Tree,Number),
not(recorded(noun,noun(A,B,Tree,Number),_)),
    recorda(noun,noun(A,B,Tree,Number),_)].

dets --->
[recorded(pos,position(A,B,Det),_),
 lex(determiner,Det,Tree,Number),
not(recorded(det,det(A,B,Tree,Number),_)),
     recorda(det,det(A,B,Tree,Number),_)].

sentnouns --->
[recorded(pos,position(A,B,Sn),_),
 lex(sentnoun,Sn,Tree,Number),
not(recorded(sentnoun,sentnoun(A,B,Tree,Number),_)),
     recorda(sentnoun,sentnoun(A,B,Tree,Number),_)].

vintrs --->
[recorded(pos,position(A,B,Vi),_),
 lex(verbintr,Vi,Tree,Number),
not(recorded(verbintr,verbintr(A,B,Tree,Number),_)),
     recorda(verbintr,verbintr(A,B,Tree,Number),_)].

vtrs --->
[recorded(pos,position(A,B,Vtr),_),
 lex(verbtr,Vtr,Treeverb,Number),
not(recorded(verbtr,verbtr(A,B,Treeverb,Number),_)),
     recorda(verbtr,verbtr(A,B,Treeverb,Number),_)].

vcomps --->
[recorded(pos,position(A,B,Vcomp),_),
 lex(vcomp,Vcomp,Treeverb,Number),
not(recorded(vcomp,vcomp(A,B,Treeverb,Number),_)),
     recorda(vcomp,vcomp(A,B,Treeverb,Number),_)].

coords --->
[recorded(pos,position(A,B,And),_),
 lex(coord,And,Treeand),
not(recorded(coord,coord(A,B,Treeand),_)),
    recorda(coord,coord(A,B,Treeand),_)].

/* PREDICATS  GRAMMATICAUX */

/* DETERMINANTS */

gennpdet --->
 [ recorded(apo,apo(B,C),_),
   recorded(np,np(A,B,Tree,Number),_),
  not(recorded(det,det(A,C,[det,Tree],_),_)),
     recorda(det,det(A,C,[det,Tree],_),_)].

/*GROUPES NOMINAUX */

/* avec un déterminant différent de zéro */

simplenps --->
[recorded(det,det(A,B,Tree1,Number),_),
recorded(noun,noun(B,C,Tree2,Number),_),
not(recorded(np,np(A,C,[np,simplenp,Tree1,Tree2],
Number),_)),
recorda(np,np(A,C,[np,simplenp,Tree1,Tree2],Number),_)].

/* avec déterminant zéro */

simplezerodetnps --->
[recorded(noun,noun(A,B,Tree,plural),_),
not(recorded(np,np(A,B,[np,simplenp,det(zero),Tree],
                                                                         plural),_)),
recorda(np,np(A,B,[np,simplenp,det(zero),Tree],plural),_)].

/* avec comme centre un nom régissant une proposition */

sentnounnps --->
[ recorded(sentnoun,sentnoun(B,C,Tree2,Number),_),
recorded(det,det(A,B,Tree1,Number),_),
recorded(s,s(C,D,Tree3,sing),_),
not(recorded(np,np(A,D,[np,sententialnp,Tree1,Tree2,Tree3],
Number),_)),
recorda(np,np(A,D,[np,sententialnp,Tree1,Tree2,Tree3],
Number),_)].

/* avec une relative */

relnps --->
[recorded(det,det(A,B,Tree1,Number),_),
 recorded(noun,noun(B,C,Tree2,Number),_),
 recorded(relclause,relclause(C,D,Tree3,Number),_),
not(recorded(np,np(A,D,[np,relclausenp,Tree1,Tree2,Tree3],
Number),_)),
recorda(np,np(A,D,[np,relclausenp,Tree1,Tree2,Tree3],
Number),_)].

/* groupes nominaux coordonnés */

coordnps --->
[ recorded(coord,coord(B,C,Tree2),_), recorded(np,np(A,B,Tree1,Number1),_),
recorded(np,np(C,D,Tree3,Number3),_),
not(recorded(np,np(A,D,[np,Tree1,Tree2,Tree3],plural),_)),
recorda(np,np(A,D,[np,Tree1,Tree2,Tree3],plural),_)].

/* GROUPES VERBAUX */

/* intransitifs */

verbintrvps --->
[recorded(verbintr,verbintr(A,B,Tree,Number),_),
 not(recorded(vp,vp(A,B,[vp,Tree],Number),_)),
     recorda(vp,vp(A,B,[vp,Tree],Number),_)].

/* transitifs */

verbtrvps --->
[recorded(verbtr,verbtr(A,B,Treeverb,Number),_),
 recorded(np,np(B,C,Treenp,Numbernp),_),
not(recorded(vp,vp(A,C,[vp,Treeverb,Treenp],Number),_)),
 recorda(vp,vp(A,C,[vp,Treeverb,Treenp],Number),_)].

/* avec un objet et un attribut de l'objet */

vcompvps --->
[recorded(vcomp,vcomp(A,B,Treeverb,Number),_),
 recorded(np,np(B,C,Treenp1,Numbernp),_),
 recorded(np,np(C,D,Treenp2,Numbernp),_),
not(recorded(vp,vp(A,D,[vp,Treeverb,Treenp1,Treenp2],
Number),_)),
recorda(vp,vp(A,D,[vp,Treeverb,Treenp1,Treenp2],
                                                                 Number),_)].

/* RELATIVES */

relclauses --->
[recorded(det,det(A,B,Tree1,Number),_),
 recorded(noun,noun(B,C,Tree2,Number),_),
 recorded(verbtr,verbtr(C,D,Tree3,Number),_),
not(recorded(relclause,relclause(A,D,[relclause,Tree1,Tree2,
                                                       Tree3],Number),_)),
recorda(relclause,relclause(A,D,[relclause,Tree1,Tree2,Tree3],
                                                       Number),_)].

/* PHRASES */

sentences --->
[ recorded(vp,vp(B,C,Treevp,Number),_),
  recorded(np,np(A,B,Treenp,Number),_),
not(recorded(s,s(A,C,[s,Treenp,Treevp],sing),_)),
     recorda(s,s(A,C,[s,Treenp,Treevp],sing),_)].

/* STRUCTURES  COORDONNEES (à l'exception des groupes nominaux) */

coordstructures --->
[ recorded(coord,coord(B,C,Tree2),_),
  (X=verbtr;X=vcomp;X=vp;X=relclause;X=s),
  Term1 =.. [X,A,B,Tree1,Number],
  Term2 =.. [X,C,D,Tree3,Number],
  Term3 =.. [X,A,D,[X,Tree1,Tree2,Tree3],Number],
  recorded(X,Term1,_),
  recorded(X,Term2,_),
not(recorded(X,Term3,_)),
 recorda(X,Term3,_)].

/* impression des résultats ... */

results --->
[recorded(s,s(0,B,Tree,sing),_),
 recorded(fin,fin(B),_),
not(recorded(tree,tree(0,B,Tree),_)),
dealwith(B,Tree)].
dealwith(X,Tree):-
nl,
prpr(Tree,0),
recorda(tree,tree(0,B,Tree),_),
nl,
write($ --- ANY KEY TO GO ON ---$),nl,
get0_noecho(_) .

/* arrêt ... */

stopping --->
[recorded(pos,position(0,1,stop),_), halt].

/* raz de la bd ... */

clear:-
       eraseall(pos),
       eraseall(fin),
       eraseall(tree),
       eraseall(s),
       eraseall(np),
       eraseall(vp),
       eraseall(verbintr),
       eraseall(verbtr),
       eraseall(coord),
       eraseall(det),
       eraseall(sentnoun),
       eraseall(noun),
       eraseall(vcomp),
       eraseall(relclause),
       eraseall(apo),
       expunge.

/* expunge est prédéfini en Arity Prolog; il rend la mémoire qui était occupée par les prédicats qui ont fait l'objet de eraseall  */     

 /* pretty printer: voir version 1 */

 

Chapitre 10 Analyse et génération de variantes morphologiques

            Les programmes d'analyse du langage naturel que nous avons étudiés jusqu'à présent font usage d'un lexique où les variantes morphologiques sont toutes répertoriées, accompagnées de l'analyse appropriée. Nous allons voir à présent qu'on peut construire des analyseurs/générateurs de variantes morphologiques en Prolog.

            Nous prendrons pour exemple une partie de la morphologie inflectionnelle de l'anglais. Nous rendrons compte des variantes morphologiques suivantes:

 

noms

pluriel

adjectifs

comparatif

adjectifs

superlatif

verbes

3e personne du sg, indicatif présent

verbes

forme en -ING

verbes

forme en -ED (prétérit, participe passé)

 

            Notons tout d'abord que nous n'essayerons pas d'établir une compilation de toutes les formes irrégulières. Nous n'en citerons que quelques-unes, pour montrer comment on peut traiter les exceptions.

            Deuxièmement, notre analyseur / générateur devra posséder des informations sur les lexèmes dont il est censé fournir ou analyser les variantes morphologiques.

Ces informations seront de deux types: 

1. partie du discours: on utilisera les prédicats à un argument isnoun(X), isadj(X), et isverb(X);

2. redoublement consonantique: on utilisera le prédicat à une place double(X).

            Examinons tout d'abord les cas les plus simples, c'est-à-dire les exceptions. Il suffit de les répertorier. On aura par exemple, tout au début du paquet de clauses qui traite du pluriel des noms:

   plural(child,children):-
         writeplu(child, children),!.

            On remarquera la coupure. Le pluriel de child est children: il est inutile d'en chercher un autre. Si on laissait la règle générale s'appliquer, on générerait *childs. C'est une stratégie commune en Prolog de traiter d'abord les exceptions et les cas particuliers, et de les isoler à l'aide de la coupure.

            Le prédicat writeplu n'a évidemment rien de bien mystérieux:

     writeplu(X,Y):-
         write(Y),write($ is the plural of $),write(X),nl.

            Les autres exceptions recevront un traitement semblable.

            Les cas généraux sont eux aussi assez simples à traiter. Prenons comme exemple le comparatif. On aura les règles suivantes:

    comparative(X,Y):-
         not var(X),
         isadj(X),
         var(Y),
         conc(X,er,Y),
         write(Y),
         write($ is the comparative of $),
         write(X),
         nl.
   
comparative(X,Y):-
         var(X),
         not var(Y),
         conc(X,er,Y),
         isadj(X),
         comparative(X,Z),
         Y = Z.

            La première de ces règles se charge de la génération. En effet, le prédicat prédéfini var(X) est satisfait si, au moment  de l'appel, X est une variable libre, c'est-à-dire non encore liée à une valeur. En génération, le lexème (X) sera instancié lors de l'appel à comparative. En conséquence, le prédicat var(X) échouera, et en conséquence, le prédicat not var(X) réussira. De même,Y représente la variante morphologique à générer, et n'est donc pas instanciée lors de l'appel à comparative.

            Notons que le test d'appartenance de X à la catégorie des adjectifs peut se faire dès qu'on a établi que X était instanciée.

            On concatène (conc) ER au lexème pour obtenir le comparatif (LONG + ER ----> LONGER). Toutefois, on aimerait que le même prédicat conc puisse servir à la fois l'analyse (quel est l'adjectif qui concaténé à er donne longer?) et la génération (qu'est-ce que j'obtiens si je concatène long et er?).

            Pour ce faire, on va définir le prédicat conc de telle manière qu'il puisse s'appliquer pour autant qu'il reçoive deux variables instanciées, soit la première et la deuxième (génération: conc(long,er,X) ), soit la deuxième et la troisième (analyse: conc(X,er,longer) ). Conc fera donc appel à var.

            Notre prédicat conc fait aussi appel à un autre prédéfini, à savoir name(Atom,List). Ce prédicat sert à transformer un atome en liste de caractères, ou vice-versa. On notera un caractère soit à l'aide de son code ASCII, soit en le faisant précéder du backquote, c'est-à-dire le signe `. On aura donc la valeur de vérité yes pour les prédicats suivants:

name(pierre,[ `p,`i,`e,`r,`r,`e]).
name(pierre, [112,105,101,114,114,101]).

            Nous allons utiliser name pour transformer les lexèmes ou variantes morphologiques en listes de caractères, auxquelles nous pourrons appliquer l'opération de concaténation de liste définie par append, que nous connaissons déjà. Nous obtenons:

GENERATION:

conc(A1,A2,A3):-
not var(A1), not var(A2), var(A3),
name(A1,List1),name(A2,List2),
append(List1,List2,List3),
name(A3,List3).

ANALYSE:

conc(A1,A2,A3):-
var(A1), not var(A2), not var(A3),
name(A2,List2),name(A3,List3),
append(List1,List2,List3),
name(A1,List1).

            Passons à présent à la deuxième règle du cas par défaut, celle qui s'applique à l'analyse. Nous la répétons ci-dessous:

    comparative(X,Y):-
         var(X),
         not var(Y),
         conc(X,er,Y),
         isadj(X),
         comparative(X,Z),
         Y = Z.

            On constate que lorsqu'on a obtenu le lexème au départ de la variante morphologique, par exemple dans ce cas long au départ de longer, on appelle le prédicat en mode génération (X est à présent instanciée, suite à l'opération accomplie par conc) et on contrôle que le résultat obtenu (Z) est bien la variante morphologique dont on dispose, c'est-à-dire Y. On doit procéder de la sorte pour éviter que l'analyse ne reconnaisse par exemple *happyer comme le comparatif de happy. Dans les exemples d'utilisation du programme, on pourra se rendre compte de l'utilité de ce rôle rectificatif joué par l'appel au prédicat en mode génération alors qu'on est en train d'accomplir l'analyse[12]. Si on propose une forme incorrecte à l'analyse, on obtiendra plus que le message laconique no: on obtiendra la forme correcte.

            Voyons à présent certains cas intermédiaires, de portée plus large que les exceptions, mais naturellement plus étroite que le cas par défaut. On envisagera comme exemple l'alternance Y-IES, que l'on trouve dans l'opposition singulier - pluriel dans les noms et autres personnes - troisième personne du singulier à l'indicatif présent des verbes.

En génération, on peut partir de la paire suivante:

plural (X,Y):-
                       conc(Z,y,X),
                       conc(Z,ies,Y), ...

En effet, au départ de plural(city,Plural), le premier conc sera instancié comme suit lors de l'appel:

                        conc(Z,y,city),

ce qui donnera Z=cit.

Le deuxième appel de conc sera donc:

                         conc(cit,ies,Pural),

ce qui donnera Plural=cities.

En analyse, il conviendra d'inverser l'ordre des deux conc. Schématiquement,

plural(Sing,cities) ---->
                              conc( Z,ies,cities)                        Z=cit
                              conc(cit,y,Sing)                           Sing=city

On fera appel à l'opérateur de disjonction (;) pour réunir analyse et génération en une seule règle.

            Notons qu'il faut encore tester que le y n'est pas précédé d'une voyelle. Ce test est élémentaire. On se souviendra que la variable Z dans notre règle est instanciée à cit dans le cas de city ou cities, c'est-à-dire au radical du mot. On testera donc l'appartenance de la dernière lettre de Z à la liste des voyelles. La dernière lettre s'obtiendra par last(X,Y) que nous avons étudié dans LIBRARY, et l'appartenance sera testée par member(X,Y), étudié au même endroit. On obtient donc:

   plural(X,Y):-
         (conc(Z,ies,Y),
         conc(Z,y,X);
         conc(Z,y,X),
         conc(Z,ies,Y)),
         isnoun(X),
         name(Z,Zlist),
         last(Zlist,Last),
         not member(Last,[`a,`e,`i,`o,`u,`y]),
         write(Y),write($ is the plural of $),write(X),nl,!.    

            Traitons à présent du redoublement consonantique, exemplifié dans RED - REDDER. On se souvient que nous avons pris comme hypothèse que le lexique indique quels sont les lexèmes qui ont cette propriété. Concrètement, le lexique inclura donc une clause:

double(red).

            Examinons le cas de la génération:

    comparative(X,Y):-
         isadj(X),
         double(X),
         name(X,Xlist),
         last(Xlist,Last),
         append(Xlist,[Last],Redoubled),
         name(R,Redoubled),
         conc(R,er,Y),
         write(Y),write($ is the comparative of $),write(X),nl,!.

            On s'assure d'abord qu'on a bien un adjectif (isadj) et qu'il possède le redoublement consonantique (double). A l'aide de last, on isole la dernière lettre, et à l'aide d'append on la concatène au radical  red + d  ---> redd. On ajoute ensuite la terminaison:

redd + er ---> redder.

            En analyse, on procède un peu différemment:

    comparative(X,Y):-
         conc(X1,er,Y),
         name(X1,Xlist),
         last(Xlist,Last),
         append(X2,[Last],Xlist),
         name(X,X2),
         isadj(X),
         double(X),
         write(Y),write($ is the comparative of $),write(X),nl,!.

            Le premier conc instanciera X1 à redd. Append sera appelé avec les valeurs suivantes:

append(X2,[d],[r,e,d,d])

ce qui donnera X2=red. On peut alors vérifier que red est un adjectif et qu'il possède le redoublement consonantique.

            Les autres cas particuliers (church - churches, introduce - introduced, etc.) sont plus simples, et ils font appel aux mêmes mécanismes. On laissera au lecteur le soin de les décortiquer.

            Finalement, on étudiera comment le programme est appelé. Il a bien sûr deux modes, analyse (an(X)) et génération (gen(X)). Ces deux prédicats font appel à angen(X,Y), qui se charge à la fois de l'analyse et de la génération. Gen instancie le premier argument de angen, alors que an en instancie le second. Angen lui-même passe en revue tous les prédicats d'analyse / génération morphologique. On a donc:

gen(X):- angen(X,Y),fail.
gen(X).
an(X) :- angen(Y,X),fail.
an(X).

et

angen(X,Y):- plural(X,Y).
angen(X,Y):- comparative(X,Y).
angen(X,Y):- superlative(X,Y).
angen(X,Y):- thirdperson(X,Y).
angen(X,Y):- ingform(X,Y).
angen(X,Y):- edform(X,Y).

            On remarquera l'usage du prédéfini fail pour s'assurer que angen est satisfait de toutes les façons possibles, avant de s'avouer vaincu et passer la main à la deuxième clause de gen ou de an, qui réussit de manière triviale.

/* ANGEN */

/* analyse et génération de certaines variantes inflectionnelles de l'anglais */

/* usage:

            gen(Lemma)

            an(Variant)  */

/* démarrage */

gen(X):- angen(X,Y),fail.
gen(X).
an(X) :- angen(Y,X),fail.
an(X).

/* LE LEXIQUE */

/* noms */

   isnoun(city).
   isnoun(toy).
   isnoun(help).
   isnoun(cow).
   isnoun(cat).
   isnoun(try).
   isnoun(arm).
   isnoun(kiss).
   isnoun(church).
   isnoun(child).
   isnoun(play).
   isnoun(dog).
   isnoun(boy).
   isnoun(analysis).
   isnoun(hypothesis).
   isnoun(thesis).
   isnoun(knife).
  
isnoun(loaf).

/* verbes */

   isverb(carry).
   isverb(go).
   isverb(come).
   isverb(see).
   isverb(help).
   isverb(try).
   isverb(stop).
  
isverb(lull).
   isverb(play).
   isverb(hiss).
   isverb(kiss).
   isverb(put).
   isverb(arrive).
   isverb(acquire).

/* adjectifs */

   isadj(red).
   isadj(quick).
   isadj(happy).
   isadj(good).
   isadj(smart).
   isadj(fast).
   isadj(pretty).
   isadj(white).

/* redoublement  consonantique */

   double(stop).
   double(red).
   double(put).

/* PLURIEL DES NOMS */

   plural(child,children):-
         writeplu(child, children),!.

/* city cities */

   plural(X,Y):-
         (conc(Z,ies,Y),
         conc(Z,y,X);
         conc(Z,y,X),
         conc(Z,ies,Y)),
         isnoun(X),
         name(Z,Zlist),
         last(Zlist,Last),
         not member(Last,[`a,`e,`i,`o,`u,`y]),
         write(Y),write($ is the plural of $),write(X),nl,!.    

/* analysis analyses */

  plural(X,Y):-
         (conc(Z,es,Y),
         conc(Z,is,X);
         conc(Z,is,X),
         conc(Z,es,Y)),
         isnoun(X),
         write(Y),
         write($ is the plural of $),write(X),nl,!.    

/* loaf loaves */

    plural(X,Y):-
         (conc(Z,ves,Y),
         conc(Z,f,X);
         conc(Z,f,X),
         conc(Z,ves,Y)),
         isnoun(X),
         write(Y),
         write($ is the plural of $),write(X),nl,!.

/* knife knives */

plural(X,Y):-
         (conc(Z,ves,Y),
         conc(Z,fe,X);
         conc(Z,fe,X),
         conc(Z,ves,Y)),
         isnoun(X),
         write(Y),
         write($ is the plural of $),write(X),nl,!.    

/* kiss kisses        church churches */

   plural(X,Y):-
          isnoun(X),
          name(X,Xlist),
          last(Xlist,Ending),
          member(Ending,[`s,`z,`x]),
          conc(X,es,Y),
          write(Y),
          write($ is the plural of $),
          write(X), nl,!. 

   plural(X,Y):-
          isnoun(X),
          name(X,Xlist),
          lasttwo(Xlist,Endinglist),
          name(Ending,Endinglist),
          member(Ending,[ch,sh]),
          conc(X,es,Y),
          write(Y),
          write($ is the plural of $),
          write(X), nl,!. 

plural(X,Y):-
          conc(X,es,Y),
          isnoun(X),
          name(X,Xlist),
          lasttwo(Xlist,Endinglist),
          name(Ending,Endinglist),
          member(Ending,[ch,sh]),
          write(Y),
          write($ is the plural of $),
          write(X), nl,!. 

   plural(X,Y):-
          conc(X,es,Y),
          isnoun(X),
          name(X,Xlist),
          last(Xlist,Ending),
          member(Ending,[`s,`z,`x]),
          write(Y),
          write($ is the plural of $),
          write(X), nl,!. 

  /* cas par défaut boy boys */

   plural(X,Y):-
          not var(X), var(Y),
          isnoun(X),
          conc(X,s,Y),
          write(Y),
          write($ is the plural of $),write(X),nl.    

   plural(X,Y):-
          var(X), not var(Y),
          conc(X,s,Y),
          isnoun(X),
          plural(X,Z),
          Z = Y.

/* TROISIEME PERSONNE

INDICATIF PRESENT SINGULIER */

   thirdperson(go,goes):-
         writethird(go,goes),!.

/* try tries */

   thirdperson(X,Y):-
         (conc(Z,ies,Y),
         conc(Z,y,X);
         conc(Z,y,X),
         conc(Z,ies,Y)),
         isverb(X),
         name(Z,Zlist),
         last(Zlist,Last),
         not member(Last,[`a,`e,`i,`o,`u,`y]),
         write(Y),
         write($ is the third person singular present tense of $),
         write(X),nl,!.    

/* kiss kisses    munch munches */

   thirdperson(X,Y):-
          isverb(X),
          name(X,Xlist),
          last(Xlist,Ending),
          member(Ending,[`s,`z,`x]),
          conc(X,es,Y),
          write(Y),
          write($ is the third person singular present tense of $),
          write(X), nl,!. 

   thirdperson(X,Y):-
          isverb(X),
          name(X,Xlist),
          lasttwo(Xlist,Endinglist),
          name(Ending,Endinglist),
          member(Ending,[ch,sh]),
          conc(X,es,Y),
          write(Y),
          write($ is the third person singular present tense of $),
          write(X), nl,!. 

thirdperson(X,Y):-
          conc(X,es,Y),
          isverb(X),
          name(X,Xlist),
          lasttwo(Xlist,Endinglist),
          name(Ending,Endinglist),
          member(Ending,[ch,sh]),
          write(Y),
          write($ is the third person singular present tense of $),
          write(X), nl,!. 

   thirdperson(X,Y):-
          conc(X,es,Y),
          isverb(X),
          name(X,Xlist),
          last(Xlist,Ending),
          member(Ending,[`s,`z,`x]),
          write(Y),
          write($ is the third person singular present tense of $),
          write(X), nl,!. 

/* cas par défaut  make makes */

   thirdperson(X,Y):-
          not var(X), var(Y),
          isverb(X),
          conc(X,s,Y),
          write(Y),
          write($ is the third person singular present tense of $),
          write(X),nl.    

   thirdperson(X,Y):-
          var(X), not var(Y),
          conc(X,s,Y),
          isverb(X),
          thirdperson(X,Z),
          Z = Y.

/* COMPARATIF */

    comparative(good, better):-
          writecomp(good,better),!.

/* happy happier */

   comparative(X,Y):-
         (conc(Z,y,X),
         conc(Z,ier,Y);
         conc(Z,ier,Y),
         conc(Z,y,X)),
         isadj(X),
         name(Z,Zlist),
         last(Zlist,Last),
         not member(Last,[`a,`e,`i,`o,`u,`y]),
         write(Y),write($ is the comparative of $),write(X),nl,!.

/* white whiter */

   comparative(X,Y):-
         (conc(Z,e,X),
         conc(Z,er,Y);
          conc(Z,er,Y),
         conc(Z,e,X)),
         isadj(X),
         write(Y),write($ is the comparative of $),write(X),nl,!.

/* red redder */

    comparative(X,Y):-
         isadj(X),
         double(X),
         name(X,Xlist),
         last(Xlist,Last),
         append(Xlist,[Last],Redoubled),
         name(R,Redoubled),
         conc(R,er,Y),
         write(Y),write($ is the comparative of $),write(X),nl,!.

    comparative(X,Y):-
         conc(X1,er,Y),
         name(X1,Xlist),
         last(Xlist,Last),
         append(X2,[Last],Xlist),
         name(X,X2),
         isadj(X),
         double(X),
         write(Y),write($ is the comparative of $),write(X),nl,!.

/* cas par défaut  long longer */

    comparative(X,Y):-
         not var(X),isadj(X),var(Y),
         conc(X,er,Y),
         write(Y),write($ is the comparative of $),write(X),nl.

    comparative(X,Y):-
         var(X),not var(Y),
         conc(X,er,Y),
         isadj(X),
         comparative(X,Z),
         Y = Z.

/* SUPERLATIF */

superlative(good, best):-
          writesup(good,best),!.

superlative(X,Y):-
         (conc(Z,y,X),
         conc(Z,iest,Y);
         conc(Z,iest,Y),
         conc(Z,y,X)),
         isadj(X),
          name(Z,Zlist),
         last(Zlist,Last),
         not member(Last,[`a,`e,`i,`o,`u,`y]),
         write(Y),write($ is the superlative of $),write(X),nl,!.

   superlative(X,Y):-
         (conc(Z,e,X),
         conc(Z,est,Y);
         conc(Z,est,Y),
         conc(Z,e,X)),
         isadj(X),
         write(Y),write($ is the superlative of $),write(X),nl,!.

    superlative(X,Y):-
         isadj(X),
         double(X),
         name(X,Xlist),
         last(Xlist,Last),
         append(Xlist,[Last],Redoubled),
         name(R,Redoubled),
         conc(R,est,Y),
         write(Y),write($ is the superlative of $),write(X),nl,!.

 superlative(X,Y):-
         conc(X1,est,Y),
         name(X1,Xlist),
         last(Xlist,Last),
         append(X2,[Last],Xlist),
         name(X,X2),
         isadj(X),
         double(X),
         write(Y),write($ is the superlative of $),write(X),nl,!.

superlative(X,Y):-
         not var(X),isadj(X),var(Y),
         conc(X,est,Y),
         write(Y),write($ is the superlative of $),write(X),nl.

    superlative(X,Y):-
         var(X),not var(Y),
         conc(X,est,Y),
         isadj(X),
         superlative(X,Z),
         Y = Z.

/* FORME EN ING */

/* put putting */

    ingform(X,Y):-
         isverb(X),
         double(X),
         name(X,Xlist),
         last(Xlist,Last),
         append(Xlist,[Last],Redoubled),
         name(R,Redoubled),
         conc(R,ing,Y),
         write(Y),write($ is the ing form of $),write(X),nl,!. 

ingform(X,Y):-
         conc(X1,ing,Y),
         name(X1,Xlist),
         last(Xlist,Last),
         append(X2,[Last],Xlist),
         name(X,X2),
         isverb(X),
         double(X),
         write(Y),write($ is the ingform of $),write(X),nl,!.

/* come coming */

ingform(X,Y):-
         (conc(Z,ing,Y),
         conc(Z,e,X);
         conc(Z,e,X),
         conc(Z,ing,Y)),
         isverb(X),
         write(Y),write($ is the ingform of $),write(X),nl,!.

/* cas par défaut  bring bringing */

    ingform(X,Y):-
          not var(X),var(Y),isverb(X),
          conc(X,ing,Y),
          write(Y),write($ is the ing form of $),write(X),nl. 

    ingform(X,Y):-
           var(X),not var(Y),
          conc(X,ing,Y),
          isverb(X),
          ingform(X,Z),
          Y = Z.

/* FORME EN ED */

edform(see,saw_seen):-
         writeed(see,saw_seen),!.
    edform(go, went_gone):-
         writeed(go,went_gone),! .

    edform(put, put):-
         writeed(put,put), !.

    edform(come, came_come):-
         writeed(come,came_come), !.

/* stop stopped */

edform(X,Y):-
         isverb(X),
         double(X),
         name(X,Xlist),
         last(Xlist,Last),
         append(Xlist,[Last],Redoubled),
         name(R,Redoubled),
         conc(R,ed,Y),
         write(Y),write($ is the ed form of $),write(X),nl,!. 

edform(X,Y):-
         conc(X1,ed,Y),
         name(X1,Xlist),
         last(Xlist,Last),
         append(X2,[Last],Xlist),
         name(X,X2),
         isverb(X),
         double(X),
         write(Y),write($ is the ed form of $),write(X),nl,!. 

/* introduce introduced */

   edform(X,Y):-
         (conc(Z,ed,Y),
         conc(Z,e,X);
         conc(Z,e,X),
         conc(Z,ed,Y)),
         isverb(X),
         write(Y),write($ is the ed form of $),write(X),nl,!. 

/* try tried */

   edform(X,Y):-
         (conc(Z,ied,Y),
         conc(Z,y,X);
         conc(Z,y,X),
         conc(Z,ied,Y)),
         isverb(X),
          name(Z,Zlist),
         last(Zlist,Last),
         not member(Last,[`a,`e,`i,`o,`u,`y]),
         write(Y),
         write($ is the ed form of $),write(X),nl,!.    

/* cas par défaut  bang banged */

    edform(X,Y):-
         not var(X),var(Y),
         isverb(X),
         conc(X,ed,Y),
         write(Y),write($ is the ed form of $),write(X),nl. 

edform(X,Y):-
         var(X),not var(Y),
         conc(X,ed,Y),
         isverb(X),
         edform(X,Z),
         Y = Z.

/* passage en revue  */

    angen(X,Y):- plural(X,Y).
    angen(X,Y):- comparative(X,Y).
    angen(X,Y):- superlative(X,Y).
    angen(X,Y):- thirdperson(X,Y).
    angen(X,Y):- ingform(X,Y).
    angen(X,Y):- edform(X,Y).

/* écriture des résultats */

writeplu(X,Y):-
         write(Y),write($ is the plural of $),write(X),nl.

writethird(X,Y):-
         write(Y),
         write($ is the third person singular present tense of $),
         write(X),nl.     

writeed(X,Y):-
         write(Y),write($ is the edform of $),write(X),nl.    

writecomp(X,Y):-
         write(Y),write($ is the comparative of $),write(X),nl.     

writesup(X,Y):-
         write(Y),write($ is the superlative of $),write(X), nl.     

/* utilitaires */

member(X,[X|_]).
member(X,[_|T]):- member(X,T).
append([],L,L).
append([H|L1],L,[H|L2]):- append(L1,L,L2).
conc(A1,A2,A3):- not var(A1), not var(A2), var(A3),
name(A1,List1),name(A2,List2),append(List1,List2,List3),
name(A3,List3).
conc(A1,A2,A3):-  var(A1), not var(A2), not var(A3),
name(A2,List2),name(A3,List3),append(List1,List2,List3),
name(A1,List1).
last([X],X).
last([H|Tail],X):- last(Tail,X).
lasttwo([X,Y],[X,Y]).
lasttwo([H|Tail],X):- lasttwo(Tail,X).

 Exemples d'invocation et résultats obtenus (en gras) 

?- gen(city).
      cities is the plural of city
?- an(cities)
      cities is the plural of city
?- gen(red).
      redder is the comparative of red.
      reddest is the superlative of red
?- gen(put).
      puts is the third person singular present tense of put
      putting is the ing form of put
      put is the ed form of put
?- gen(try).
      tries is the plural of try
      tries is the third person singular present tense of try
      trying is the ing form of try
      tried is the ed form of try
?- an(tries).
      tries is the plural of try
      tries is the third person singular present tense of try
?- an(trys).
      tries is the plural of try
      tries is the third person singular present tense of try
?- an(puting).
      putting is the ing form of put

Chapitre 11 Utilisation de macros pour la gestion du vocabulaire

            Dans tout projet de traitement du langage naturel d'une certaine ampleur, les informations contenues dans le lexique seront bien plus abondantes qu'elles ne le sont dans les petits programmes que nous avons examinés jusqu'ici. Se pose alors la question de savoir comment ces informations seront  entrées dans le système et comment le système en fera usage.

            Nous supposerons ici que l'analyseur travaille avec un dictionnaire où toutes les variantes morphologiques sont répertoriées (FULLFORM DICTIONARY).  Nous ne ferons donc pas usage du générateur de variantes morphologiques que nous venons de décrire.

            Il est certain qu'on ne peut pas demander au lexicographe d'associer à chaque variante morphologique de chaque lexème toute l'information dont le système pourrait avoir besoin. Ce travail serait extrêmement fastidieux, et  partant, rapidement entaché d'erreurs.

            On tentera donc de demander à Prolog lui-même de faire une partie non négligeable du travail. Cette opération s'effectuera par la création de macros, leur expansion, et l'ajout à la base de données des résultats produits par cette expansion.

            Le concept de macro est bien connu dans le domaine des éditeurs et systèmes de traitement de texte. Une chaîne de caractères est remplacée par une autre, plus longue, dont la saisie directe au clavier s'avérerait  fastidieuse si elle devait être maintes fois répétée.

            En Prolog, les macros vont générer des clauses au départ d'autres clauses. Pour qu'il y ait gain, il faut que les premières soient plus nombreuses ou plus complexes, ou encore plus nombreuses et plus complexes, que les secondes.

            Nous allons illustrer le processus en examinant des extraits d'un système expérimental de traduction automatique anglais-français développé par l'auteur. Nous nous intéresserons exclusivement  aux verbes monotransitifs du volet anglais de ce système.

            Voyons d'abord ce que nous désirons obtenir. Nous voulons un dictionnaire répertoriant toutes les variantes morphologiques de ces verbes, avec l'information suivante associée à chaque variante:

/* structure of the macro results */

   verbtr ( wordform,lex,reading number,
            voice,number,subject structure, object structure,
            subject semantics,object semantics,type,tense */

wordform = la variante morphologique
lex = le lemme
reading number = le numéro d'acception
voice = la voix
number = le nombre
subject structure = la structure syntaxique du sujet (la valeur sp signifiera un groupe nominal simple, par opposition à toute une proposition)
object structure = structure syntaxique de l'objet (il s'agit de monotransitifs directs)
subject semantics = restrictions sémantiques sur le sujet, par exemple ab (abstrait), co (concret), hu (humain),etc.
object semantics = restrictions sémantiques sur l'objet
type = fi (finite), in (infinitive), enpass (participe passé à valeur passive), enact (participe passé à valeur active), ing
forme en ing), etc.
tense = le temps morphosyntaxique, pa (past) ou pr (present)

            On désire donc obtenir un lexique contenant des entrées commes celles citées ci-dessous:

verbtr(allows,allow,1,active,sg,sp,sp,ab,ab,fi,pr).
verbtr(allow,allow,1,active,pl,sp,sp,ab,ab,fi,pr).
verbtr(allow,allow,1,active,A,sp,sp,ab,ab,in,B).
verbtr(allowing,allow,1,active,A,sp,sp,ab,ab,ing,B).
verbtr(allowed,allow,1,active,A,sp,sp,ab,ab,fi,pa).
verbtr(allowed,allow,1,active,A,sp,sp,ab,ab,enact,B).
verbtr(allowed,allow,1,passive,A,sp,sp,ab,ab,enpass,B).
verbtr(teaches,teach,1,active,sg,sp,sp,hu,ab,fi,pr).
verbtr(teach,teach,1,active,pl,sp,sp,hu,ab,fi,pr).
verbtr(teach,teach,1,active,A,sp,sp,hu,ab,in,B).
verbtr(teaching,teach,1,active,A,sp,sp,hu,ab,ing,B).
verbtr(taught,teach,1,active,A,sp,sp,hu,ab,fi,pa).
verbtr(taught,teach,1,active,A,sp,sp,hu,ab,enact,B).
verbtr(taught,teach,1,passive,A,sp,sp,hu,ab,enpass,B).
verbtr(teaches,teach,1,active,sg,sp,sp,hu,hu,fi,pr).
verbtr(teach,teach,1,active,pl,sp,sp,hu,hu,fi,pr).
verbtr(teach,teach,1,active,A,sp,sp,hu,hu,in,B).
verbtr(teaching,teach,1,active,A,sp,sp,hu,hu,ing,B).
verbtr(taught,teach,1,active,A,sp,sp,hu,hu,fi,pa).
verbtr(taught,teach,1,active,A,sp,sp,hu,hu,enact,B).
verbtr(taught,teach,1,passive,A,sp,sp,hu,hu,enpass,B).

            Il faut bien se rendre compte qu'on n'a ci-dessus que deux verbes, chacun d'eux limité à une acception. On ne peut pas demander au lexicographe de produire de telles listes. On va en fait lui demander de produire les clauses qui seront soumises à l'opération d'expansion de macro. Dans le système décrit ici, elles prennent la forme suivante:

/* structure of the macro */

   m_verbtr(lex, V, Vs, Ving, Ved, Ven, Stru_subj, Stru_obj, Sem_subj, Sem_obj, Rnu)

lex = le lemme
V = forme de l'indicatif présent, à l'exclusion de la troisième personne du singulier
Vs = indicatif présent, 3e personne du sg
Ved = forme du prétérit
Ven = forme du participe passé
Stru_subj = structure syntaxique du sujet
Stru_obj = structure syntaxique de l'objet
Sem_subj = restrictions sémantiques sur le sujet
Sem_obj = restrictions sémantiques sur l'objet
Rnu = numéro d'acception

On pourrait bien sûr générer automatiquement V, Vs, Ving, Ved et Ven, du moins pour les verbes réguliers.

Le lexicographe produira donc, pour les deux items examinés ci-dessus:

   m_verbtr(allow,allow,allows,allowing,allowed,allowed,
                   sp,sp,ab,ab,1).
   /* the facts allow the explanation he gave to the students */
   m_verbtr(teach,teach,teaches,teaching,taught,taught,
                   sp,sp,hu,ab,1).
   /* teach linguistics */
   m_verbtr(teach,teach,teaches,teaching,taught,taught,
                   sp,sp,hu,hu,1).
  /* teach the students */

            Le procédé de macro-expansion va se servir des clauses m_verbtr pour produire les clauses verbtr, qui seront ajoutées à la base de données via assert. Ce procédé est extrêmement simple à programmer (cf. Walker et al. 1987, p. 336):

/* macro expansion */

gen_verbtr:-
m_verbtr(Lex,V,Vs,Ving,Ved,Ven,Stru1,Stru2,Sem1,Sem2,Rnu),
assert((verbtr(Vs,Lex,Rnu,active,sg,
            Stru1,Stru2,Sem1,Sem2,fi,pr))),
assert((verbtr(V,Lex,Rnu,active,pl,
            Stru1,Stru2,Sem1,Sem2,fi,pr))),
assert((verbtr(V,Lex,Rnu,active,_,
            Stru1,Stru2,Sem1,Sem2,in,_))),
assert((verbtr(Ving,Lex,Rnu,active,_,
            Stru1,Stru2,Sem1,Sem2,ing,_))),
assert((verbtr(Ved,Lex,Rnu,active,_,
            Stru1,Stru2,Sem1,Sem2,fi,pa))),
assert((verbtr(Ven,Lex,Rnu,active,_,
            Stru1,Stru2,Sem1,Sem2,enact,_))),
assert((verbtr(Ven,Lex,Rnu,passive,_,
            Stru1,Stru2,Sem1,Sem2,enpass,_))),
fail.

gen_verbtr.

            Le générateur gen_verbtr a deux clauses: la première s'empare de la première clause m_verbtr(...) et ajoute à la base de données les 7 clauses verbtr(...) correspondantes. Le dernier prédicat de gen_verbtr est fail, et donc le processus échoue après avoir injecté les clauses verbtr(...) dans la base. Il reprendra avec la deuxième clause m_verbtr(...) et ainsi de suite jusqu'à épuisement du stock de ces clauses. Il passera alors à la seconde clause, le fait (gen_verbtr.), qui réussira de manière triviale.

 

Chapitre 12 Le traitement des dépendances de longue distance

            Dans parse, nous n'avons pas vraiment mis à profit les avantages qu'offre une grammaire dcg par rapport à une grammaire cfg utilisant les mêmes terminaux et non-terminaux. En bref, nous n'avons pas pleinement profité de la possibilité d'enrichir les catégories grammaticales et les terminaux d'arguments quelconques qui obtiennent les valeurs appropriées via le mécanisme d'unification. Tout au plus avons-nous partiellement rendu compte du phénomène d'accord en nombre à l'intérieur du groupe nominal et entre le groupe nominal sujet et le groupe verbal.

            Bien sûr, on ne peut pas se permettre dans ce bref ouvrage d'élaborer une grammaire sophistiquée, dont la taille serait considérable, et qui nécessiterait bien des explications. Pour ce chapitre, nous procéderons comme au précédent, c'est-à-dire que nous travaillerons sur base d'extraits d'une grammaire plus élaborée, à savoir celle qui sous-tend notre système expérimental de traduction automatique. Ici aussi, nous nous limiterons à des extraits de la grammaire du volet anglais de ce système.

            On se souvient que le traitement des propositions relatives dans parse était purement ad hoc. Reprenons en effet les définitions des prédicats qui se chargent  de l'analyse des groupes nominaux contenant une relative, et des relatives elles-mêmes:

  nounphrase(P0,P3,[relnp,Det,N,Relcl],Number,Sem):-
     determiner(P0,P1, Det,Number,Sem),
     noun(P1,P2,N,Number),
     relclause(P2,P3, Relcl).

relclause(P0,P3,[relcl,Det,N,Vtr]):-
     determiner(P0,P1,Det,Number),
     noun(P1,P2,N,Number,Sem),
     verbtr(P2,P3,Vtr,Number,Semsubj,Semobj),
     sfok(Semsubj,Sem).      

            On remarque qu'aucun lien n'est établi entre le verbe (nécessairement transitif direct) de la relative et son antécédent. Dans "the book the man reads", parse n'établit aucune relation entre book et reads. En conclusion, il est incapable de vérifier que l'objet qui est associé à reads résulte, par exemple, d'un choix sémantiquement correct. Un groupe nominal tel que "the woman the man reads" ne sera nullement rejeté par parse, même si on lui enseigne que read n'accepte pas d'humain comme objet direct. Le problème est que parse ne "sait" pas que woman est objet de reads dans le groupe nominal en question.

            Le problème principal dans la récupération de ce lien qui existe entre le verbe de la relative et son antécédent est qu'il n'est pas possible de pré-déterminer la nature des éléments qui vont les séparer, ni même la  distance maximale entre antécédent et verbe de la relative. Il s'agit d'une dépendance de longue distance (LONG DISTANCE DEPENDENCY, UNBOUNDED DEPENDENCY). Le mot "unbounded" dans un des deux termes anglais qui désignent le concept est bien choisi, comme en témoignent les énoncés suivants:

            the books she thinks he knows the man likes reading
            the books she made the claim she had read already

            On constate dans le premier de ces énoncés que les frontières des propositions peuvent être allègrement franchies; et dans le second que l'on peut parfois franchir la frontière d'une proposition enchâssée dans un groupe nominal.

            Dans notre esquisse d'une solution, nous commencerons par remarquer que l'on peut très bien décrire une proposition relative (pronom relatif exclus) comme une phrase à laquelle il manque un élément. En anglais, cet élément sera un groupe nominal (np) ou un groupe prépositionnel (pp). Par exemple,

the book which the man likes ---> the man likes: s auquel il manque un
                                                                                                          np

the man on whom he relies ---> he relies: s auquel il manque un pp

            Nous conviendrons d'appeler discontinuité le "trou" (GAP) dans la relative. Bien sûr, ce trou est destiné à être rempli par l'antécédent: c'est précisément là la relation qui nous intéresse.

            Pour rendre compte des relatives, nous allons organiser notre grammaire de telle sorte qu'un groupe nominal puisse être constitué par une discontinuité. Ainsi, la relative the man likes sera une proposition syntaxiquement correcte: l'objet direct de likes est tout simplement un gap.  Nous aurons donc, parmi les clauses qui se chargent de l'analyse du groupe nominal, la clause suivante:

  nounphrase(P0,P0,S_role,D_role,
                      gapped_np(S_role,D_role,Antecedent),
                      gap(Antecedent,Number,sp,Sem,_,
                             S_role,D_role,none,noprep),
                      light,Number,sp,Sem).

            On remarque en premier et deuxième arguments de nounphrase la liste d'entrée et la liste de sortie. On constate qu'elles sont identiques (même variable P0). En effet, la lecture d'un trou ne doit pas consommer de mot! Que sait-on de ce trou? Rien. On va donc se contenter d'ouvrir des positions qui seront prêtes pour recevoir l'information quand cette dernière sera disponible. Le passage d'information se fera évidemment par unification.  Les arguments de la structure gap s'analysent comme suit:

Antecedent: s'unifiera avec la structure représentant l'antécédent
Number: le nombre de l'antécédent
sp: désigne un gap de type np (par opposition à pp, gap de type groupe prépositionnnel)
Sem: les traits sémantiques
S_role: le rôle syntaxique joué par la discontinuité dans la structure de surface
D_role: le rôle syntaxique joué par la discontinuité en structure profonde
none et noprep: constantes qui indiquent qu'il n'y a pas de préposition; nous traitons ici des np gaps.

            On voit que les arguments de la structure gap se retrouvent aussi en dehors de cette structure, comme arguments de nounphrase. L'unification se chargera de tout instancier au moment voulu.

            Prenons au hasard une clause de la définition du groupe verbal:

verbphrase([Verb|P1],P2,
                  vp_tran(Type,Tense,lex(Vtr,Rnu),Np),
                  Gap,
                   subject(Npsubj,Number,S1type,
                               S1sem,d_subj),
                   Type,Tense,active):-
    verbtr(Verb,Vtr,Rnu,active,Number,S1type,
               S2type,S1sem,S2semvp,Type,Tense),
    nounphrase(P1,P2,s_obj,d_obj,
                       Np,Gap,Weight,_,S2type,S2sem),
    sfok(S2semvp,S2sem).

            On constate ici l'attribution de valeurs à certains des arguments du prédicat nounphrase. Comme nous examinons ici la clause verbphrase pour les monotransitifs, voix active, nous voyons que les rôles syntaxiques sont déterminés: s_obj et d_obj (le np est objet en surface et en profondeur). Nous connaissons déjà le prédicat sfok, qui se charge de vérifier que les traits sémantiques du np sont licites par rapport aux restrictions sémantiques contenues dans le lexique pour le verbe transitif instancié dans Verb.

            La variable Gap peut ici s'unifier à une structure du type que nous venons d'examiner, ou elle peut recevoir la valeur nogap, ce qui sera le cas si on lit dans la phrase un vrai np et non pas un simple trou.

            Voyons à présent comment on définit une proposition relative. Ici aussi, on n'examinera qu'une seule clause parmi le paquet qui est nécessaire à un traitement complet:

  relclause([Relative|P1],P2,
                 relative_clause(Rel,s(gapped,A,B,C)),
                 gap(N,Number,sp,Semx,_,S_role,
                        D_role,none,noprep)) :-
     relative(Relative,Rel),
     sentence(P1,P2,s(gapped_in_vp,A,B,C),
                   gap(N,Number,sp,Semx,_,S_role,
                          D_role,none,noprep),
                   fi,Num),
     S_role \= s_subj.
           

            Nous avons affaire ici au type de relative exemplifié par the man likes: la relative est un s qui est gapped_in_vp, c'est-à-dire dont la discontinuité se trouve dans le groupe verbal. On constate en passant que le rôle syntaxique de surface ne peut pas recevoir la valeur sujet. Quant à la  structure gap, on voit qu'elle est partagée entre le niveau de la proposition analysée comme relative (prédicat sentence) et la tête de la clause. Elle sera donc véhiculée comme argument de relclause.

            On peut à présent compléter le traitement en s'assurant que dans la clause qui définit un groupe nominal constitué d'un antécédent et d'une relative,  les valeurs associées à l'antécédent et qui intéressent la relative sont partagées par celle-ci:

   nounphrase(P0,P2,Smain,Dmain,
               np_relative(NP,Relcl),
               nogap,heavy,Number,sp,Semnp) :-
     corenounphrase(P0,P1,Smain,Dmain,
                               NP,nogap,Weight,Number,sp,Semnp),
     relclause(P1,P2,Relcl,
                    gap(NP,Number,Type,Semnp,
                           Sempp,Srel,Drel,Prep,Prepinornot)) .

            Le passage de toute la structure associée à l'antécédent est réalisé par le passage de la variable NP.  Le nombre et la sémantique doivent aussi être unifiables. Par contre le rôle syntaxique joué par l'antécédent dans sa proposition (ici Smain et Dmain) ne doit pas correspondre à celui joué par la discontinuité dans la relative. Par exemple, dans the book the man reads is good, the book est sujet de is good, mais la trace liée à the book est objet de reads.

            En conclusion, on peut dire que tout le traitement des dépendances de longue distance s'accomplit par les vertus de l'unification. Elle a le merveilleux pouvoir de permettre la manipulation de variables qui ne sont pas encore instanciées ou, en termes moins chronologiques, dont l'instanciation est laissée à d'autres prédicats de la grammaire.

            On trouvera ci-dessous l'analyse associée à la phrase the book the man reads is good.


 

[the,book,the,man,reads,is,good]
   s main decl
      np_relative
         simple_np s_subj d_subj sp sg
            thing ab
            det the
            n book 1
         relative_clause
            rel zero
            s gapped decl
               simple_np s_subj d_subj sp sg
                  hu
                  det the
                  n man 1
               vp_tran fi pr
                  lex read 1
                  gapped_np s_obj d_obj
                     simple_np s_subj d_subj sp sg
                        thing ab
                        det the
                        n book 1
      vp_copula fi pr
         cop is
         adj_phr
            adj good 1

 

Annexe 1 De la chaîne de caractères à la liste de mots

            Nous allons étudier ici la manière de transformer une chaîne de caractères en une liste de mots, d'effectuer, par exemple, le passage de "the cat is on the mat" à [the,cat,is,on,the,mat].

            Nous développerons, dans la seconde partie de cette annexe, les adaptations qui doivent être apportées au programme pour qu'il puisse traiter le français.

            La chaîne d'entrée sera saisie caractère par caractère à l'aide du prédicat prédéfini get0 qui lit un seul caractère sur le périphérique d'entrée. Get0 prend deux arguments:

1. l'identificateur du périphérique d'entrée (par défaut, il s'agira bien sûr de la console; on ne s'étonnera pas de trouver get0 à un seul argument dans ce cas),

2. la valeur ascii du caractère saisi.

            Le problème auquel nous sommes confrontés est qu'un prédicat de lecture comme get0, ou read, ou d'autres encore, ne peuvent pas être resatisfaits par remontée. On doit donc lire le caractère, et puis décider de ce qu'on en fait. On ne peut pas prendre de mauvaise décision, car le caractère ne peut pas être restitué à la chaîne à saisir (pas de ungetchar!). On va donc toujours faire en sorte d'avoir lu un caractère à l'avance, pour déterminer par exemple si on a atteint la fin d'un mot.  Supposons que j'ai lu un blanc: je sais maintenant que l'avant-dernier caractère lu est le dernier d'un mot, et que je peux donc traiter un mot complet.

            Voyons tout cela plus en détail. Le prédicat getsentence lance le processus. Il lit le premier caractère et le passe à getrest, qui va essayer de l'utiliser comme premier caractère du premier mot de la liste de mots à  constituer dans Wordlist:

     getsentence(Wordlist,Handle):- get0(Handle,Char),
                                    getrest(Handle,Char,Wordlist).

            Getrest fait appel à getletters, qui essaie de réunir tous les caractères d'un mot dans une liste de caractères. Ensuite cette liste de caractères est transformée en atome par name, et  cet atome (Word) vient se placer en tête de la liste de mots à constituer. Getrest reprend alors son travail avec le caractère d'avance qui lui est passé par getletters, à savoir Nextchar, pour constituer le reste de la liste de mots:

     getrest(Handle,Letter,[Word|Wordlist]):-
             getletters(Handle,Letter,Letters,Nextchar),
             name(Word,Letters),
             getrest(Handle,Nextchar,Wordlist).

            Getletters collecte les caractères dans son troisième argument. On verra que cette collecte se fait à l'aide de get0. Il s'arrête lorsqu'il rencontre un caractère marquant la fin d'un mot, comme un blanc ou un signe de ponctuation. Remarquez qu'il ne consomme pas ce dernier caractère: il le renvoie dans son quatrième argument, celui qui était désigné par la variable Nextchar dans la définition de getrest:

    getletters(Handle,46,[],46):-!. /* ascii 46 désigne le point (.) */
    getletters(Handle,32,[],32):-!. /* ascii 32 désigne le blanc ( ) */
    getletters(Handle,63,[],63):-!.
                 /* ascii 63 désigne le point d'interrogation (?) */

           

            On peut donc modifier la liste de délimiteurs de mots. On se souvient que dans grpd.ari nous voulions traiter le génitif anglo-saxon. Nous avons donc prévu dans ce programme l'ajout de l'apostrophe comme délimiteur de mot, pour que "the man's book" donne [the,man,s,book]. On a donc ajouté la clause:

     getletters(Handle,39,[],39):-!. 
/* ascii 39 désigne l'apostrophe (')  */
     

            Il faut absolument que getletters nous débarrasse d'un problème important: la chaîne d'entrée peut contenir des mots commençant par une majuscule, et, si on les conserve comme tels, name les placera entre guillemets pour qu'ils ne soient pas interprétés comme désignant des variables, ce qui n'est certainement pas l'intention de l'auteur de la chaîne. Par exemple, "He is here" serait transformé en ['He',is,here] et le lien entre 'He' et he devrait être programmé.

            La solution proposée ici est que getletters demande au prédicat transform de transformer un caractère avant de le laisser passer: si la valeur ascii de ce caractère correspond à la valeur ascii d'une majuscule, le caractère est transformé dans la minuscule correspondante par l'ajout de 32 à sa valeur ascii. Cette clause de getletters permet de saisir au vol toutes les majuscules. Les différentes clauses de getletters sont reprises dans l'ordre ci-dessous:

     getletters(Handle,46,[],46):-!.
     getletters(Handle,32,[],32):-!.
     getletters(Handle,63,[],63):-!.
     getletters(Handle,Let,[Let1|Letters],Nextchar):-
                 transform(Let,Let1),!,
                 get0(Handle,Char),
                 getletters(Handle,Char,Letters,Nextchar).
     getletters(Handle,Let,Letters,Nextchar):-
                 get0(Handle,Char),
                 getletters(Handle,Char,Letters,Nextchar).

            La dernière clause de getletters s'applique si le caractère à traiter n'est ni un délimiteur de mot (clauses 1 à 3), ni un caractère transformable par transform (clause 4): il est alors tout simplement négligé, en ce sens qu'il n'est pas collecté dans le troisième argument de getletters.

            Le code de transform est très simple:

     transform(C,C):- C>96,C<123.
     transform(C,C1):-C>64,C<91,C1 is C+32. /* no capital letters */

            Le caractère C est renvoyé non modifié si c'est une lettre minuscule, c'est-à-dire si son code ascii est supérieur à 96 et inférieur à 123. S'il se trouve dans la tranche 65-90, c'est une majuscule, et transform lui ajoute 32 (par exemple H est 72: h est 104 (72+32)). S'il tombe en dehors de ces deux tranches, transform ne réussit pas, et c'est la cinquième clause de getletters qui traitera le caractère en le laissant tout simplement tomber. On comprend donc que transform doit être modifié pour le traitement d'une langue accentuée comme le français (cette transformation est donnée dans la seconde partie de cette annexe).

            Revenons à getrest. Il a fini son travail lorsqu'il rencontre un signe de ponctuation qui indique la fin de la chaîne. Ici aussi, les délimiteurs peuvent être adaptés en fonction des chaînes à traiter (ajout du point d'exclamation, par exemple). Les clauses d'arrêt sont les suivantes:

     getrest(Handle,46,[]):-!.        /* point final */
     getrest(Handle,63,[]):-!.      
/* point d'interrogation */

            Si getletters passe un blanc à getrest (fin de mot), ce dernier appelle getsentence pour constituer la liste de mots. Le blanc disparaît donc dans l'opération:

     getrest(Handle,32,Wordlist):-!,getsentence(Wordlist,Handle).

            Si on veut également utiliser l'apostrophe comme délimiteur de mot, on ajoutera la clause:

     getrest(Handle,39,Wordlist):-!,getsentence(Wordlist,Handle).

            Notez la coupure. Puisque getsentence est relancé pour constituer Wordlist, getrest n'a plus rien à faire.

           

            Voici toutes les clauses de getrest dans l'ordre:

     getrest(Handle,46,[]):-!.        /* period */
     getrest(Handle,63,[]):-!.       /*? */
     getrest(Handle,32,Wordlist):-!,getsentence(Wordlist,Handle).
     getrest(Handle,Letter,[Word|Wordlist]):-
             getletters(Handle,Letter,Letters,Nextchar),
             name(Word,Letters),
             getrest(Handle,Nextchar,Wordlist).

            Il faut se garder de croire que les virgules qui apparaissent dans la liste de mots renvoyée par getsentence y ont été introduites par lui: la virgule est le séparateur des éléments d'une liste, et c'est Prolog qui se charge de la faire apparaître quand on demande à examiner le contenu de la liste.

            Getsentence est évidemment très procédural. Une lecture déclarative du programme est rendue impossible par l'usage de la coupure.

            On trouvera getsentence en entier ci-dessous, légèrement adapté de Bratko 1990, p.158. Notez que les clauses pour le traitement de l'apostrophe comme délimiteur de mot n'y sont pas reprises.

 /* passage d'une chaîne de caractères à une liste de mots */

getsentence(Wordlist,Handle):- get0(Handle,Char),
                                    getrest(Handle,Char,Wordlist).
     getrest(Handle,46,[]):-!.    
     getrest(Handle,63,[]):-!.   
     getrest(Handle,32,Wordlist):-!,getsentence(Wordlist,Handle).
     getrest(Handle,Letter,[Word|Wordlist]):-
             getletters(Handle,Letter,Letters,Nextchar),
             name(Word,Letters),
             getrest(Handle,Nextchar,Wordlist).
     getletters(Handle,46,[],46):-!.
     getletters(Handle,32,[],32):-!.
     getletters(Handle,63,[],63):-!.
     getletters(Handle,Let,[Let1|Letters],Nextchar):-
                 transform(Let,Let1),!,
                 get0(Handle,Char),
                 getletters(Handle,Char,Letters,Nextchar).
     getletters(Handle,Let,Letters,Nextchar):-
                 get0(Handle,Char),
                 getletters(Handle,Char,Letters,Nextchar).
    
transform(C,C):- C>96,C<123.
     transform(C,C1):-C>64,C<91,C1 is C+32.

            ADAPTATION AU FRANCAIS

            On doit prévoir l'apostrophe et le tiret comme délimiteurs de mot. Cela se fait par l'ajout des clauses:

getletters(H,45,[],45):-!.  /* trait d'union: sais-tu que ... */
getletters(H,39,[],39):-!. /* apostrophe: qu'une d'entre elles ... */
getrest(H,39,Wordlist):-!, getsentence(Wordlist,H).
getrest(H,45,Wordlist):-!, getsentence(Wordlist,H).

            Il s'agit aussi de ne plus rejeter les caractères accentués. On modifiera transform de manière à ce que sa première clause agisse comme bascule des majuscules en minuscules, et sa deuxième laisse tout passer, sauf les caractères de contrôle (ceux qui précèdent l'espace, 32, dans le code ascii):

      transform(C,C1):- C>64,C<91,!,C1 is C+32.
      transform(C,C):- C>31.

            Finalement, au lieu d'appeler tout de suite name, on en invoquera une variante (appelons-la frenchname) qui pourra restituer les lettres disparues par élision, par exemple le e du de et du que dans l'exemple de l'usage de l'apostrophe cité ci-dessus:

            qu'une d'entre elles -> que une de entre elles

            On aura donc:

      frenchname(que,[113,117]):-!.  /* 113: q, 117:u */
      frenchname(de,[100]):-!.          /* d:100 */

etc.

suivis de la clause par défaut:

      frenchname(X,Y):- name(X,Y).

 

Annexe 2 Le pretty-printer PRPR

            Nous étudions ici un utilitaire d'emploi très fréquent appelé pretty-printer. Le code est emprunté à Clocksin et Mellish 1981, p.82.

            Pretty-printer une liste, c'est en faire apparaître la hiérarchie interne, la position d'un élément par rapport à la marge de gauche (niveau d'indentation) reflétant le degré d'enchâssement de l'élément dans la liste soumise au pretty-printer.

            Reprenons un exemple ici. Soit la liste suivante produite par parse:

[s,[snp,[det(the)],[n(man)]],[vpt,[vtr(read)],

                                                       [snp,[det(the)],[n(book)]]]]

            Le pretty-printer en fera ceci:

            s
              snp
                det(the)
                n(man)
              vpt
                vtr(read)
                snp
                  det(the)
                  n(book)

            Le degré d'indentation est déterminé par le nombre d'espaces que le pretty-printer imprimera avant d'imprimer l'élément de liste proprement dit. Ce degré d'indentation est variable, et nous en ferons donc une variable passée au prédéfini tab. Tab(X) imprime X blancs.

            On invoquera le pretty-printer en lui passant deux arguments:

1. la liste à pretty-printer,

2. le degré d'indentation au départ (ce sera souvent 0).

            On aurait donc, dans notre cas, invoqué prpr (le pretty-printer) comme suit:

prpr([s,[snp,[det(the)],[n(man)]],[vpt,[vtr(read)],

                                             [snp,[det(the)],[n(book)]]]], 0).

            Si prpr a une liste à imprimer, alors il avance d'un degré d'indentation et imprime cette liste. Il en imprime la tête; il peut s'agir d'une liste, donc il utilise prpr pour le faire. Ensuite il imprime la queue de la liste, en maintenant le même degré d'indentation, à l'aide du prédicat prprx, que nous étudierons dans un instant:

  prpr([H|T],I):- !, J is I+2, prpr(H,J), prprx(T,J).

            On peut bien sûr choisir un autre incrément que 2. Cela dépendra de la place dont on dispose et du degré d'enchâssement des diverses sous-listes qui constituent la liste à pretty-printer.

            Si prpr n'a pas une liste à imprimer, mais seulement un élément, il indente au degré voulu, imprime l'élément, et passe à la ligne (chaque élément sera donc sur une ligne différente):

  prpr(X,I):- tab(I),write(X),nl.

            Passons à prprx, chargé d'imprimer la queue de la liste. Le cas de base de la récursion intervient quand la liste est vide: prprx ne fait rien:

  prprx([],_).

            Si la liste n'est pas vide, il en "pretty-printe" le premier élément avec prpr, et s'invoque récursivement pour imprimer le reste de la liste, en maintenant toujours la même indentation:

  prprx([H|T],I):- prpr(H,I),prprx(T,I).

            Que peut-on faire si l'on dispose d'une autre représentation que la liste, à savoir une structure complexe parenthésée? Par exemple, nous aurions pu représenter l'arbre syntaxique par un terme (au sens prologien):

(s,(snp,(det(the)),(n(man))),(vpt,(vtr(read)),
                                                      (snp,(det(the)),(n(book)))))

            Une méthode consiste à transformer le terme dans la liste correspondante, et de transformer ses sous-termes en sous-listes, et ainsi de suite. On se souvient qu'on dispose pour ce faire d'un prédicat prédéfini qui s'utilise sous forme d'opérateur infixe, à savoir =.., prononcé univ pour raisons historiques. Univ transforme le terme qui est à sa gauche en une liste qu'il place à sa droite, ou il transforme la liste qui est à sa droite en un terme qu'il place à sa gauche. Par exemple, on aura l'équivalence:

s(np,vp) =.. [s,np,vp]

            Le foncteur du terme est donc la tête de la liste. On pourra dès lors définir un prédicat listify, qui transformera récursivement un terme complexe en une imbrication de listes, qu'on pourra soumettre au pretty-printer. Voyons les cas de base:

     listify(X,X) :- atomic(X),!.
     listify([A|B],[A|B]) :-!.

            Le premier dit qu'il ne faut pas toucher à un atome, et le second à une liste.

            Pour ce qui est du cas général, on listifie la liste avec univ, et on exécute un prédicat listifylist pour listifier les éléments de la liste ainsi obtenue:

     listify(X,X2) :- X =.. X1,listifylist(X1,X2).

            La clause d'arrêt du prédicat listifylist concerne la liste vide: arrêt des opérations:

     listifylist([],[]) :-!.

            Autrement, on applique listify à la tête et listifylist à la queue:

     listifylist([H|T],[H2|T2]) :- listify(H,H2),
                                                listifylist(T,T2).

 

Annexe 3 La notation DCG

            La notation dcg est supportée par la plupart des implantations de Prolog, et notamment par Arity Prolog. Elle permet une écriture plus succincte des grammaires dcg. Nous n'en avons pas fait usage dans cette introduction, car il nous a semblé important que le lecteur comprenne bien le mouvement de progression dans la liste d'entrée effectué par l'interprétation normale par Prolog des règles gouvernant les terminaux et non-terminaux.

            Distinguons le cas des non-terminaux de celui des terminaux. Pour les premiers, la notation dcg permet de dispenser des 2 arguments qui reflètent la progression dans la liste, à savoir la liste d'entrée et la liste de sortie. Prenons une clause de parse et sa traduction en notation dcg:

/* notation de parse */

nounphrase(P0,P2,[snp,Det,N],Number,Sem):-
     determiner(P0,P1,Det,Number),
     noun(P1,P2,N,Number,Sem).

/* notation dcg */

  nounphrase([snp,Det,N],Number,Sem) -->
            determiner(Det,Number),
            noun(N,Number,Sem).

            On constate la disparition pure et simple des 2 premiers arguments, ceux qui désignent la liste d'entrée et la liste de sortie. On remarque aussi que l'opérateur:- est remplacé par -->. Ce remplacement indique à l'interpréteur ou au compilateur Prolog qu'il est en présence d'une règle en notation dcg. En conséquence, il suppléera les deux arguments automatiquement.

            Pour les terminaux on se contente de citer à droite de l'opérateur --> le mot ou les mots qui les constitue(nt), en utilisant pour ce faire la notation de liste. On aura donc la traduction suivante:

/* notation de parse */

 verbintr([thinks|X],X,[vintr(thinks)],sing,human).

/* notation dcg */

 verbintr([vintr(thinks)],sing,human)-->[thinks] .

           

            Les indications de liste d'entrée et de liste de sortie sont donc absentes  ici aussi. Si le terminal est vide, comme par exemple l'article zéro dans parse, on le notera par la liste vide. Nous aurons donc:

      determiner(X,X,[det(zero)],plural).

traduit par

      determiner([det(zero)],plural) --> [] .

           

            Si la clause contient des buts qui ne sont pas censés affecter la liste d'entrée, on les met entre accolades. Ce sera le cas, dans la transcription de PARSE, pour les contrôles sémantiques. On aura donc la transcription:

/* notation de parse */

  verbphrase(P0,P2,[vpt,Vtr,Np],Number,Semsubj):-
    verbtr(P0,P1,Vtr,Number,Semsubj,Semobj),
    nounphrase(P1,P2,Np,_,Sem),
    sfok(Semobj,Sem).

/* notation dcg */

  verbphrase([vpt,Vtr,Np],Number,Semsubj) -->
    verbtr(Vtr,Number,Semsubj,Semobj),
    nounphrase(Np,_,Sem),
    { sfok(Semobj,Sem) }.

            Pour Arity Prolog, il y a stricte équivalence entre les deux notations, mais le prédicat d'invocation de l'analyseur doit stipuler la liste d'entrée et la liste de sortie (cette dernière sera la plupart du temps vide: on exigera que l'analyse fournie couvre toute la liste à analyser). Ces deux arguments doivent nécessairement occuper les deux dernières places. Par exemple, si je veux faire usage du prédicat suivant pour débuter l'analyse au plus haut niveau:

  sentence([s,Np,Vp]) -->
     nounphrase(Np, Number,Semsubj),
     verbphrase(Vp, Number,Semverb),
     { sfok(Semverb,Semsubj) }.

j'invoquerai ce prédicat de la manière suivante:

      sentence(Parsetree,[the,man,read,the,book],[]).

Bien sûr, en général l'invocation ne se fera pas par l'utilisateur au terminal, et donc la liste d'entrée sera désignée par une variable. Par exemple:

      sentence(Parsetree,Sentence,[]).

On trouvera ci-dessous la grammaire et le lexique de parse en format dcg.

/* PARSE EN FORMAT  DCG*/

/* invocation */

  sentence(Parsetree,Sentence,[]) 

/* grammaire */

sentence([s,Np,Vp]) -->
     nounphrase(Np,Number,Semsubj),
     verbphrase(Vp, Number,Semverb),
     { sfok(Semverb,Semsubj) }.

  nounphrase([snp,Det,N],Number,Sem) -->
     determiner(Det,Number),
     noun(N,Number,Sem).

nounphrase([sentnp,Det,Sentn,S],Number,Sem) -->
     determiner(Det,Number),
     sentnoun(Sentn,Number,Sem),
     sentence(S).

nounphrase([relnp,Det,N,Relcl],Number,Sem) -->
     determiner(Det,Number),
     noun(N,Number,Sem),
     relclause(Relcl).

relclause([relcl,Det,N,Vtr]) -->
     determiner(Det,Number),
     noun(N,Number,Sem),
     verbtr(Vtr,Number,Semsubj,Semobj),
     { sfok(Semsubj,Sem) }.      

verbphrase([vpi,Vintr],Number,Semsubj) -->
  verbintr(Vintr,Number,Semsubj).

verbphrase([vpt,Vtr,Np],Number,Semsubj) -->
    verbtr(Vtr,Number,Semsubj,Semobj),
    nounphrase(Np,_,Sem),
    { sfok(Semobj,Sem) }.

verbphrase([vpc,Vcomp,Np1,Np2],Number,Semsubj) -->
    vcomp(Vcomp,Number,Semsubj,Semobj),
    nounphrase(Np1,_,Sem),
    nounphrase(Np2,_,Sem),
    { sfok(Semobj,Sem) } .
 

/* le lexique */

  verbintr([vintr(thinks)],sing,human) -->[thinks].
  verbintr([vintr(think)],plural,human) -->[think].
  verbintr([vintr(thought)],_,human)  -->[thought].

  verbtr([vtr(buys)],sing,human,thing) -->[buys].
  verbtr([vtr(buy)],plural,human,thing) -->[buy].
  verbtr([vtr(bought)],_,human,thing) -->[bought].
  verbtr([vtr(considers)],sing,human,_) -->[considers].
  verbtr([vtr(consider)],plural,human,_) -->[consider].
  verbtr([vtr(considered)],_,human,_) -->[considered].
  verbtr([vtr(likes)],sing,human,_) -->[likes].
  verbtr([vtr(like)],plural,human,_) -->[like].
  verbtr([vtr(liked)],_,human,_) -->[liked].
  verbtr([vtr(makes)],sing,_,_) -->[makes].
  verbtr([vtr(make)],plural,_,_) -->[make].
  verbtr([vtr(made)],_,_,_) -->[made].
  verbtr([vtr(reads)],sing,human,reading_matter) -->[reads].
  verbtr([vtr(read)],plural,human,reading_matter) -->[read].
  verbtr([vtr(read)],_,human,reading_matter) -->[read].
  verbtr([vtr(sees)],sing,human,concrete) -->[sees].
  verbtr([vtr(see)],plural,human,concrete) -->[see].
  verbtr([vtr(saw)],_,human,concrete) -->[saw].
  verbtr([vtr(sells)],sing,human,thing) -->[sells].
  verbtr([vtr(sell)],plural,human,thing) -->[sell].
  verbtr([vtr(sold)],_,human,thing) -->[sold].

  vcomp([vcomp(considers)],sing,human,_) -->[considers].
  vcomp([vcomp(consider)],plural,human,_) -->[consider].
  vcomp([vcomp(considered)],_,human,_) -->[considered].

determiner([det(a)], sing) -->[a].
  determiner([det(the)],_) -->[the].
 
determiner([det(an)],sing) -->[an].
  determiner([det(zero)],plural) -->[].
 
determiner([det(some)],_) -->[some].
  determiner([det(any)],_) -->[any].

  noun([n(book)],sing,[thing,reading_matter]) -->[book].
  noun([n(books)],plural,[thing,reading_matter]) -->[books].
  noun([n(claim)],sing,[abstract]) -->[claim].
  noun([n(claims)],plural,[abstract]) -->[claims].
  noun([n(computer)],sing,[thing,human]) -->[computer].
  noun([n(computers)],plural,[thing,human]) -->[computers].
  noun([n(man)],sing,[human]) -->[man].
  noun([n(men)],plural,[human]) -->[men].
  noun([n(oversimplification)],sing,
                                  [abstract]) -->[oversimplification]. 
  noun([n(oversimplifications)],plural,
                                   [abstract]) -->[oversimplifications]. 
  noun([n(woman)],sing,[human]) -->[woman].
  noun([n(women)],plural,[human]) -->[women].

  sentnoun([sentn(claim)],sing,[abstract]) -->[claim]. 
 
sentnoun([sentn(claims)],plural,[abstract]) -->[claims].  

Notes bibliographiques

            Ces notes sont destinées à guider le lecteur qui désirerait approfondir certaines parties de cette introduction. Elles ne constituent nullement une bibliographie, même succincte, des sujets abordés.

1.Prolog

1) Prolog: syntaxe d'Edimbourg

            a) Clocksin, W.F. et Mellish, C.S., Programming in Prolog, Third Edition, Springer-Verlag, 1987 (probablement l'ouvrage le plus connu et le plus cité sur la programmation en Prolog; quelques passages difficiles pour le débutant).

            b) Sterling, L. et Shapiro, E., The Art of Prolog, Advanced Programming Techniques, The MIT Press, 1986 (mérite son sous-titre; un très beau livre, aussi physiquement; très intéressant, mais pas à lire comme première introduction, bien que l'ouvrage parte de zéro).

            c) Rogers, J.B., A Prolog Primer, Addison-Wesley, 1986 (convient pour une première introduction; approche originale du sujet; facile et clair, mais n'aborde pas les applications intéressantes).

            d) Marcus, C., Prolog Programming, Addison-Wesley, 1986 (excellent; traite des applications dans le domaine des systèmes experts, sgbd, et traitement du langage naturel; assez difficile; programmes écrits en Arity/Prolog).

            e) Bratko, I., Prolog Programming for Artificial Intelligence, Addison-Wesley, 1986 (deux parties; la première une introduction à Prolog; la seconde l'utilisation de Prolog en IA; toutes deux excellentes). Il existe une deuxième édition (1990), enrichie, notamment par un chapitre sur l'analyse du langage naturel.

            f) Covington, M et al., Prolog Programming in Depth, Scott, Foresman and Company, London, 1988 (contient un chapitre (Chap 12) très pédagogique sur les rapports entre la logique du premier ordre et Prolog).

    2) Prolog en général; syntaxe de Marseille

            a) Condillac, M., Prolog: fondements et applications, Dunod, 1986 (Condillac est un nom collectif; bon chapitre sur Prolog et les sgbd)

            b) Giannesini, F. et al., Prolog, InterEditions, 1985

            3) Prolog et l'analyse du langage naturel:

            a) Pereira, F.C.N. et Shieber, S.M., Prolog and Natural-Language Analysis, CSLI Lecture Notes, Nr 10, 1987 (excellent mais parfois assez difficile; on regrettera l'absence d'un corrigé pour les exercices!)

            b) Gazdar, G. and Mellish, Ch., Natural Language Processing in PROLOG, Addison-Wesley, Reading, Mass., 1989. Ouvrage remarquablement bien écrit, très pédagogique. Le code source des programmes est donné en entier. Hautement recommandé. Mériterait trois toques dans un autre contexte ...

            c) Walker, A. et al., Knowledge Systems and Prolog, Addison-Wesley, Reading, Mass, 1987. Cet ouvrage est rédigé par une équipe de chercheurs travaillant à l'IBM T.J. Watson Research Center. Le Prolog utilisé est le Prolog IBM, dont la syntaxe diffère quelque peu de celle d'Edimbourg. La partie consacrée à l'analyse du langage naturel (par Michael McCord) est remarquable. L'ouvrage est toutefois d'un niveau d'exigence assez élévé (comparable à Pereira et Shieber, op. cit.).

2. Intelligence artificielle et linguistique computationnelle

            L'ouvrage capital est une encyclopédie:

            Shapiro, S.C (editor-in-chief), Encyclopedia of Artificial Intelligence, 2 Volumes, 1219 pp., Wiley, New-York, 1990

            Les divers articles de cette encyclopédie sont rédigés par des spécialistes de renommée mondiale. La plupart des articles ont été écrits en 1985 et 1986: il y donc un effort de mise à jour à accomplir par le lecteur. Toutefois, les concepts de base de la linguistique computationnelle y sont remarquablement bien exposés, dans une langue soignée. Les articles sur les différents types de grammaire utilisés en intelligence artificielle et en linguistique computationnelle sont des modèles de clarté d'exposition.

            Thayse, A. et al., Approche logique de l'intelligence artificielle, 3 volumes, Bordas, Paris, 1989-1990.

            Cet ouvrage apporte exactement ce que son titre indique. On ne s'étonnera donc pas des exigences qu'il pose en ce qui concerne la compréhension de la logique contemporaine. Pour notre propos, on lira les chapitres suivants du premier volume:

            Chapitre Trois, Représentation de la connaissance et raisonnement

            Chapitre Cinq, Grammaires formelles et programmation logique

            Chapitre Six, Prolog et la programmation logique

            Sabah, G., L'intelligence artificielle et le langage, Tome 1: Représentations des connaissances, 2e édition; Tome 2: Processus de compréhension; Hermès, Paris, 1990

            Cet ouvrage pourrait aussi figurer au point 3 de ces notes bibliographiques (théories linguistiques, qui sont passées en revue dans le premier volume). Le deuxième volume a une orientation plus informatique.

 

            Charniak, E., Mc Dermott, D., Introduction to Artificial Intelligence, Addison-Wesley, 1985 (exemples en Lisp)

            Winston, P.H., Artificial Intelligence, Second Edition, Addison-Wesley, 1984 (également exemples en Lisp; à lire avec l'ouvrage de Winston et Horn, B.K.P., Lisp, Second Edition, même éditeur, 1984)

            O'Shea, T. et Eisenstadt, M. (eds), Artificial Intelligence, Harper and Row, 1984 (contient une introduction à Prolog par W.F. Clocksin, deux chapitres sur Lisp, et deux chapitres sur le traitement du langage naturel)

            Numéro spécial de La Recherche, Octobre 1985, L'intelligence artificielle (lire surtout les articles de Pitrat, Ganascia, Kayser, Sansonnet, Gallaire; donne une idée des travaux en France en IA; paru sous forme de livre: Seuil, Points)

            Grishman, R., Computational Linguistics: An Introduction, Cambridge University Press, 1986 (bonne introduction: cfg, atn, etc.)

            Winograd, T., Language as a Cognitive Process, Vol.I, Syntax, Addison-Wesley (assez exhaustif; très pédagogique; par une des sommités du domaine).

            Allen, J., Natural Language Understanding, Benjamin / Cummmings, Menlo Park, Cal., 1987. Orienté LISP. Intéressant surtout pour la partie sémantique et représentation de la connaissance.

3. Théories linguistiques

            Les théories linguistiques les plus connues à l'heure actuelle sont en partie construites sur le concept d'unification (dont la définition s'écarte toutefois à des degrés divers de celle qui est adoptée dans Prolog). On tiendra compte du fait que les diverses théories linguistiques tendent à mettre en exergue les différences qui les séparent les unes des autres, plutôt que leurs points de convergence. Il ne faut certes pas voir des différences notationnelles là où il y a des différences de substance, mais il nous semble qu'on tombe plus facilement dans le travers contraire.

            Comme introduction aux grammaires d'unification, on se tournera vers l'ouvrage de Shieber:

            Shieber, S., An Introduction to Unification-Based Approaches to Grammar, Chicago University Press, Chicago, 1986

            Les théories linguistiques appartenant au modèle génératif (GB, GPSG, LFG) sont décrites et confrontées dans deux ouvrages; notre préférence va à celui de Horrocks:

            Sells, P, Lectures on Contemporary Syntactic Theories, CSLI Lecture Notes Nr 3, Chicago University Press, Chicago, 1985

            Horrocks,G., Generative Grammar, Longman, London, 1987

            On trouvera une description plus poussée des quatre modèles principaux de grammaire d'unification dans les ouvrages cités ci-dessous; ces ouvrages ne prétendent pas être des introductions pédagogiques.

            1) Lexical Functional Grammar (LFG)

            Bresnan, J.W., Kaplan, R.M., Lexical Functional Grammar, in Bresnan, J.W. (ed), The Mental Representation of Grammatical Relations, Cambridge, Mass., MIT Press, 1982

            2) Generalized Phrase Structure Grammar (GPSG)

            Gazdar, G., Klein, E., Pullum, G., Sag, I., Generalized Phrase Structure Grammar,  Basil Blackwell, Oxford, 1985

            3) Head-Driven Phrase Structure Grammar (HPSG)

            Pollard, C.J, Sag, I.A., Information-based Syntax and Semantics, Vol. 1: Fundamentals, CSLI Lecture Notes nr 13, Chicago University Press, Chicago,  1987; Vol.2: Agreement, Binding, and Control, à paraître en 1991.

            4) Government and Binding (GB)

            Chomsky, N., Lectures on Government and Binding, Foris, Dordrecht, 1982

            Et pour terminer ces notes bibliographiques, un recueil de présentations orales et des discussions auxquelles elles ont donné lieu, sur le sujet des applications informatiques de théories linguistiques.

     Whitelock, P., Wood, M.M., Somers, H.L., Johnson, R. et Bennett, P (eds), Linguistic Theory and Computer Applications, Academic Press, New York, 1987



[1]  Arity Corporation, 29 Domino Drive, Concord, Mass., U.S.A. Les programmes de cet ouvrage ont été développés à l'aide de la version 5.0, sous OS/2 version 1.1. Le matériel utilisé est un IBM Modèle 70 avec 4 Mégaoctets de mémoire vive et un disque dur de 120 Mégaoctets.

[2]   On distingue donc relation et prédicat. Le premier terme n'appartient pas à Prolog, le second bien. En conséquence, on ne fera pas disparaître les caractères accentués des noms de relation, alors qu'on limitera les caractères utilisés dans les noms de prédicat à du pur ASCII.

[3]  On aurait pu écrire pgcd(X,Y,X):- X=Y., l'égalité des deux premiers arguments étant alors testée dans une clause indépendante. Mais c'est moins élégant et moins efficace.

[4]  Sur le clavier d'un IBM PC ou compatible, | s'obtient en maintenant enfoncée la touche ALT et en entrant 124 au pavé numérique.

[5]  findall n'est pas un prédéfini dans toutes les implantations de Prolog.

[6]  La version utilisée ici est celle de 1978. Le rédacteur en chef en était Paul Procter.

[7] Bien sûr, dans la réalité les répertoires sont également des fichiers. Nous dirons que nous modélisons une appréhension assez naïve des objets informatiques, une taxonomie populaire, en quelque sorte ...

[8]   Réifier (philo.): Constituer en une chose extérieure et autonome (Dictionnaire Hachette de la langue française)

[9] Qui assure que toute conclusion déduite de certaines hypothèses reste valide après tout ajout de nouvelles hypothèses (S.Pavel, Intelligence Logicielle, Dictionnaire français-anglais, Réseau international de néologie et de terminologie, Module Canadien, Secrétariat d'Etat du Canada, 1989)

[10] Il convient de citer ici Sterling et Shapiro 1986, p. 109: "In Prolog programming (in contrast, perhaps, to life in general) our goal is to fail as quickly as possible."

[11] Bien que des analyses partielles soient intéressantes à obtenir dans certains contextes, par exemple lorsque l'analyseur est confronté à des énoncés partiellement grammaticaux.

[12] Cette possibilité de rectification n'est pas superflue, à en juger par cette phrase extraite de Sterling et Shapiro 1986, p. 202:" The size of the chunks of code that should be written and debugged as a whole varys (sic) and grows as the experience of the programmer grows".