Un ancêtre de Prolog, les systèmes-Q

L’histoire de la naissance de Prolog s’arrête donc à la fin de l’année 1975. Passons maintenant à des aspects plus techniques et tout d’abord décrivons les systèmes-Q, le résultat d’un premier pari : développer un langage de programmation de très haut niveau, même si les temps d’exécution qu’il implique puissent sembler effarants [Colmerauer, 1970b]. Ce pari et l’expérience acquise dans l’implantation des systèmes-Q furent déterminants dans le deuxième pari : Prolog. Unification unidirectionnelle
Un système-Q consiste en un ensemble de règles de réécriture portant sur des suites de symboles complexes séparés les uns des autres par le signe +. Chaque règle est de la forme e1 + e2 + …. + em  f1 + f2 + …. + fn et signifie : dans la suite de symboles que l’on est en train de manipuler on peut remplacer toute sous-suite de la forme e1 + e2 + …. + em par la sous-suite de la forme f1 + f2 + …. + fn.
Les ei et les fi sont des expressions parenthésées représentant des symboles complexes, en fait
des arbres. Ces expressions ressemblent étrangement à des termes Prolog, mais font intervenir trois types de variables. Suivant que la variable commence par une lettre de l’ensemble {A,B,C,D,E,F}, {I,J,K,L,M,N}, ou {U,V,W,X,Y,Z} elle désigne une étiquette, un arbre, ou une suite (éventuellement vide) d’arbres séparés par des virgules. Par exemple la règle P + A*(X*,I*,Y*)  I* + A*(X*,Y*)
(les variables sont suivies d’une astérisque) appliquée sur la suite P + Q(R,S,T) + P produit trois suites possibles
R + Q(S,T) + P,
S + Q(R,T) + P,
T + Q(R,S) + P.
La notion d’unification est donc déjà présente, mais elle est unidirectionnelle : les variables apparaissent dans les règles mais jamais dans la suite d’arbres que l’on est en train de transformer. Par contre l’unification prend en compte l’associativité de la concaténation et, comme dans l’exemple précédent, peut produire plusieurs résultats.

Stratégie d’application des règles

Ceci est pour la partie unification. En ce qui concerne la stratégie d’application des règles Alain [1970b] écrit :
« Utiliser un ordinateur pour analyser une phrase est une entreprise difficile. Le problème principal est de nature combinatoire: pris isolément chaque groupe d’éléments de la phrase peut se combiner de différentes façons avec d’autres groupes et en former de nouveaux qui à leur tour peuvent se recombiner, et ainsi de suite. En général il n’existe qu’une seule façon de regrouper la totalité des éléments, mais pour la découvrir, il faut essayer tous les groupements possibles. Pour représenter d’une façon économique cette multitude de regroupements, j’utilise un graphe orienté où chaque flèche est surmontée d’une expression parenthésée représentant un arbre. Un système-Q n’est rien d’autre qu’un ensemble de règles permettant de transformer un tel graphe en un autre graphe. Cette transformation peut correspondre à une analyse, à une synthèse de phrase, ou à une manipulation formelle de ce genre. »
On conserve tous les chemins qui vont du point d’entrée au point de sortie et qui ne comportent pas de flèches ayant été utilisées pour produire d’autres flèches. On conserve donc l’unique flèche S c’est-à-dire la suite réduite au seul symbole S.
Cette façon de procéder est relativement efficace car elle préserve le maximum de parties communes entre toutes les suites. Un autre aspect des systèmes-Q est la possibilité de les enchaîner les uns à la suite des autres. Chacun prend comme donnée le graphe résultant du précédent. Cette technique était largement utilisée dans le projet de traduction automatique, puisqu’une phrase anglaise ne subissait pas moins de 15 systèmes-Q avant d’être traduite en français. Deux systèmes-Q s’occupaient de la morphologie, un autre de l’analyse de l’anglais, deux du passage d’une structure anglaise à un structure française, un de la synthèse du français et 9 de la morphologie française [TAUM 71].
Signalons le coté réversible des système-Q. Le signe de réécriture que nous avons noté  était en fait noté == et, suivant l’option choisie et spécifiée en tête de programme, était interprété comme une réécriture de gauche à droite ou une réécriture de droite à gauche. Ceci veut dire que le même programme pouvait être utilisé pour décrire une transformation et la transformation inverse, comme l’analyse et la synthèse d’une phrase.
Il est intéressant de noter que contrairement aux analyseurs écrits en Prolog qui utilisent une stratégie descendante (top-down), les analyseurs écrits en systèmes-Q utilisent une stratégie remontante (bottom-up). En fait Alain avait une longue expérience de ce type de stratégie. Sa thèse passée à Grenoble (en France) portait déjà sur des analyseurs remontants mais fonctionnant par backtracking [Colmerauer, 1970a]. Le non-déterminisme était alors limité par des relations de précédences très proches de celles de Robert Floyd [1963]. De plus, juste avant de concevoir les systèmes-Q et toujours dans le cadre du projet de traduction automatique, Alain avait écrit un analyseur et un synthétiseur général pour W-grammaire, le formalisme introduit par A. van Wijngardeen pour décrire Algol 68 [Wijngardeen, 1968]. Là aussi un analyseur remontant était utilisé pour retrouver la structure des symboles complexes (définis par une méta-grammaire) ainsi qu’un deuxième analyseur remontant pour l’analyse du texte proprement dite [Chastellier, 1969].

Réalisation

