Řez a upnutí
Rez, negace
Rez a ořezání
f(X,Y) s(X,Y) s(X,Y)
s(X,Y).
Y i s X + 1.
Y i s X + 2.
f(X,Y) s(X,Y) s(X,Y)
s(X,Y), !.
Y i s X + 1.
Y i s X + 2.
?- fCl.Z).
Z = 2 ? ; Z = 3 ? ; no
Z = no
fCl.Z). 2 ? ;
Ořezání: po splnění podcílů před řezem se už neuvažuje další možné splnění těchto podcílů
Smazání řezu změní chování programu
Hana Rudová, Logické programování I, 28. února 2011
f(X,0) f(X,2) f(X,4)
X < 3,   ! .
3 =< X, X < 6, !
6 =< X.
přidání operátoru řezu
6
?- f(l,Y), Y>2.
f(X,0) :- X < 3, !. %(1) f(X,2) :- X < 6, !. %(2) f(X,4).
?- fCl.Y).
1 Smazání řezu v (1) a (2) změní chování programu
1 Upnutí: po splnění podcílů před řezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 28. února 201 1 2
Řez, negace
Chování operátoru řezu
Předpokládejme, že klauzule H :- TI, T2, Tm, !
aktivována voláním cíle C, který je unifikovatelný s H.
V momentě, kdy je nalezen řez, existuje řešení cílů TI, ..., Tm
...Tn.je
G=h(X,Y)
X=1,Y=1
Ořezání: při provádění řezu se už další možné splnění cílů TI, .. nehledá a všechny ostatní alternativy jsou odstraněny
Upnutí: dále už nevyvolávám další klauzule, jejichž hlava je také unifikovatelná s C
Tm
Y=2 X=2
?- h(X,Y).
h(l,Y) h(2,Y)
tl(Y), !. a.
tl(l) tl(2)
b.
c.
h(X,Y) X=l   /     \ X=2
tl(Y) a (vynechej: upnutí) Y=l /     \ Y=2
b c   (vynechej: ořezání)
/
Hana Rudová, Logické programování I, 28. února 201 1
Rez: návrat na rodiče
?- a(X).
CD a(X) :-(2) a(X) :-
C3) h(l,Y)
(4) h(2,Y)
(5) tl(l) : C6) tl(2) :
h(X,Y). d.
:- tl(Y), : - a.
- b.
- c.
e(X).
(7) b :- c.
(8) b :- d.
(9) d.
(10) e(l) ■
(11) e(2).
■ Po zpracování klauzule s řezem se vracím až na rodiče této klauzule, tj. a(X)
Hana Rudová, Logické programování I, 28. února 2011
Řez: cvičení
1. Porovnejte chování uvedených programů pro zadané dotazy.
a(X,X) :- b(X). a(X,Y)  :- Y is X+l. b(X)  :- X > 10.
?- a(X,Y). ?- a(l,Y). ?- a(ll,Y).
a(X,X) a(X,Y) bCX) :-
:- b(X),!. :- Y is X+l. X > 10.
a(X,X) a(X,Y) bCX) :-c :- ! .
:- b(X),c. :- Y is X+l. X > 10.
2. Napište predikát pro výpočet maxima max( X, Y, Max )
c(X) c(X)
PCX). v(X).
Řez: příklad
cl(X) :- pCX), ! cl(X)  :- v(X).
P(D. P(2).
v(2).
?- c(2).
true ? ; %p(2)
true ? ; %v(2) no
?- cl(2).
true ?   ; %p(2)
no
?- c(X).
X = 1 ? X = 2 ? X = 2 ?
no
%P(D %p(2) %v(2)
?- cl(X).
X = 1 ?   ; %p(l)
no
Hana Rudová, Logické programování I, 28. února 201 1
Typy řezu
Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet Zelený řez: odstraní pouze neúspěšná odvození
■ f(X,l)  :- X >= 0,   !.    f(X,-l)  :- X < 0.
bez řezu zkouším pro nezáporná čísla 2. klauzuli
Modrý řez: odstraní redundantní řešení
■ f(X,l) :- X >= 0, !. f(0,l). f(X,-l) :- X < 0. bez řezu vrací f(0,l) 2x Červený řez: odstraní úspěšná řešení
■ f(X,l) :- X >= 0,  !.   f(_X,-l).      bez řezu uspěje 2. klauzule pro nezáporná čísla
Hana Rudová, Logické programování I, 28. února 2011 7 Řez, negace Hana Rudová, Logické programování I, 28. února 201 1
Negace jako neúspěch
Negace jako neúspěch: operátor \+
Speciální cíl pro nepravdu (neúspěch) fail a pravdu true
Xa Y nejsou unifikovatelné: different(X, Y)
differentC X, Y )  :- X = Y,  !, fail. differentC _X, _Y ).
Xje muž: muz(X)
muz( X ) :- zena( X ),  !, fail. muz( _X ).
different(X,Y) :- X different(_X,_Y).
Y,  !, fail.       muz(X)  :- zena(X),  !, fail muz(_X).
Unární operátor \+ P
■ jestliže P uspěje, potom \+ P neuspěje \+(P) :- P,  !, fail.
■ v opačném případě \+ P uspěje \+(_)■
differentC X, Y ) :- \+ X=Y. muz( X ) :- \+ zena( X ).
Pozor: takto definovaná negace \+P vyžaduje konečné odvození P
Hana Rudová, Logické programování I, 28. února 2011
Negace a proměnné
\+(P) :- P, !, fail. % (I) \+(_). % (ID
dobre( citroen ). dobre( bmw ).
drahe( bmw ).
rozumne( Auto ) :-\+ drahe( Auto ).
% (D
% (2)
% (3)
% (4)
?- dobre( X ), rozumne( X ).
d ob re (X), rozum n e (X)
dle (1), X/citroen
rozumne(citroen) dle (4)
\+ drahe(citroen) \ dle (II) dle (I)
drahe(citroen),!, fail
□ yes
no
Hana Rudová, Logické programování I, 28. února 2011
Hana Rudová, Logické programování I, 28. února 201 1
Negace a proměn
\+(P) :- P, !, fail. % (I) \+(_). % (ID
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto )  :- % (4)
\+ drahe( Auto ).
?- rozumne( X ), dobre( X ).
b'žTimne(X), dobre(X) dle (4)
\+ drahe(X), dobre(X) dle (I)
drahe(X),!,fail,dobre(X) dle (3), X/bmw
!, fail, dobre(bmw)
fail,dobre(bmw)
no
Hana Rudová, Logické programování I, 28. února 201 1
Bezpečný cíl
?- rozumne( citroen ). yes ?- rozumne( X ). no ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no \+ Pje bezpečný: proměnné Pjsou v okamžiku volání P instanciovány ■ negaci používáme pouze pro bezpečný cíl P
Hana Rudová, Logické programování I, 28. února 2011
Predikáty na řízení běhu programu I.
řez „!"
fai 1: cíl, který vždy neuspěje      true: cíl, který vždy uspěje \+ P: negace jako neúspěch
\+ P :- P,  !, fail ; true. once(P): vrátí pouze jedno řešení cíle P
once(P) :- P,  !. Vyjádření podmínky: P -> Q ; R
■ jestliže platí P tak Q        (P -> Q ; R) : - P,  ! , Q.
■ v opačném prípade R      (P -> Q ; R) :- R.
■ príklad: min(X,Y,Z) : - X =< Y -> Z = X ; Z = Y. P -> Q
■ odpovídá: (P -> Q; fail)
■ príklad: zaporne(X) :- number(X) -> X < 0.
Hana Rudová, Logické programování I, 28. února 2011 1 5
Chování negace
?- \+ drahe( citroen ). ?- \+ drahe( X ).
Negace jako neúspěch používá předpoklad uzavřeného světa pravdivé je pouze to, co je dokazatelné
yes no
?- \+ drahe( X ).
\+ drahe( X ) :- drahe(X),!,fail.      \+ drahe( X ).
z definice \+ plyne: není dokazatelné, že existuje X takové, že drahe( X ) platí tj. pro všechna X platí \+ drahe( X )
■ ?- drahe( X ). VÍME: existuje X takové, že drahe( X ) platí
1 ALE: pro cíle s negací neplatí existuje X takové, že \+ drahe( X )
p negace jako neúspěch není ekvivalentní negaci v matematické logice
Hana Rudová, Logické programování I, 28. února 201 1 14 Řez, negace
Predikáty na řízení běhu programu II.
1 cal 1 (P): zavolá cíl P a uspěje, pokud uspěje P 1 nekonečná posloupnost backtrackovacích voleb: repeat repeat.
repeat :- repeat.
klasické použití: generuj akci X, proveď ji a otestuj, zda neskončit Hlava :- ...
u"loz_stav( StaryStav ),
repeat,
generuje X ), % deterministické: generuj, prováděj, testuj
prováděj( X ), testuj( X ),
i
obnov_stav( StaryStav ),
Hana Rudová, Logické programování I, 28. února 201 1
Reprezentace seznamu
Seznamy
1 Seznam: [a, b, c], prázdný seznam []
1 Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo)
■ všechny strukturované objekty stromy - i seznamy
■ funktordva argumenty
■ .(a,  .(b,  .(c,  []))) = [a, b, c]
■ notace: [ Hlava | Telo ] = [a | Tel o]
Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] ' Lze psát i: [a, b | Tel o]
■ před " |" je libovolný počet prvků seznamu , za " | "je seznam zbývajících prvků
■ [a.b.c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]]
■ pozor: [ [a,b]  |  [c]]r[a,b|  [c] ]
1 Seznam jako neúplná datová struktura: [a,b,c|T]
■ Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S]
Hana Rudová, Logické programování I, 28. února 201 1 1 8
Prvek seznamu
■ member( X, S )
■ platí: member( b,  [a,b,c] ).
■ neplatí: member( b,  [[a,b]|[c]] ).
■ Xje prvek seznamu S, když
■ Xje hlava seznamu S nebo member( X,  [ X | _ ] ). %(1)
■ Xje prvek těla seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
■ Další příklady použití:
■ memberCX,[1,2,3]) .
■ memberCl,[2,1,3,1]).
Hana Rudová, Logické programování I, 28. února 2011 1 9
dle (1).
□ yes
dle(1).
□ yes
member(1,[2,1,3,1,4])
dle (2) member(1,[1,3,1,4])
dle (2) member(1,[3,1,4])
dle (2) member(1 ,[1,4])
dle (2) member(1 ,[4])
|  dle (2) member(1,[]) dle (2)
no
Spojení seznamů
append( LI, L2, L3 )
Platí: append( [a,b],  [c,d],  [a,b,c,d] )
Neplatí: append( [b,a],  [c,d],  [a,b,c,d] ), append( [a,[b]],  [c,d],  [a,b,c,d] )
Definice:
■ pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy: append( [], S, S ).
■ pokud je 1. argument neprázdný seznam, pak má 3. argument stejnou hlavu jako 1.: append( [X|S1], S2,  [X|S3] )  :- append( SI, S2, S3).
X
S1
S2
S3
Hana Rudová, Logické programování I, 28. února 201 1
Příklady použití append
■ appencK [] , S, S ) .
appencK [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
■ Spojení seznamů: append ( [a,b,c],  [1,2,3], S ). S = [a,b,c,1,2,3]
append( [a,  [b,c], d],  [a,  [], b], S ). S = [a,  [b,c], d, a,  [], b] ]
■ Dekompozice seznamu na dva seznamy: append ( SI, S2 ,  [a, b ]).
SI = [], S2 = [a, b] ; SI = [a], S2 = [b] ? ; SI = [a,b], S2 = []
■ Vyhledávání v seznamu: append( Pred,  [ c | Za ],  [a,b,c,d,e] ).
Pred = [a,b], Za = [d,e]
■ Předchůdce a následník: append( _,  [Pred ,c,Za|_],  [a, b,c,d,e] ).
Pred = b, Za = d
Hana Rudová, Logické programování I, 28. února 2011 21 Seznamy
Smazání prvku seznamu delete( X, S, SI )
■ Seznam SI odpovídá seznamu S, ve kterém je smazán prvek X
■ jestliže X je hlava seznamu S, pak výsledkem je tělo S delete( X,  [X|Telo], Telo).
■ jestliže X je v těle seznamu, pak X je smazán až v těle
delete( X,  [Y|Telo],  [Y|Telol] ) :- delete( X, Telo, Telol ).
■ delete smaže libovolný výskyt prvku pomocí backtrackingu ?- delete(a,  [a,b,a,a], S).
S = [b,a,a]; S = [a,b,a]; S = [a,b,a]
■ delete, který smaže pouze první výskyt prvku X
■ delete( X,  [X|Telo], Telo) :- !.
delete( X,  [Y|Telo],  [Y|Telol] ) :- delete( X, Telo, Telol).
Hana Rudová, Logické programování I, 28. února 201 1 22 Seznamy