Licence Informatique

Module Théories et Modèles pour l'Informatique II


Option Programmation logique en Prolog

 

Philippe Collard

 


Atelier 2 : Fonctionnement du moteur Prolog


 

Le moteur prolog est sollicité par une question. Il gère :

·        La pile des buts à effacer (atteindre) pour répondre à la question

·        L’ensemble des liaisons sur les variables qui ont permis d’effacer les buts

 

Initialement la pile contient la question

 

Des faits pour effacer une question sans variable

boite(a).            %2

boite(b).            %1

boite(c).            %0

 


?- boite(b).

yes

 

E={}

P=boite(b).

1

E={}

P=.

succès

 

 


?- boite(g).

no

 

E={}

P=boite(g).

échec

 

 


Des faits pour effacer une question avec variable

boite(a).            %2

boite(b).            %1

boite(c).            %0

 

?- boite(X).

X=a ;

X=b ;

X=c ;

no

 

initialement la variable X est libre

E={X=_}

P=boite(X).

%2

E={X=a}

P=.

succès

%1

E={X=b}

P=.

succès

%0

E={X=c}

P=.

succès

échec

 

Prolog est non déterministe, il effectue un retour arrière (backtrack) sur succès pour fournir toutes les solutions (en fait il faut taper ; pour forcer le backtract)

 

On considère la procédure Prolog suivante :

pere(michel,jacques).         %2

pere(michel,julien).          %1

pere(jacques,jean).           %0

 

Effacer la question 

?- pere(X,jacques).

E={X=_}

P=pere(X,jacques).

 

 

Effacer la question 

?- pere(michel,Y).

E={Y=_}

P=pere(michel,Y).

 

 


Des faits et des règles pour effacer une question sans variable

pere(michel,jacques).             %2

pere(michel,julien).              %1

pere(jacques,jean).               %0

 

a_un_pere(Z) :- pere(_, Z).       %0

 

Effaçons la question 

?- a_un_pere(julien).

E={}

P=a_un_pere(julien).

0

E={}

P=pere(_,julien).

1

E={}

P=.

succès

 

 

Appliquer une règle consiste à substituer sa queue à sa tête au sommet de la pile

 

Cette substitution ne peut avoir lieu que si le sommet de la pile peut être mis en correspondance (unifié) avec la tête de la règle moyennant des liaisons sur les variables

 

Ici il n’y a pas de backtrack car sans variable dans la question il ne peut y avoir plusieurs solutions

 

 


Des faits et des règles pour effacer une question avec variable

pere(michel,jacques).             %2

pere(michel,julien).              %1

pere(jacques,jean).               %0

 

a_un_pere(Z) :- pere(_, Z).       %0

 

Effaçons la question 

?- a_un_pere(X).

E={X=_}

P=a_un_pere(X).

0

E={X=_}

P=pere(_,X).

2

E={X=jacques}

P=.

    succès

1

E={X=julien}

P=.

    succès

0

E={X=jean}

P=.

    succès

échec

 

On considère le programme suivant :

enfant(jacques,michel).               %2

enfant(julien,lola).                  %1

enfant(michel,isabelle).              %0

 

sexe(lola,f).                         %5

sexe(isabelle,f).                     %4

sexe(sylvie,f).                       %3

sexe(jacques,h).                      %2

sexe(michel,h).                       %1

sexe(julien,h).                       %0

 

mere(X,Y) :- sexe(X,f) , enfant(Y,X). %0

 

 

Effacer la question :

?- mere(Z, michel).

E={Z=_}

P=mere(Z,michel).

 

Noter bien que Prolog backtrack aussi bien sur succès (tapez ;) que sur échec afin de trouver toutes les solutions

 


Le mécanisme d’unification

Deux prédicats sont unifiables s’ils ont le même nom, la même arité et si leurs arguments sont unifiables

 

Deux constantes sont unifiables si elles sont identiques

 

Deux variables sont unifiables, elles deviennent identiques

 

Une variable est unifiable avec une constante, un terme composé ou une liste. La variable est alors instanciées (liée) avec la valeur correspondante

 

Deux termes composés sont unifiables s’ils ont le même nom, la même arité et si leurs arguments sont unifiables

 

Deux listes sont unifiables si elles ont le même nombre d’éléments et si leurs éléments sont unifiables

 


Structure de liste

Notation en extension  [p,r,o,l,o,g]

Notation [tête|queue] [p|[r,o,l,o,g]]

Liste vide []

 

·        Simplifier les écritures suivantes (préciser dans chaque cas le nombre d’éléments) :

[0|[]]

