Kate Konczycki

Metaprogramovací techniky v Prologu

Doteď jsme se k predikátům v Prologu chovali, jako kdyby to byla neměnná část jazyka. Prolog však má nástroje k tomu, abychom mohli s predikáty a termy obecně více pracovat.

Ověřování typu termu

Často se stává, že nám určité kombinace volných proměnných v parametrech způsobí nekorektnost predikátu, nebo jeho zacyklení. Často by se hodilo si předem zjistit, které proměnné jsou volné, případně zda daná proměnná je hledaného typu.

Právě k tomuto účelu má Prolog vestavěné predikáty, které jsou vždy tvaru je_typu(@Term). Kontrola vždy probíhá v čase vyhodnocení predikátu až po unifikaci. Názvy predikátů pak kontrolují, zda Term je typu:

Testy pak vypadají následovně:

?- var(X), X = [], nonvar(X).
X = [].

?- ground(atom), ground(append([a],[b],[c])), \+ground(length(L,5)).
true.

?- number(10.3), \+integer(10.3), integer(10).
true.

?- string("Hello, Prolog!").
true.

?- atom(atom), \+atom([]).
true.

?- atomic(atom), atomic(10), atomic([]).
true.

?- compound(funktor(_)), compound(X-X).
true.

Cvičení: Zkuste naprogramovat predikát is_list(+Term) kontrolující, zda je Term dosazený seznam (nesmí to být proměnná, ale proměnné jako prvky obsahovat může).

Analýza a skládání termů

Další poměrně užitečná část Prologu je možnost zkoumat vnitřní strukturu termů a případně ji upravovat.

První predikát tohoto druhu je functor(?Term, ?Nazev, ?Arita) splnitelný, jestliže Term odpovídá termu Nazev/Arita. Pokud je Term atomický, Arita se zunifikuje na 0 a Name = Term. Pokud Term je proměnná, Nazev i Arita musí být dosazeny, jinak dostaneme chybu. Tento predikát funguje i na vstupní Termy, které jsou operátory.

?- functor(s(0), N, A).
N = s,
A = 1.

?- functor([1,2|X]-X, N, A).
N =  (-),
A = 2.

?- functor(f(X,Y,Z), f, 2).
false.

?- functor(F, f, 2).
F = f(_8342, _8344).

?- functor(f(X,Y,Z), N, _), functor(F, N, 2).
N = f,
F = f(_10816, _10818).

Cvičení: Naprogramujte predikát na_atomicke(+L, -AL) splnitelný, jestliže L a AL jsou seznamy a AL obsahuje pouze atomické termy, jejichž názvy odpovídají názvům termů v seznamu L. Tudíž platí na_atomicke([f(X), g(X, Y), h], [f, g, h]).

Zatím můžeme kontrolovat název a počet parametrů. Celý systém by ale nebyl úplný, kdybychom neměli jak zkoumat samotné parametry.

Proto dále v Prologu najdeme predikát arg(?K, +Term, ?Hodnota) splnitelný, jestliže K-tý parametr složeného Termu je Hodnota. Parametry se číslují od jedničky. Pokud je K větší, než arita nebo nula, predikát selže. Pokud je K záporné, nebo Term je atomický, Prolog vyhodí chybu.

?- arg(2, f(X, Y, Z), H).
Y = H.

?- arg(1, f([1,2]), [X|Xs]).
X = 1,
Xs = [2].

?- arg(K, f(X, [a]), []).
K = 1,
X = [] ;
false.

?- arg(K, f(a, b, c), H).
K = 1,
H = a ;
K = 2,
H = b ;
K = 3,
H = c.

?- arg(3, f(a, b), _).
false.

?- arg(_, f([], []), [_|_]).
false.

?- arg(_, atom, _).
ERROR: Type error: `compound' expected, found `atom' (an atom)

Cvičení: Naprogramujte predikát vse_seznamy(+Term) jestliže Term je složený a každý jeho parametr je seznam.

