Programmation logique avec Prolog

Programmation logique avec Prolog

Un programme logique est un ensemble de règles définissant des relations entre des objets. Le traitement d’un programme logique est la déduction de conséquences (soit le résultat d’une règle) du programme. Un programme déflnit un ensemble de conséquences, ce qui lui donne sa signiflcation. L’art de la programmation logique est de construire des programmes concis et élégants qui possèdent la signiflcation désirée.
L’interprétation procédurale de ce langage correspond aµ la clause logique de Horn :
B1; B2; : : : ; Bn ) A
Ce qui signifle A est vrai si B1 est vrai et B2 est vrai et : : : et Bn est vrai ; ou encore, pour
résoudre A, résoudre B1 et B2 et : : : et Bn.
La procédure de preuve de clause de Horn est l’interpréteur de Prolog. L’algorithme d’uni-flcation, qui est au coeur de la procédure de résolution de preuve, efiectue les opérations de manipulations de données pour l’assignation de variable, le passage de paramètres, la sélection de données et la construction de données. En fait, Prolog ofire un système de déduction capable de répondre aµ toute question dont la réponse est logiquement déductible des connaissances fournies préalablement. Cette réponse est obtenue par une exploration systématique de l’ensemble des cheminements logiques permettant de remonter de la ques-tion aux faits par l’entremise de règles.
En Prolog, il y a trois énoncés de base : les faits, les règles et les requ^etes (ou questions), et
une seule structure de données : le terme logique.

Faits

