Présentation

Article

1 - CLAUSES DE HORN ET PRINCIPE DE RÉSOLUTION

  • 1.1 - Calcul des prédicats
  • 1.2 - Termes Prolog
  • 1.3 - Premier aperçu de l’unification
  • 1.4 - Clauses de Horn
  • 1.5 - Preuve par réfutation

2 - PREMIERS PAS EN PROLOG

  • 2.1 - Faits et questions
  • 2.2 - Règles et questions
  • 2.3 - Contrôle Prolog
  • 2.4 - Coupure

3 - LISTES

  • 3.1 - Listes et unification
  • 3.2 - Traitements de liste

4 - ARBRES

  • 4.1 - Évaluation d’expressions booléennes
  • 4.2 - Gestion des vols dans un aéroport

5 - APPLICATION À LA CÉSURE DES MOTS

6 - DOMAINES D’APPLICATION

| Réf : H3098 v1

Clauses de Horn et principe de résolution
Langage Prolog

Auteur(s) : Patrice BOIZUMAULT

Date de publication : 10 févr. 2001

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

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’article

INTRODUCTION

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.

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

VERSIONS

Il existe d'autres versions de cet article :

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-h3098


Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 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

ABONNEZ-VOUS

Lecture en cours
Présentation

1. Clauses de Horn et principe de résolution

Un premier point de vue consiste à considérer Prolog comme un démonstrateur automatique de théorèmes [4]. L’univers Prolog est constitué d’un ensemble S de formules de la logique du premier ordre énoncées sous forme clausale. À partir des formules de S considérées comme vraies (axiomes), Prolog en déduit de nouvelles (théorèmes) à l’aide de règles d’inférence basées sur le principe de résolution [5].

La pratique de Prolog consiste alors à poser des questions (requêtes) afin de déterminer si celles-ci sont des conséquences logiques de S. La réponse à une requête s’effectue par réfutation en montrant que la conjonction de S et de la négation de la requête est contradictoire. Cette réfutation repose sur le principe de résolution et utilise une stratégie particulière [6].

Historique

Le langage Prolog est né au tout début des années 1970, grâce aux travaux de Alain Colmerauer (qui utilisait la logique pour le traitement du langage naturel) et de Robert Kowalski dans le domaine de la démonstration automatique. Le premier interprète Prolog [1] a été développé en 1971 à l’université d’Aix-Marseille par Philippe Roussel. Le premier compilateur (Prolog Dec10) a été développé à l’université d’Édimbourg par D.H. Warren [2] [3].

c’est à lui que nous devons la syntaxe des langages Prolog actuels.

Prolog fut alors employé dans bon nombre de domaines non numériques : traitement du langage naturel, compilation, manipulation symbolique de formules, bases de données, intelligence artificielle...

L’annonce en 1981 du projet japonais de cinquième génération a donné naissance à une très grande activité dans le domaine de la programmation en logique, aussi bien du point de vue de la recherche que du point de vue des applications.

Même si le projet très ambitieux de construction de machines parallèles conçues pour exécuter un langage de programmation en logique dérivé de Prolog, n’a pas abouti, cette activité importante dans le domaine de la programmation en logique a permis de construire des implantations très efficaces, des environnements de programmation confortables et de très nombreuses applications.

Actuellement, tous les constructeurs proposent des compilateurs Prolog et...

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 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

ABONNEZ-VOUS

Lecture en cours
Clauses de Horn et principe de résolution
Sommaire
Sommaire

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

1 Sites Internet

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

2 Organismes

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

http://www.alplc.org

Réseau compulog

http://kmi.open.ac.uk/compulog

HAUT DE PAGE

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 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

ABONNEZ-VOUS