Contrôle du moteur Prolog

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