Les systèmes-Q furent écrits en Algol par Alain et furent opérationnels dès octobre 1969. Michel van Caneghem et François Stellin, terminant alors une maîtrise d’informatique, en produirent une version Fortran et Gilles Steward une version ultra rapide en langage machine pour l’ordinateur CDC 6400 de l’Université de Monréal.
Ces systèmes-Q furent utilisés pour construire une chaîne complète de traduction automatique anglais-français par toute l’équipe du projet TAUM: Brian Harris écrivit la morphologie de l’anglais, Richard Kittredge écrivit une importante grammaire pour l’analyse de l’anglais, Gilles Stewart écrivit la phase de transfert, Jules Danserau écrivit la grammaire pour la synthèse du français et Michel van Caneghem produisit une morpholgie complète du français [Taum 71]. Les systèmes-Q furent aussi utilisés quelques années plus tard pour écrire le système METEO dont une version industrielle actuelle traduit tous les jours les bulletins météréologiques canadiens d’anglais en français.

Le Prolog préliminaire

Passons maintenant à la version préliminaire de Prolog qui fut créée au cours de l’écriture du système de communication homme machine en automne 1972 [Colmerauer, 1972].
Rappelons que l’objectif fixé était extrêmement ambitieux : disposer d’un outil nous permettant de traiter les problèmes syntaxiques et sémantiques de la langue naturelle, en considérant la logique du premier ordre non seulement comme un langage de programmation, mais aussi comme un langage de représentation des connaissances. Autrement dit, la formulation logique devait servir non seulement pour les différents modules du système de communication mais aussi pour les informations échangées y compris avec l’utilisateur.
Le choix s’étant porté sur la logique du premier ordre (sous forme clausale) et non pas sur une logique d’ordre supérieure, il y avait là une apparente impossibilité à vouloir que des programmes puissent manipuler d’autres programmes. C’est bien sûr par le biais de mécanismes extra-logiques que nous avons résolu ce problème. En fait, cette version initiale de Prolog fut conçue plutôt comme l’outil d’une l’application que comme un langage de programmation universel. Les prémisses d’un tel langage étaient cependant là.

Choix de la méthode de résolution, raisons

La décision concernant le choix du système logique et le mécanisme d’inférence de base que nous allions adopter était crucial pour le succès du projet. Si le principe de résolution de A. Robinson s’imposait naturellement par la simplicité de la forme clausale, l’unicité de la règle d’inférence et certaines similitude avec l’appel de procédures des langages classiques, il fut difficile de décider quel type d’adaptation était nécessaire pour répondre à nos objectifs. Il fallait prendre en compte la validité et la complétude logique du système, les problèmes d’implantation en machine et surtout les risques d’explosion combinatoire que nous connaissions parfaitement après nos expérimentations.
Parmi les systèmes de questions-réponses et les techniques de résolution de problèmes que nous avions étudiés, figuraient entre autres celui de D. Luckham [1971] et N.J. Nilson, celui de J.L. Darlington [1969] et celui de Cordell Green [1969]. Cette étude, les essais de Jean Trudel et Robert Pasero qui utilisaient les versions expérimentales des démonstrateurs de Philippe, les recherches d’Alain sur la formulation logique des grammaires ainsi que les nombreuses discussions avec Robert Kowalski, tout cela nous amena à considérer le principe de résolution de A. Robinson selon un point de vue différent de celui qui prévalait alors. Plutôt que de vouloir démontrer un théorème par l’absurde, nous voulions calculer un ensemble « intéressant » de clauses déductibles d’un ensemble donné de clauses. De tels ensembles constituant dans notre esprit des programmes, nous avions ainsi des programmes engendrant d’autres programmes. C’est cette idée qui fut constamment sous-jacente dans la conception de cette version préliminaire du langage comme dans la réalisation de l’application.
Le choix final porta sur une adaptation de la méthode de résolution proche de la philosophie générale du Prolog que l’on connaît maintenant, mais comportant cependant des éléments originaux. Chaque exécution s’effectuait avec un ensemble de clauses constituant le
« programme » et un ensemble de clauses constituant les « questions », le tout produisant un ensemble de clauses constituant les « réponses ». Les littéraux des clauses étaient ordonnés de gauche à droite, l’unification s’effectuait entre le littéral de tête de la résolvante et celui d’une des clauses du programme. L’originalité résidait dans le fait que dans chaque clause une partie des littéraux, séparée par le signe /, n’étaient pas traités au cours de l’exécution, mais étaient accumulés pour produire une des clauses réponse en fin de déduction. En outre, certains prédicats (tel DIF) étaient traités par une évaluation retardée et pouvaient également être transmis en réponse. Enfin, il fut décidé que le non-déterminisme serait traité par backtracking, ce qui voulait dire qu’une seule branche de l’arbre de recherche résidait à un instant donné en mémoire.
Formellement, la méthode de déduction choisie peut se décrire selon les trois règles ci-dessous, où « question », « clause choisie » et « réponse » sont trois clauses prises respectivement dans les ensembles « questions », « programme » et « réponses » tandis que « résolvante » est une clause intermédiaire.

Introduction
Partie I. L’histoire
Année 1971, les premiers travaux
Année 1972, l’application qui crée Prolog
Année 1973, le vrai premier Prolog
Année 1974 et 1975, la diffusion de Prolog
Partie II. Un ancêtre de Prolog, les systèmes-Q
Unification unidirectionnelle
Stratégie d’application des règles
Réalisation
Partie III. Le Prolog préliminaire
Choix de la méthode de résolution, raisons
Caractéristiques du Prolog préliminaire
Réalisation du Prolog préliminaire
Partie IV. Le Prolog définitif
Stratégie de résolution
Syntaxe et Primitives
Un exemple de programme
Réalisation de l’interprète
Conclusion
Bibliographie