Programmation logique - Définition

Introduction

La programmation logique est une forme de programmation qui définit les applications à l'aide d'un ensemble de faits élémentaires les concernant et de règles de logique leur associant des conséquences plus ou moins directes. Ces faits et ces règles sont exploités par un démonstrateur de théorème ou moteur d'inférence, en réaction à une question ou requête.

Cette approche se révèle beaucoup plus souple que la définition d'une succession d'instructions que l'ordinateur exécuterait. La programmation logique est considérée comme une programmation déclarative plutôt qu’impérative, car elle s'attache davantage au quoi qu'au comment, le moteur assumant une large part des enchaînements. Elle est particulièrement adaptée aux besoins de l’intelligence artificielle, dont elle est un des principaux outils.

Vers la démonstration automatique

Dans les années 1930, Herbrand avait posé les conditions de validité d'une démonstration automatique. En 1953, Quine donnait une règle d'inférence originale ; définie pour l'ordre O, elle présentait peu d'intérêt si ce n'est pour améliorer le calcul des circuits logiques. En 1965, Robinson donnait sa Méthode de Résolution : il basait une démonstration automatique sur les conditions d'Herbrand, avec un raisonnement par l'absurde utilisant des énoncés logiques mis sous forme clausale, et une Règle de Résolution, extension à l'ordre 1 de la règle de Quine. Les premiers essais montrèrent que l'idée y était, mais qu'il restait à en trouver une expression efficace : ce sera Prolog.

L'Avènement de Prolog

Alain Colmerauer, universitaire français passé de la compilation à la traduction automatique (Montréal, 1967-70), eut d'abord l’idée des Q-systèmes (1969), formés de règles de réécriture d’arbres, invoquées selon les besoins et utilisant l’unification. Ces systèmes furent à la base d’une chaîne de traduction anglais→français, puis de la rédaction du système Météo qui, au Canada, traduit chaque jour les bulletins météorologiques de l’anglais au français.

Après 1970, Colmerauer revenu à Marseille s’intéressa davantage à l’exploitation de textes qu’à leur traduction ; voulant utiliser la logique pour représenter la sémantique aussi bien que pour les raisonnements liés aux questions, il s’intéressa aux travaux de Robinson sur le Principe de Résolution.

Durant l’été 1971, Colmerauer et Kowalski virent que la forme clausale pouvait représenter les grammaires formelles et qu’un moteur d’inférence pouvait être utilisé pour l’analyse de textes, certains moteurs fournissant une analyse ascendante, et la SL-résolution de Kowalski une analyse descendante. L’été suivant, ils développèrent l’interprétation procédurale des implications, et établirent qu’on pouvait restreindre les clauses aux clauses de Horn, correspondant à des implications où antécédents et conséquent sont des énoncés atomiques.

A. Colmerauer et P. Roussel développèrent alors le langage Prolog comme outil permettant de décrire un monde en français, et de traiter ensuite des questions sur ce monde, Prolog servant aussi bien à l’analyse/synthèse en français qu’aux raisonnements élaborant les réponses. Ce premier Prolog diffusa rapidement. L’intérêt de Prolog pour l’interrogation en langue naturelle de bases de données déboucha sur un configurateur pour ordinateurs Solar (Télémécanique), dont dériveront divers systèmes d’interrogation en français, en anglais (Warren), en portugais (Pereira, Lisbonne), puis en allemand.

D'autres applications naquirent parallèlement : composition d'un repas diététique, calcul symbolique, organisation d'un voyage aérien...

1976 vit un premier portage de Prolog sur micro-ordinateur.

En 1977, D. Warren développa à Édimbourg un compilateur Prolog, qui apporta à Prolog la performance qui lui manquait. Le Prolog d’Édimbourg devint ainsi un standard.