Pro některé však může být použití těchto dvou predikátů příliš krkolomné, zvláště když chceme kontrolovat jak term samotný, tak jeho parametry.

Proto Prolog definuje i operátor =.. splnitelný, jestliže pravá strana operátoru je seznam, jehož hlava je název termu nalevo a zbytek seznamu jsou jeho parametry, v původním pořadí. Použití =.. vyžaduje, aby alespoň jedna jeho strana byla dostatečně dosazená.

?- f(X, g(Y), z) =.. L.
L = [f, X, g(Y), z].

?- T =.. [f, x, y].
T = f(x, y).

?- f(x, y, z) =.. [N|P], reverse(P, RP), NT =.. [N|RP].
N = f,
P = [x, y, z],
RP = [z, y, x],
NT = f(z, y, x).

?- L = [f|_], length(L, K), T =.. L.
L = [f],
K = 1,
T = f ;
L = [f, _2424],
K = 2,
T = f(_2424) .

?- T =.. [N, a, b, c].
ERROR: Arguments are not sufficiently instantiated

Cvičení: Naprogramujte predikáty functor a arg pomocí =...

Metaprogramování

Jistě jste si všimli, že velmi často píšeme predikáty, které se svou strukturou skoro neliší, pouze se často liší jedním pravidlem uvnitř rekurzivního pravidla nebo základními případy.

Například uvažme seznam, jehož prvky jsou tvaru X-Y. Chtěli bychom jej umět třídit jak podle X, tak podle X+Y. To už bychom zvládli s chytrým použitím arg naprogramovat jako jeden predikát. Stále však nemáme k dispozici obecné třídění, kterému můžeme dát libovolný porovnávací predikát.

Nezoufejme však, Prolog má prostředky umožňující zavolat libovolný term jako predikát, čímž si pořídíme metaprogramování. Vzhledem k tomuto budeme dodržovat další konvenci. Metaparametry budeme v seznamu parametrů definice predikátu značit :.

Úplně nejjednodušší způsob, jak zavolat term jako predikát, je jej prostě přidat do pravidla přímo. I jako proměnnou, která bude za daný term dosazená.

% plati_vse(:L) :- L je seznam predikátů, které jsou splnitelné.
plati_vse([]).
plati_vse([P|Ps]) :- P, plati_vse(Ps).

?- plati_vse([reverse([1, 2], X), append([x],[y],L)]).
X = [2, 1],
L = [x, y] ;
false.

Jistě uznáte, že tento způsob není moc flexibilní. Samozřejmě můžeme zneužít =.. k tomu, abychom si term připravili před jeho vyhodnocením.

Cvičení: Naprogramujte predikát plati(+Nazev, +Param), jestliže platí term z názvem Nazev a Param je seznam jeho parametrů.

Pro tyto účely Prolog definuje skupinu predikátů call(:Goal, …) s libovolným počtem parametrů. Tento predikát dělá to, že k termu Goal připojí zbytek parametrů call a pak tento spojený term vyhodnotí. Díky tomu, jak je call definovaný, si můžeme předpřipravit první parametry vyhodnocovaného termu a callem akorát dosadit zbytek. To se může hodit pro ještě obecnější metaprogramování.

?- call(reverse([a, b], X)).
X = [b, a].

?- call(reverse, [a, b], X).
X = [b, a].

?- call(reverse([a, b]), X).
X = [b, a].

Pomocí metaprogramování můžeme nyní naprogramovat predikát, který aplikuje jiný predikát na seznamu po složkách. V jiných jazycích můžete takové chování znát jako map.

% pro_kazdy_prvek(:Pred, ?L) :- Pro každý prvek L platí Pred.
pro_kazdy_prvek(_, []).
pro_kazdy_prvek(Pred, [P|L]) :- call(Pred, P), pro_kazdy_prvek(L).

plati_vzdy(_).

Nyní můžeme námi napsaný predikát využívat k tomu, abychom mohli snadno kontrolovat nějakou vlastnost všech prvků v seznamu.

