Programmation logique

Un article de Wikipédia, l'encyclopédie libre.

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.

[modifier] 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.

[modifier] Approche informatique

En 1958, John McCarthy proposait déjà d’utiliser la logique comme langage declaratif de representation des connaissances, un démonstrateur de théorème devenant un résolveur de problème. La résolution de problèmes est alors répartie entre le cogniticien, responsable de la validité de l’application exprimée logiquement, et le moteur d’inférence, responsable d’une exécution valide et efficace.

En un sens plus étroit et plus commun, la programmation logique joue sur une ambivalence représentation declarative/représentation procédurale : ainsi, un raisonnement régressif associera à l’implication B1&…&Bn → H une procédure « pour établir H, établir B1 puis… puis Bn ». De ce fait, au nom de l’efficacité, le programmeur peut être amené à exploiter les propriétés physiques du démonstrateur, se rapprochant ainsi d’une programmation classique. Cependant, les programmes logiques gardent toujours une interprétation logique pure permettant de garantir leur correction, et, du fait de leur caractère déclaratif, sont plus abstraits que leur contrepartie impérative, tout en restant exécutables.

Les premières applications de la programmation logique (1964-69) concernèrent des systèmes de questions/réponses. Absys (1969) fut probablement le premier langage de programmation à base d’assertions.

La programmation logique au sens étroit remonte aux débats de cette époque concernant la représentation des connaissances en intelligence artificielle. Stanford et Édimbourg, avec J. McCarthy et Kowalski, tenaient pour une représentation déclarative, et le MIT, avec Marvin Minsky et Seymour Papert, pour une représentation procédurale.

Planner (Hewitt 1969), langage basé sur la logique, émergea cependant au MIT. Son sous-ensemble Micro-Planner (Sussman, Charniak, Winograd) fut utilisé par Winograd pour SHRDLU, programme basé sur l’interprétation d’un dialogue en langage naturel. Planner invoquait des plans procéduraux à partir de buts et d’assertions, et utilisait des reprises en arrière pour ménager le peu de mémoire disponible. Dérivèrent de Planner QA-4, Popler, Conniver, QLISP, Ether.

Cependant, Hayes et Kowalski à Édimbourg essayaient de réconcilier approche déclarative et représentation des connaissances avec l’approche procédurale à la Planner. Hayes (1973) developpa un langage équationnel, Golux, qui pouvait invoquer diverses procedures en altérant le fonctionnement du moteur d’inférence. Kowalski montrait par ailleurs que la SL-resolution traitait les implications comme procédures réductrices des buts.

[modifier] 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.

[modifier] Développements

En 1982 sortit Prolog II, qui utilisait des systèmes d’équations plutôt que l’unification, et abordait le traitement des arbres infinis.

À partir de 1987, Prolog III intégrait au niveau de l’unification : une manipulation des arbres, éventuellement infinis, avec un traitement spécifique pour les listes ; un traitement complet de l’algèbre de Boole ; un traitement numérique portant sur l’addition, la multiplication par une constante et les relations usuelles.

En 1996, Prolog IV s’attaqua résolument au traitement des contraintes. Programmer par contraintes consiste à formuler un problème en termes d’inconnues soumises à une contrainte, énoncé du premier ordre faisant intervenir des opérations et des relations du domaine de calcul. Résoudre la contrainte, et par là le problème, consiste à trouver les valeurs à attribuer aux variables libres de la formule pour la rendre vraie, ce qui unifie la programmation logique et la programmation mathématique (au sens de la recherche opérationnelle). Au prix d’un moteur dix fois plus gros que pour Prolog II, Prolog IV traite un vaste jeu de contraintes, allant des contraintes sur les listes et les arbres aux contraintes numériques, en passant par les contraintes traitées par réduction des intervalles de valeur, s’appliquant aussi bien aux réels qu’aux entiers voire aux booléens.

[modifier] Descendance

À partir de Prolog, furent développés par exemple Gödel, Oz ou Visual Prolog. λProlog abordait les logiques d'ordre supérieur. Outre datalog et divers langages de programmation logique sous contraintes, le projet japonais d'ordinateurs de 5^e génération fut à l'origine de nombreux langages de programmation logique concurrente, tels que plus récemment CS Prolog ou Actor Prolog.