Programmation logique
Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » ().
Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.
La programmation logique est une forme de programmation qui définit les applications à l'aide :
- d'une base de faits : ensemble de faits élémentaires concernant le domaine visé par l'application,
- d'une base de règles : règles de logique associant des conséquences plus ou moins directes à ces faits,
- d'un moteur d'inférence (ou démonstrateur de théorème ) : exploite ces faits et ces règles 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
[modifier | modifier le code]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 0, elle présentait peu d'intérêt si ce n'est pour améliorer le calcul des circuits logiques. En 1965, John Alan 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.
Approche informatique
[modifier | modifier le code]En 1958, John McCarthy proposait déjà d’utiliser la logique comme langage déclaratif de représentation des connaissances, un démonstrateur de théorème devenant un 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 déclarative/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 fondé sur la logique, émergea cependant au MIT. Son sous-ensemble Micro-Planner (Sussman, Charniak, Winograd) fut utilisé par Winograd pour SHRDLU, programme fondé 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) développa un langage équationnel, Golux, qui pouvait invoquer diverses procédures 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.
L'avènement de Prolog
[modifier | modifier le code]Alain Colmerauer, universitaire français passé de la compilation à la traduction automatique (Montréal, 1967-70), eut d'abord l’idée des systèmes-Q (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 comprirent que les formes propositionnelles pouvaient représenter des 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 résolution-SL de Kowalski une analyse descendante. L’été suivant, ils développèrent l’interprétation procédurale des implications, et établirent qu’on peut 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 permettant ensuite de répondre à des questions sur ce monde, Prolog servant aussi bien à l’analyse qu'à la synthèse en français et aux raisonnements permettant d'élaborer les réponses. Ce premier Prolog se 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, avec sa syntaxe particulière, devint ainsi un standard.
Développements
[modifier | modifier le code]En 1982 sortit Prolog II, qui utilisait des systèmes d’équations plutôt que l’unification, et, surtout, permettait le traitement des arbres infinis.
À partir de 1987, Prolog III intégrait au niveau de l’unification : une représentation des arbres rationnels (é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.
Descendance
[modifier | modifier le code]À partir de Prolog, furent développés par exemple Gödel, Oz, Mercury, Erlang 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.
Langages de programmation logique
[modifier | modifier le code]- Prolog : Le premier langage de programmation logique ;
- Oz ;
- CLIPS ;
- Python : PyPy permet de l'utiliser pour la programmation logique.[réf. nécessaire]
Bibliographie
[modifier | modifier le code]- C. Baral et M. Gelfond, « Logic programming and knowledge representation », The Journal of Logic Programming, vol. 19–20, , p. 73–148 (DOI 10.1016/0743-1066(94)90025-6, lire en ligne)
- R. A. Kowalski, « The early years of logic programming », Communications of the ACM, vol. 31, , p. 38–43 (DOI 10.1145/35043.35046, S2CID 12259230, lire en ligne)
Liens externes
[modifier | modifier le code]