?- pro_kazdy_prvek(plati_vzdy, [a, b, c]).
true.

?- pro_kazdy_prvek(integer, [1, 2, 3]).
true.

?- pro_kazdy_prvek(<(0), [1, 2, 3]). % 0 < X
true.

Podobně, jako u call, Prolog definuje skupinu predikátů maplist, které se liší počtem parametrů, které berou vyhodnocovaný predikát. Pak je maplist splnitelný, jestliže zbylých k parametrů jsou seznamy stejné délky a postupně pro každou k-tici prvků jednotlivých seznamů na stejné pozici platí predikát. Stejně, jako u call, maplist umožňuje částečné dosazení prvních parametrů.

?- maplist(integer, [1, 2, 3]).
true.

?- maplist(reverse, [[a, b], [c, d], [e, f]], LRL).
LRL = [[b, a], [d, c], [f, e]].

?- maplist(append([x]), [[y], [z]], LAL).
LAL = [[x, y], [x, z]].

?- maplist(select, LP, [[a, b, c], [1, 2, 3]], [[a, c], [2, 3]]).
LP = [b, 1];
false.

?- maplist(select(a), [[a, b, c, a], [b, a, d, c, a]], L).
L = [[b, c, a], [b, d, c, a]] ;
L = [[b, c, a], [b, a, d, c]] ;
L = [[a, b, c], [b, d, c, a]] ;
L = [[a, b, c], [b, a, d, c]].

?- maplist(reverse, [[a, b, c]], [[c, X, a]]).
X = b.

Cvičení: Naprogramujte predikat setrizeny(:Nejvyse, +L) splnitelný, jestliže pro libovolné dva sousední prvky A, B seznamu L platí Nejvyse(A, B).

Cvičení: Naprogramujte predikat setrid(:Nejvyse, +L, -SL) splnitelný, jestliže SL je setřízený seznam obsahující prvky L.

Cvičení: Popřemýšlejte o tom, jak by se akumulátorová technika mohla zobecnit do metapredikátu.

Metapredikáty však jdou i použít jako parametry jiných predikátů. Když jako parametr maplistu dáme zase maplist, dostaneme variantu map pro seznamy seznamů.

add1(X,Y) :- Y is X+1.

?- maplist(add1 [1,2,3], LY).
LY = [2, 3, 4].

?- maplist(maplist(add1), [[1,2],[3,4,5],[6]], LLY).
LLY = [[2, 3], [4, 5, 6], [7]].

Stromy

Doteď jsme pracovali se seznamy, zkusme si tedy pohrát se strukturami složitějšími. Speciálně binárními stromy. Binární strom budeme reprezentovat dvěma termy. Atom nil bude reprezentovat prázdný strom a term t(L, X, R) nechť reprezentuje kořen stromu, jehož vrchol obsahuje klíč X, levý syn je strom L a pravý syn je strom R.

Začněme jednoduše kontrolou, že to, co máme v ruce, je opravdu strom. Tuto kontrolu provedeme predikátem strom(?T).

% strom(?T) :- T je strom.
strom(nil).
strom(t(L, _, R)) :- strom(T), strom(R).

?- strom(t(t(nil, _, nil), _, nil)).
true.

Vzhledem k tomu, jak se chová vyhodnocování pravidel, tato kontrola prohledává strom do hloubky. Obecně libovolná technika, která funguje na principu prohledávání stromu do hloubky, lze v Prologu snadno napsat.

Všimněme si, že děláme stejnou práci jako u seznamů. Základní případ je, pokud je strom (seznam) prázdný. Jinak rozděláme strukturu neprázdného stromu (seznamu), něco uděláme s uloženým prvkem a zarekurzíme se. Pro seznamy jsme toto chováni popsali metapredikátem maplist. To samé můžeme udělat i pro stromy!

% maptree(:P, ?T) :- pro každý prvek ve stromu platí P.
maptree(_, nil).
maptree(P, t(L, X, R)) :- call(P, X), maptree(P, L), maptree(P, R).
% maptree(:P, ...) obecně pro více stromů.

