Prolog jako jazyk už jsme víceméně jako jazyk probrali celý. Pojďme si ještě projít užitečné nástroje, které se nám můžou při programování hodit.
Shromažďování řešení
Často se nám stává, že máme nedeterministický predikát, který nám postupně vrací různá řešení. To nám málokdy stačí, často by nás zajímaly všechny výsledky, protože s nimi chceme dále něco udělat najednou.
Z tohoto důvodu můžeme v Prologu najít predikáty bagof/3
, setof/3
a
findall/3
, které umí projít zadaný cíl a shromáždit všechna jeho řešení
do jednoho seznamu. Všechny tyto predikáty berou tyto tři parametry:
+T
popisující šablonu. Při nalezení řešení cíle, se tato šablona zunifikuje s tímto řešením.:G
popisující cíl, jehož řešení chceme shromáždit. V případě, žeG
obsahuje volné proměnné, které nejsou vT
, se predikáty chovají následovně:- V případě
findall
jsou tyto proměnné vázané existenčním kvantifikátorem, a tedy dostaneme seznam všech řešení, která libovolně tyto proměnné splní. - Predikáty
bagof
asetof
budou backtrackovat a vracet různé seznamy pro všechny možnosti těchto volných proměnných. Pokud chceme, aby se volná proměnnáV
chovala stejně, jako vefindall
, musíme ji v tomto parametru svázat operátorem^
s cílem. Pak tento parametr bude vypadatV^G
.
- V případě
-L
unifikovaný se seznamem, který bude obsahovat shromážděná řešení. Predikátsetof
vrací seznam řešení seřazený dle standardního uspořádání bez duplikací. U predikátůbagof
afindall
naopak jsou řešení seřazena přesně podle pořadí, v jakém bychom je dostali normálně.
V tomto případě můžeme zadat cíl i jako konjunkci více predikátů, pokud ji uložíme do závorek.
Ukažme si chování těchto predikátů na jednoduchých faktech.
plati(a, b, c). plati(a, b, d). plati(b, c, e). plati(b, c, f). plati(c, c, g). ?- findall(C, plati(A, B, C), L). L = [c, d, e, f, g]. ?- findall(A+B, plati(A, B, C), L). L = [a+b, a+b, b+c, b+c, c+c]. ?- bagof(C, plati(A, B, C), L). A = a, B = b, L = [c, d] ; A = b, B = c, L = [e, f] ; A = B, B = c, L = [g]. ?- bagof(C, A^plati(A, B, C), L). B = b, L = [c, d] ; B = c, L = [e, f, g]. ?- bagof(I -> X, nth0(I, X, [3, 1, 4, 1, 5]), L). L = [(0->3), (1->1), (2->4), (3->1), (4->5)]. ?- setof(X, (member(X, [3, 1, 4, 1, 5]), X mod 2 > 0), L). L = [1, 3, 5]. ?- findall([X|NL], (select(X, [0, 1, 0, 2], NL), X > 0), L). L = [[1, 0, 0, 2], [2, 0, 1, 0]].
Intuitivně se můžeme na bagof
a findall
podívat jako na množinový zápis, například
findall(C, plati(A, B, C), L)
odpovídá L = { C | ∃A ∃B: plati(A, B, C) }
.
Tyto predikáty nám umožňují zjednodušit některé úlohy. Vzpomeňme si třeba na převádění binárního stromu na seznam. To teď můžeme udělat snadno:
preorder(t(_, X, _), X). preorder(t(L, _, _), X) :- preorder(L, X). preorder(t(_, _, P), X) :- preorder(P, X). preorder_list(T, L) :- findall(X, preorder(T, X), L). ?- preorder(t(t(nil, 1, nil), 2, t(nil, 3, nil)), X). X = 2 ; X = 1 ; X = 3 ; false. ?- preorder_list(t(t(nil, 1, nil), 2, t(nil, 3, nil)), L). L = [2, 1, 3].
Cvičení: Mějme graf definovaný predikátem Hrana(+U, -V)
splnitelným pro
vrcholy U, V
spojeny hranou. Naprogramujte predikáty na_grafE(:Hrana, -G)
a
na_grafN(:Hrana, -G)
splnitelným, jestliže G
je graf reprezentovaný
seznamem hran a seznamem sousednosti.
Cvičení: Naprogramujte predikát komponenta(:Hrana, +V, -L)
splnitelný, jestliže L
je komponenta souvislosti pro grafu daného
predikátem Hrana
, která obsahuje V
.
Jiný příklad, kdy nám shromažďování výsledku velmi usnadňuje práci, je generování všech permutací.
% permutace(?L, ?P) :- P je permutace L. permutace([], []). permutace(L, [X|P]) :- select(X, L, LX), permutace(LX, P). ?- permutace([a, b, c], P). P = [a, b, c] ; P = [a, c, b] ; P = [b, a, c] ; P = [b, c, a] ; P = [c, a, b] ; P = [c, b, a] ; false. ?- findall(P, permutace([a, b, c], P), L). L = [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].
Cvičení: Naprogramujte predikát podseznamy(+L, -PL)
splnitelný, jestliže
P
je seznam všech podseznamů L
.
Cvičení: Naprogramujte predikát stejne_delky(+L, ?N, -NL)
splnitelný,
jestliže L
je seznam seznamů a NL
obsahuje pouze ty seznamy L
, které mají
délku N
.
Cvičení: Naprogramujte predikáty kombinace(+L, +N, -O)
a variace(+L, +N,
-O)
splnitelné, jestliže O
je seznam podseznamů L
o N
prvcích. Navíc,
kombinace
musí splňovat, že prvky jsou v původním pořadí, u variace
může
být pořadí libovolné.
?- kombinace([a, b, c, d], 2, K). K = [[a, b], [a, c], [a, d], [b, c], [b, d], [c, d]]. ?- variace([a, b, c, d], 2, V). V = [[a,b], [a,c], [a,d], [b,a], [b,c], [b,d], [c,a], [c,b], [c,d], [d,a], [d,b], [d,c]].
Databáze
Způsob, jakým můžeme používat predikáty, nám doteď umožňoval si ukládat pouze data na zásobník. Speciálně tedy libovolné dosazení proměnné je při backtrackingu zrušeno a nemůžeme si tak posílat informaci o něčem, co se nám nepodařilo splnit. Jinými slovy, zatím neumíme způsobit vedlejší efekty.
Prolog nám však dává k dispozici určitá rozhraní databáze, což je globální paměť, která umí přežit backtracking. V řeči Prologu je tato databáze prostě seznam všech pravidel a faktů (klauzulí), které mají stejnou hlavu.
Abychom si pořídili databázi s hlavou, která má název N
a aritu A
, musíme
použít magickou formuli :- dynamic N/A.
. Můžeme najednou vytvořit více
databází najednou oddělením čárkou. Za dynamickou databázi můžeme prohlásit
libovolný predikát, a to i takový, co má v programu předem určené klauzule.
Jakmile máme pořízenou databázi, máme k dispozici predikáty:
asserta(+Term)
přidávající novou klauzuli před všechny existující,assertz(+Term)
přidávající novou klauzuli za všechny existující,assert(+Term)
ekvivalentníassertz(+Term)
,retract(+Term)
odstraňující existující klauzuli zunifikovatelnou naTerm
z databáze,retractall(+Head)
odstraňující všechny klauzule, jejichž hlave se zunifikuje sHead
.
Vzpomeňme si na rodinné vztahy a zkusme je udělat dynamické. Ve výsledku budeme moct za běhu vztahy přidávat. Pak si zkusíme dotazy a odstraňování vztahů.
:- dynamic muz/1, zena/1, rodic/2. osoba(O) :- muz(O). osoba(O) :- zena(O). otec(O, P) :- muz(O), rodic(O, P). matka(O, P) :- zena(O), rodic(O, P). pridej(Kam, Co) :- Pred =.. [Kam|Co], assert(Pred). jednoprvek(P, [P]). pridej_muze(L) :- maplist(jednoprvek, L, PL), maplist(pridej(muz), PL). pridej_zeny(L) :- maplist(jednoprvek, L, PL), maplist(pridej(zena), PL). pridej_rodice(R, P) :- osoba(R), osoba(P), !, pridej(rodic, [R, P]).
Ukažme na tomto programu konkrétní posloupnost dotazů jdoucí po sobě. Nyní už totiž záleží i na pořadí dotazů!
% Zpočátku neznáme žádnou osobu ?- osoba(O). false. % Adama ani Kaina neznáme, přidání rodiče selže ?- pridej_rodice(adam, kain). false. % Přidáme známé osoby ?- pridej_muze([adam, kain, abel]), pridej_zeny([eva]). true. % Nyní už můžeme přidat rodiče ?- maplist(pridej_rodice(adam), [kain, abel]). true. % Nyní se můžeme ptát na otce, v databázi jej máme ?- otec(O, kain). O = adam; false. % Ještě nemáme žádnou matku ?- matka(M, abel). false. % Přidáme druhého rodiče ?- maplist(pridej_rodice(eva), [kain, abel]). true. % Teď už ano ?- matka(M, abel). M = eva ; false. % Adama nechceme jako rodiče ?- retract(rodic(adam, _)). true ; % Odstranili jsme relaci adam-kain true. % Též jsme odstranili relaci adam-abel % Adama už neznáme jako rodiče, Evu stále ano ?- rodic(R, kain). R = eva ; false. ?- otec(_, abel). false. % Odstranění pouze jednoho ze dvou rodičovských pravidel Adama ?- maplist(pridej_rodice(adam), [kain, abel]), once(retract(rodic(adam, _)), otec(adam, P). P = abel ; false. % Odstraníme najednou a s jistotou všechny zmínky o rodičovství Evy ?- retractall(rodic(eva, _)), \+matka(_, _). true. % Vyprázdnění databází ?- retractall(muz(_)), retractall(zena(_)), retractall(rodic(_,_)). true.
Predikát retract
je schopen odstraňovat více prvků z databáze postupně díky
nedeterminismu, pokud se podaří hlavy klauzule zunifikovat. Pozor, odstranění
je trvalé i přes backtracking! Pokud však chceme odstranit každý takový výskyt,
musíme použít retractall
.
Vedlejší efekty umí rozbít chování predikátů, pokud je použijeme neopatrně. Například nechceme volat ten samý predikát k více různým účelům nebo vícekrát po sobě.
:- dynamic visited/1. member_once(X, L) :- member(X, L), \+visited(X), assert(visited(X)). najdi_soucet(L, S, A, B) :- member(A, L), member(B, L), S =:= A + B. najdi_soucet_once(L, S, A, B) :- member_once(A, L), member_once(B, L), S =:= A + B. ?- member_once(X, [a, b, a, c, b]). X = a ; X = b ; X = c ; false. % Podruhé už predikát nefunguje ?- member_once(X, [a, b, a, c, b]). false. ?- member_once(b, [a, b, a, c, b]). false. % Musíme vyprázdnit návštěvy ?- retractall(visited(_)), member_once(b, [a, b, a, c, b]). true ; false. ?- najdi_soucet([1,2,3,4], 7, A, B). A = 3, B = 4 ; A = 4, B = 3 ; false. % Najdeme jen jedno řešení, na každý prvek šáhneme nejvýše jednou ?- najdi_soucet_once([1,2,3,4], 5, A, B). A = 1, B = 4 ; false. ?- najdi_soucet([1,2,4], 4, A, B). A = B, B = 2 ; false. % Řešení se nepodaří najít i přes vyprázdnění návštěv ?- retractall(visited(_)), najdi_soucet_once([1,2,2,4], 4, A, B). false.
Cvičení: Naprogramujte pomocí databáze frontu ignorující backtracking,
která bude identifikovaná atomem. Rozhraní k frontě pak bude push(+Name,
+Term)
, pop(+Name, -Term)
a empty(Name)
.