Programmation Logique

Partie 1 : Introduction à laPartie 1 : Introduction à la programmation logique

Jean-Michel Adam

Université Pierre Mendès FranceU.F.R. Sciences de l’Hommes et de la Société (SHS)

Département Informatique et Mathématiques appliquées aux Sciences SocialesDépartement Informatique et Mathématiques appliquées aux Sciences SocialesGrenoble - France

Organisation de l’enseignement30 heures30 heures

5 cours (5 x 2 heures)5 TD (5 2 h )5 TD (5 x 2 heures)5 TP (5 x 2 heures)

Cours1. Introduction à la programmation logique1. Introduction à la programmation logique2. Le langage Prolog3 Les listes en Prolog3. Les listes en Prolog4. Les graphes en Prolog, compléments

G i t t t d’ét t fi i P l5. Grammaires et automates d’états finis en Prolog

PrologProlog est un langage extraordinaire, parce qu'il nous montre qu'il peut exister d'autres moyens de programmer un ordinateur. P l (P ti L i ) t é F 1972 (M ill )Prolog (Programmation Logique) est né en France en 1972 (Marseille) et a servi de base aux programmes de recherche japonais sur les ordinateurs de 5ème génération. Ce qui est phénoménal, c'est qu'en Prolog, il suffit

de décrire ce que l'on sait sur le domaine étudié, (en Intelligence Artificielle, on appelle cela une base de connaissances), puis on décrit notre problème

et Prolog va nous le résoudre, sans que l’on ait à lui dire comment faire !

Programmation logique et Prolog

Historique – modes de programmationD é l ti t f itDonnées, relations et faitsPrédicats et formulesRègles Clauses de HornClauses de HornDémonstration en PrologStratégie de Prolog

Historique1965 : ce mode de programmation a vu le jour grâce àJohn Robinson qui a posé en 1965 les bases de lalogique.1972 : création de Prolog par A. Colmerauer et P. Roussel à Marseille (Luminy).1980 : reconnaissance de Prolog comme langage de g g gdéveloppement en Intelligence ArtificielleDepuis, plusieurs versions ont été développées, dont des p , p pp ,extensions pour la programmation par contraintes, mais il n’existe pas vraiment de standard de ce langage.

Information complémentaires sur Prolog

La syntaxe et la sémantique du langage Prolog est l’ensemble des règles qui définissent comment un g qprogramme Prolog est écrit et interprété. Les règles sont énoncées dans la norme ISO ISO/IECLes règles sont énoncées dans la norme ISO ISO/IEC 13211, bien qu'il existe des différences dans les implémentations de Prolog voir:implémentations de Prolog, voir:http://en.wikipedia.org/wiki/Comparison_of_Prolog_implementationsplementationsDans ce cours nous utiliserons la syntaxe Edinburgh

t t l’i t èt SWI P l (f )syntax et l’interprète SWI-Prolog (freeware)

Les modes de programmation

Programmation impérativeProgrammation fonctionnelleProgrammation fonctionnelleProgrammation déclarativeProgrammation par Objets

Les modes de programmation

La programmation impérativeDémarche algorithmique qui décrit la façon de traiter lesDémarche algorithmique qui décrit la façon de traiter les données pour atteindre un résultat par une série d’actions (instructions). L’ordre d’exécution des instructions est impératif : déterminé à l’avance. Le déroulement du programme est parfaitement déterministe.E l d t l l B i P l C F tExemple de tels langages : Basic, Pascal, C, Fortran, …

Les modes de programmationLa programmation fonctionnelle

La programmation consiste à faire de la composition de p g pfonctions. Proche de la programmation impérative ; cependant ses p g p ; pfondements (λ-calcul) ainsi que l’absence de branchements et d’affectations (du moins dans sa forme théorique) en fait un mode de programmation à part.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)

Les modes de programmationLes modes de programmation impérative et fonctionnelle sont dits procéduraux car ils cherchent à obtenir le résultat

â à édgrâce à une procédure A cela on oppose la programmation logique qui est dite déclarativedéclarative. La programmation déclarative

Le programmeur ne s’occupe pas de la manière d’obtenir le résultat;Le programmeur 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érifientrelations qu ils vérifient. Ensuite, le mécanisme de résolution intégré au langage, général et universel, parcourt de façon non déterministe toutes les possibilités du problème et calcule les solutions.

Les modes de programmation

