Qu’est-ce que Prolog, et pourquoi des chercheurs en IA ont-ils bâti un langage à partir de la logique?

La plupart des langages de programmation vous demandent de détailler des étapes : fais ceci, puis cela, puis recommence. Prolog demande autre chose. Vous lui dites ce qui est vrai, sous forme de faits et de règles, puis vous lui posez une question. C’est le langage lui-même qui se charge de déterminer si la réponse découle de ce que vous avez dit et, si oui, comment.

Cette idée est née d’une petite équipe de Marseille, en France, en 1971 et 1972. Ses responsables, Alain Colmerauer et Philippe Roussel, ne cherchaient pas du tout à inventer un langage de programmation. Ils voulaient un ordinateur capable de lire des phrases en français, de raisonner à leur sujet et de répondre à des questions. Prolog est l’outil qu’ils ont construit en chemin.

Ce qui s’est passé à Marseille

Colmerauer avait passé trois ans au Canada, où il avait dirigé le projet de traduction automatique de l’Université de Montréal et conçu un langage de réécriture de règles appelé les systèmes-Q. En 1970, il est rentré en France et a lancé un projet à la nouvelle faculté des sciences de Luminy, à Marseille. Roussel et Robert Pasero, tous deux âgés de 25 ans, se sont joints à lui, ainsi que Jean Trudel, un doctorant canadien qui travaillait sur la démonstration automatique de théorèmes, c’est-à-dire des programmes qui vérifient si un énoncé découle logiquement d’autres énoncés.

En 1971, l’équipe a construit un premier système de questions-réponses. Il pouvait prendre des phrases comme « Tom est un chat » et « Les chats tuent les souris », puis répondre à « Que fait Tom? ». La partie raisonnement tournait sur l’un des démonstrateurs de théorèmes de Roussel.

L’influence extérieure déterminante a été celle de Robert Kowalski, de l’Université d’Édimbourg. Il est venu une semaine en juin 1971, puis deux mois au printemps 1972, et il a apporté une méthode de preuve appelée la résolution SL. Sa façon de procéder étape par étape ressemblait beaucoup à la manière dont les programmes ordinaires appellent des procédures, ce qui la rendait pratique à exécuter sur un ordinateur.

À l’automne 1972, Roussel a écrit le premier système Prolog dans un langage appelé Algol-W, pendant que Colmerauer et Pasero s’en servaient, au fur et à mesure qu’il prenait forme, pour écrire un programme de conversation en français. Ce programme comptait 610 clauses, les énoncés de base d’un programme Prolog. Henry Kanoui en a fourni 104, qui traitaient les terminaisons des mots français. Roussel a choisi le nom, une abréviation de PROgrammation en LOGique, et les deux auteurs mentionnent aussi une suggestion de sa femme.

En 1973, l’équipe a conçu une deuxième version plus simple, écrite en Fortran par Gérard Battani, Henry Méloni et René Bazzoli. Les récits divergent ici : Colmerauer et Roussel considèrent le programme en Algol-W de 1972 comme le premier Prolog, tandis que certains résumés désignent l’interpréteur en Fortran comme la première implémentation. Tous s’entendent pour dire que c’est la version de 1973 qui s’est répandue. Des copies sont parties vers Édimbourg, Budapest, Varsovie, Montréal, Waterloo et Louvain, souvent rapportées par des visiteurs. Comme le disent les auteurs, Prolog « n’a pas vraiment été distribué; il s’est plutôt “échappé” et “multiplié” ».

Comment Prolog fonctionne

Un programme Prolog contient deux sortes d’énoncés. Un fait affirme que quelque chose est vrai. Une règle affirme que quelque chose est vrai si d’autres choses sont vraies. Ensuite, vous posez une requête, et Prolog essaie de la prouver.

Voici un minuscule programme familial :

parent(ana, ben).
parent(ben, chloe).
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Les deux premières lignes sont des faits : Ana est le parent de Ben, et Ben est le parent de Chloé. La troisième ligne est une règle. Lisez le symbole « :- » comme « si » : X est un grand-parent de Z si X est le parent d’un certain Y et que ce Y est le parent de Z. Les mots qui commencent par une majuscule sont des variables, des emplacements que Prolog remplit.

Demandez maintenant ?- grandparent(ana, Who). Voici ce que fait Prolog :

Si une étape avait échoué, Prolog serait revenu au dernier choix qu’il avait fait pour essayer l’option suivante. Cette habitude de reculer pour réessayer s’appelle le retour arrière (backtracking), et c’est le moteur de tout programme Prolog. L’appariement d’un but avec un fait ou une tête de règle, qui remplit les variables, s’appelle l’unification.

Pourquoi c’était important

Prolog a transformé une idée issue de la logique en un outil qui fonctionne. Kowalski a ensuite montré que la stratégie choisie par l’équipe marseillaise est complète pour un type restreint de règles appelées clauses de Horn, ce qui a donné au langage une assise théorique solide. David Warren, à Édimbourg, a écrit le premier compilateur Prolog, DEC-10 Prolog, avec Fernando Pereira, et sa syntaxe est devenue celle que suivent la plupart des versions ultérieures.

Dans les années 1970 et 1980, les chercheurs européens en IA avaient tendance à préférer Prolog, tandis que les laboratoires américains préféraient Lisp, et la rivalité était vive. Prolog convenait aux tâches fondées sur des règles : l’analyse de phrases, l’interrogation de bases de données, les mathématiques symboliques et les systèmes experts. En 1982, le Japon a choisi la programmation logique comme cœur de son ambitieux projet d’ordinateurs de cinquième génération. Une norme internationale du langage a suivi en 1995.

Vu de 2019, Prolog appartient à la branche « symbolique » de l’IA, où les connaissances sont écrites explicitement sous forme de règles lisibles par une personne. La plupart des IA qui font les manchettes aujourd’hui, comme les modèles de langage qui prédisent du texte, apprennent plutôt des régularités à partir de données. Les deux approches répondent à des besoins différents : un modèle appris excelle dans les tâches floues comme la reconnaissance de la parole, tandis qu’un programme logique donne des réponses qu’on peut retracer, étape par étape, jusqu’aux faits qui les justifient.

Prolog vaut-il encore la peine d’être appris quand on s’intéresse à l’IA?

Oui, si vous voulez comprendre comment on peut rendre le raisonnement mécanique. Écrire même un petit programme Prolog vous oblige à énoncer vos connaissances avec précision, et le regarder revenir en arrière vous apprend ce que veut dire la recherche en IA mieux que n’importe quel schéma. Des systèmes gratuits et bien entretenus comme SWI-Prolog fonctionnent sur des portables ordinaires.

C’est moins utile si votre but est de construire des modèles d’apprentissage automatique, qui sont surtout écrits en Python. Les idées se transposent tout de même. Les moteurs de règles, les langages de requête de bases de données et les vérificateurs de types de nombreux outils modernes empruntent à Prolog sa façon d’apparier des motifs et de chercher des réponses.

Pour un débutant, une bonne démarche consiste à passer une fin de semaine avec Prolog : écrire des arbres généalogiques, un petit casse-tête de coloriage de carte et une courte grammaire qui vérifie des phrases simples. Vous en ressortirez avec une idée claire de ce que l’« IA symbolique » signifiait pour les chercheurs des années 1970 et 1980, et une meilleure compréhension de ce que les systèmes d’apprentissage d’aujourd’hui font autrement.