Prolog
En 1970, Alain Colmerauer ne cherche pas à inventer un nouveau langage de programmation. Ce professeur assistant en informatique à l’Université de Montréal dirige le projet TAUM (Traduction Automatique de l’Université de Montréal) et veut simplement pousser plus loin ses recherches sur le traitement informatique des langues. Deux jeunes enseignants de 25 ans de la toute nouvelle faculté des sciences de Luminy, Robert Pasero et Philippe Roussel, le rejoignent pour deux mois. Ils découvrent les systèmes-Q, un langage que Colmerauer a développé pour son projet de traduction.
Jean Trudel, doctorant canadien sous la direction de Colmerauer, travaille sur la démonstration automatique de théorèmes. Il s’appuie sur l’article fondateur d’Alan Robinson sur le principe de résolution, publié en 1965. Il a l’avantage d’avoir suivi un cours de logique avec Martin Davis à New York et maîtrise déjà l’unification selon une approche moderne où tous les calculs se résument à modifier des pointeurs.
Début 1971, l’équipe se reconstitue à Marseille. Alain Colmerauer obtient un poste de maître de conférences en informatique et Jean Trudel l’accompagne grâce à une bourse de deux ans d’Hydro-Québec. Leur objectif était de réaliser des déductions à partir de textes français. La répartition du travail est telle que Jean Trudel et Philippe Roussel s’attaquent aux déductions, Robert Pasero et Alain Colmerauer au langage naturel. Leur environnement de travail tient du luxe pour la France de l’époque. L’IBM 360-44 de leur département offre près de 900 Ko de mémoire interne, sans mémoire virtuelle. Jean Trudel développe un moniteur interactif et ils monopolisent la machine la nuit.
En juin 1971, l’équipe invite Robert Kowalski, l’un des inventeurs de la SL-resolution. Cette rencontre change tout. Pour la première fois, ils échangent avec un spécialiste capable d’expliquer le principe de résolution, ses variantes et ses raffinements. Kowalski découvre des chercheurs passionnés par ses travaux et déterminés à les appliquer au traitement du langage naturel.
En février 1972, l’Institut de Recherche d’Informatique et d’Automatique (IRIA) leur accorde 122 000 FF pour 18 mois. Cette subvention leur permet d’investir dans un terminal télétype, une liaison dédiée à 300 bauds vers l’IBM 360-67 de Grenoble, et le recrutement d’Henry Kanoui.
L’automne 1972 voit naître le premier système Prolog. Philippe Roussel le développe en Algol-W tandis qu’Alain Colmerauer et Robert Pasero créent en parallèle le système de communication homme-machine en français. L’interaction entre Philippe, qui code Prolog, Alain et Robert, qui programment dans un langage en cours de création, se pérennise. C’est l’épouse de Philippe qui suggère le nom définitif : Prolog, abréviation de « PROgrammation en LOGique ».
Le premier grand programme écrit en Prolog est le système de communication homme-machine. Ses 610 clauses se répartissent ainsi : Alain en écrit 334 pour l’analyse, Robert Pasero 162 pour la partie déductive, et Henry Kanoui développe une morphologie française en 104 clauses. Cette morphologie gère les liens entre singulier et pluriel de tous les noms communs et tous les verbes, réguliers et irréguliers, à la troisième personne du singulier du présent.
La reconnaissance officielle arrive en 1973. Le CNRS constitue une « équipe de recherche associée » baptisée « Dialogue homme-machine en langage naturel » et accorde 39 000 FF pour la première année. Les utilisateurs de la version préliminaire de Prolog ont suffisamment programmé pour que leur expérience nourrisse une deuxième version, orientée vers un véritable langage de programmation et non plus seulement un système déductif automatisé.
Entre juin et décembre 1973, trois étudiants en DEA – Gérard Battani, Henry Méloni et René Bazzoli – écrivent l’interpréteur en FORTRAN et son superviseur en Prolog. Cette version introduit toutes les caractéristiques de base des Prolog actuels. C’est aussi à cette période que disparaît la vérification d’occurrence (occur check), jugée trop coûteuse.
La diffusion commence vraiment en 1974-1975. David Warren séjourne à Marseille de janvier à mars 1974 et utilise Prolog pour écrire Warplan, son système de génération de plans. La version interactive de Prolog qui fonctionne à Grenoble via télétype suscite de nombreuses demandes. Gérard Battani et Henry Méloni croulent sous les distributions. Ils expédient Prolog à Budapest, Varsovie, Toronto, Waterloo et se déplacent à Édimbourg pour aider David Warren à l’installer sur un PDP 10. Hélène Le Gloan, ancienne étudiante, l’installe à l’Université de Montréal. Michel Van Caneghem fait de même à l’IRIA à Paris avant de rejoindre l’équipe. Maurice Bruynooghe emporte Prolog à Louvain après trois mois à Marseille.
En 1975, toute l’équipe participe au portage sur un mini-ordinateur 16 bits, le T1600 de Télémécanique. La machine ne dispose que de 64 Ko et nécessite un système de gestion de mémoire virtuelle spécifique. Pierre Basso s’attaque à cette tâche et remporte le concours de la séquence d’instructions la plus courte qui réalise un adressage sur 32 bits tout en testant le défaut de page. Chaque membre du laboratoire traduit alors deux pages de FORTRAN en langage machine. Les fragments réassemblés fonctionnent. Après cinq ans, ils possèdent enfin leur propre machine et leur Prolog tourne, lentement, mais il tourne.
L’histoire de la naissance de Prolog s’achève fin 1975, mais son influence perdure. L’article d’Alan Robinson de janvier 1965, « A machine-oriented logic based on the resolution principle », contenait les germes du langage Prolog. Si cet article a donné naissance à un courant important de travaux sur la démonstration automatique de théorèmes, la contribution spécifique de l’équipe marseillaise a été de transformer ce démonstrateur en langage de programmation. Pour y parvenir, ils n’ont pas hésité à introduire des mécanismes purement calculatoires et des restrictions qui constituaient des hérésies pour le modèle théorique existant. Ces modifications, souvent critiquées, ont assuré la viabilité et donc le succès de Prolog.
Robert Kowalski a isolé le concept de « clause de Horn », légitimant leur principale hérésie : une stratégie de démonstration linéaire avec retour arrière et unifications uniquement aux têtes de clauses. L’équipe marseillaise disposait des conditions idéales pour cette création. Colmerauer appartenait à la première génération de docteurs en informatique français et sa spécialité était la théorie des langages. Il avait acquis une expérience précieuse en créant les systèmes-Q au sein du projet de traduction automatique de l’Université de Montréal. La rencontre avec Philippe Roussel et les conditions particulières de Marseille ont fait le reste. L’équipe a bénéficié d’une liberté d’action dans un centre scientifique nouvellement créé et, sans pressions extérieures, elle a pu se consacrer pleinement à son projet.