La programmation orientée objetCe mode de programmation est mis à part car ilCe mode de programmation est 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 qprocédurale.Exemple de langages : Smalltalk, C++, Java, C#,Exemple de langages : Smalltalk, C , Java, C#, ActionScript, VisualBasic, etc.

Construction d’un programme Prolog

Principe : décrire le problème à résoudre. D l d P l f li â àDans le cas de Prolog, on formalise grâce à un langage dérivé du calcul des prédicats.Les prédicats servent à donner les caractéristiques (qualifier) des objets du problème et à décrire les (q ) j prelations dans lesquelles ils sont impliqués.

Prédicats et formules

En Prolog, une relation possède :un nomun nomun nombre d ’arguments

ex: couleur(voiture rouge)ex: couleur(voiture, rouge)

En logique, relation = prédicatcouleur

L’application du prédicat à ses arguments est appelé formule.

Prédicats et formules

Nombre d ’arguments du prédicat = aritéunaire le prédicat est une propriété de l’argumentunaire le prédicat est une propriété de l argument

homme(jerome).arité zéro signification logique très restreinte (un fait vrai)arité zéro signification logique très restreinte (un fait vrai)

p.

Exercice : écrire les faits suivants sous forme deExercice : écrire les faits suivants sous forme de prédicats

La chèvre est un animal herbivorele loup est un animal cruel

Programme PrologUn programme Prolog est constitué d’une suite de prédicats ou clauses de deux types :p yp

les faits : l’affirmation d’une relation entre certains objetsles règles qui permettent d’établir de nouveaux faitsles règles qui permettent d établir de nouveaux faits

Prolog est un langage interprétéL’ é ti d’ i t àL’exécution d’un programme consiste à poser une question à l’interprète qui va rechercher toutes les solutions.

Les FaitsLes faits sont des données élémentaires que l’on considère vraies. Ce sont des formules atomiques constituées du nom d’un prédicat (c’est à dire d’une relation) suivi entre parenthèse d’une liste ordonnée d’arguments qui sont les objets dud 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 ouUn programme Prolog est au moins constitué d un ou plusieurs faits car c’est à partir d’eux que Prolog va pouvoir rechercher des preuves pour répondre aux requêtes de l’utilisateur Ce sont en quelque sorte les hypothèses de travail.

Les FaitsExemples :

Henri IV est le père de Louis XIII se traduit par : pere(henri4 louis13)pere(henri4,louis13).Marie de Médicis est la mère de Henri IV se traduit par : mere(marie-de-medicis,henri4).S l f l d d iSuperman est plus fort que tout le monde se traduit par : plusfort(superman,X).0! = 1 se traduit par : factorielle(0,1).p ( )

Généralement, on place toutes les déclarations de faits au début du programme même si ce n’est pas obligatoire. U f it t i t j i tUn fait se termine toujours par un point « . »

Les Faits

Forme : nomprédicat(arg1,arg2, …, argn).Exemples:Exemples:

capitale(france,paris).t (t )astre(terre).

étoile(soleil).satellite(terre,soleil).satellite(lune,terre).plus_petit_que(3,6).

Les données manipulées

Constantes Symbole : chaîne de caractères (minuscule)Symbole : chaîne de caractères (minuscule)Nombres : entiers ou flottants

V i bl h î d tè tVariables : chaîne de caractères commençant par une majuscule. Elles servent à

Exprimer une propriété concernant une catégorie d’objetsExprimer une question lorsque l’on interroger le système Prolog

Règles PrologUn programme Prolog contient presque toujours des règles, cependant ce n’est pas une obligation. Si les faits sont les hypothèses de travail, 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).

Exemple : La relation telle que si on est invincible, alors on est plus fort que tout le monde se traduit par la règle :

