Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Licence informatique 2001 / 2002 Programmation fonctionnelle et logique Program

Licence informatique 2001 / 2002 Programmation fonctionnelle et logique Programmation fonctionnelle et logique --- Dossier sur PROLOG Dossier sur PROLOG Martin Ludovic Dossier sur PROLOG Table des matières Table des matières I. La programmation logique ........................................................................................................................ 1 I.1. Un mode de programmation à part..................................................................................................... 1 I.1.1. Les autres modes de programmation........................................................................................... 1 I.1.1.1. La programmation impérative .............................................................................................. 1 I.1.1.2. La programmation fonctionnelle .......................................................................................... 1 I.1.2. La programmation logique .......................................................................................................... 1 I.1.3. La programmation orientée objet ................................................................................................ 1 I.2. Constitution d’un programme PROLOG............................................................................................ 2 I.2.1. Les faits........................................................................................................................................ 2 I.2.2. Les règles..................................................................................................................................... 2 I.2.3. Les conventions de SWI-PROLOG©........................................................................................... 3 II. Utilisations de PROLOG.......................................................................................................................... 3 II.1. Interrogation de bases de données relationnelles.............................................................................. 3 II.1.1. Programmation de la base de données ....................................................................................... 3 II.1.2. Interrogation de la base de données ........................................................................................... 4 II.1.2.1. Vérification de la présence d’une donnée dans la table ...................................................... 4 II.1.2.2. Recherche d’une liste simple............................................................................................... 4 II.1.2.3. Recherche d’une liste multiple............................................................................................ 5 II.1.2.4. Recherche dans un intervalle de valeurs ............................................................................. 6 II.1.2.5. Utilisation des sous-tables................................................................................................... 7 II.2. Formalisation de systèmes experts.................................................................................................... 8 II.2.1. PROLOG et les systèmes experts............................................................................................... 8 II.2.2. Constitution de la base de connaissance .................................................................................... 8 II.2.2.1. Enumération exhaustive...................................................................................................... 9 II.2.2.2. Ecritures condensées ........................................................................................................... 9 II.2.2.2.1. Règle de commutation.................................................................................................. 9 II.2.2.2.2. Enumération par variables.......................................................................................... 11 II.2.2.2.3. Relations entre paramètres ......................................................................................... 12 II.2.3. Mise en place des règles de décision........................................................................................ 13 II.3. Calculs............................................................................................................................................. 14 II.3.1. Utilisation d’une pile................................................................................................................ 14 II.3.2. Appel récursif terminal............................................................................................................. 16 II.3.3. Valeur approchée...................................................................................................................... 17 II.3.3.1. Première approximation.................................................................................................... 17 II.3.3.2. Calcul logarithmique......................................................................................................... 19 II.3.3.3. Approximation plus fine.................................................................................................... 20 II.4. Représentation spécialisée de nombres........................................................................................... 21 II.4.1. Définition d’un système numérique......................................................................................... 21 II.4.1.1. Représentation syntaxique................................................................................................. 21 II.4.1.2. Conversion entre systèmes................................................................................................ 22 II.4.2. Définition d’opérateurs ............................................................................................................ 22 III. La recherche de solution....................................................................................................................... 23 III.1. L’unification .................................................................................................................................. 23 III.1.1. Termes..................................................................................................................................... 24 III.1.2. Substitutions............................................................................................................................ 24 III.1.3. Unification .............................................................................................................................. 26 III.1.3.1. Définition......................................................................................................................... 26 III.1.3.2. Algorithme de J. Herbraund............................................................................................. 27 III.1.3.2.1. Désaccord.................................................................................................................. 27 III.1.3.2.2. Eclatement................................................................................................................. 27 III.1.3.2.3. Suppression............................................................................................................... 27 i Dossier sur PROLOG Table des matières III.1.3.2.4. Elimination d’une variable........................................................................................ 27 III.1.3.2.5. Renversement............................................................................................................ 28 III.1.3.2.6. Teste d’occurrence.................................................................................................... 28 III.1.3.2.7. Indéterminisme ......................................................................................................... 28 III.2. Exécution d’un programme PROLOG........................................................................................... 29 III.2.1. L’interactivité par les requêtes................................................................................................ 29 III.2.1.1. Des questions et des réponses.......................................................................................... 29 III.2.1.2. Un programme évolutif.................................................................................................... 30 III.2.2. La recherche de preuves par l’unification............................................................................... 30 III.2.2.1. Fonctionnement général................................................................................................... 30 III.2.2.1.1. La logique ................................................................................................................. 30 III.2.2.1.2. L’implémentation...................................................................................................... 30 III.2.2.2. Exemples avec des opérations en unaire.......................................................................... 31 III.2.2.3. Exemples avec des listes.................................................................................................. 39 III.2.2.3.1. Propriétés des listes................................................................................................... 39 III.2.2.3.2. Exemples................................................................................................................... 40 IV. Conclusion............................................................................................................................................ 45 ii Dossier sur PROLOG Liste des programmes Liste des programmes Programme 1 : Biographie des rois de France.................................................................................................. 3 Programme 2 : Base de connaissances exhaustive ........................................................................................... 9 Programme 3 : Base de connaissances commutative (erronée)........................................................................ 9 Programme 4 : Base de connaissances avec énumération par variable (erronée)........................................... 11 Programme 5 : Base de connaissances avec relation entre paramètres (erronée)........................................... 12 Programme 6 : Base de connaissances condensée (finale)............................................................................. 12 Programme 7 : Formalisation d'un système expert (complète)....................................................................... 13 Programme 8 : Calcul avec pile...................................................................................................................... 15 Programme 9 : Calcul avec appel récursif terminal........................................................................................ 16 Programme 10 : Calcul approché.................................................................................................................... 17 Programme 11 : Calcul approché logarithmique ............................................................................................ 19 Programme 12 : Calcul approché précis......................................................................................................... 20 Programme 13 : Définition d’un système unaire............................................................................................ 21 Programme 14 : Conversion unaire / décimal................................................................................................. 22 Programme 15 : Définition d’un système numérique complet (avec les opérateurs)..................................... 22 Programme 16 : Définition du système unaire avec répétitions ..................................................................... 31 Programme 17 : Appartenance à une liste (1ère version)................................................................................. 41 Programme 18 : Appartenance à une liste (2ème version) ............................................................................... 44 iii Dossier sur PROLOG La programmation logique PROLOG est un langage qui, comme son nom l’indique (PROgrammation LOGique), utilise un mode de programmation dit ‘logique’. Ce mode de programmation a vu le jour grâce à John Robinson qui a posé en 1965 les bases de la logique. Le développement de PROLOG a commencé en 1972 à l’université de Marseille dans le Groupe d’Intelligence Artificielle de Lumigny dirigé par A. Colmerauer. Il a été poursuivi principalement à Marseille et à Edimbourg. Aujourd’hui, PROLOG est un langage mûr ; pourtant il ne possède toujours pas de norme. Nous allons voir dans un premier temps ce qu’est la programmation logique afin de mieux comprendre la ‘philosophie’ des programmes PROLOG. Ensuite, nous nous intéresserons à ce que permet de faire PROLOG. Enfin, nous essaierons de comprendre sa méthode de recherche de solutions. I. La programmation logique I.1. Un mode de programmation à part Il est important avant d’expliquer ce qu’est PROLOG et d’étudier son utilisation de bien voir ce qu’il n’est pas ; c’est à dire de comprendre sa ‘philosophie’. Pour cela, il faut décrire ce qu’est la programmation logique et la comparer aux autres modes de programmation. I.1.1. Les autres modes de programmation I.1.1.1. La programmation impérative Cette programmation s’inscrit dans une démarche algorithmique qui décrit la façon de traiter les données pour atteindre un résultat par une série d’actions. Celles-ci sont toujours de trois types : le test, l’ordre (chaque instruction par laquelle le programme passe est impérative) et l’itération (obtenue grâce aux branchement). Le déroulement du programme est parfaitement déterministe. Exemple de langages : Fortran, Pascal, C … I.1.1.2. La programmation fonctionnelle Le résultat est ici comme la composition de fonctions. Pratiquement, elle est proche de la programmation impérative ; cependant ses fondements (λ-calcul) ainsi que l’absence de branchement et d’affectation (du moins dans sa forme théorique) en fait un mode de programmation à part. Rem : Dans la programmation fonctionnelle, on distingue deux grandes familles : - les langages fortement typés : ML (ex : Caml) - les langages non typés : LISP (ex : Scheme) I.1.2. La programmation logique Les modes de programmation décrits juste au-dessus sont dits procéduraux car ils cherchent à obtenir le résultat grâce à une procédure (qui peut être une suite d’actions ou une composition de fonctions). A cela on oppose la programmation logique qui est dite déclarative. En effet, ici on ne s’occupe pas de la manière d’obtenir le résultat ; par contre, le programmeur doit faire la description du problème à résoudre en listant les objets concernés, les propriétés et les relations qu’ils vérifient. Ensuite, le mécanisme de résolution (pris entièrement en charge par le langage) est général et universel. Il parcourt de façon non déterministe (cela sera détaillé au chapitre I) toutes les possibilités du problème et peut donc retourner plusieurs solutions. I.1.3. La programmation orientée objet Ce mode de programmation a été mis à part car il regroupe en fait tous les modes précédemment vus en utilisant à la fois des techniques déclaratives et d’autres procédurale. Exemple de langages : C++, Java … 1 Dossier sur PROLOG La programmation logique I.2. Constitution d’un programme PROLOG Nous avons vu que le principe de la programmation logique est de décrire le problème à résoudre. Dans le cas de PROLOG, cela est formalisé grâce à un langage dérivé du calcul des prédicats (ou calcul du premier ordre). Les prédicats servent à qualifier (donner les caractéristiques de) les objets du problème et à décrire les relations dans lesquelles ils sont impliqués. I.2.1. Les faits Les faits sont des données élémentaires qu’on considère vraies. Ce sont des formules atomiques constituées du nom d’un prédicat (c’est à dire d’une relation (au sens mathématique du terme)) (pour plus de renseignement sur le calcul des prédicat, voir la première partie du cour de Génie Logiciel) suivi entre parenthèse d’une liste ordonnée d’arguments qui sont les objets du problème principal ou d’un sous-problème. Un programme PROLOG est au moins constitué d’un ou plusieurs fait(s) car c’est à partir de lui (d’eux) que PROLOG va pouvoir rechercher des preuves pour répondre aux requêtes de l’utilisateur (voir chapitre III.1.3.2 page 27 pour comprendre comment fonctionne un programme PROLOG) ; ce sont en quelque sorte ses hypothèses de travail. Ex : Henri IV est le père de Louis XIII se traduit par : pere(henri4,louis13). Marie de Médicis est la mère de Henri IV se traduit par : mere(marie-medicis,henri4). Adam est l’ancêtre de tout le monde se traduit par : ancetre(Adam,X). Superman est plus fort que tout le monde se traduit par : plusfort(superman,X). 0 ! = 1 se traduit par : factorielle(O,1). Rem : Généralement, on place toutes les déclarations de faits au début du programme même si ce n’est pas obligatoire. I.2.2. Les règles Un programme PROLOG contient presque toujours des règles, cependant ce n’est pas une obligation. Si les faits sont les hypothèses de travail de PROLOG, les règles sont des relations qui permettent à partir de ces hypothèses d’établir de nouveaux faits par déduction (si on a démontré F1 et F1⇒F2 alors on a démontré F2). Ex : La relation telle que si on est invincible, alors on est plus fort que tout le monde se traduit par la règle : plusfort(X,Y):-invincible(X). Les relations qui se traduisent en règle sont de la forme : H1 ? H2 ? … Hn ⇒ C Où : ? peut être soit une disjonction (∨) soit une conjonction (∧) • • • H1, H2,… Hn sont des formules atomiques ou uploads/Philosophie/ cours-complet-prolog.pdf