Václav Končický

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:

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:

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