Upload
lita
View
51
Download
0
Embed Size (px)
DESCRIPTION
Contrôle du moteur Prolog. Nous avons étudié le fonctionnement du moteur Prolog. Nous allons maintenant montrer qu’il est possible de le contrôler L’outil de base pour agir sur le comportement de Prolog est un prédicat prédéfini appelé le CUT (ou coupure). La coupure (cut). - PowerPoint PPT Presentation
Citation preview
1
Contrôle du moteur Prolog
2
• Nous avons étudié le fonctionnement du moteur Prolog. Nous allons maintenant montrer qu’il est possible de le contrôler
• L’outil de base pour agir sur le comportement de Prolog est un prédicat prédéfini appelé le CUT (ou coupure)
3
La coupure (cut)
• 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– ainsi que sur tous les buts introduits depuis son
introduction
4
Un premier exemple
a :- b. %0
b :- c, !, d. %1b. %0
c. %1c :- e , f. %0
P = a.0P = b.1P = c,!,d.1P = !,d. !P=d.no
5
Effet du Cut dans une questionavec variables
b(1). %1b(2). %0
c(1). %1c(2). %0
{X=_,Y=_} P=b(X),c(Y).1
{X=1,Y=_} P=c(Y).1
{X=1,Y=1} P=. succès0
{X=1,Y=2} P=. succès{X=_,Y=_} P=b(X),c(Y).0
{X=2,Y=_} P=c(Y).1
{X=2,Y=1} P=. succès0
{X=2,Y=2} P=. succès
6
Effet du Cut dans une questionavec variables
b(1). %1b(2). %0
c(1). %1c(2). %0
{X=_,Y=_} P=b(X),!,c(Y).1
{X=1,Y=_} P=!, c(Y). !
{X=1,Y=_} P=c(Y).1{X=1,Y=1} P=. succès0{X=1,Y=2} P=. succès
le cut rend déterministe les prédicats qui le précèdent
7
Effet du Cut dans la queue d’une règle
a(X,Y):-b(X),c(Y). %1
a(3,3). %0 b(1). %1b(2). %0 c(1). %1
c(2). %0
{X=_,Y=_} P=a(X,Y).1 {X=_,Y=_} P=b(X),c(Y).
1 {X=1,Y=_} P=c(Y).1 {X=1,Y=1} P=. succès
0 {X=1,Y=2} P=. succès0 {X=2,Y=_} P=c(Y).
1{X=2,Y=1} P=. succès
0{X=2,Y=2} P=. succès
0 {X=3,Y=3} P=b(3),c(3). no
8
Effet du Cut dans la queue d’une règle
a(X,Y):-b(X),!, c(Y). %1
a(3,3). %0 b(1). %1b(2). %0 c(1). %1
c(2). %0
{X=_,Y=_} P=a(X,Y).1
{X=_,Y=_} P=b(X), ! ,c(Y).1
{X=1,Y=_} P= !,c(Y). !
{X=1,Y=_} P=c(Y).1
{X=1,Y=1} P=. succès0
{X=1,Y=2} P=. succès
9
Effet du Cut sur le réponse(succès ou bien échec)
a :- fail.%1a . %0
P = a.1
P = fail .échec
0P = .succès
10
Effet du Cut sur le réponse(succès ou bien échec)
a :- !, fail. %1a . %0
P = a.1
P = !, fail . !
P = fail .échec
11
Effet du Cut sur le réponse(instanciation de variable)
a(_). %1
a(1). %0
{X=_} P = a(X).1
{X=_} P = .succès
0{X=1} P = .succès
12
Effet du Cut sur le réponse(instanciation de variable)
a(_):- !. %1
a(1). %0
{X=_} P = a(X).1
{X=_} P = ! . !
{X=_} P = .succès
13
A quoi cela sert-il ?obtenir une unique solution
chiffre(0). %9chiffre(1). %8chiffre(2). %7chiffre(3). %6chiffre(4). %5chiffre(5). %4chiffre(6). %3chiffre(7). %2chiffre(8). %1chiffre(9). %0
Comment obtenir uniquement le premier
chiffre (0) ?
?- chiffre(X).
14
A quoi cela sert-il ?obtenir une unique solution
chiffre(0). %9chiffre(1). %8chiffre(2). %7chiffre(3). %6chiffre(4). %5chiffre(5). %4chiffre(6). %3chiffre(7). %2chiffre(8). %1chiffre(9). %0
Comment obtenir uniquement le premier
chiffre (0) ?
?- chiffre(X), ! .
15
A quoi cela sert-il ?obtenir une unique solution
chiffre(0). %9chiffre(1). %8chiffre(2). %7chiffre(3). %6chiffre(4). %5chiffre(5). %4chiffre(6). %3chiffre(7). %2chiffre(8). %1chiffre(9). %0
{X=_} P = chiffre(X) , ! .9 {X=0} P = !.
!{X=0} P=. succes
16
A quoi cela sert-il ?obtenir une unique solution
chiffre(0). %9chiffre(1). %8chiffre(2). %7chiffre(3). %6chiffre(4). %5chiffre(5). %4chiffre(6). %3chiffre(7). %2chiffre(8). %1chiffre(9). %0
premier_chiffre(X) :- chiffre(X), ! .
Comment obtenir uniquement le premier
chiffre (0) ?
17
A quoi cela sert-il ?obtenir une unique solution
chiffre(0). %9chiffre(1). %8chiffre(2). %7chiffre(3). %6chiffre(4). %5chiffre(5). %4chiffre(6). %3chiffre(7). %2chiffre(8). %1chiffre(9). %0
premier_chiffre(C) :- chiffre(C), ! . %0
{X=_} P=premier_chiffre(X).0
{X=_} P=chiffre(X),!. 9 {X=0} P=!.
!{X=0} P=. succes
18
A quoi cela sert-il ?optimiser le moteur
max(X,Y,X) :- Y =< X. %1max(X,Y,Y) :- X < Y. %0
{X=_} P= max(2,3,X).1 {X=2} P= 3=<2. no
0{X=3} P= 2<3.<{X=3} P=. succes
19
A quoi cela sert-il ?optimiser le moteur
max(X,Y,X) :- Y =< X. %1max(X,Y,Y) :- X < Y. %0
{X=_} P= max(3,2,X).1 {X=3} P= 2=<3.=<{X=2} P=. succes
0{X=2} P= 3<2. no
20
A quoi cela sert-il ?optimiser le moteur
max(X,Y,X) :- Y =< X, ! . %1max(X,Y,Y) :- X < Y. %0
{X=_} P= max(3,2,X).1 {X=3} P= 2=<3, !.
=<{X=3} P= !.
!{X=3} P=. succes
21
A quoi cela sert-il ?optimiser le moteur
max(X,Y,X) :- Y =< X, ! . %1max(X,Y,Y) :- X < Y. %0
{X=_} P= max(2,3,X).1 {X=2} P= 3=<2, !. no
0{X=3} P= 2<3.<
{X=3} P=. succes
22
Peut-on encore simplifier ?
max(X,Y,X) :- Y =< X, ! . %1max(_,Y,Y). %0
{X=_} P= max(3,2,X).1 {X=3} P= 2=<3, !.
=<{X=3} P= !.
!{X=3} P=. succes
23
Peut-on encore simplifier ?
max(X,Y,X) :- Y =< X, ! . %1max(_,Y,Y). %0
{X=_} P= max(2,3,X).1 {X=2} P= 3=<2, !. no
0{X=3} P=. succes
24
Peut-on encore simplifier ?
max(X,Y,X) :- Y =< X, ! . %1max(_,Y,Y). %0
P= max(2,3,2).1 {X=2} P= 3=<2, !. no
25
Peut-on encore simplifier ?
max(X,Y,X) :- Y =< X, ! . %1max(_,Y,Y). %0
P= max(2,3,3).0P=. succes
26
Peut-on encore simplifier ?
max(X,Y,X) :- Y =< X, ! . %1max(_,Y,Y). %0
P= max(3,2,2).0P=. succes
27
A quoi cela sert-il ?définir la négation
non_c :- c , ! , fail. %1non_c. %0
P=non_c.1P= c, ! , fail.cP= ! , fail.
!P= fail. no
28
A quoi cela sert-il ?définir la négation
non_c :- c , ! , fail. %1non_c. %0
P=non_c.1
P= c, ! , fail. no0
P= . succes
29
Définir un (méta) prédicatnot/1
• prend en argument un prédicat– échoue si ce prédicat réussit– réussit dans le cas contraire
not(P) :- P , ! , fail.%1
not(_).%0
30
A quoi cela sert-il ?implémenter une structure alternative
proc(X) :- X=0, ! ,write(‘nul’). %1
proc(_) :- write(‘non nul’). %0
Proc(X)Si (X==0) ecrire(«nul»)Sinon ecrire(«non nul»)
FinProc
31
A quoi cela sert-il ?implémenter une structure alternative
proc(X) :- X=0,!,write(‘nul’). %1proc(_) :- write(‘non nul’). %0
P=proc(0).1
P= 0=0, !, write(‘nul’).=
P= ! , write(‘nul’). !
P= write(‘nul’).write
P=. succès
32
A quoi cela sert-il ?implémenter une structure alternative
proc(X) :- X=0,!,write(‘nul’). %1proc(_) :- write(‘non nul’). %0
P=proc(1).1
P= 1=0, !, write(‘nul’). no
0 P= write(‘non nul’).write
P=. succès
33
Définir un (méta) prédicatsi/3
• prend en argument trois prédicats– Si le premier s’efface alors effacer le second – Sinon effacer le troisième
si(C,P,_) :- C, !, P. %1
si(_,_,Q) :- Q. %0
34
A quoi cela sert-il ?implémenter une structure répétitive
repeat. %1repeat :- repeat %0
proc :- repeat, a, b, c, !. %0
Procrepeter
ab
jusque c
35
repeat. %1repeat :- repeat %0
proc :- repeat, a, b, c, !. %0
On suppose que les prédicats a et b sont déterministes et s’effacent avec succès
P= repeat,a,b,c,!.1 P= a,b,c,!.
a P= b,c,!.b P= c,!. No
0 P= repeat,a,b,c,!.a P= b,c,!b P= c,!.c P= !.
! P=. succes
36
A quoi cela sert-il ?Traduire le procédure suivante
Proc :-repeat,read(Note),Si( Note>10,
write(“admis”),write(« refuse »)
),Note=-1, !.
ProcRepeter
Lire(Note)si Note>10 écrire(«admis»)sinon écrire(«refuse»)Jusque Note=-1