Home

La naissance de Prolog - Colmerauer, Alain

1. Robinson J A A machine oriented logic based on the resolution principle J ACM 12 1 pages 23 a 41 janvier 1965 TAUM 71 rapport annuel du projet de Traduction Automatique de l Univer sit de Monr al Universit de Montr al Janvier 1971 Warren David H D Warplan A System for Generating Plans research re port University of Edimburgh Department of Computational Logic memo 76 juin 1974 Warren David H D Luis M Pereira et Fernando Pereira Prolog the language and its implementation Proceedings of the ACM Symposium on Artificial Intelligence and Programming Languages Rochester N Y ao t 1977 Wijngardeen van A B J Mailloux J E L Peck et G H A Koster Final Draft Report on the Algorithmic Language Algol 68 Mathematish Centrum Amsterdam d cembre 1968 Winograd Terry Understanding Natural Language Academic Press 1973 60
2. 40 Chapitre 5 Appendice 5 1 Le programme de fr re et soeur Entre temps Prolog et sa syntaxe c est stabilis voire Prolog ISO standard 16 Les variables sont des identificateurs commencant par une majuscule Une clause c est a dire une instruction Po P1 Pa S crit Po 17 Payin Pa Cette clause est interpr t e comme po est vrai si p et et pn est vrai ou encore d une fa on plus proc durale comme pour ex cuter py il faut ex cuter successivement p et et Dn Consid rons une petite banque de donn es H l ne est fille de Marguerite Nicole est fille de Rosalie Rachel est fille de Rosalie Jules est fils de Marguerite Paul est fils de Marguerite Robert est fils Rosalie Plus une r gle x et z sont fr re et s ur si x est le fils y et z est la fille de y Cela se traduit par le programme Prolog freresoeur X Z estfilsde X Y estfillede Z Y estfillede helene marguerite estfillede nicole rosalie estfilsde jules marguerite estfilsde paul marguerite 41 La question quel est le x qui est tel que Paul et x sont fr re et soeur devient freresoeur paul X X helene qui produit la r ponse H l ne Cette r ponse se calcule a l aide de trois param tres la contrainte courante la question courante et la r gle choisie courante 1 2 Initialiser la contrainte vide Initialiser la question la question initiale Si la question est vid
3. Y2 w A2 Z2 ajout X2 Y2 Z2 contrainte fajout X1 Y1 nul ajout w A2 X2 Y2 w A2 Z2 U X w A1 X1 Y Y1 Al a Zi nul nul w A3 X3 fin echec 5 5 Le programme des mutants avec des parenth ses En partant de l ensemble d animaux alligator bouquetin caribou cheval chevre hibou lapin ours pintade tortue vache avec beaucoup de parenth se nous produirons alligatortue caribouquetin caribours chevalligator chevalapin hibouquetin hibours lapintade vacheval vachevre avec toujours des parenth ses 90 mutantprovisoire Z animalprovisoire X animalprovisoire Y ajout A B X ajout B C Y nonnul B nonnul A ajout X C Z nonnul w A X ajout nul Y Y ajout w A X Y w A Z ajout X Y Z animalprovisoire w a w l w l w i w g w a w t w o w r aul animalprovisoire w b w o w u w q w u wl e w t w i w n nul animalprovisoire w c w a w r w i w b w o w u nul animalprovisoire w c w h w e w v w a w 1 nul animalprovisoire w c w h w e w v w r w e nul animalprovisoire w h w i w b w o w u nul animalprovisoire w l w a w p w i w n nul animalprovisoire w p w i w n w t w a w d w e nul animalprovisoire w o w u w r w s nul animalprovisoire w p w i w n w t w a w d w e nul animalprovisoire w t w o w r w t w u w e nul animalprovisoire w v w a w c w h w e nul mutantprovisoire Z Z wla w l w
4. me de calcul formel 3 4 23 et un syst me g n ral de r solution de probl mes appel Sugiton 22 D autre part Robert Pasero continue l utiliser dans le cadre de son travail sur la s mantique du francais qu il conclut en soutenant une th se au mois de mai 33 De f vrier avril 73 Philippe fait un s jour la School of Artificial Intelligence de l Universit d Edimbourg au sein du D partement de Logique Computation nelle dirig e par Bernard Meltzer et o Robert Kowalski l avait invit Outre les discussions nombreuses qu il a avec lui et David Warren il rencontre galement Robert Boyer et Jay Moore qui avaient b ti une implantation de la r solution selon un proc d extr mement ing nieux bas sur une technique de partage de structures pour repr senter les formules logiques engendr es au cours d une d duction Le r sultat de ce s jour et la n cessit pour le laboratoire de disposer d un v ritable langage de programmation nous d cident jeter les bases d un deuxi me Prolog De mai juin 1973 nous fixons les grandes lignes du langage en particulier les 16 choix de la syntaxe des primitives de base et des principes de calcul de l interpr te le tout allant dans le sens d une simplification par rapport a la version initiale De juin la fin de l ann e G rard Battani Henry M loni et Ren Bazzoli alors tudiants de DEA r alisent l interpr te en Fortran et son superviseur en
5. num re et crit en sortie tous les couples de villes reli es par un vol avec ou sans escales la m me ville ne figurant qu une seule fois sauf pour les cir cuits qui partent et arrivent au m me endroit Les param tres heure d part gt et heure arriv e d signent respectivement l heure de d part et l heure d arriv e calcul es Enfin heure mini d part et heure mazi arriv e sont des contraintes d ho raires et les seuls param tres que doit fournir l usager du pr dicat Tout plan de vol calcul par le pr dicat fournira un premier vol dont l heure de d part suit heure mini d part et un dernier vol dont l heure d arriv e pr c de heure maxi arriv e gt 34 Pour d finir ce pr dicat itineraire plusieurs pr dicats interm diaires sont d fi nis Le pr dicat route ville d part ville arriv e gt heure d part heure arriv e itin raire lt escales gt heure mini d part heure mazi arriv e est analogue a itineraire Il comporte deux param tres suppl mentaires en entr lt escales gt qui d signe la liste cx cCp 1 ci mil des villes d j visit es dans l ordre inverse du parcours et en sortie itin raire qui d signe la liste f1 f nil des noms des vols constituant le voyage Les pr dicats precedehoraires h1 h2 et plushoraires h1 h2 h3 concernent le traitement arithm tique des horaires Le pr dicat ecrireplan permet d crire un plan com
6. Intelligence Artificielle Facult des Sciences de Luminy Univer sit Aix Marseille II France novembre 1975 English version Metamorpho sis grammars Natural Language Communication with Computers Lectures Notes in Computer Science 63 dit par L Bolc Springer Verlag Berlin Heidelberg New York pp 133 189 1978 ISBN 3 540 08911 X Darlington J L Theorem proving and information retrieval Machine Intel ligence 4 Edinburgh University Press pp 173 707 1969 P Deransart A Ed Dbali et L Cervoni Prolog The Standard Reference Manual Springer 1996 Elcok E W Absys the first logic programming language a restrospective and a commentary Journal of Logic Programming 9 1 1 17 Juillet 1990 Floyd Robert W Syntactic analysis and operator precedence J ACM 10 pp 316 333 1963 Floyd Robert W Nondeterministic algorithms J ACM 14 4 pp 636 644 Octobre 1967 Green Cordell C Application of theorem proving to problem solving Pro ceedings of First International Joint Conference on Artificial Intelligence Washington D C pp 219 239 1969 Hewitt Carl PLANNER A language for proving theorems in robots Pro ceedings of First International Joint Conference on Artificaila Intelligence Washington D C pp 295 301 1969 98 22 23 24 25 26 tn 27 28 29 30 31 32 dit 33 Joubert Michel Un syst me de r solution de probl mes a tend
7. Prolog Ainsi que le lecteur pourra en juger dans la quatri me partie de ce papier ce nouveau Prolog qui y est d crit en d tails introduit toutes les fonctionnalit s essentielles des Prolog actuels Signalons au passage que c est cette occasion que dispara t l occur check jug trop co teux 1 4 Ann e 1974 et 1975 la diffusion de Prolog La version interactive de Prolog qui fonctionne sur Grenoble a l aide d une console teletype est tres sollicit e David Warren qui est chez nous pendant le mois de janvier et de f vrier 1974 l utilise pour crire son syst me de g n rateur de plans Warplan 39 A cette occasion il fait le commentaire suivant sur le syst me Prolog The present system is implemented partly in Fortran partly in Prolog itself and running on an IBM 360 67 achieves roughly 200 unifications per second Henry Kanoui et Marc Bergman l utilisent pour r aliser un syst me de ma nipulation formelle d une certaine envergure appel Sycophante 5 24 G rard Battani et Henry Meloni l utilisent pour r aliser un syst me de reconnaissance de la parole permettant de poser des questions sur le mode d emploi du syst me d exploitation CP CMS de PIBM de Grenoble 2 31 L interface entre le signal acoustique et la suite de phon mes qu il repr sente est emprunt e au CNET Lannion et bien entendu n est pas crite en Prolog Au d but de l ann e 1975 Alain a compl tement r crit le superviseur en
8. a 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 programma tion de tr s haut niveau m me si les temps d ex cution qu il implique puissent sembler effarants 11 Ce pari et l exp rience acquise dans l implantation des syst mes Q furent d terminants dans le deuxi me pari Prolog 2 1 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 eg ete temofitktw x fa et signifie dans la suite de symboles que l on est en train de manipuler on peut remplacer toute sous suite de la forme ee e par la sous suite de la forme fifo fn Les e et les f sont des expressions parenth s es repr sentant des sym boles complexes en fait des arbres Ces expressions ressemblent trangement des termes Prolog mais font intervenir trois types de variables qui se terminent toutes par une ast risque suivant que la variable commence par une lettre de l ensemble fa 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 Ax Xx Ix Yx gt Ix Ax Xx Yx appliqu e sur la suite P Q R S T P 19 produit trois suit
9. dans l ensemble y et une formule de la forme Vrai r x y exprime que les ensembles x et y sont dans la relation r Aux clauses qui codent les phrases Jean Trudel ajoute quatre clauses liant les trois symboles Le Dans Vrai Vz Dans z x Vz Vy V2 Dans z y A Dans y z gt Dans x z Va Vb Dans Le a Le b gt Dans Le b Le a Vr Vy Vr Vr Vy Vrailr x y A Dans x x A Dans y y gt Vrai r 2 y Le probl me majeur est d viter une production intempestive d inf rences due aux axiomes de transitivit et de r flexivit de la relation d inclusion Dans En continuant ses recherches sur la d monstration automatique Jean Trudel tombe sur une m thode tr s int ressante la SL r solution 25 I nous convainc d inviter l un de ses cr ateurs Robert Kowalski Celui ci nous rend visite en juin 1971 et reste une semaine La rencontre reste inoubliable Pour la premi re fois nous discutons avec un sp cialiste de d monstration automatique qui nous fait saisir ce qu est vraiment le principe de r solution ses variantes et ses raffinements Quant a Robert Kowalski il rencontre des gens passionn s par ses recherches et d cid s a les mettre en application dans le traitement des langues naturelles Avec Jean Trudel nous revoyons Bob Kowalski a l occasion d un congr s IJCAI en septembre 71 a Londres ou nous assistons a un expos de Terry Winograd 42 sur un interface en langue naturelle qui
10. 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 21 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 a Grenoble en France portait d ja sur des analyseurs remontants mais fonctionnant par backtracking 10 Le non d terminisme tait alors limit par des relations de pr c dences tr s proches de celles de Robert Floyd 18 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 41 L aussi un analyseur remon tant 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 7 2 3 R alisation Les syst mes Q furent crits en Algol par Alain et furent op rationnels d s oc tobre 1969 Michel van Caneghem et Francois Stellin terminant alors une maitrise d informatique en produirent une
11. francais De son cot Robert Kowalski obtient un financement de OTAN qui financera de nombreux changes entre Edinburgh et Marseille De tous les syst mes de r solution qui furent implant s par Philippe SL r solution de R Kowalski et D Kuehner semble le plus int ressant Son fonc tionnement en pile similaire la gestion des appels de proc dures dans un langage de programmation classique est particuli rement adapt a un traitement du non d terminisme par backtracking la Robert Floyd 19 plut t que par recopie et sauvegarde des r solvantes SL r solution servira donc de support la th se de Philippe qui porte sur le traitement de l galit formelle en d monstration auto matique 35 L galit formelle est moins expressive que l galit classique mais par contre peut tre trait e efficacement La these de Philippe d bouchera sur l introduction du pr dicat dif pour 4 dans la toute premi re version de Prolog Nous invitons a nouveau Robert Kowalski mais cette fois ci pour une p riode plus longue avril et mai Ensemble nous avons tous maintenant une connaissance plus calculatoire de la d monstration automatique Nous savons axiomatiser de petits probl mes addition de nombres entiers concat nation de listes retour nement de listes etc de fagon a ce qu un d monstrateur de type SL r solution calcule rapidement le r sultat Mais le paradigme clause de Horn nous est inconnu et Alain ne voit to
12. introduite tr s simplement du point de vue syntaxique Dans toute clause une variable d signant un terme peut figurer comme litt ral Dans le m me esprit et ceci originellement l intention des sp cialistes de la logique computationnelle sont introduites des primitives permettant d acc der la d duction en cours en la consid rant comme un objet de type Prolog add delete De m me le pr dicat prononc cut par les dimbourgeois devient param trable d une facon tr s puissante par acc s aux anc tres 4 3 Un exemple de programme Pour que le lecteur ait une id e de ce a quoi ressemble un programme Prolog de l poque nous reprenons un vieil exemple Il s agit de d terminer des itin raires d avions respectant certaines contraintes d horaires partir de la connaissance des vols directs Les donn es de base vols directs entre deux villes sont repr sent es par des clauses unaires de la forme vol ville d part gt ville arriv e gt heure d part gt heure arriv e gt nom de vol ou les heures sont repr sent es par des couples d entiers de la forme heure minute Nous supposons que tous les vols s effectuent enti rement dans une m me journ e Le pr dicat suivant est utilis par l usager pour tablir un itin raire itineraire ville d part ville arriv e gt heure d part heure arriv e heure mini d part heure maxi arriv e gt Il
13. pr c dences num riques s est av r e par la suite tr s utile et tr s souple d emploi quoique compliquant les analyseurs de clauses Elle subsiste toujours telle quelle dans les divers Prolog actuels Dans la version pr liminaire de Prolog il existait un moyen de cr er des clauses logiquement d ductibles a partir d autre clauses L exp rience nous a montr ce pendant qu il est souvent n cessaire de manipuler des clauses dans des perspectives quelquefois tr s loign es de la logique du premier ordre Ce type de traitement in tervient par exemple dans la programmation de raisonnements de type temporel dans la gestion d informations persistantes d une dur e de vie al atoire ou encore dans la simulation de logiques exotiques Nous sentons que sur le plan de la s mantique il faudra encore de nombreuses recherches pour mod liser ces probl mes de mise jour d ensembles de clauses D o le choix extr mement pragmatique de primitives extra logiques agissant par effet de bord pour cr er ou modifier un programme ajout supp Ce choix semble avoir t le bon puisque ces fonctions ont t conserv es par la suite Un des manques ressentis avec la version pr liminaire de Prolog est celui d un m canisme permettant de calculer un terme qui puisse tre ensuite consid r comme un litt ral r soudre Cette fonction essentielle pour r aliser des m ta 33 programmes comme par exemple un interpr te de commandes est
14. r alis l aide d une repr sentation des clauses tout fait originale se situant mi chemin entre la technique bas e sur le partage de structures qu utili saient Robert Boyer et Jay Moore dans leurs travaux sur la preuve de programmes 16 32 et la technique par backtracking utilis e dans la version pr liminaire de Pro log C est au cours de son s jour Edimbourg que Philippe apr s de nombreuses discussions avec Robert Boyer imagine cette solution Dans cette nouvelle ap proche les clauses d un programme sont cod es en m moire comme un ensemble de squelettes templates pouvant tre instanci s sans recopie plusieurs fois dans une m me d duction gr ce des contextes contenant les substitutions effectuer 37 sur les variables Cette technique a de nombreux avantages par rapport a celles utilis es alors en d monstration automatique lunification s effectuait dans tous les syst mes connus en des temps au mieux lin aires par rapport la taille des termes unifi s dans notre syst me la plupart des unifications s effectuent dans des temps constants fonction non pas de la taille des donn es mais de celle des squelettes mis en jeu par les clauses du programme appel ainsi la concat nation de deux listes s effectue en un temps lin aire par rapport la taille de la premi re et non pas comme dans tous les syst mes bas s sur des techniques de recopie en des temps quadratiques selon le
15. version Fortran et Gilles Steward une version ultra rapide en langage machine pour l ordinateur CDC 6400 de l Universit de Montr al Ces syst mes Q furent utilis s pour construire une chaine compl te de tra duction automatique anglais francais par toute l quipe du projet TAUM Brian Harris crivit la morphologie de l anglais Richard Kittredge crivit une impor tante grammaire pour l analyse de l anglais Gilles Stewart crivit la phase de transfert Jules Danserau crivit la grammaire pour la synth se du francais et Michel van Caneghem produisit une morpholgie compl te du francais 38 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 rologiques canadiens d anglais en francais 22 Chapitre 3 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 13 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 modul
16. AIRES H1 M1 H2 M2 INF H1 H2 PRECEDEHORAIRES H1 M1 H1 M2 INF M1 M2 PLUSHORAIRES H1 M1 H2 M2 H3 M3 PLUS M1 M2 M RESTE M 60 M3 DIV M 60 H PLUS H H1 HH PLUS HH H2 H3 ECRIREPLAN X NIL SORT xX ECRIREPLAN X Y SORT X ECRIT ECRIREPLAN xY ELEMENT X X Y ELEMENT X Y Z ELEMENT xX Z NON X X ECHEC NON X LISTE DES VOLS VOL PARIS LONDRES 06 50 07 30 AF201 VOL PARIS LONDRES 07 35 08 20 AF210 VOL PARIS LONDRES 09 10 09 55 BA304 VOL PARIS LONDRES 11 40 12 20 AF410 VOL MARSEILLE PARIS 06 15 07 00 IT100 VOL MARSEILLE PARIS 06 45 07 30 IT110 VOL MARSEILLE PARIS 08 10 08 55 IT308 VOL MARSEILLE PARIS 10 00 10 45 IT500 36 VOL MARSEILLE LONDRES 08 15 09 45 BA560 VOL MARSEILLE LYON 07 45 08 15 IT115 VOL LYON LONDRES 08 30 09 25 TAT263 SAUVEGARDE DU PROGRAMME SAUVE INTERROGATION ITINERAIRE MARSEILLE LONDRES HD HA 00 00 09 30 Voici les r ponses fournies par l ordinateur PLAN DE VOL ENTRE MARSEILLE ET LONDRES HORATRE DEPART 06 15 HORAIRE ARRIVEE 08 20 VOLS IT100 AF210 PLAN DE VOL ENTRE MARSEILLE ET LONDRES HORAIRE DEPART 07 45 HORATRE ARRIVEE 09 25 VOLS ITi15 TAT263 4 4 R alisation de l interpr te Le systeme de r solution dans lequel le non d terminisme est g r par backtra cking est
17. La naissance de Prolog Alain Colmerauer et Philippe Roussel Juillet 1992 Table des mati res La chronologie des faits 1 1 Ann e 1971 les premiers travaux 1 2 Ann e 1972 l application qui cr e Prolog 1 3 Ann e 1973 le Prolog d finitif wii aie See ae ee Ede ee ek 1 4 Ann e 1974 et 1975 la diffusion de Prolog Un anc tre de Prolog les syst mes Q 2 1 Unification unidirectionnelle 2 2 Strat gie d application des r gles 29 a FOS DONN e stark Gods A Se we WB hse ee te ban ke Le Prolog pr liminaire 3 1 Choix de la m thode de r solution 3 2 Caract ristiques du Prolog pr liminaire 3 3 R alisation du Prolog pr liminaire Le Prolog d finitif 4 1 Strat gie de r solution rc a a es AP eee 4 2 Syntaxe et primitives A A a 4 3 Un exemple de programme es e w ak w 4444 44 R alisation de l interpr te Appendice 5 1 Le programme de fr re et s ur 5 2 Le programme des repas kre ua a Se ao an da bee dr 5 3 Le programme des repas quilibr s 5 4 Le programme de l ajout de listes 5 5 Le programme des mutants avec des parenth ses 5 6 Le programme des mutants 19 19 20 22 23 23 26 28 31 31 33 34 37 Avant propos Pr
18. ance naturel le these de 3i me cycle Groupe Intelligence Artificielle Facult des Sciences de Luminy Universit Aix Marseille II France F vrier 1974 Kanoui Henry Application de la d monstration automatique aux manipula tions alg briques et l int gration formelle sur ordinateur th se de 3i me cycle Groupe Intelligence Artificielle Facult des Sciences de Luminy Uni versit Aix Marseille II France Octobre 1973 Kanoui Henry Some aspects of Symbolic Integration via Predicate Logic Pro gramming ACM SIGSAM Bulletin 1976 Kowalski Robert A et D Kuehner Linear resolution with selection function memo 78 University of Edinburgh School of Artificial Intelligence 1971 Also in Artificial Intelligence Vol 2 pp 227 60 1971 Kowalski Robert A Predicate Logic as Programming Language memo 70 University of Edimburgh School of Artificial Intelligence November 1973 Also in Proceedings of IFIP 1974 North Holland Publishing Company Am sterdam pp 569 574 1974 Kowalski Robert A and Maarten van Emden The semantics of predicate logic as programming language memo 78 University of Edinburgh School of Artificial Intelligence 1974 Aussi dans JACM 22 1976 pages 733 a 742 Kowalski Robert A The early history of logic programming CACM vol 31 no 1 pp 38 43 1988 Loveland D W Automated theorem proving A quarter century review Am Math Soc 29 pages 1 a 42 1984 Luckam D and N J Nilson Extrac
19. apitre 1 La chronologie des faits Au d but de juillet 1970 Robert Pasero et Philippe arrivent a Montr al Ils sont invit s par Alain alors professeur assistant d informatique l Universit de Montr al et responsable du projet de traduction automatique TAUM Tous sont un tournant de leurs carri res Robert et Philippe ont 25 ans et viennent juste d tre nomm s assistants en informatique a la nouvelle Facult des sciences de Luminy Alain a 29 ans et s appr te a rentrer en France apr s un s jour de 3 ans au Canada Durant leurs deux mois de s jour Montr al Robert et Philippe se familia risent avec le traitement informatique des langues naturelles ils programment des analyseur context free non d terministes en Algol 60 et un g n rateur de pa raphrases fran aises avec les syst mes Q le langage de programmation qu Alain avait d velopp pour le projet de traduction voir deuxi me partie Parall lement Jean Trudel chercheur canadien inscrit en th se de doctorat avec Alain poursuit ses travaux sur la d monstration automatique Son article de r f rence est celui de Alan Robinson 37 sur le principe de r solution C est un article difficile a comprendre mais Jean a l avantage d avoir suivi un cours de lo gique avec Martin Davis a New York Il a maintenant d j crit un d monstrateur complet dans lequel l unification est programm e dans un style moderne tous les calculs consistent modifier des poin
20. bjectifs assign s utiliser une strat gie simple pr visible et contr lable par le programmeur permettant de donner tout pr dicat extra logique comme les entr es sorties une d finition op rationnelle 32 disposer d un interpr te capable de faire des d ductions dont les profondeurs pouvaient tre de mille ou m me de dizaines de mille chose totalement impensable dans les syst mes d ductifs existant a l poque 4 2 Syntaxe et primitives Dans l ensemble la syntaxe retenue est la m me que celle de la version pr liminaire Sur le plan lexical la syntaxe des identificateurs est proche de celle de la plupart des langages qui l poque n utilisaient pas les lettres minuscules les claviers et syst mes d exploitation ne le permettant pas syst matiquement Il faut noter que parmi les primitives de base traitant des probl mes de morphologie une seule d entre elles univ sert tout la fois cr er dynamiquement un atome partir d une suite de caract res construire un objet structur partir de ses l ments ou au contraire effectuer les op rations inverses de d composition Cette primitive devient un des outils de base servant la cr ation dynamique de programmes ainsi qu a la manipulation d objets dont les structures ne sont pas connue avant l ex cution du programme La possibilit laiss e l usager de d finir ses propres op rateurs unaires et binaires par l emploi de
21. chniques de r solution de probl mes que nous avions tudi s figuraient entre autres celui de D Luckham 30 et N J Nilson celui de J L Darlington 15 et celui de Cordell Green 20 Cette tude les essais de Jean Trudel et Robert Pasero qui utilisaient les ver sions 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 a 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 constam ment 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 connait 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 L
22. de syntaxe en Prolog m me mais l exp rience manquait encore sur ce sujet l objet de la premi re application tant de d gager les principes m me de l analyse syntaxique en programmation logique 29 30 Chapitre 4 Le Prolog d finitif Ayant longuement d crit jusqu a maintenant les deux anc tres il est temps de donner la fiche signal tique du Prolog d finitif de 1973 Notre souci majeur apr s la version pr liminaire est de renforcer l aspect langage de programmation de Prolog en minimisant les concepts et en am liorant ses fonctionnalit s interactives dans la gestion des programmes Prolog devient un langage bas sur le seul principe de r solution et sur la mise disposition d un ensemble de de pr dicats proc dures pr d finis permettant de tout faire dans le langage lui m me Cet ensemble est concu comme un ensemble minimal permettant de cr er et modifier des programmes en m moire lire des programmes source les analyser et les charger en m moire interpr ter dynamiquement des requ tes ayant une structure analogue aux autres l ments du langage acc der dynamiquement a la structure et aux l ments d une d duction contr ler l ex cution d un programme le plus simplement possible 4 1 Strat gie de r solution L exp rience de la premi re version nous am ne a consid rer une version sim plifi e de la strat gie de r solution Ce choix nous est dict par les exp rie
23. diante l installe a l Universit de Montr al Michel Van Cane ghem l installe a PIRIA a Paris avant de venir travailler chez nous Enfin Maurice Bruynooghe apr s un s jour de trois mois a Marseille octobre a d cembre 75 l emporte Leuven Belgique En fait comme nous l a fait remarquer David Warren Prolog s est peut tre surtout diffus par l interm diaire de personnes qui s y sont int ress es et qui en ont pris une copie soit directement de Marseille soit d un site interm diaire comme Edinburgh Ainsi Prolog n a pas tellement t distribu il s est chapp et s est multipli Pendant l ann e 1975 toute l quipe r alise un portage de l interpr te sur un mini ordinateur de 16 bits le T 1600 de la compagnie francaise T l m canique La machine ne dispose que de 64K octets et il faut crire une gestion de m moire virtuelle de toute pi ce Pierre Basso s en occupe et gagne aussi le concours de la s quence d instructions la plus courte qui effectue un adressage sur 32 bits tout en testant le d faut de page Chaque membre du laboratoire recoit alors deux pages de Fortran a traduire en langage machine On rassemble tous les bouts de programme traduits et cela marche Apr s 5 ans nous disposons enfin d une machine bien a nous sur laquelle notre cher Prolog fonctionne lentement mais fonctionne 18 Chapitre 2 Un anc tre de Prolog les syst mes Q L histoire de la naissance de Prolog s arr te donc
24. e poss dait deux qualit s pour ainsi dire uniques cette poque et essentielles nos travaux celle de permettre un programmeur de disposer d une m moire virtuelle de 1Mo s il le d sirait nous n avions droit qu a 750 Ko et celle de permettre l criture de programmes inter actifs Ce fut donc sur une seule console fonctionnant 300 bauds que fut r alis non seulement l interpr te mais galement le syst me de questions r ponses lui m me Le choix d Algol W s tait impos par le fait qu il tait le seul langage de haut niveau dont nous disposions qui permettait la cr ation dynamique d objets structur s tout en tant muni d une r cup ration de m moire L implantation de la r solution tait bas e sur un codage des clauses sous forme de structures entre point es avec recopie anticip e de chaque r gle utilis e dans une d duction le non d terminisme tant g r par une pile de backtracking et les substitutions effectu es uniquement par cr ation de cha nes de pointeurs Cette approche permettait d viter les copies de termes lors des unifications et donc am liorait grandement les temps de calculs et la place m moire utilis e 28 L analyseur des clauses tait crit lui aussi en Algol W les atomes tant g r s par une technique classique de hash code Cet analyseur constituait une partie non n gligeable du syst me ce qui conforta Alain dans son d sir de r soudre ces probl mes
25. e alors une r ponse est la contrainte limit e aux variables interrog es Sinon choisir une r gle dont le membre gauche l appelant a pour pr dicat le m me que celui du premier litt ral l appel de la question courante et renommer ses variable 3 La contrainte courante est gale appelant appel U contrainte 6 R soudre la contrainte c est dire moyennant les trois transformations d crites ci dessous la mettre sous l une des formes a zi tilez do ti 23 t tn til les x tant des variables et t x tant un terme contenant la variable xj Cette contrainte est insoluble est un cycle b f s1 5m glfi tn avec f et g des symboles fonctionnels diff rents et les s et t des termes quelconques Cette contrainte est inso luble c fai t1 Tn tn les x tant des variables toutes diff rentes les t des termes quelconque et le syst me ne contenant pas de cycle Cette contrainte est soluble Si la contrainte est insoluble alors s arr ter Sinon consid rer la question comme la question dans laquelle on a remplac l appelant par la queue de r gle Aller l tape 2 Ces transformations sont 1 2 3 t x x t avec x une variable et t un terme F s1 58n f h tn gt 81 ti Sn tn avec f un symbole fonctionnel et les s et t des termes quelconque insoluble U C insoluble o C est une contrainte quelconq
26. e de phrase ou une manipulation formelle de ce genre Par exemple la suite AtA B B C cC A A B B E C gt gt bb et l application des 4 r gles A B C gt 5 A S X C gt 5 X C gt C X B B gt B X 20 produit le graphe 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 francais 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 francais et 9 de la morphologie fran aise 38 Signalons le cot r versible des syst me Q Le signe de r criture que nous avons not gt 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
27. en entr e et 17 r gles de syst me Q en sortie La partie raisonnement est r alis e par l un des d monstrateurs de Philippe Il est alors possible d avoir la conversation 10 suivante avec l ordinateur Utilisateur Les chats tuent les souris Minou est un chat qui n aime pas les souris qui mangent du fromage Miquette est une souris qui mange du fromage Max n est pas une souris Que fait Minou Machine Le Minou ne aime pas les souris qui mangent le fromage Le Minou tue les souris Utilisateur Qui est un chat Machine Le Minou Utilisateur Qu est ce que mange Miquette Machine Le fromage Utilisateur Qui n aime pas les souris qui mangent du fromage Machine Le Minou Utilisateur Qu est ce que mange Minou Machine Ce que mange les chats qui ne aiment pas les souris qui mangent le fromage Les formules logiques cr es font intervenir des constantes qui repr sentent des l ments Minou Miquette Max LeFromage des constantes qui repr sentent des ensembles LesChats LesSouris LesSourisQuiMangentDuFromage LesChatsQuiNaimentPasLesQuiMangentDuFromage des constantes qui repr sentent des relations binaires portant sur des ensembles Tuent NaimePas Mange un symbole fonctionnel d arit 1 et deux symboles relationnels d arit 2 et 3 Le Dans Vrai 11 Un terme de la forme Le a repr sente l ensemble constitu du seul l ment a Une formule de la forme Dans z y exprime que l ensemble x est inclus
28. entendu Lo et L sont des litt raux compl mentaires unifiables et la substitution la plus g n rale qui les unifie Un exemple est donn plus tard La raison premi re du choix de cette technique de r solution lin aire avec ordre de s lection pr d fini des litt raux tait sa simplicit et le fait que nous pouvions produire des clauses logiquement d ductibles du programme ce qui garantissait donc d une certaine facon la validit des r sultats produits Nous nous tions large ment inspir pour cela de la SL r solution de Robert Kowalski que Philippe avait implant pour sa th se sur l galit formelle Cependant malgr son fonctionne ment en pile analogue a l appel de proc dures des langages classiques nous avions constat que cette m thode introduisait des calculs certes n cessaires dans le cas g n ral mais inutiles pour la plupart de nos exemples C est donc cette version ex tr mement simplifi e de SL Resolution que nous venons de d crire formellement qui fut adopt e et qui continue d tre la base de tous les Prologs Le choix concernant le traitement du non d terminisme fut li a des probl mes d efficacit La programmation par Philippe d un certain nombre de m thodes avait montr qu un des probl mes cruciaux tait celui de l explosion combinatoire et donc du manque de m moire Le backtracking pour la gestion du non d terminisme fut rapidement adopt plut t qu un syst me de gestion de plusi
29. es ainsi que l encha ne ment entre programmes taient sp cifi s dans un langage de commandes agissant sur des ensembles de clauses lecture copie criture fusion d monstration etc Ce langage sans instruction de contr le ne permettait de d finir que des enchai nements d finis statiquement mais il avait comme vertu de traiter uniform ment les communications travers la notion d ensemble de clauses Soulignons que d j dans cette premi re version figurait l valuation par n cessit ou co routin e si l on pr f re de certains pr dicats en l occurrence dif et boum Le pr dicat dif fut abandonn dans la version suivante mais est r apparu dans des Prologs modernes Les seuls op rateurs de contr le taient plac s en fin de clauses comme signes de ponctuation et avaient pour effet de proc der des coupures dans l espace de recherche Le signe effectuait une coupure apr s la t te de la clause effectuait une coupure apr s l ex cution de toute la r gle effectuait une coupure apr s production d au moins une r ponse tait sans effet Ces op rateurs extra logiques taient suffisamment exotiques pour poser pro bl me leurs usagers Ils furent donc abandonn s par la suite Curieusement cette ponctuation avait t introduite par Alain en souvenir des r gles de transforma tions optionnelles et obligatoires du linguiste Noam Chomsky 8 Sur le plan de la s
30. es de clauses z1 n pour obte nir l ensemble de clauses y demontrer x y z lance une ex cution le programme tant x l ensemble des r solvantes de d part tant y et l ensemble des r ponses tant z ecrire x imprime l ensemble x de clauses 27 Le systeme de communication homme machine fonctionnait en quatre phases et faisait intervenir 4 programmes c est dire 4 ensembles de clauses C1 pour analyser un texte T0 et produire une structure profonde T1 C2 pour retrouver dans T1 les ant c dents des pronoms et produire une forme logique T2 C3 pour d composer la formule logique T2 en un ensemble T3 d informations l mentaires CZ pour faire des d ductions partir de T3 et produire les r ponses T4 en fran ais La suite des commandes tait donc DEMONTRER C1 TO T1 DEMONTRER C2 T1 T2 DEMONTRER C3 T2 T3 DEMONTRER C4 T3 T4 o TO le texte francais traiter et T 4 les r ponses produites taient repr sent es par des faits l mentaires portant sur des listes de caracteres 3 3 R alisation du Prolog pr liminaire Le centre de calcul localis Luminy ayant t d plac l interpr te fut r a lis par Philippe en Algol W sur la machine IBM 360 67 du Centre de calcul de l Universit de Grenoble machine munie du syst me d exploitation CP CMS bas sur le concept de machines virtuelles Cette machine laquelle nous tions connect s par ligne t l phonique sp cialis
31. es 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 la 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 3 1 Choix de la m thode de r solution 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 similitudes 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 23 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 te
32. es 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 ponses 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 a 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 ou 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 R gle d initialisation de la d duction question Li Lm Ri Ra resolvante L4 Lm Ri Rn 24 R gle de d duction de base resolvante LoL1 Lm R1 Ra clause choisie LoL Liy Ri Ry r solvante o L 0 L o L1 0 Lm o R 0 Ri o R1 0 Rn R gle de fin de d duction r solvante Ri R r ponse R R o bien
33. es possibles R Q S T P S QCR T P T Q R S P La notion d unification est donc d ja 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 2 2 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 11 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 sen ter 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 corres pondre une analyse une synth s
34. eurs branches de calcul r sidant simultan ment en m moire syst me qui aurait eu pour effet d augmenter consid rablement la taille de la m moire n cessaire a l ex cution des d ductions Alain avait une pr dilection pour cette m thode introduite par Robert Floyd 19 pour traiter les langages non d terministes et l enseignait a tous ses l ves L utilisation du backtracking amenait certes a la perte de la compl tude dans le cas de d ductions comportant des branches infinies mais nous jugions que compte tenu de la simplicit de la strat gie de d duction traitement des litt raux de gauche a droite et choix des clauses dans l ordre ou elles taient crites c tait au programmeur a veiller ce que l ex cution de son programme se termine 25 3 2 Caract ristiques du Prolog pr liminaire Outre le m canisme de d duction dont nous avons parl un certain nombre de pr dicats pr d finis taient rajout s au syst me au fur et mesure des be soins d Alain et de Robert Pasero des pr dicats pour tracer une ex cution copy pour copier un terme boum pour d composer un identificateur en une liste de caract res ou pour le composer dif pour traiter l galit formelle de la th se de Philippe Il est noter que nous nous refusions inclure des pr dicats d entr e sortie dans cette liste car consid r s comme trop loign s de la logique Ces entr es sorties la sp cification des r solvantes initial
35. ffusion de Fortran sur l ensemble des machines de l poque et sur le fait que la machine notre disposition n accepte pas d autres langages adapt s cette t che Nous esp rons ainsi disposer d un syst me portable pr vision qui se r v lera exacte G rard Battani 1 et Henri Meloni sous la supervision de Philippe r alisent l interpr te proprement dit entre juin 1973 et octobre 1973 sur un CII 10070 variante du SIGMA 7 tandis que Ren Bazzoli est charg d crire le superviseur dans le langage Prolog lui m me sous la direction d Alain L ensemble est constitu 38 d environ 2000 instructions sensiblement de la m me taille que le programme Algol W de la version initiale La machine est dot e d un syst me d exploitation par lots batch sans pos sibilit d interactions a travers un terminal Donn es et programmes sont donc introduits sur cartes perfor es On mesure la performance de ces jeunes cher cheurs pour r aliser un syst me aussi complexe que celui la dans un tel contexte et dans un d lai aussi court en sachant qu aucun d entre eux ne connaissait For tran Cet interpr te est mis au point de fa on d finitive en d cembre 1973 par G rard Battani et Henry M loni apr s un portage sur la machine IBM 360 67 de Grenoble et donc dans des conditions d exploitation plus raisonnables Philippe crit le manuel de r f rence et d utilisation de ce nouveau Prolog seulement deux ans plus tard 36 39
36. gar dant les d clarations d op rateurs infix s en Prolog mais en lui adjoignant un compilateur de grammaires dites de m tamorphoses Cette fois ci contrai rement a Ren Bazzoli il utilise un analyseur top down pour lire les r gles Prolog Il s agit d un bon exercice de m ta programmation Plus tard David War ren inclura de telles r gles de grammaires dans sa version compil e de Prolog 40 et avec Fernando Pereira rebaptisera definite clauses grammars une variante simplifi e des grammaires de m tamorphoses 34 Les grammaires de m tamorphoses permettent d crire directement des r gles de grammaire param tr es comme on avait coutume de les crire en syst me Q Le superviseur compile ces r gles en des clauses Prolog efficaces en ajoutant deux param tres suppl men 17 taires Pour montrer l efficacit et l expressivit des grammaires de m tamorphoses Alain crit un petit compilateur modele d un langage style Algol vers un langage machine imaginaire et un syst me complet de dialogue homme machine en fran cais avec d ductions automatiques Tout ce travail avec une justification th orique des grammaires de m tamorphose est publi dans 14 G rard Battani et Henry Meloni sont tr s sollicit s pour diffuser Prolog Il l envoient Budapest Varsovie Toronto Waterloo Canada et se d placent Edinburgh pour aider David Warren a mieux l installer sur un PDP 10 H l ne Le Gloan une ex tu
37. iversity Press New York pages 101 a 116 1972 Chastellier de Guy et Alain Colmerauer W Grammar Proccedings of the ACM Congress San Francisco Aout ACM New York pages 511 a 518 1969 Chomsky Noam Aspects of the Theory of Syntax MIT Press Cambridge 1965 Cohen Jacques A view of the origins and development of Prolog Commun ACM 31 1 pages 26 a 36 janvier 1888 57 10 11 12 13 re 14 E 15 16 17 18 19 20 21 Colmerauer Alain Total precedence relations J ACM 17 1 pp 14 30 Jan vier 1970 Colmerauer Alain Les syst mes q ou un formalisme pour analyser et synth tiser des phrases sur ordinateur Internal publication 43 D partement d in formatique de l Universit de Montr al Septembre 1970 Colmerauer Alain Fernand Didier Robert Pasero Philippe Roussel Jean Trudel R pondre Internal publication Groupe Intelligence Artificielle Fa cult des Sciences de Luminy Universit Aix Marseille II France Mai 1971 Cette publication est un listing avec des annotations ccrits a la main Colmerauer Alain Henry Kanoui Robert Pasero et Philippe Roussel Un syst me de communication en francais rapport pr liminaire de fin de contrat IRIA Groupe Intelligence Artificielle Facult des Sciences de Luminy Uni versit Aix Marseille II France Octobre 1972 Colmerauer Alain Les grammaires de m tamorphose publication interne Groupe
38. l ajout de listes Maintenant quelque chose de plus compliqu 48 Nous allons travailler sur des listes Voici quelques exemples de listes W W nul JENN EN a W c nul Pa b W YON c nul w a w b w c nul w c nul nul Nous introduisons la relation ternaire d ajout ajout w W W YE IM JA W W c nul a W EN b nul b W FA c nul ajout w a w b nul w c nul w a w b w c nul Elle se programme ainsi dans le cas g n ral ajout nul Y Y ajout w A X Y w A Z ajout X Y Z Voici une premi re question ajout w a w b nul w c nul Z Z w a w b w c nul et une deuxi me question plus subtile ajout X Y w a nul X nul Y w a nul X w a nul Y nul 49 Int ressons nous au d tail de l ex cution contrainte vide question ajout X Y w a nul r gle ajout nul Y1 Y1 contrainte tajout X Y w a nul ajout nul Y1 Y1 U vide X nul Y Y1 Yi w a nul question fin X nul Y w a nul r gle ajout w A1 X1 Y1 w 41 Z1 ajout X1 Y1 Z1 contrainte tajout X Y w a nul ajout w A1 X1 Y1 w A1 Z1 Uvide X w A1 X1 Y Y1 A a Zi nul question ajout X1 Y1 Z1 r gle ajout nul Y2 Y2 contrainte tajout X1 Y1 Z1 ajout nul Y2 Y2 U X w A1 X1 Y Y1 Al a Zi nul X w A1 X1 Y Y1 Ai a Zi nul Xi nul Yi Y2 Y2 Z1 question fin X w a nul Y nul r gle ajout w A2 X2
39. l w i w g wla w t wlo w r w t w u wle nul Z w c w a w r w i w b w o w u w q w u w r s nul1 Z wc w a u r w i w b w o w u w r w s nul Z w c w h wle w v wla w 1 w 1 w i w g w a w t w o w r nul Z w c w h w e w v w a w 1 w a w p w i w n nul Z w h w i w b wlo w u w q w u wle w t w i w m nul Z w h w i w b w o w u w r w s nul Z w l w a w p w i w n w t w a w d w e nul Z w l w a w p w i w n w t w a w d w e nul Z w v w a w c w h w e w v w a w 1l nul Z w v w a w c w h w e w v w r w e nul false 5 6 Le programme des mutants En fait les listes jouent un r le tellement important en Prolog qu il existe des notations sp ciales pour les manipuler Le symbole fonctionnel unaire w est remplac par et la constante nul par On crit ti to au lieu de tj ta et fi ta au lieu de la liste t ta lt tn D On dispose du pr dicat pr d fini atom__chars x y qui cr e l identificateur x form de la liste y de caract res ou la liste y de caracteres de l identificateur x Avec ce pr dicat pr d fini on peut enfin calculer des vrais mutants Il suffit de compl ter le programme pr c dent et de remplacer le pr dicat nonnul par nonvide et le pr dicat ajouter par adjonction mutant Zp animal Xp animal Yp atom_chars Xp X atom_chars Yp Y adjo
40. m me sch ma la place m moire n cessaire a une tape de d duction est fonction non pas des donn es mais de la clause du programme utilis e ainsi globalement la concat nation de deux listes ne mettra en oeuvre qu une quantit de m moire proportionnelle la premi re des deux listes la gestion du non d terminisme ne n cessite pas en premi re approche de r cup ration de m moire sophistiqu e mais simplement l emploi de plusieurs piles synchronis es sur le backtracking facilitant ainsi une r alisation rapide et n anmoins conome de l interpr te En ce qui concerne la repr sentation en m moire des squelettes il est d cid d utiliser une repr sentation pr fix e exactement l inverse de la notation polo naise Le syst me est compos de l interpr te proprement dit c est dire la ma chine inf rentielle munie de la biblioth que des pr dicats pr d finis d un chargeur destin lire des clauses dans une syntaxe restreinte et enfin d un superviseur crit en Prolog Ce superviseur contient entre autres un valuateur de requ tes un ana lyseur acceptant la syntaxe avec op rateurs un chargeur de clauses en m moire et la d finition d une biblioth que de pr dicats d entr e sorties de haut niveau Alain qui comme nous tous n aime gu re Fortran finit cependant par convaincre l quipe de l adopter pour programmer l interpr te Ce choix essentiel repose sur la large di
41. me une suite de noms de vols Enfin non p d finit une n gation par chec pour p et element e l s value vrai si l l ment e figure dans la liste d l ments Voici donc le programme final avec ses donn es et le lancement d une ex cution OPERATEURS INFIXES AJOP 1 XIX IX AJOP 2 CXIX IX PREDICAT USAGER ITINERAIRE DEP ARR HDEP HARR HMINDEP HMAXARR ROUTE DEP ARR HDEP HARR PLAN VDEP NIL HMINDEP HMAXARR SORM LIGNE SORM PLAN DE VOL ENTRE SORT DEP SORM ET SORT ARR LIGNE SORM a LIGNE SORM HORAIRE DEPART SORT HDEP LIGNE SORM HORAIRE ARRIVEE SORT HARR LIGNE SORM VOLS ECRIREPLAN PLAN LIGNE LIGNE 39 PREDICATS DE CALCUL ROUTE DEP ARR HDEP HARR NOMVOL NIL VISITES HMINDEP HMAXARR VOL DEP ARR HDEP HARR NOMVOL PRECEDEHORATRES HMINDEP HDEP PRECEDEHORATRES HARR HMAXARR ROUTE DEP ARR HDEP HARR PLAN VISITES HMINDEP HMAXARR VOL DEP ESCALE HDEP HARRESCALE NOMVOL PRECEDEHORAIRES HMINDEP HDEP PLUSHORATRES HARRESCALE 00 15 HMINDEPESCALE PRECEDEHORAIRES HMINDEPESCALE HMAXARR NON ELEMENT ESCALE VISITES ROUTE ESC ARR HDEPESCALE HARR NOMVOL PLAN ESCALE VISITES HMINDEPESCALE HMAXARR PRECEDEHOR
42. mod le th orique existant Ce sont ces modifications si souvent critiqu es qui ont assur la viabilit et donc le succ s de Prolog Le m rite de Robert Kowalski a t de d gager la notion de clause de Horn qui a l gitim notre principale h r sie une strat gie de d monstration lin aire avec backtracking et des unifications uniquement sur les t tes de clauses Le langage Prolog est si simple que l on a l impression que t t ou tard quelqu un devait le d couvrir Pourquoi nous plut t que d autres Tout d abord Alain tait bien arm pour cr er un langage de programmation Il appartenait a la premi re g n ration de docteurs d informatique en France et sa sp cialit tait la th orie des langages Il avait accumul une pr cieuse exp rience en concevant un premier langage de programmation les syst mes Q dans le cadre du projet de Traduction Automatique de l Universit de Montr al Ensuite notre rencontre la cr ativit de Philippe et les conditions de travail particuli res Marseille firent le reste Nous avons b n fici d une grande libert d action dans un centre scientifique nouvellement cr et sans pression ext rieure nous avons donc pu nous consacrer enti rement notre projet 99 C est sans doute pourquoi cette p riode de notre vie reste une des plus heu reuses dans nos souvenirs communs Nous avons pris plaisir l voquer pour crire ce papier tout en go tant les amande
43. n Colmerauer et Philippe Roussel sont donc pr sent s mais il est vident que bien d autres personnes ont particip a un tel projet Pour rester objectifs en racontant l histoire de la naissance de Prolog qui a d ja vingt ans maintenant nous avons repris tous les documents qui nous restaient et nous avons jou les historiens Nous avons d abord suivi la chronologie de tr s pres pour exposer les faits et d crire les acteurs de l t 70 la fin 76 Ceci constitue la premi re partie de l article Les autres parties sont plus techniques Elles sont consacr es aux trois langages de programmation qui se sont succ d s rapidement les syst mes Q concus pour la traduction automatique le Prolog pr liminaire cr en m me temps que son application et le Prolog d finitif cr ind pendamment de toute application Ce papier n est pas le premier sur l histoire de Prolog Signalons celui de Jacques Cohen 9 directement sur Prolog et celui de Robert Kowalski 28 sur la naissance de la discipline Logic Programming Il est aussi int ressant de prendre connaissance de l histoire de la d monstration automatique vue par Do nald Loveland 29 et de l existence ant rieure d un possible concurrent a Prolog 1 Il existe une version anglaise de ce papier dans un livre History of Pro gramming Languages par Thomas J Bergin et Richard G Gibson Addison WesleyPublishing Company 1996 le langage Absys vu par Elcock 17 Ch
44. nces des premiers programmeurs mais aussi par des consid rations d efficacit et par le choix de Fortran comme langage de programmation de l interpr te qui nous oblige a g rer nous m me l espace m moire Les diff rences essentielles avec l ancienne version sont les suivantes plus d valuation retard e dif boum remplacement du pr dicat boum par le pr dicat plus g n ral univ plus de m canisme de g n ration de clauses comme r sultat d une d duction 31 mais les fonctions assert et retract alors not es ajout et supp un seul op rateur pour le contr le du backtracking l op ration de coupure de l espace de recherche not e alors le concept d appel calcul meta call permettant d utiliser une variable a la place d un litt ral l acc s aux litt raux anc tres eta la r solvante en cours consid r e comme un terme pour les programmeurs d sireux de d finir leurs propres m ca nismes de r solution a l aide des pr dicats valuables ancetre et tat qui ont disparu des Prologs actuels Le backtracking et le fait d ordonner chaque ensemble de clauses d finissant un pr dicat sont les l ments de base conserv s comme technique de gestion du non d terminisme La version pr liminaire de Prolog nous avait donn grande satisfaction sur ce point La r duction par Alain une seule primitive le cut de la gestion du contr le du backtracking au lieu des tr
45. nction A B X adjonction B C Y nonvide B nonvide A adjonction X C Z atom_chars Zp Z nonvide AIX adjonction Y Y adjonction A X Y AIZ adjonction X Y Z animal alligator animal bouquetin animal caribou animal cheval animal chevre animal hibou animal lapin animal ours animal pintade animal tortue animal vache 92 A la question quelles sont les mutants on obtient mutant X alligatortue caribouquetin caribours chevalligator chevalapin hibouquetin hibours lapintade vacheval PI P PA P P P P P PM vachevre false 53 54 Conclusion Apr s toutes ces p rip ties et tous ces d tails techniques il serait int ressant de prendre du recul et de situer la naissance de Prolog dans une perspective plus vaste L article de Alan Robinson publi en janvier 1965 A machine oriented logic ba sed on the resolution principle contenait en germe le langage Prolog Cet article a t a la base d un courant important de travaux sur la d monstration automatique et nul doute que Prolog est essentiellement un d monstrateur de th or mes a la Robinson Notre contribution a t de transformer ce d monstrateur en un langage de programmation Pour cela nous n avons pas eu peur d introduire des m canismes et des restrictions purement informatiques qui taient des h r sies pour le
46. nous rend perplexe C est cette occasion que nous prenons connaissance de l existence du langage de program mation Planner de Carl Hewitt 21 Le manque de formalisation de ce langage notre m connaissance de Lisp et surtout le fait que nous tenons tout prix a la logique tout cela fait que ces travaux eurent peu d influence sur la suite de nos recherches 1 2 Ann e 1972 l application qui cr e Prolog L ann e 72 est la plus fertile Tout d abord en f vrier l quipe obtient une subvention de 122 O00FF l poque environ 20 000 de l Institut de Recherche d Informatique et d Automatique une institution d pendant du minist re francais de l industrie et cela pour une dur e de 18 mois Ce contrat permet d acqu rir un terminal teletype 30 caract res par seconde et de le connecter sur l IBM 360 67 dot du merveilleux syst me d exploitation CP CMS qui g rait des machines 12 virtuelles de Universit de Grenoble au moyen d une ligne sp cialis e de 300 bauds Ce fut de loin le moyen de calcul le plus agr able dont l quipe disposa durant les trois ann es qui suivirent et tout le monde l utilisa y compris les nombreux chercheurs qui nous rendirent visite Nous avons mis plusieurs ann es ponger la dette en heures machines que nous avons ainsi accumul e Grenoble Le contrat permet enfin d engager une secr taire et un chercheur Henry Kanoui tudiant de DEA qui s occupera de la morphologie du
47. olog est n d un projet dont le but n tait pas de faire un langage de pro grammation mais de traiter les langages naturels en l occurrence le francais Ce projet a donn naissance un Prolog pr liminaire a la fin 1971 et un Prolog plus d finitif la fin de l ann e 1972 Cet article relate l histoire de ce projet d crit en d tail la version pr liminaire de Prolog puis sa version d finitive Les auteurs ont aussi jug bon de d crire les syst mes Q un langage qui a jou un r le important dans la gen se de Prolog Nous avons aussi ajout un appendice avec six exemples de programmes pour se familiser avec le Prolog actuel Nous sommes en 2014 Introduction Il est de notori t publique que le nom de Prolog a t cr Marseille en 1972 C est Philippe Roussel qui l a choisi comme abr viation de PROgrammation en LOGique pour d signer l outil informatique concu pour implanter un syst me de communication homme machine en langage naturel On peut dire que Prolog a t le fruit d un mariage r ussi entre le traitement du langage naturel et la d monstration automatique L utilisation directe du francais pour raisonner et dialoguer avec un ordinateur tait un r ve un peu fou c tait le projet labor d s l t 70 par Alain Colmerauer qui avait une certaine exp rience dans le traitement informatique des langages naturels et qui souhaitait largir sa recherche Les deux auteurs de cet article Alai
48. op nombreux concepts de la premi re version simplifie extraordinairement le langage Il devient possible au programmeur non seulement de r duire la taille de son espace de recherche par des crit res purement pragmatiques mais aussi de r aliser un traitement de la n gation certes simplifi et r ducteur dans sa s mantique mais extr mement utile pour la programmation la plus courante D autre part Philippe apr s le s joura Edinburgh a en t te les bases d une architecture extr mement simple a r aliser du point de vue de la gestion de la m moire et beaucoup plus efficace en temps et en espace surtout si l on conserve la gestion du non d terminisme par backtracking Enfin toutes les premi res exp riences de programmation ont montr que cette technique a permis a nos usagers d int grer assez facilement le non d terminisme comme une dimension additionnelle au contr le de l ex cution de pr dicats En ce qui concerne le traitement du ou implicite entre litt raux a l int rieur d une clause la s quentialit s impose l encore comme l interpr tation la plus naturelle de cet op rateur puisque formellement l ordre d ex cution des litt raux n affectait en rien l ensemble des r sultats obtenus modulo l viction de branches infinies comme l avait prouv Robert Kowalski a propos de SL resolution En r sum ces deux choix concernant le traitement du et et du ou se justifient pleinement par les o
49. ories artichautsMelanie 147 calories barAuxAlgues 302 calories cressonDeufPoche 202 calories fraisesChantilly 398 calories grilladeDeBoeuf 530 calories loupAuFenouile 254 calories melonEnSurprise 122 calories pouletAuTilleul 400 calories sorbetAuxPoires 223 calories truffesSousLeSel 212 On calcule tous les repas quilibr s 46 repasEquilibre E E artichautsMelanie F artichautsMelanie F artichautsMelanie F artichautsMelanie F artichautsMelanie E artichautsMelanie E artichautsMelanie E artichautsMelanie E cressonDeufPoche E cressonDeufPoche E cressonDeufPoche E cressonDeufPoche E cressonDeufPoche E truffesSousLeSel E truffesSousLeSel E truffesSousLeSel E truffesSousLeSel E truffesSousLeSel P D P grilladeDeBoeuf D melonEnSurprise P pouletAuTilleul D melonEnSurprise P pouletAuTilleul D sorbetAuxPoires P barAuxAlgues D melonEnSurprise P barAuxAlgues D sorbetAuxPoires P loupAuFenouile D fraisesChantilly P loupAuFenouile D melonEnSurprise P loupAuFenouile D sorbetAuxPoires P pouletAuTilleul D melonEnSurprise P barAuxAlgues D melonEnSurprise P barAuxAlgues D sorbetAuxPoires P loupAuFenouile D melonEnSurprise P loupAuFenouile D sorbetAuxPoires P pouletAuTilleul D melonEnSurprise P barAuxAlgues D melonEnSurprise P barAuxAlgues D sorbetAuxPoires P loupAuFenouile D melonEnSurprise P loupAuFenouile D sorbetAuxPoires 47 5 4 Le programme de
50. r Tout psychiatre est une personne Chaque personne qu il analyse est malade Jacques est un psychiatre a Marseille Est ce que Jacques est une personne O est Jacques Est ce que Jacques est malade Machine Oui A Marseille Je ne sais pas Le texte original suivi des trois r ponses tait en fait Utilisateur TOUT PSYCHIATRE EST UNE PERSONNE CHAQUE PERSONNE QU IL ANALYSE EST MALADE JACQUES EST UN PSYCHIATRE A MARSEILLE EST CE QUE JACQUES EST UNE PERSONNE DU EST JACQUES EST CE QUE JACQUES EST MALADE Machine OUI A MARSEILLE JE NE SAIS PAS Toutes les inf rences sont faites a partir des pronoms il ils elle des articles le les un tout et des fonctions sujet et compl ment avec ou sans pr positions de a En fait le syst me ne connaissait que les pronoms les articles et les pr positions le vocabulaire tait cod en 164 clauses il reconnaissait les noms propres par l ast risque obligatoire qui devaient les pr c der et les verbes et les noms communs par les 104 clauses de morphologie g n rale du francais Pendant le mois de novembre nous entreprenons avec Robert Pasero une vaste tourn e des laboratoires de recherche am ricains apr s une visite d Edinburgh Nous emportons un rapport pr liminaire sur notre syst me de communication en langue naturelle et sur notre tout premier Prolog Nous laisserons des copies de ce rapport un peu partout Jacques Cohen nous accueille a Bos
51. s de Horn Robert Kowalski 26 montrera ce point et avec Maarten van Emden donnera la s mantique moderne par point fixe de la programmation avec clauses de Horn 27 Pendant l automne 1972 le premier syst me Prolog est implant par Philippe en Algol W le langage de Niklaus Wirth Parall lement Alain et Robert Pasero r alisent le syst me de communication homme machine en fran ais tant d sir 13 Une interaction constante a lieu entre Philippe qui implante Prolog et Alain et Robert Pasero qui programment dans un langage qui se cr e au fur et mesure Cette version pr liminaire de Prolog est d crite en d tails dans la troisi me partie de ce papier C est cette poque qu est choisi galement le nom d finitif du langage nom sugg r par Jacqueline l pouse de Philippe a partir de mots cl s qui lui avaient t fournis Le syst me de communication homme machine est le premier programme Pro log cons quent qui fut jamais crit 13 Il comporte 610 clauses Alain en a crit 334 essentiellement la partie analyse Robert Pasero 162 la partie purement d ductive et Henry Kanoui a crit en 104 clauses une morphologie du francais qui permet de faire le lien entre le singulier et le pluriel de tous les noms communs et de tous les verbes m me irr guliers la troisi me personne du pr sent Voici un exemple de texte soumis au syst me de communication homme machine et les 14 r ponses en 1972 Utilisateu
52. s fraiches autour d un Martini dry 96 Bibliographie 1 Battani G rard et Henry M loni Interpr teur du langage PROLOG rapport de DEA Groupe Intelligence Artificielle Facult des Sciences de Luminy Universit Aix Marseille II France 1973 Battani G rard Mise en oeuvre des contraintes phonologiques syntaxiques et s mantiques dans un syst me de compr hension automatique de la parole th se de 3i me cycle Groupe Intelligence Artificielle Facult des Sciences de Luminy Universit Aix Marseille II France Juin 1975 Bergman Marc and Henry Kanoui Application of mechanical theorem proving to symbolic calculus Third International Colloquium on advanced Computing Methods in Theoretical Physics Marseille France Juin 1973 Bergman Marc R solution par la d monstration automatique de quelques problemes en int gration symbolique sur calculateur these de 3i me cycle Groupe Intelligence Artificielle Facult des Sciences de Luminy Universit Aix Marseille II France Octobre 1973 Bergman Marc et Henry Kanoui SYCOPHANTE syst me de calcul formel sur ordinateur rapport de fin de contrat DRET Direction des Recherches et Etudes Techniques Groupe Intelligence Artificielle Facult des Sciences de Luminy Universit Aix Marseille II France 1975 Boyer Robert S et J S Moore The sharing of Structure in Theorem Proving Programs Machine Intelligence 7 dit par B Melzer et D Michie Edinburgh Un
53. ssonDeufPoche P barAuxAlgues D sorbetAuxPoires E cresson0eufPoche P loupAuFenouile D fraisesChantilly E cressonDeufPoche P loupAuFenouile D melonEnSurprise E cressonDeufPoche P loupAuFenouile D sorbetAuxPoires E truffesSousLeSel P grilladeDeBoeuf D fraisesChantilly 45 E truffesSousLeSel P grilladeDeBoeuf D melonEnSurprise E truffesSousLeSel P grilladeDeBoeuf D sorbetAuxPoires E truffesSousLeSel P pouletAuTilleul D fraisesChantilly E truffesSousLeSel P pouletAuTilleul D melonEnSurprise E truffesSousLeSel P pouletAuTilleul D sorbetAuxPoires E truffesSousLeSel P barAuxAlgues D fraisesChantilly E truffesSousLeSel P barAuxAlgues D melonEnSurprise E truffesSousLeSel P barAuxAlgues D sorbetAuxPoires E truffesSousLeSel P loupAuFenouile D fraisesChantilly E truffesSousLeSel P loupAuFenouile D melonEnSurprise E truffesSousLeSel P loupAuFenouile D sorbetAuxPoires 5 3 Le programme des repas quilibr s Dans le Prolog il y a un certain nombre de pr dicat pr d finis Entre autres il est possible de calculer le r sultat y d une expression arithm tique sous forme fonctionnelle f x1 x par y is f x1 2 Il est aussi possible de tester si x est plus petit que v2 par 11 lt Zo Nous pouvons compl ter le programme pr c dent par repasEquilibre E P D repas E P D equilibre E P D equilibre E P D calories E X calories P Y calories D Z V is X Y Z V lt 800 cal
54. teurs 1 1 Ann e 1971 les premiers travaux Tout le monde se retrouve Marseille au d but de l ann e 1971 Alain a obtenu un poste de ma tre de conf rence en informatique et Jean Trudel a pu le suivre gr ce une bourse d Hydro Qu bec de deux ans Le projet est donc de faire des d ductions sur des textes crits en francais Le travail se r partit comme suit 9 Jean Trudel et Philippe s occupent de la partie d duction Robert Pasero et Alain de la partie langue naturelle Nous avons acc s la machine du centre de calcul de l universit de Marseille un IBM 360 44 dans nos locaux dot de 900Ko environ de m moire centrale et muni d un systeme d exploitation sans m moire virtuelle Gr ce un moniteur in teractif que Jean Trudel r alise et en utilisant la machine de nuit pour b n ficier de toute la m moire disponible l quipe peut travailler dans des conditions excep tionnelles pour l poque en France quasiment 1 Mo de m moire pour ex cuter les programmes et une conception interactive des communications entre utilisateurs et programmes a travers la console de l op rateur Jean Trudel am liore son d monstrateur puis partir du mois de mai Philippe en produit toute une s rie crits en Algol W Un syst me tr s naif de communi cations en langue naturelle est alors r alis par toute l quipe 12 Les interfaces entre les formules logiques et le francais consistent en 50 r gles de syst mes Q
55. ting information from resolution proof trees Artificial Intelligence 12 1 pages 27 54 1971 Meloni Henry Mise en uvre des contraintes phonologiques syntaxiques et s mantiques dans un systeme de compr hension automatique de la parole these de 3eme cycle Groupe Intelligence Artificielle Facult des Sciences de Luminy Universit Aix Marseille II France juin 1975 Moore J Computational Logic Structure sharing and proof of program pro perties part I and II memo 67 University of Edinburgh School of Artificial Intelligence 1974 Pasero Robert Repr sentation du francais en logique du premier ordre en vue de dialoguer avec un ordinateur these de 3 me cycle Groupe Intelligence Ar tificielle Facult des Sciences de Luminy Universit Aix Marseille II France mai 1973 59 34 35 36 iS 37 38 39 40 41 42 Pereira Fernando C and David H D Warren Definite clause grammars for language analysis Artificial Intelligence 13 pages 231 a 278 1980 Roussel Philippe D finition et traitement de l galit formelle en d monstra tion automatique th se de 3i me cycle Groupe Intelligence Artificielle Fa cult des Sciences de Luminy Universit Aix Marseille II France mai 1972 Roussel Philippe Prolog manuel de r f rence et d utilisation Groupe Intel ligence Artificielle Facult des Sciences de Luminy Universit Aix Marseille II France septembre 1975
56. ton et nous 15 introduit au MIT Nous y sommes tr s bien accueillis et nous discutons avec Minsky Charniak Hewitt et Winograd Nous rendons aussi visite a Woods a BBN Nous allons ensuite Stanford visitons le SRI le laboratoire d IA de John McCarthy rencontrons Cordell Green exposons nos travaux devant J Feldman tr s critique et passons Thanks Giving chez Robert Floyd 1 3 Ann e 1973 le Prolog d finitif Au d but de l ann e 73 plus exactement en avril notre groupe acquiert une existence officielle Le CNRS le reconna t comme quipe de recherche associ e avec l intitul Dialogue homme machine en langue naturelle et le dote d un budget de 39 000F environ 6500 pour la premi re ann e Cette somme doit tre compar e avec les 31 6880F environ 50 000 que nous obtenons en octobre de VIRIA pour renouveler le contrat Communication homme machine en langue naturelle avec d ductions automatiques pour une dur e de 2 ans et demi Les utilisateurs de la version pr liminaire de Prolog au sein du laboratoire ont maintenant suffisamment programm pour que leur exp rience serve de base une deuxi me version de Prolog version r solument orient e vers un langage de programmation et non pas simplement vers un syst me d ductif plus ou moins automatis Outre le syst me de communication en fran ais de 1972 deux autres applications sont r alis es l aide de cette version initiale de Prolog un syst
57. ue 42 Cela donne contrainte vide question freresoeur paul X r gle freresoeur X1 Z1 estfilsde X1 Y1 estfillede Z1 Y1 contrainte freresoeur paul X freresoeur X1 Z1 U vide Xi paul X Z1 question estfilsde X1 Y1 estfillede Z1 Y1 r gle estfilsde jules marguerite contrainte estfilsde X1 Y1 estfilsde jules marguerite U X1 paul X Z1 paul jules fin echec r gle estfilsde paul marguerite contrainte estfilsde X1 Y1 estfilsde paul marguerite U X1 paul X Z1 X1l paul X Z1 Yi marguerite question estfillede Z1 Y1 r gle estfillede helene marguerite contrainte estfillede Z1 Y1 estfillede helene marguerite U X1 paul X Z1 Yi marguerite X1 paul X Z1 Yi marguerite Zi helene question fin X helene r gle estfillede nicole rosalie contrainte estfillede Z1 Y1 estfillede nicole rosalie U X1 paul X Z1 Yi marguerite marguerite rosalie fin echec 43 Une autre question quel est le x qui est tel que x et H l ne sont fr re et s ur produit deux r ponses freresoeur X helene X jules X paul Ce que je ne comprends pas c est pourquoi mon fr re a deux soeurs alors que je n en ai qu une 5 2 Le programme des repas Consid rons le programme repas E P D entree E plat P dessert D plat P viande P plat P poisson P entree artichautsMelanie entree cressonDe
58. ufPoche entree truffesSousLeSel viande grilladeDeBoeuf viande pouletAuTilleul 44 poisson barAuxAlgues poisson loupAuFenouile dessert fraisesChantilly dessert melonEnSurprise dessert sorbetAuxPoires Si on demande quels sont les repas on obtient repas E P D F artichautsMelanie P grilladeDeBoeuf D fraisesChantilly EzartichautsMelanie P grilladeDeBoeuf D melonEnSurprise EzartichautsMelanie P grilladeDeBoeuf D sorbetAuxPoires F artichautsMelanie P pouletAuTilleul D fraisesChantilly E artichautsMelanie P pouletAuTilleul D melonEnSurprise E artichautsMelanie P pouletAuTilleul D sorbetAuxPoires EzartichautsMelanie P barAuxAlgues D fraisesChantilly F artichautsMelanie P barAuxAlgues D melonEnSurprise F artichautsMelanie P barAuxAlgues D sorbetAuxPoires F artichautsMelanie P loupAuFenouile D fraisesChantilly E artichautsMelanie P loupAuFenouile D melonEnSurprise E artichautsMelanie P loupAuFenouile D sorbetAuxPoires E cressonDeufPoche P grilladeDeBoeuf D fraisesChantilly E cressonDeufPoche P grilladeDeBoeuf D melonEnSurprise E cressonDeufPoche P grilladeDeBoeuf D sorbetAuxPoires E cressonDeufPoche P pouletAuTilleul D fraisesChantilly E cressonDeufPoche P pouletAuTilleul D melonEnSurprise E cressonDeufPoche P pouletAuTilleul D sorbetAuxPoires E cresson0eufPoche P barAuxAlgues D fraisesChantilly E cresson0eufPoche P barAuxAlgues D melonEnSurprise E cre
59. ujours pas comment se passer des syst mes Q pour tout ce qui concerne l analyse des langues naturelles Apr s le d part de Robert Kowalski Alain trouve enfin une facon de r aliser des analyseurs puissants A chaque symbole non terminal N de la grammaire il associe un pr dicat binaire N x y signifiant que x et y sont des mots terminaux pour lesquels le mot u d fini par x uy existe et est d rivable de N En repr sen tant x et y par des listes chaque r gle de la grammaire peut alors tre cod e par une clause ayant exactement le m me nombre de litt raux que d occurrences de symboles non terminaux Il n est jamais n cessaire de faire appel la concat na tion de liste Cette technique est connue maintenant sous le nom de technique de diff rence de listes De plus dans chaque non terminal Alain introduit des para 13 m tres suppl mentaires pour propager et calculer des informations Comme dans les syst mes Q l analyseur non seulement v rifie que la phrase est correcte mais extrait une formule repr sentant l information contenue dans celle ci Plus rien ne s oppose alors faire un syst me de communication homme machine enti rement en logique Une d cision draconienne est prise quitte tre incomplets nous choisissons une r solution lin aire avec unification uniquement entre les t tes de clauses Sans le savoir nous avons d couvert une strat gie qui est compl te lorsque l on se limite aux clause
60. yntaxe l criture des termes se faisait sous forme fonction nelle avec cependant la possibilit d introduire des op rateurs unaires ou binaires d finis par pr c dences ainsi qu un op rateur binaire infix pouvant tre repr sent par absence de signe comme un produit en math matique et fort utile dans les entr es sorties de cha nes Voici un exemple d enchainement de programmes qui produisait et crivait un ensemble de clauses d finissant les petits neveux d une personne d nomm e Marie 26 LTRE REGLES DESC X Y ENFANT xX Y DESC X Z ENFANT X Y DESC Y Z FRERESOEUR X Y ENFANT Z X ENFANT Z y DIF X Y AMEN LIRE FAITS ENFANT PAUL MARIE ENFANT PAUL PIERRE ENFANT PAUL JEAN ENFANT PIERRE ALAIN ENFANT PIERRE PHILIPPE ENFANT ALAIN SOPHIE AMEN LIRE QUESTION FRERESOEUR MARIE X DESC X Y PETITNEVEUX Y MASC xY AMEN CONCATENER LIENSDEPARENTE REGLES FAITS DEMONTRER LIENSDEPARENTE QUESTION REPONSE ECRIRE REPONSE AMEN La sortie de ce programme n est donc pas un terme mais l ensemble de clauses binaires PETITNEVEUX ALAIN MASC ALAIN PETITNEVEUX SOPHIE MASC SOPHIE PETITNEVEUX PHILIPPE MASC PHILIPPE La commande lire lit un l ensemble de clause pr c d d un nom x et se terminant par amen et lui attribue le nom z concatener y k1 n unit les ensembl

La naissance de Prolog - Colmerauer, Alain

Contents

Download Pdf Manuals

Related Search

Related Contents