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. %1

b. %0

c. %1

c :- e , f. %0

P = a.0P = b.1

P = c,!,d.1

P = !,d. !

P=d.no

5

Effet du Cut dans une question

avec variables b(1). %1

b(2). %0

c(1). %1

c(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 question

avec variables b(1). %1

b(2). %0

c(1). %1

c(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ès

0

{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). %1

b(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ès

0 {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). %1

b(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ès

0

{X=1,Y=2} P=. succès

9

Effet du Cut sur le réponse(succès ou bien échec)

a :- fail. %1

a . %0

P = a.

1

P = fail .

échec

0

P = .

succès

10

Effet du Cut sur le réponse(succès ou bien échec)

a :- !, fail. %1

a . %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). %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

Comment obtenir uniquement le premier

chiffre (0) ?

?- chiffre(X).

14

A quoi cela sert-il ?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

Comment obtenir uniquement le premier

chiffre (0) ?

?- chiffre(X), ! .

15

A quoi cela sert-il ?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

{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). %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

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. %1

max(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. %1

max(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, ! . %1

max(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, ! . %1

max(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, ! . %1

max(_,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, ! . %1

max(_,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, ! . %1

max(_,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, ! . %1

max(_,Y,Y). %0

P= max(2,3,3).

0

P=. succes

26

Peut-on encore simplifier ?

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

max(_,Y,Y). %0

P= max(3,2,2).

0

P=. succes

27

A quoi cela sert-il ?définir la négation

non_c :- c , ! , fail. %1

non_c. %0

P=non_c.

1

P= c, ! , fail.

c

P= ! , fail.

!

P= fail. no

28

A quoi cela sert-il ?définir la négation

non_c :- c , ! , fail. %1

non_c. %0

P=non_c.

1

P= c, ! , fail. no

0

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’). %1

proc(_) :- 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’). %1

proc(_) :- 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. %1

repeat :- repeat %0

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

Proc

repeter

a

b

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, !.

Proc

Repeter

Lire(Note)

si Note>10

écrire(«admis»)

sinon

écrire(«refuse»)

Jusque Note=-1