Licence Informatique

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


Option Programmation logique en Prolog


Correction


Atelier 3 : Contrôle du moteur Prolog


L’outil de base pour agir sur le comportement de Prolog est un prédicat prédéfini appelé le CUT et noté !

Une définition :

·        Le cut est un prédicat déterministe qui peut toujours être effacé

·        Son effacement a pour effet de « couper » les choix en attente portant

·         sur le but qui l’a introduit dans le pile (le but père)

·         ainsi que sur tous les buts introduits depuis son introduction

 


Exercice 1 : le Cut pour obtenir une unique solution

chiffre(0).          %9

chiffre(1).          %8

chiffre(2).          %7

chiffre(3).          %6

chiffre(4).          %5

chiffre(5).          %4

chiffre(6).          %3

chiffre(7).          %2

chiffre(8).          %1

chiffre(9).          %0

 

·         Poser les deux questions suivantes :

?- chiffre(C).

 

?- chiffre(C), !.

 

·         Dessiner le schéma d’effacement de la question précédente

 

·         Définir un prédicat  premier_chiffre/1 qui permet d’obtenir uniquement la première solution fournie par Prolog.

premierChiffre(X) :- chiffre(X), !.

·         Définir un prédicat first/2 qui prend en argument un prédicat d’arité 1 et une variable. L’effacement en mode (in,out) de first donne la première solution de l’effacement du prédicat en mode (out). Par exemple l’effacement de la question first(chiffre,X) est équivalent à l’effacement de premier_chiffre(X)

first(P,X) :- B =.. [P,X], B, ! .

·         Définir un prédicat deuxieme_chiffre/1

 deuxiemeChiffre(X) :- chiffre(X), premierChiffre(Y), X \== Y, !.


Exercice 2 : le cut pour optimiser le moteur

sup(X,Y,X) :- Y =< X.         %1

sup(X,Y,Y) :- X  < Y.         %0

 

·         Poser les deux questions suivantes :

?- sup(2,3,X).

?- sup(3,2,X).

?- sup(3,2,3).

?- sup(3,2,2).

 

·         Dessiner le schéma d’effacement des questions suivantes :

?-sup(2,3,X).

?-sup(3,2,X).

 

·         Modifier le code de la procédure sup/3 pour optimise son effacement

sup(X,Y,X) :- Y =< X, ! .        %1

sup(X,Y,Y) :- Y >  X.            %0

 

retirer(T,[T|Q],Q).                            %1

retirer(X,[T|Q],[T|L]) :- retirer(X,Q,L).      %0

?- retirer(c,[a,b,c,d],L).

?- retirer(c,[a,b,c,d,c,e],L).

 

retirer(T,[T|Q],Q) :- !.

retirer(X,[T|Q],[T|L]) :- retirer(X,Q,L).


Exercice 3 : le cut pour définir la négation

Le (méta)prédicat not/1 qui prend en argument un prédicat et échoue si ce prédicat réussit et réussit dans le cas contraire.

not(P) :- P! , fail.           %1

not(_).                           %0

 

Par exemple, on devra observer les résultats suivants selon que le fait pere(jean) est ou bien n’est pas déclaré

?-pere(jean).

yes

?-not(pere(jean)).

no

 

?-pere(jean).

no

?-not(pere(jean)).

yes

 

·                     Tester les questions suivantes et noter les différences de comportement de Prolog. Expliquer en dessinant le schéma d’effacement de la dernière question

?-pere(jean).

yes

?-not(not(pere(jean))).

yes

 

?-pere(jean).

no

?-not(not(pere(jean))).

no

 

?-pere(X).

X=jean

yes

?-not(not(pere(X))).

yes

 


Exercice 4 : le cut pour implémenter une structure alternative

Soit à coder le pseudo-code suivant :

Proc(X)

Si (X=0) écrire(‘nul’)

Sinon écrire(‘non nul’)

 

Voici une traduction « directe » en Prolog :

proc(X) :- X=0 , ! , write(nul’).    %1

proc(_) :- write(‘non nul’).          %0

 

?-proc(0).

1

0=0 , ! , write(nul’).

=

! , write(nul’).

%  %  !

write(nul’).

         write

.

succès

 

?-proc(1).

0

1=0 , ! , write(‘nul’).

échec

1

P= write(‘non nul’).

write

P=.

succès

 

·        Définir un méta-prédicat si/3 qui implémente une alternative. Tester ce prédicat sur l’exemple précédent.

si(C, Alors, _) :- C, !, Alors.

si(_,_,Sinon) :- Sinon.

proc(X) :- si(X=0, write('nul'),write('non nul')).

 

proc(Delta)

si (Delta>=0)

si (Delta=0) écrire(‘une solution’)

Sinon        écrire(‘deux solutions’)

Sinon écrire(‘pas de solution’)

proc1(Delta) :-

si(Delta>=0,

            si(Delta=0,

                          write('une solution'),

                          write('deux solutions')),

            write('pas de solution')).


Exercice 5 : le cut pour implémenter une structure répétitive

Pour coder une structure alternative de type (1,n), on peut utiliser le prédicat prédéfini repeat/0 qui  pourrait être défini récursivement comme suit :

repeat.                       %1

repeat :- repeat              %0

 

Pour illustrer sa mise en œuvre, nous allons traduire le pseudo-code suivant :

Proc

Repeter

a

b

Jusque c

FinProc

 

proc :- repeat, a, b, c, !.   %0

 

On suppose que les prédicats a et b sont déterministes et s’effacent avec succès

 

·        Effacer la question ?-proc.

 

·        Traduire le procédure suivante :

répéter

Lire(Note)

Si (Note>10) écrire(‘admis’) sinon écrire(‘non admis’)

jusque (Note=0)

 

proc :-

repeat,

            read(Note),

            si(Note>=10, write('admis'),write('non admis')),

     Note=0 , !.


Exercice 6 : Un générateur de nombres entiers

pour(K,K,_).                                                %1

pour(K,Debut,Fin):- Debut<Fin,
Suivant is Debut+1,
pour(K,Suivant,Fin).                  %0

 

?-pour(K,0,3).

 

pour(D,D,_) .

pour(_,F,F) :- !, fail.

pour(K,D,F) :- S is D+1, pour(K,S,F).