{ Etablissent une relation (ou un prédicat) entre objets (ou atomes)
{ Donnent une description de la situation. Ils sont similaires aµ une base de données. Un fait indique que la relation établie entre les objets est vraie. Les faits sont toujours vrais. Plusieurs faits du m^eme type correspondent aµ une disjonction de la relation entre les objets (OU).
{ Tous termes doivent utiliser une minuscule comme première lettre, µa l’inverse de la conven-tion utilisée dans le volume de Russell et Norvig. Ils se terminent par un point.
{ Un exemple de base de faits couramment rencontré dans la littérature est les liens de parenté :
father(terach,abraham). male(terach).
father(terach,nachor). male(abraham).
father(terach,haran). male(nachor).
father(abraham,isaac). male(haran).
father(haran,lot). male(isaac).
father(haran,milcah). male(lot).
father(haran,yiscah).
female(sarah).
mother(sarah,isaac). female(milcah).
female(yiscah).

Requetes

{ Permet d’obtenir de l’information d’un programme logique. En demandant P?, on demande si un but P est vrai.
{ Une requ^ete sera préflxée par ?-.
{ Répondre aµ une requ^ete en fonction d’un programme consiste aµ déterminer si elle est une conséquence logique du programme aµ partir de règles de déduction. Trois principales règles sont utilisées :
1. L’identité : vérifle si un but correspond aµ un des faits présents dans la base de faits :
?-father(abraham,isaac).yes
?-father(abraham,lot).no
2. La généralisation : Pour exploiter cette règle de déduction, on doit introduire le concept de variable. Les variables sont le moyen de résumer plusieurs requ^etes. Une variable est une entité unique mais non déflnie (pas de type). On identifle une variable en employant la majuscule comme première lettre, aµ l’inverse de la convention utilisée dans le volume de Russell et Norvig. La généralisation consiste aµ efiectuer une requ^ete vériflant l’existence (quantiflcateur existentiel) d’une substitution valide pour la variable, permettant de rendre vraie la requ^ete.
?-father(abraham,X). X = isaac
?-father(haran,X).X = lot, X = milcah, X = yiscah
Il est aµ noter que Prolog peut instancier temporairement des variables dans l’espoir qu’elles pourront l’^etre plus tard avec des éléments de la base de connaissances. Ces variables sont présentées sous le format _# (i.e., _ suivi d’un numéro de variable, par exemple : X=_143). S’il ne peut instancier ces variables, c’est un signe qu’une erreur est présente dans la base de connaissances.
3. L’instanciation ou l’uniflcation : L’utilisation de variables dans les faits permet de résumer ou de synthétiser plusieurs faits. L’instanciation consiste aµ trouver les sub-stitutions aµ cette variable permettant de rendre le fait vrai. Cette fa»con de procéder est similaire aµ rendre le fait universel (8).
L’uniflcation consiste aµ considérer deux termes et de tenter de les rendre identiques par l’instanciation de leurs variables. Prolog unifle des termes pour gérer les appels nécessaires aµ l’exécution d’un programme ainsi que la transmission des paramètres.
Les règles de l’uniflcation des termes S et T sont :
{ si S et T sont des constantes, ils s’uniflent s’ils correspondent au m^eme objet.
{ si S est une variable et T est un objet, l’uniflcation consiste aµ instancier S aµ T. Ceci est aussi valable si S est un objet et T est une variable.
{ si S et T sont des termes composés, alors il s’uniflent s’ils ont la m^eme racine et que leurs composantes s’uniflent deux aµ deux.
Voici quelques exemples :
(a) titi(X,2,tutu(Z)) et titi(tutu(1),Y,tutu(4)) Uniflcation X=tutu(1), Y=2, Z=4
(b) Si titi(Z,Y,tutu(2)) avec titi(X,2,tutu(Z)) Non uniflable car Z=X=???
(c) Sachant que plus(0,3,3) existe, plus(0,X,X) peut ^etre instancié avec X=3
{ Les requ^etes peuvent comporter des conjonctions de requ^etes. On représente la conjonction entre les buts d’une requ^ete par une virgule. Il ne faut pas confondre ceci avec l’utilisation de la virgule aµ l’intérieur d’un fait qui sert aµ séparer les objets d’une relation.
{ Les conjonctions de requ^etes sont intéressantes lorsqu’elles partagent des variables entre les buts. La portée de la variable est la conjonction en entier.
?-father(haran,X),male(X).X = lot
{ La réponse aµ une question peut ^etre positive, dans ce cas les variables sont instanciées aux réponses obtenues étant vraies selon le programme logique. La réponse peut aussi ^etre négative lorsque aucune substitution permet de rendre les buts de la requ^ete vrais.
{ Si plusieurs réponses peuvent ^etre apportées aµ une question, alors Prolog donnera la première, puis les suivantes aµ la demande de l’utilisateur.

Règles

{ Elles déclarent des choses vraies sous certaines conditions.
{ Les règles ont la forme A ( B1; B2; : : : ; Bn, soit T ete^ ( Corps. Le corps est une conjonc-tion de buts séparés par des virgules. Les caractères :- correspondent au symbole (. son(X,Y) :- father(Y,X),male(X).
grandfather(X,Z) :- father(X,Y),father(Y,Z).
{ Interprétation procédurale (comment obtenir les solutions) : pour conna^‡tre si X est le grand-père de Z, il faut déterminer si X est le père de Y et Y est le père de Z. Pour exécuter A il faut exécuter B1 et puis B2, etc.
{ Interprétation déclarative (quelles sont les solutions) : pour tout X, Y et Z, X est le grand-père de Z si1 X est le père de Y et Y est le père de Z.
1Formulé autrement : s’il existe un Y tel que, ce qui est équivalent µa un quantiflcateur existentiel µa l’intérieur de la règle.
{ La loi du Modus ponens établit que de B0 (un ensemble de faits) et A:-B (une règle A ( B1; B2; : : : ; Bn), on peut déduire A0 .
{ Un fait est un cas spécial de règle avec aucun antécédents, i.e. une règle qui a son corps vide. Une règle se termine donc aussi par un point. Une requ^ete ne possède qu’un corps et pas de t^ete.
{ Une règle permet d’exprimer une requ^ete sous forme de plusieurs requ^etes (plus simples on l’espère !).

Terme

{ Un terme est soit une constante, une variable ou un terme composé. Il sert aµ déflnir des objets.
{ Une constante peut ^etre un nombre (par exemple, 1, -5, 0.5), ou un atome (une cha^‡ne de lettres qui commence par une minuscule, par exemple abraham ou une cha^‡ne entre ’ ’, par exemple ’composante X’).
{ Un terme composé est formé d’un foncteur, soit son nom f , et de ses arguments ti, donc
de la forme f (t ; : : : ; t ) et d’arité n. , ¶ et
1 n tree(tree(nil,3,nil),5,R) père(Luc,Eric) foo(X) sont des exemples de termes composés. On fait habituellement référence aux prédicats en employant la structure foncteur/arité.
{ Certains prédicats ont certaines restrictions quand aux types d’arguments admissibles. Convention : f(+Arg1, ?Arg2, -Arg3), le + signiflant un argument d’entrée qui doit ^etre instancié lors de l’appel, le – référant aµ un argument de sortie qui doit ^etre non-instancié lors de l’appel et qui sera instancié si le prédicat réussit, et le ? réfère aµ un argument d’entrée ou de sortie, instancié ou non-instancié.
{ Un terme est dit ground s’il ne contient pas de variables.
{ Un but est soit un atome ou un terme composé. On utilise le terme but pour illustrer que Prolog envisage les questions comme autant de buts aµ satisfaire.
{ Le type d’un objet est déflni entièrement par son apparence syntaxique.
{ La portée lexicale d’une variable est d’une seule clause. Le m^eme nom dans deux clauses correspond donc aµ deux variables difiérentes.

Opérateurs artihmétiques

Des opérateurs arithmétiques peuvent ^etre programmés en utilisant des clauses logiques, mais ceci n’est pas très e–cace. Des opérateurs ont donc été prédéflnis pour efiectuer ces opérations. Ils occasionnent toutefois des contraintes sur les types possibles des arguments.

Prédicats de controle

Il existe aussi des prédicats qui permettent de contr^oler l’exécution du programme. Nor-malement, le programme cherche de fa»con non-déterministe pour une solution, efiectuant des retours en arrière et terminant quand la première solution est trouvée. Les prédicats de contr^ole permettent de modifler ce comportement. La virgule pour la conjonction entre les buts dans le corps d’une clause est un de ces prédicats.
L’usage du cut est contreversé, car son utilisation doit souvent ^etre interprétée de fa»con procédurale, ce qui va aµ l’encontre du style de programmation logique. Toutefois, son usage peut améliorer l’e–cacité de programmes sans compromettre leur interprétation. Pour le cours, nous allons tenter de ne pas l’utiliser, car des consignes doivent ^etre respectées lors de son utilisation et ces aspects s’éloignent des objectifs du cours.

Listes

La liste est aussi une structure de données importante en Prolog. Elle s’exprime par la forme [X|Xs], oµu X est la t^ete de la liste et Xs la queue de la liste. La liste vide se représente par []. Voici quelques exemples :
[a,b,c,d,e]
[a,[1,2],[b],q,r,s,[[3],2]]

1 Objectifs
2 Introduction 
3 Programmation logique avec Prolog 
3.1 Faits
3.2 Requetes
3.3 Rµegles
3.4 Terme
3.5 Operateurs artihmetiques
3.6 Predicats de contr^ole
3.7 Listes
3.8 Programme logique
3.9 Exercices serie A
4 Structures de programmes couramment utilisees 
4.1 Points importants
4.2 Exercices série B
4.3 Exercices série C
4.4 Exercices série D
5 Resolution de problemes par deduction logique 
5.1 Exercices série E
5.2 Puzzles ou enigmes logiques
5.3 Exercices serie E (suite)
A Notions importantes sur LPA Prolog
B Solutions aux exercices