Présentation
Auteur(s)
-
Patrice BOIZUMAULT : Professeur à l’École des mines de Nantes
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleINTRODUCTION
Les logiciels des grands systèmes informatiques d’aujourd’hui ont une durée de vie, une taille et une complexité croissante. Le développement de tels systèmes nécessite des méthodes formelles capables de raisonner sur le logiciel, en prenant en compte tous les aspects allant de la spécification à la validation et l’analyse de performances. Les méthodes formelles ouvrent la voie à la mathématisation du logiciel.
Au-delà des méthodes d’assertion qui sont le plus couramment utilisées en génie logiciel, il est possible de relier plus profondément mathématiques et calcul. En particulier, on peut établir une correspondance forte entre logique et programmation en identifiant : un programme à une théorie logique et une exécution à la recherche d’une preuve. Cette correspondance est l’idée maîtresse de la programmation en logique et elle se résume par la formule : programme=théorie logique exécution=recherche de preuve
Un programme logique est un ensemble d’axiomes (règles et faits) qui définissent les relations entre les entités du problème à traiter. L’exécution d’un programme logique consiste à déduire les conséquences logiques du programme. L’art de la programmation en logique consiste à construire des programmes concis et élégants qui ont les conséquences logiques attendues.
L’idée d’utiliser la logique des prédicats comme langage de programmation est née au tout début des années 1970. La puissance et la simplicité du langage Prolog, ainsi que l’existence d’une sémantique bien définie à partir du calcul des prédicats, ont donné naissance à de très nombreuses implantations et applications dans les domaines de la spécification et du prototypage, des bases de données, des systèmes à base de connaissances, de la simulation, du traitement du langage naturel, de l’écriture de compilateurs, de la conception assistée par ordinateur (CAO), de l’enseignement assisté par ordinateur (EAO), etc.
La présentation du langage Prolog dans cet article ne demande aucun prérequis en programmation. Il est organisé selon un degré de complexité croissant. Nous avons privilégié une présentation intuitive à partir d’exemples, en mentionnant également certains aspects plus formels.
La programmation en logique est un paradigme de programmation déclarative : il s’agit moins d’exprimer comment on calcule le résultat que de fournir les propriétés de ce résultat. Nous décrivons cet aspect au début de l’article, où Prolog est présenté comme un démonstrateur de théorèmes, avec un rappel des notions de base sur la logique de prédicats.
Prolog est certes un langage déclaratif, mais un bon programmeur Prolog doit aussi savoir tirer profit de la stratégie de contrôle du démonstrateur pour obtenir efficacement des solutions. Nous nous intéressons donc ensuite au modèle d’exécution de Prolog exprimé comme une stratégie particulière de parcours d’un arbre de recherche (en profondeur d’abord). Puis est exposé le traitement des listes et des arbres en Prolog.
VERSIONS
- Version courante de juin 2022 par Laurent BLOCH
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Technologies logicielles Architectures des systèmes
(238 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
4. Arbres
Les arbres permettent de représenter des informations de manière structurée. Ainsi, pour le terme f(a,g(X)), f sera la racine, a et g(X) les deux fils. Nous présentons deux exemples : le premier illustre le traitement récursif d’arbres en Prolog, le second montre comment les termes structurés (listes ou arbres) permettent d’organiser des informations.
4.1 Évaluation d’expressions booléennes
On considère des expressions booléennes définies par la grammaire suivante :
<expr> ::= <bin>(<expr>, <expr>)
<expr> ::= <un>(<expr>)
<expr> ::= vrai
faux
<bin> ::= et
ou
<un> ::= non
et(ou(vrai,faux),vrai) et et(non(vrai),ou(vrai,faux)) sont deux exemples de telles expressions. Évaluer une expression booléenne consiste à appliquer l’opérateur concerné à l’évaluation récursive de chacun des deux fils. L’unification permet d’identifier l’opérateur et d’accéder aux fils. La formulation est incrémentale ; pour traiter l’implication, il suffirait d’ajouter une règle dans la définition du prédicat evaluer/2, ainsi que la table de vérité correspondante.
evaluer(vrai, vrai).
evaluer(faux, faux).
evaluer(et(G, D), R) :-
evaluer(G, RG),
evaluer(D, RD),
table_et(RG, RD, R).
evaluer(ou(G, D), R) :-
evaluer(G, RG),
evaluer(D, RD),
table_ou(RG, RD, R).
evaluer(non(E), R) :-
evaluer(E, RE),
table_non(RE, R).
table_et(vrai, vrai, vrai). table_et(faux, vrai, faux).
table_et(vrai, faux, faux). table_et(faux, faux, faux).
table_ou ...
table_non ...
Nous pouvons améliorer l’efficacité de notre solution en remarquant que si un sous-arbre gauche s’évalue en faux pour un opérateur et, alors il est inutile d’évaluer le sous-arbre droit (faux est absorbant pour et). Il en est de même pour vrai vis-à-vis de l’opérateur ou.
evaluer(et(G, D), R) :-
evaluer(G, RG),
cont_et(RG, D, R).
evaluer(ou(G, D), R) :-
evaluer(G, RG),
cont_ou(RG, D, R).
cont_et(faux, _, faux).
cont_et(vrai, Expr, R) :- evaluer(Expr, R).
cont_ou(vrai,...
Cet article fait partie de l’offre
Technologies logicielles Architectures des systèmes
(238 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Arbres
BIBLIOGRAPHIE
-
(1) - COLMERAUER (A.), KANOUI (H.), PASERO (R.), ROUSSEL (P.) - Un système de communication homme machine en français - . 1972 Technical report, GIA université d’Aix-Marseille.
-
(2) - WARREN (D.H.) - Implementing Prolog : compiling predicates logic programs - . Technical Report 39-40, 1977, DAI Edimbourg.
-
(3) - CLOCKSIN (W.F.), MELLISH (C.S.) - Programming in Prolog - . 2e éd., 1984 Springer-Verlag.
-
(4) - APT (K.) - From Logic Programming to Prolog - . 1997 Prentice Hall.
-
(5) - ROBINSON (J.A.) - A machine oriented logic based on the resolution principle - . JACM, 12(1), 1965, 23-44.
-
(6) - APT (K.R.), VAN EMDEN (M.H.) - Contribution to the theory of Logic Programming - . JACM, 29(3), 1982, 841-862.
-
...
DANS NOS BASES DOCUMENTAIRES
-
Langages pour la conception des circuits intégrés
ANNEXES
Revue Theory and Practice of Logic Programming
http://www.cwi.nl/projects/alp/TPLP/index.html
Archives (logiciels libres, systèmes commerciaux, manifestations scienti-fiques...)
http://archive.comlab.ox.ac.uk/logic-prog.html
HAUT DE PAGE
Association internationale pour la programmation en logique ALP
http://www.cwi.nl/projects/alp
Association française pour la programmation en logique et la programmation par contraintes AFPLC
Réseau compulog
http://kmi.open.ac.uk/compulog
HAUT DE PAGECet article fait partie de l’offre
Technologies logicielles Architectures des systèmes
(238 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive