Programmation logique - Définition
La liste des auteurs de cet article est disponible ici.
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.
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 5e génération fut à l'origine de nombreux langages de programmation logique concurrente, tels que plus récemment CS Prolog ou Actor Prolog.
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.
