CSI 3525 - Groupe de discussion #1

Initiation a Prolog

Revisions

I. Prolog, langage declaratif

 

    1. Introduction

    Prolog est fondamentalement different des langages de programmation classiques que l'on utilise pour les gros projets de developpement logiciel (Ada, Java ou C++ par exemple). En effet, il s'agit d'un langage dit declaratif. Cela signifie que le programmeur donne moins de details sur la facon dont il veut arriver a un resultat : l'interpreteur lit un certain nombre de faits et de regles et en deduit, par des inferences logiques, les resultats qu'il peut obtenir. Pour caricaturer, on peut dire qu'un utilisateur de Prolog est plus interesse par le resultat que par la facon d'y parvenir (ce qui fait une difference fondamentale avec les langages imperatifs, ou le programmeur decrit en detail toutes les etapes de son algorithme.
    Cette apparente "intelligence" de la machine est basee sur l'utilisation de la logique symbolique dont nous allons maintenant etudier les regles de base. En cela, Prolog est le langage de la logique symbolique et il lui doit d'ailleurs son nom (PROgrammation LOGique).
 

      2. Logique symbolique

    La logique est l'etude des propositions. Les definitions d'une proposition sont multiples. Disons pour simplifier qu'il s'agit d'un enonce portant une valeur de verite (Vrai ou Faux). Il s'agit donc :     Pour cela, on utilise les symboles suivants :
Ø : NON logique
º : EQUIVALENCE logique
Ç : ET logique
È : OU logique
É : IMPLIQUE
Ì : RESULTE
 

3. Forme normale et clauses de Horn

    Pour concevoir un langage informatique logique, il est apparu necessaire de restreindre le plus possible les differentes manieres d'exprimer une relation logique (typiquement la relation si A alors B). C'est la raison pour laquelle on a choisi de privilegier une forme d'expression de liens logiques que l'on appelle forme normale :
B1ÈB2È...ÈBN Ì A1ÇA2Ç...ÇAM
Avec N entier naturel et M entier naturel superieur ou egal a 1.
Cette formule exprime tout simplement que si toutes les propositions Ai (i variant de 1 a M) sont vraies alors au moins une des propositions Bi est vraie.
    On a choisi de simplifier encore cette forme en ne considerant que les cas N=0 et N=1. Il s'agit des clauses de Horn.
N = 0 correspond a A1ÇA2Ç...ÇAM vraies et permet de definir des faits dans Prolog. Il s'agit des hypotheses desquelles partira Prolog pour effectuer le raisonnement.
N = 1 correspond a B Ì A1ÇA2Ç...ÇAM, c'est a dire que si toutes les propositions Ai sont vraies alors B est vraie.
 

4. La semantique de Prolog

    Avant de passer a l'explication proprement dite des commandes Prolog, insistons sur cette autre particularite de Prolog. La semantique, c'est a dire le sens qui reside derriere les commandes informatiques, n'a rien a voir avec les autres langages car la part la plus importante de la signification est uniquement dans la tete du programmeur.
    Alors que dans un langage imperatif, l'ecriture d'un while par exemple signifie une boucle aussi bien pour le programmeur que pour le compilateur, en Prolog, la plupart du code a beaucoup plus de sens pour celui qui l'ecrit que pour l'interpreteur. Clarifions cela sur un exemple :
homme(claude).
pere(claude,jean).
La personne ecrivant ces lignes de code voudra vraissemblablement dire que Claude est un homme et qu'il est le pere de Jean. Pourtant, pour l'interpreteur Prolog, homme et pere ne sont que des foncteurs (nous reviendrons sur ce terme ulterieurement) sans lien avec une quelconque realite. Mais au fur et a mesure que le programme s'etoffera, les relations deviendront de plus en plus nombreuses et les deductions faites par Prolog (par simple logique) seront transposables dans la semantique du programmeur.
 

II. Les commandes Prolog et le principe du retour arriere

 

1. Syntaxe de Prolog

    La syntaxe de Prolog est relativement simple et basee sur les clauses de Horn evoquees precedemment. Dans le mode d'acquisition des faits et des regles (ou dans un fichier Prolog), on saisit les hypotheses et les inferences sur lesquelles on desire que Prolog obtienne des conclusions. Pour les faits (on parle aussi d'expressions atomiques pour dire que la ligne n'est constituee que d'une simple proposition), on utilise un terme compose d'un foncteur (appele ainsi par analogie avec les fonctions mathematiques et designant en general une caracteristique) et d'un nombre non nul de parametres (qui sont les elements verifiant la relation). On peut par exemple ecrire :

homme(claude).
parent(claude,jean).
femme(claudine).
parent(claudine,jean).

    Pour les regles, on transpose la forme normale, le symbole resulte se traduisant par :- et le symbole ET logique par une virgule. Les regles sont definies sur des variables muettes que l'on distingue des constantes (les parametres dans la declaration de faits) en ecrivant leur premiere lettre en majuscule. Voici un exemple de regle :

pere(X,Y) :- parent(X,Y), homme(X).

Cela signifie que si X est le parent de Y et si X est un homme alors X est le pere de Y (mais insistons sur le fait que les significations "humaines" de ces mots n'entrent jamais dans l'intrepreteur de Prolog).
 