?- maptree(integer, t(t(nil, 5, nil), 3, nil)).
true.

?- maptree(reverse, t(nil, [1,2,3], t(nil, [a,b,c], nil)), T).
T = t(nil, [3,2,1], t(nil, [c,b,a], nil)) .

Cvičení: Mějme predikáty Zkombinuj(VL, X, VR, V), který zkombinuje výsledky z levého a pravého podstromu s hodnotou v kořeni do V, a Nil(V), který místo nil vrátí V. Naprogramujte metapredikát dfs(:Zkombinuj, :Nil, ?T, ?V), který takto zkombinuje strom do jednoho prvku.

Pojďme nyní převádět strom na seznam. Jak to ale provést? Existuje několik možností, my si vezmeme pořadí preorder. V tomto pořadí by seznam měl pro daný strom nejprve obsahovat hodnotu kořene, pak jeho levý podstrom v preorder uspořádání a nakonec pravý podstrom v preorder uspořádání.

% preorder_list(+T, -L) :- L je seznam vrcholů T v preorder pořadí.
preorder_list(nil, []).
preorder_list(t(L, X, R), [X|S]) :-
    preorder_list(L, SL),
    preorder_list(R, SR),
    append(SL, SR, S).

?- preorder_list(t(t(nil, b, t(nil, c, nil)), a, t(nil, d, nil)), L).
L = [a, b, c, d].

Cvičení: Naprogramujte predikáty inorder_list/2 a postorder_list/2 fungující podobně, jako preorder_list, které však používají inorder (levý podstrom, kořen, pravý podstrom) a postorder (levý podstrom, pravý podstrom, kořen) pořadí.

Cvičení: Naprogramujte preorder_list pomocí metapredikátu dfs.

Ne vždy však chceme jako výsledek dostat seznam, naopak bychom chtěli využít nedeterminismu k tomu, abychom postupně prozkoušeli všechny prvky stromu. Nechť postorder(+T, -X) je splnitelný, jestliže X je vrcholem T a navíc predikát vrací všechny vrcholy v postorder uspořádání.

postorder(t(L, _, _), X) :- postorder(L, X).
postorder(t(_, _, R), X) :- postorder(R, X).
postorder(t(_, X, _), X).

?- postorder(t(t(nil, b, t(nil, c, nil)), a, t(nil, d, nil)), X).
X = c ;
X = b ;
X = d ;
X = a.

Cvičení: Naprogramujte predikáty inorder/2 a preorder/2 analogicky.

Stromy můžeme využít třeba k tomu, abychom popsali vyhodnocování aritmetických výrazů. Listy budou obsahovat čísla a vnitřní vrcholy budou obsahovat operátor, který se má aplikovat na vyhodnocené podstromy.

Zde si můžeme trochu upravit definici stromu, speciálně nil zahodíme a místo toho list budeme reprezentován přímo číslem. Toto můžeme udělat, protože ve vyhodnocovacím stromu bude mít vnitřní vrchol vždy dva syny.

Pojďme tedy naprogramovat predikát vyhodnot(+T, -H) splnitelný, jestliže T je vyhodnocovací strom a H je hodnota, na kterou se vyhodnotí. Řekněme, že budeme podporovat sčítání a násobení.

vyhodnot(H, H) :- number(H).
vyhodnot(t(L, +, R), H) :- vyhodnot(L, HL), vyhodnot(R, HR), H is HL + HR.
vyhodnot(t(L, *, R), H) :- vyhodnot(L, HL), vyhodnot(R, HR), H is HL * HR.

?- vyhodnot(t(3,+,5), H).
H = 8.

?- vyhodnot(t(t(1,+,2),*,4), H).
H = 12.

Cvičení: Upravte pomocí metaprogramovacích technik predikát vyhodnot tak, aby vnitřní vrchol mohl být libovolný operátor, který je podporován operátorem is.