Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

La naissance de Prolog juillet 1992 Alain Colmerauer Faculté des Sciences de Lu

La naissance de Prolog juillet 1992 Alain Colmerauer Faculté des Sciences de Luminy, 70 route Léon Lachamp 13288 Marseille, cedex 9, France e-mail: colmer@gia.univ-mrs.fr fax: (33) 91 26 92 75 tel: (33) 91 40 11 37 Philippe Roussel Elsa Software, Technopôle de Chateau Gombert 13013 Marseille, France e-mail: proussel@elsa.fr fax: (33) 91 05 50 09 tel: (33) 91 05 50 08 Résumé Le langage de programmation Prolog est né d'un projet, dont le but n'était pas de faire un langage de programmation mais de traiter les langages naturels, en l'occurrence le Français. Ce projet a donné naissance à un Prolog préliminaire à 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. Table des matières Introduction...................................................................................................................... 2 Partie I. L'histoire............................................................................................................. 2 Année 1971, les premiers travaux .......................................................................... 3 Année 1972, l'application qui crée Prolog .............................................................. 5 Année 1973, le vrai premier Prolog........................................................................ 8 Année 1974 et 1975, la diffusion de Prolog............................................................ 9 Partie II. Un ancêtre de Prolog, les systèmes-Q............................................................... 10 Unification unidirectionnelle................................................................................ 10 Stratégie d'application des règles.......................................................................... 11 Réalisation........................................................................................................... 13 Partie III. Le Prolog préliminaire.................................................................................... 14 Choix de la méthode de résolution, raisons .......................................................... 14 Caractéristiques du Prolog préliminaire ............................................................... 17 Réalisation du Prolog préliminaire....................................................................... 19 Partie IV. Le Prolog définitif .......................................................................................... 20 Stratégie de résolution.......................................................................................... 20 Syntaxe et Primitives ........................................................................................... 21 Un exemple de programme .................................................................................. 22 Réalisation de l'interprète..................................................................................... 26 Conclusion ..................................................................................................................... 27 Bibliographie.................................................................................................................. 28 Colmerauer et Roussel La naissance de Prolog Page 2 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 conçu 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 français 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, Alain Colmerauer et Philippe Roussel, sont donc présentés, mais il est évident que bien d'autres personnes ont participé à un tel projet. Pour rester objectifs en racontant l'histoire de la naissance de Prolog, qui a déjà 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 près, 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 programmations qui se sont succédés rapidement : les systèmes-Q conçus 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 [1988], directement sur Prolog, et celui de Robert Kowalski [1988], 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 Donald Loveland [1984] et de l'existence antérieure d'un possible concurrent à Prolog, le langage Absys vu par Elcock [1988]. Partie I. L'histoire Au début de juillet 1970, Robert Pasero et Philippe arrivent à 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) à la nouvelle Faculté des sciences de Luminy. Alain a 29 ans et s'apprête à 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 familiarisent 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 paraphrases 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). Colmerauer et Roussel La naissance de Prolog Page 3 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 [1965] sur le principe de résolution. C'est un article difficile à comprendre, mais Jean a l'avantage d'avoir suivi un cours de logique avec Martin Davis à 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 pointeurs. 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 français. Le travail se répartit comme suit : 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 localisé dans nos locaux, doté de 900Ko environ de mémoire centrale et muni d'un système d'exploitation sans mémoire virtuelle. Grâce à un moniteur interactif 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 exceptionnelles 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 à travers la console de l'opérateur. Jean Trudel améliore son démonstrateur puis, à partir du mois de mai, Phillippe en produit toute une série écrits en Algol-W. Un système très naïf de communications en langue naturelle est alors réalisé par toute l'équipe [Colmereauer, 1971]. Les interfaces entre les formules logiques et le français consistent en 50 règles de systèmes-Q 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 suivante avec l'ordinateur : Colmerauer et Roussel La naissance de Prolog Page 4 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 mangent 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, LesChatsQuiNaimentPasLesSourisQuiMangentDuFromage, 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. Un terme de la forme Le(a) représente l’ensemble constitué du seul élément a. Une formule de la forme Dans(x,y) exprime que l'ensemble x est inclus 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 : Colmerauer et Roussel La naissance de Prolog Page 5 (∀x) [Dans(x,x)], (∀x)(∀y)(∀z) [Dans(x,y)∧Dans(y,z) ⇒ Dans(x,z], (∀a)(∀b) [Dans(Le(a),Le(b)) ⇒ Dans(Le(b),Le(a))], (∀x)(∀y)(∀r)(∀x')(∀y') [Vrai(r,x,y)∧Dans(x,x')∧Dans(y,y') ⇒ Vrai(r,x',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 [Kowalski 1971]. Il 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 à Robert Kowalski il rencontre des gens passionnés par ses recherches et décidés à les mettre en application dans le traitement des langues naturelles. Avec Jean Trudel nous revoyons Bob Kowalski à l'occasion d'un congrès IJCAI en septembre 71 à Londres, où nous assistons à un exposé de Terry Winograd uploads/Ingenierie_Lourd/ histoire-prolog-colmerauer-roussel.pdf