Ř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
?- fCl.Z).
Z = 2 ? ; no
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í deklarativní význam programu
Hana Rudová, Logické programování I, 24. února 2007
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í deklarativní význam programu
1 Upnutí: po splnění podcílů před řezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 24. února 2007 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) :- tl(Y), ! . h(2,Y)  :- a.
tl(l) :- b. tl(2)  :- 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, 24. února 2007
c (X) c (X)
P (X), vCX).
Rez: 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
X P CD
%P(2) %v(2)
?- cl(X).
X = 1 ?   ; %p(l)
no
Hana Rudova, Logické programování I, 24. února 2007
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
Řez: cvičení
1. Porovnejte chování uvedených programů pro zadané dotazy.
:- b(X),!. :- Y is X+l. X > 10.
a(X,X) a(X,Y) b(X) :■ c : - !
a(X,X)  :- b(X). a(X,X)
a(X,Y)  :- Y is X+l. a(X,Y)
b(X) :- X > 10. b(X) :-
?- a(X,Y). ?- a(l,Y). ?- a(ll,Y).
2. Napište predikát pro výpočet maxima max( X, Y, Max )
:- b(X),c. :- Y is X+l. X > 10.
Hana Rudová, Logické programování I, 24. února 2007
Negace jako neúspěch
Speciální cíl pro nepravdu (neúspěch) fail a pravdu true
Xa Y nejsou unifikovatelné: different(X, Y)
different( X, Y ) :- X = Y,  !, fail. different( _X, _Y ).
Xje muž: muz(X)
muz( X ) :- zena( X ),  !, fail. muz( _X ).
Hana Rudová, Logické programování I, 24. února 2007 7 Rez, negace Hana Rudová, Logické programování I, 24. února 2007
Negace jako neúspěch: operátor \+
muz(X) :- zena(X), !, fail. muz(_X).
different(X,Y)  :- X = Y,  !, fail. different(_X,_Y).
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 \+(_) ■
different( 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, 24. února 2007
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 ).
■o'žDmne(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
Negace a proměnné
\+(P) :- P, !, fail. % (I) \+(_). % (ID
dobre( citroen ). dob re( bmw ).
drahe( bmw ).
rozumne( Auto ) :-\+ drahe( Auto ) .
% (D
% (2)
% (3)
% (4)
?- dobre( X ), rozumne( X ).
Hana Rudová, Logické programování I, 24. února 2007
dobre(X),rozumne(X)
dle (1), X/citroen
rozumne(citroen) dle (4)
\+ drahe(citroen) \ dle (II) dle (I)
drahe(citroen),!, fail
no
□ yes
Bezpečný cíl
?- rozumne( citroen ). yes ?- rozumne( X ). no ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no \+ P je bezpečný: proměnné P jsou 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, 24. února 2007 11 Řez, negace Hana Rudová, Logické programování I, 24. února 2007
Chování negace
■ ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no
■ Negace jako neúspěch používá předpoklad uzavřeného světa
pravdivé je pouze to, co je dokazatelné
■ ?- \+ drahe( X ). \+ drahe( X ) :- drahe(X),!,fail.      \+drahe( X ).
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í
■ ALE: pro cíle s negací neplatí existuje X takové, že \+ drahe( X )
=> negace jako neúspěch není ekvivalentní negaci v matematické logice
Hana Rudová, Logické programování I, 24. února 2007 13 Řez, negace
Predikáty na řízení běhu programu II.
■ call (P): zavolá cíl P a uspěje, pokud uspěje P
■ 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 ) ,
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.
■ příklad:abs(X, AbsX ) : - X >= 0 -> AbsX = X ; AbsX i s - X.
■ P -> Q
■ odpovídá: (P -> Q; fail)
■ príklad: zaporne(X) :- number(X) -> X < 0.
Hana Rudová, Logické programování I, 24. února 2007 14 Řez, negace
Seznamy
Hana Rudová, Logické programování I, 24. února 2007
Řez,negace
Reprezentace seznamu
Seznam: [a, b, c], prázdný seznam []
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] ] + [ a, b |  [c] ] 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, 24. února 2007 17 Se
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|53] ) :- append( SI, S2, S3).
X
S1
S2
S3
Hana Rudová, Logické programování I, 24. února 2007
Seznamy
Prvek seznamu
1 member( X, S )
1 platí: member( b,  [a,b,c] ).
1 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, 24. února 2007 1 8
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
Příklady použití append
■ append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( SI, S2, S3).
1 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] ]
1 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, 24. února 2007 20 Sezn
Smazání prvku seznamu
■ Smazání prvku delete( X, S, SI )
■ 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, 24. února 2007
21
Seznamy