2. Le fonctionnement de Prolog

    Nous en savons desormais assez pour expliquer le fonctionnement de base de Prolog. L'interpreteur procede par instanciation et unification. Pour repondre a une question donnee, il passe en revue les regles qu'il connait (et qui sont susceptibles d'aboutir au resultat) en instanciant les variables muettes avec les constantes stockees dans sa base de faits. Ensuite, il essaie d'unifier les hypotheses qu'il lit dans les regles avec les propositions vraies declarees par l'utilisateur.
    Reprenons l'exemple precedent et supposons que nous avons tape les lignes precedentes. Nous posons maintenant a Prolog la question :

pere(X,jean).

Apres avoir verifie que le foncteur pere n'est pas dans la base de faits, Prolog va donc chercher les regles qui le concerne dans la base de regles. Une fois trouvee la seule regle de notre base, il va chercher un X tel que parent(X,jean) et homme(X) soient vrais. Il se trouve que l'instanciation X = claude conduit immediatement au resultat et Prolog va donc repondre X = claude.

    Imaginons maintenant que l'on rajoute la regle suivante :

mere(X,Y) :- parent(X,Y),femme(X).

et que l'on demande mere(X,jean) a l'interpreteur. Alors, de meme que precedemment, il va chercher dans la base de fait un X tel que parent(X,jean) et femme(X) soient simultanement vraies et le premier candidat sera... claude puisque Prolog parcourt la base de faits dans l'ordre dans laquelle nous l'avons entree. Mais l'instanciation X = claude ne fonctionnera pas a cause de la condition femme(claude) qui ne figure pas dans la base de fait. C'est une fois dans ce cul-de-sac que l'on comprend l'un des principes fondateurs de Prolog : le retour arriere ou backtracking. Dans cette impasse, Prolog reviendra a son choix precedent (ici l'affectation X = claude) pour le modifier et faire un autre choix (dans notre exemple, ce sera la bonne instanciation X = claudine). Le Backtracking fait toute la force du langage Prolog et n'a pas de limite (l'interpreteur remontera autant de choix qu'il faudra jusqu'a trouver une solution ou jusqu'a les avoir explorees toutes). La contre-partie est que Prolog est un langage d'execution relativement lente pour un certain nombre de taches mais il fonctionne bien pour certaines applications logiques (comme les systemes experts).
 

3. Complements de syntaxe

    Il existe un moyen de faire de l'arithmetique dans Prolog, il s'agit de l'operateur is que l'on utilise ainsi :

A is B/17 + C

Avec la condition fondamentale suivante : la partie gauche (a affecter) doit imperativement etre non instanciee alors que la partie droite doit etre toute instanciee. Impossible donc d'envisager une commande du genre i is i+1. Pour plus de precisions sur cet operateur is, consulter l'exemple de la page 646 du manuel de cours.

    La definition d'une liste dans Prolog est la suivante : [ premierelement | listedesautreselements ]. Pour comprendre un peu mieux cette definition, etudions le fonctionnement de quelques programmes :

extraire(X,[X|L],L).
extraire(X,[Y|L],[Y|Reste]) :- extraire(X,L,Reste).

Le programme sert a extraire un element d'une liste. On ecrit trois parametres, les deux premiers etant l'element a extraire et la liste complete (que l'on passera plutot en entree), le dernier etant le resultat que l'on desire, la liste sans l'element (c'est-a-dire que l'appel ressemblera a extraire(element,liste,Resultat) - NB la majuscule a Resultat montrant que c'est bien le parametre qu'il nous manque). Si l'element a extraire n'est pas dans la liste, l'intrepreteur examine la deuxieme regle. Celle-ci lui commande d'oter le premier element de la liste et de faire un appel recursif sur le reste de la liste. Lorsque Prolog aura trouve l'element a extraire, il appliquera alors la premiere ligne pour instancier L et refermera toutes les recursions en ajoutant en tete de liste, tous les elements qu'il avait enleves.

    La puissance de Prolog fait qu'avec le programme, on peut faire exactement l'operation inverse, c'est-a-dire ajouter un element avec l'appel suivant : extraire(elementaajouter,Resultat,liste). L'interpreteur instanciera alors le parametre [X|L] pour donner le resultat (il mettra d'abord l'element a ajouter au debut de la liste puis aux autres emplacements si l'on exige d'autres resultats avec la commande ;)

    Etudions maintenant le programme permutation qui donne toutes les permutations d'une liste et qui est base sur le programme extraire.

permutation([ ],[ ]).
permutation([Premier | Reste],Listepermutee) :- permutation(Reste,Restepermute),
                                                                                    extraire(Premier,Listepermutee,Restepermute)

Dans un appel comme permutation(liste,L), l'interpreteur otera par recursion tous les elements de liste jusqu'a arriver a la proposition permutation([ ],[ ]). qui provoquera l'instanciation du second parametre a la liste vide. Ensuite, les elements seront rajoutes par extraire dans tous les ordres possibles (si l'on demande a Prolog une recherche exhaustive, toujours avec l'operateur ;).

    Nous n'avons pas evoque le cut : ! qui permet d'eviter le backtracking (on le place dans les regles a la place d'une hypothese normale et sa fonction est de bloquer le retour en arriere pour toutes les hypotheses precedentes) ou le fail (proposition toujours fausse). Signalons tout de meme que l'emploi du cut n'est pas recommande (meme s'il est parfois inevitable) car il brise l'absence d'ordre dans les hypotheses, fondement de la logique et donc de Prolog.

    Pour en savoir un peu plus sur les limites de Prolog et ses applications, lire le manuel de cours des pages 652 a 660.
 

Pour toutes questions ou remarques, n'hesitez pas : rigouste@site.uottawa.ca .