l f t(X Y) i i ibl (X)plusfort(X,Y) :- invincible(X). Les variables utilisées dans une règle sont universellement quantifiées par Prolog avec le quantificateur (quel quequantifiées par Prolog, avec le quantificateur (quel que soit).

Règles PrologEnoncent la dépendance d’une relation entre objets par rapport à d’autres relationsConcernent des catégories d’objets / faits* fait : fille(helene).* règles : si X est une fille alors X aime les poupées qui s'écrit :

aime(X,poupees) :- fille(X).Le « si » s’écrit « :- » en Prolog et correspond à l’implication ⇐

fille(X) ⇒ aime(X,poupees)s’écrit en Prolog :

aime(X,pourees) :- fille(X).

Règles PrologIl peut y avoir plusieurs conditions derrière le « :- », séparées par des virgules ou des points-virgules

L i l d à ET l i ( j ti )La virgule correspond à un ET logique (conjonction)Le point-virgule correspond à un OU logique (disjonction)Exemple :Exemple : La relation telle que si on est le père du père ou de la mère de quelqu’un alors on est son grand-père se traduit par

grandpere(X,Y) :- pere(X,Z), pere(Z,Y). grandpere(X,Y) :- pere(X,Z), mere(Z,Y).

ou encore par : grandpere(X,Y) :- pere(X,Z), (pere(Z,Y) ; mere(Z,Y)).

Autre exemple :Autre exemple :planete(X) :- astre(X), etoile(Y), satellite(X,Y).

Règles PrologExercice : exprimer en Prolog les propositions suivantes, identifier les objets, les faits, les règles

la chèvre est un animal herbivorele loup est un animal cruelun animal cruel est carnivoreun animal carnivore mange de la viande un animal herbivore

d l’h bmange de l’herbeun animal carnivore mange des animaux herbivoresles carnivores et les herbivores boivent de l’eaules carnivores et les herbivores boivent de l eauun animal consomme ce qu’il boit ou ce qu’il mangeQuestion possible : y a-t-il un animal cruel et que consomme-t-il ?Question possible : y a t il un animal cruel et que consomme t il ?

Solution possibleanimal(chevre)animal(chevre).animal(loup).herbivore(chevre).cruel(loup).

carnivore(X) :- cruel(X).( ) ( )

mange(X,viande):- animal(X), carnivore(X).mange(X,herbe):- animal(X), herbivore(X).g ( , ) ( ), ( )mange(X,Y):- carnivore(X),herbivore(Y).

boit(X,eau):- animal(X), (carnivore(X); herbivore(X)).bo t( ,eau) a a ( ), (ca o e( ); e b o e( ))

consomme(X,Y) :- mange(X,Y); boit(X,Y).

Clauses de Horn (1)Le langage Prolog est basé sur les clauses de HornCe sont les faits et les règles.F é é l F F1 F2 FForme générale : F :- F1, F2,…, Fn.

Se traduit par « F si F1 et F2 et … et Fn »F : formule atomiqueFi : littéraux (formules atomiques ou leur négation)( q g )

En Prolog : pour démontrer F, il faut démontrer F1, et F2 et Fnet F2,…, et Fn.

Clauses de Horn (2)

F est la tête de la clauseF1 F2 Fn est appelée la queue de la clauseF1, F2,…, Fn est appelée la queue de la clauseUn fait est une clause dont la queue est vide* Exemples :

* naissance(prolog, 1972).( )* aime(X, bach). : « Pour tout X, X aime Bach. »

Clauses de Horn (3)Clauses de Horn (3)Une règle est une clause dont la queue est non g qvide. La plupart des règles contiennent des variables. Définition d’une variable anonyme : « _ »

a un salaire(X) :- employeur(Y,X). _ _ ( ) p y ( , )peut s’écrire :

a un salaire(X) :- employeur( ,X).a_u _sa a e( ) e p oyeu (_, )Si une variable n’est pas nécessaire pour exprimer unerelation, l’interprète Prolog interpreter affiche un gmessage d’avertissement (warning).Définir un prédicat = définir un ensemble de faits et de règles

Programme PrologProgramme Prolog

Programme Prolog = séquence de définitions deProgramme Prolog = séquence de définitions de prédicatsPas d’ordre spécifique des prédicats.Un programme peut être composé de plusieursUn programme peut être composé de plusieurs fichiers.Il est possible d’utiliser le même nom de prédicatIl est possible d utiliser le même nom de prédicat avec une arité différente.

Example : predicat nommé enfantenfant(X,Père,Mère).enfant(X,Père,Mère).enfant(X,Y) :- enfant(X,Y,_) ; enfant(X,_,Y).

Démonstration PrologA partir d’un programme Prolog, on peut poser des questions, par exemple :

frere(patrick, X).

pour trouver les frères de Patrick. C’est-à-dire déterminer les valeurs des variables (X dans notre exemple) telles que la question soit déductible des faits et prédicats du programme.On parle de résolution de question ou de p qdémonstration de question.

Unification (1)Unification (1)Exemple :Exemple :frere(X,Y) :- homme(X), enfant(X,Z), enfant(Y,Z), X\=Y.où \= représente le prédicat de différenceoù \= représente le prédicat de différence.frere(patrick,Qui).tentative d’unification avec la tête de la clause frere(X Y)tentative d unification avec la tête de la clause frere(X,Y)Unification : procédé par lequel on essaie de rendre d f l id ti d t d ldeux formules identiques en donnant des valeurs aux variables qu’elles contiennent.Résultat : c’est une substitution (ou unificateur), un ensemble d’affectations de variables.

Exemple : X=patrick, Qui=Y

Unification (2)

Exemple :frere(X Y) : homme(X) enfant(X Z) enfant(Y Z) X\=Yfrere(X,Y) :- homme(X), enfant(X,Z), enfant(Y,Z), X\=Y.

frere(patrick Qui) U ifi i f (X Y)frere(patrick,Qui). Unification avec frere(X,Y)X=patrick et Qui=Y

homme(patrick)enfant(patrick,Z)enfant(Y,Z)

t i k\ Ypatrick\=Y

Unification (3)Le résultat n’est pas forcément unique, mais représente l’unificateur le plus général.p p gL’unification peut réussir ou échouer.

e(X X) et e(2 3) ne peuvent être unifiése(X,X) et e(2,3) ne peuvent être unifiés.

Prédicat d’unification : « = »(B C) (2 3) d é lt ta(B,C) = a(2,3). donne pour résultat :

true B=2, C=3a(X Y L) = a(Y 2 carole) donne pour résultat :a(X,Y,L) a(Y,2,carole). donne pour résultat :

true X=2, Y=2, L=carolea(X,X,Y) = a(Y,u,v). donne pour résultat :

false

Démonstration Prolog (1)

Si l’unification échoue : situation d'échec sur la règle considérée pour démontrer la formule.règle considérée pour démontrer la formule.Si l’unification réussit : substitution des variables présentes dans la queue de la clause par lesprésentes dans la queue de la clause par les valeurs correspondantes des variables de l’ ifi tl’unificateur.

Démonstration Prolog(2)Démonstration Prolog(2)

L dé t ti d t bl d f l tLa démonstration de cet ensemble de formules est faite dans l’ordre de leur citationLe système est enrichi par les valeurs obtenues des variables.des variables.A la fin de la démonstration, le système a construit un ensemble des couples valeur variableun ensemble des couples valeur-variable Le sous-ensemble de couples correspondant aux variables présentes dans la question initiale forme la solution affichée par Prolog.

Points de choix

Quand plusieurs règles concernent une même question :question :

Prolog effectue des essais consécutifs dans l’ordre de déclaration des prédicatsdéclaration des prédicatsCette séquence d’essais peut être représentée par un arbre: l’arbre de recherchearbre: l arbre de rechercheLes nœuds de l’arbre sont appelés points de choix

Arbre de recherche (1)

On parle d’arbre de recherche d’une question* Racine de l’arbre : la questionRacine de l arbre : la question * Nœud : points de choix (formules à démontrer)* Passage d’un nœud vers son fils en considérant l’une* Passage d un nœud vers son fils en considérant l une

des règles et en effectuant une unification et un pas de démonstrationde démonstration

Arbre de recherche (2)

* Les nœuds sont démontrés de gauche à droite, dans l’ordre de déclaration dans la règleg

* Nœuds d'échec : aucune règle ne permet de démontrer la première formule du nœudp

* Nœuds de succès : ne contient plus aucune formule à démontrer, tout a été démontré et les éléments de ,solution sont trouves en remontant vers la racine de l’arbre

Arbre de recherche (3)Exemple de programme:

pere(charlie, david). (p1)pere(henri charlie) (p2)pere(henri, charlie). (p2)papy(X,Y) :- pere(X,Z), pere(Z,Y). (p3)

Appel du programme : papy(X,Y).

papy(X,Y)p3

pere(X,Z) pere(Z,Y)

etp

oupere(david,Y) pere(charlie,Y)

ou

p1 p2

oX=charlieZ=david

X=henriZ=charlie échec

oup1 p2

échec

oup1 p2

y=davidsuccès

Stratégie de Prolog (1)

Pour résoudre une question, Prolog construit l’arbre de recherche de la questionl arbre de recherche de la questionParcours en profondeur d’abord

d d è ’ t l ti P l l’ ffi h t* nœud de succès : c’est une solution, Prolog l’affiche et cherche d’autres solutions

d d'é h té d l’ b j 'à i t* nœud d'échec : remontée dans l’arbre jusqu'à un point de choix possédant des branches non explorées

Stratégie de Prolog (2)

On parle de backtrack. Si un tel nœud de choix n’existe pas, la démonstration est terminée, il n’yn existe pas, la démonstration est terminée, il n y a pas d’autre solution.Possibilité de branche infinie et donc dePossibilité de branche infinie et donc de recherche sans terminaison… Attention à :

L’ordre des littéraux dans la queue de clauseL’ordre des clauses

Exemple de démonstrationplanete(X) : astre(X) etoile(Y) satellite(X Y)planete(X) :- astre(X), etoile(Y), satellite(X,Y).faits:

t (l )astre(lune).astre(terre).astre(soleil)astre(soleil).astre(venus).satellite(venus, soleil). ( )satellite(lune, terre).satellite(terre, soleil).étoile(vega).étoile(soleil).

?- planete(X).

Exemple de démonstrationplanete(X) :- astre(lune), etoile(Y), satellite(lune,Y).faits:

astre(lune).astre(terre).astre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Exemple de démonstrationplanete(X) :- astre(lune), etoile(vega), satellite(lune, vega).faits: échec !

astre(lune).astre(terre).astre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Exemple de démonstrationplanete(X) :- astre(lune), etoile(soleil), satellite(lune, soleil).faits: backtrack échec !

astre(lune).astre(terre).astre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Exemple de démonstrationplanete(X) :- astre(terre), etoile(Y), satellite(terre, Y).faits: backtrack

astre(lune).astre(terre).astre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Exemple de démonstrationplanete(X) :- astre(terre), etoile(vega), satellite(terre, vega).faits: échec !

astre(lune).astre(terre).astre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Exemple de démonstrationplanete(X) :- astre(terre), etoile(soleil), satellite(terre, soleil).faits: backtrack true !

astre(lune). X = terre,astre(terre). Y = soleilastre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Exemple de démonstrationplanete(X) :- astre(soleil), etoile(Y), satellite(soleil, Y).faits: backtrack ….. échec !

astre(lune).astre(terre).astre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Exemple de démonstrationplanete(X) :- astre(venus), etoile(Y), satellite(venus, Y).faits: backtrack

astre(lune).astre(terre).astre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Exemple de démonstrationplanete(X) :- astre(venus), etoile(soleil), satellite(venus,soleil).faits: true !

astre(lune). X = venus,astre(terre). Y = soleilastre(soleil).astre(venus).satellite(venus soleil)satellite(venus, soleil). satellite(lune, terre).satellite(terre, soleil).sate te(te e, so e )étoile(vega).étoile(soleil).

Prolog utilisé en TPSWI-Prolog

Fonctionne sous Linux, Windows et MacOS.,Disponible gratuitement (licence GPL) au département informatique de l'Université de Psychologie d'Amsterdam http://www.swi-prolog.org/download/stable

Autres Prolog gratuitsg gIl y a également Visual Prolog Personal Edition, gratuit pour un usage privé GNU-Prolog (par l'INRIA).

BibliographieF d ti f L i P iFoundations of Logic ProgrammingJ. W. Lloyd, Springer-Verlag New York, Inc. New York, NY, USA ©1984 ISBN:0-387-13299-6

PrologPrologF. Giannesini, H. Kanoui, R. Pasero et M. Van Caneghem, InterÉditions, 1985 Programming in PrologW.F. Clocksin, C.S. Mellish, Springer-Verlag Telos; 4th edition (September 1994)The art of Prolog , 2nd Edition, Advanced Programming TechniquesL St li E Sh i th MIT P 1994 ISBN 13 978 0 262 19338 2L. Sterling, E. Shapiro, the MIT Press, 1994, ISBN-13: 978-0-262-19338-2 Logic Programmin and Prolog (2nd ed)Ulf Nilsson and Jan Maluszynski, free e-book, 2000U sso a d Ja a us y s , ee e boo , 000Logic programming with PrologMax Bramer, springeronline.com, 2005, free e-book, ISBN-13: 978-1852-33938-8Tutoriel en anglais:http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/intro.html