[[]|[]]

[[]|[0]]

[1|[2,3]]

[[2,3]|[1]]

 

·        Définir la procédure print_liste/1

?-print_liste([a,b,c]).

abc

yes

 

On pourra utiliser le prédicat prédéfinit write/1 qui s’efface en affichant par effet de bord son argument

 

·        Définir la procédure print_liste_inv/1

?-print_liste_inv([a,b,c]).

cba

yes


·        Définir la procédure element_de/2 qui met en relation une liste et un de ses éléments

?-element_de([a,b,c],b).      %mode(in,in)

yes

 

?-element_de([a,b,c],f).      %mode(in,in)

no

 

?-element_de([a,b,c],X).      %mode(in,out)

X=a ;

X=b ;

X=c ;

no

 

?-element_de(X,a).            %mode(out,in)

 


·        Définir la procédure concat/3 qui met en relation deux listes et leur concaténation

?-concat([1,2],[a,b],[1,2,a,b]).  %mode(in,in,in)

yes

 

?-concat([1,2],[a,b],[1,2,a,c]).  %mode(in,in,in)

no

 

?-concat([1,2],[a,b],X).          %mode(in,in,out)

X=[1,2,a,b];

no

 

?-concat([1,2],X,[1,2,a,b]).      %mode(in,out,in)

X=[a,b];

no

 

?-concat(X,[a,b],[1,2,a,b]).      %mode(out,in,in)

X=[1,2];

no

 

?-concat(X,Y,[1,2,a,b]).          %mode(out,out,in)


Voici un unique fait prolog qui réalise la concaténation de deux listes données.

concatener(moins(X,Z), moins(Z,Y), moins(X,Y)).

On pourra interpréter le terme composé moins(Liste, Fin) comme la liste Liste à laquelle on a enlever la Fin

1.     Effacer la question et expliquer comment (pourquoi) on obtient L=[1,2,3,4,5]

?- Concatener(moins([1,2,3|Q],Q), moins([4,5],[]), moins(L,[])).

2.     En remarquant que la variable Y est toujours instanciée avec la liste vide dans la question, simplifier la définition de concatener/3

 


·        Définir la procédure retirer(e,l1,l2) qui met en relation deux listes l1 et l2l2 est la liste l1 à laquelle on a retiré la première occurrence de e

 

Tester cette procédure :

?- retirer(b,[a,b,c],L).        %mode(in,in,out)

 

?- retirer(a,L,[b,c]).          %mode(in,out,in)

 

?- retirer(X,[a,b,c],[a,c]).    %mode(out,in,in)

 

Expliquer les résultats obtenues. Remplacer le prédicat prédéfini \= par \== (jeter un œil sur la doc pour en savoir plus …)

?-apropos(\==).


·        Définir la procédure maplist/3 qui met en relation une liste, un prédicat binaire et une seconde liste dont les éléments sont les transformés par le prédicat des éléments correspondants de la première liste. Par exemple :

carre(X,Y) :- Y is X*X.

 

 ?- maplist([1,2,3],carre,L).

L=[1,4,9]

 

Pour définir maplist/3, on pourra utiliser le prédicat prédéfini =.. qui convertit un terme composé (ou un prédicat) en liste ou bien une liste en terme compose. Par exemple :

?- carre(2,Y) =.. X.

X=[carre,2,Y]

 

?- B =.. [carre,2,Y].

B=carre(2,Y).

 


On veut mettre en œuvre le prédicat prédéfini bagof/3 qui met en relation une variable X, un prédicat p et une liste l qui contient toutes les instances de la variable résultant de l’effacement du prédicat p.

1.     On considère le prédicat boite/1 qui définit en extension la concept de boite. Ecrire un programme qui permet d’obtenir la liste des boites

 

2.     On considère le prédicat parent/2

enfant(jacques,anna).                 %3

enfant(jacques,michel).               %2

enfant(julien,lola).                  %1

enfant(michel,isabelle).              %0

Ecrire un programme qui permet d’obtenir la liste des enfants.

Ecrire un programme qui permet d’obtenir la liste des parents.

On pourra utiliser le prédicat ^ (voir doc)

 

3.     Ecrire un procédure bagofSr/3 qui permet d’obtenir la liste retournée par bagof sans répétition

 

4.     Utiliser le prédicat setof/3 à la place de bagof/3

 

5.     On considère le prédicat prix/2  qui met en relation un article et son prix

prix(mac,1000).               %2

prix(pc,7000).                %1

prix(pda,500).                %0

Définir un prédicat prix_total/1 dont l’argument représente la somme des prix de tous les articles