Kate Konczycki

Standardní uspořádání termů

Prolog na termech definuje standardní uspořádání, které funguje vždy. Na rozdíl od aritmetického porovnávání lze porovnávat cokoliv a nikdy nedostaneme chybu. Pořadí ve standardním uspořádání je definováno následovně:

  1. Volné proměnné jsou uspořádané podle adresy v paměti. Ta většinou odpovídá pořadí, ve kterém jsme je v programu definovali.
  2. Čísla jsou porovnávány hodnotou.
  3. Řetězce (uvnitř uvozovek, speciální typ) jsou porovnávány lexikograficky.
  4. Atomy jsou porovnávány lexikograficky.
  5. Složené termy jsou nejprve porovnané podle arity, pak podle názvu predikátu lexikograficky a nakonec rekurzivně na jejich parametrech.

Operátory, pomocí kterých můžeme porovnávat dle tohoto uspořádání, jsou ==, \==, @<, @=<, @>, @>=. Je důležité, že tyto operátory umí rozpoznat nedosazenou proměnnou od dosazené.

?- T = f(Promenna, JinaPromenna), Promenna @< JinaPromenna.
T = f(Promenna, JinaPromenna).

?- X = [], reverse(X, Y), X @< Y.
false. % X, Y jsou vázané, porovnáváme prázdné seznamy

?- 2.718 @< 3.14.
true.

?- 1000 @< tisic.
true.

?- g(X) @< f(X, Y).
true.

?- g(X) @> f(X).
true.

?- f(a) @< f(b).
true.

?- a(b(x), c(y)) @< a(b(x), c(z)).
true.

?- X \== a, X = a, X == a.
X = a.

?- L = [A, b, C], A == a.
false.

Cvičení: Naprogramujte predikat serazeny(+L) splnitelný, jestliže je L seznam, ve kterém jsou všechny prvky uspořádané dle standardního uspořádání.

Využijme nyní standardní uspořádání v praxi, abychom napsali třídicí predikáty.

Nejprve si ukažme čistě deklarativní přístup. Seznam setříďíme tak, že popřehazujeme jeho prvky tak, aby výsledný seznam byl setřízený. Popřehazování prvků není nic jiného, než permutace. Prolog obsahuje standardní predikát permutation/2, který nedeterministicky vrací jednotlivé permutace seznamu.

% setrid(+L, -SL) :- SL je L s prvky uspořádanými dle standardního uspořádání.
setrid(L, SL) :- permutation(L, SL), serazeny(SL).

Cvičení: Naprogramujte predikát permutation.

Tento přístup jistě vrátí správný výsledek, jen je nepoužitelně pomalý. Všech permutací je n! a v nejhorším případě zkusíme všechny. Proto musíme postupovat chytřeji. Na to využijeme princip rozděl a panuj.

Začneme jednoduchým sléváním dvou seřazených seznamů. Jestliže jeden seznam je prázdný, výsledkem je druhý seznam. Pro dva neprázdné seznamy vždy porovnáme jejich hlavy. Podle výsledku se zarekurzíme a na konci přilepíme k výsledku menší prvek.

% slij(+A, +B, -L) :- A,B jsou uspořádané seznamy, které jsou v L slité.
slij([], [], []).
slij([], B, B) :- B = [_|_]. % deduplikace řešení
slij(A, [], A) :- A = [_|_].

slij([A|As], [B|Bs], [A|L]) :- A @< B, slij(As, [B|Bs], L).
slij([A|As], [B|Bs], [B|L]) :- A @>= B, slij([A|As], Bs, L).

Nyní si napíšeme predikát dělící seznam na dvě poloviny. V tomto případě je jedno jak, tudíž nebudeme hledat polovinu seznamu, ale prostě vždy vezmeme první dva prvky a ty přerozdělíme.

% na_poloviny(?L, ?A, ?B) :- L je seznam, jehož liché prvky jsou v A a sudé v B.
na_poloviny([], [], []).
na_poloviny([X], [X], []).
na_poloviny([X, Y|L], [X|A], [Y|B]) :- na_poloviny(L, A, B).

Když máme k dispozici slévání seznamů, můžeme již napsat rekurzivní MergeSort.

% setrid_MS(+L, -S) :- S je seznam prvků L uspořádaných standardně
setrid_MS([], []).
setrid_MS([X], [X]).
setrid_MS(L, S) :- L = [_, _|_], % chceme alespoň 2 prvky
    na_poloviny(L, A, B),
    setrid_MS(A, SA),
    setrid_MS(B, SB),
    slij(SA, SB, S).

Zkusme nyní jiný rekurzivní třídicí algoritmus, a to QuickSort. Na rozdíl od MergeSortu máme triviální slévání, ale rozdělování je složitější.

% rozdel(+L, +P, -A, -B) :- prvky L jsou rozděleny dle pivota P na menší A a větší B.
rozdel([],_,[],[]).
rozdel([X|L], P, [X|A], B) :- X @< P, rozdel(L, P, A, B).
rozdel([X|L], P, A, [X|B]) :- X @>= P, rozdel(L, P, A, B).

setrid_QS([], []).
setrid_QS([X], [X]).
setrid_QS([P|L], S) :- L = [_|_], % chceme alespoň 2 prvky
    rozdel(L, P, A, B),
    setrid_QS(A, SA),
    setrid_QS(B, SB),
    append(SA, [P|SB], S).

Všimněme si podobnosti zápisu dvou různých třídicích algoritmů.

Samozřejmě, takto naimplementované třídění nebude nikterak rychlé. Nepoužívali jsme řezy, takže se naplno bude projevovat nedeterminismus, který bude zkoušet více variant. Navíc, QuickSort ztrácí velkou výhodu toho, že lze napsat in-place. Prolog ve standardní knihovně obsahuje predikát msort/2, který je podstatně efektivnější (je naprogramovaný v C).

Teď budeme chvíli pracovat s množinami. Ty budeme implementovat pomocí seřazených seznamů bez opakování prvků. Budeme chtít, aby vždy množiny obsahovaly každý prvek nejvýše jednou. Seznam na množinu převedeme jeho seřazením a následnou deduplikací.

na_mnozinu(L, M) :- setrid_QS(L, S), deduplikace(S, M).

Cvičení: Naprogramujte predikát deduplikace(+L, -D) splnitelný, jestliže seznam D vznikne ze seznamu L tak, že každý souvislý úsek stejných prvků P v L je nahrazen jedním P. Dotaz deduplikace([a, b, b, a], [a, b, a]) je pravdivý.

Jakmile máme množinu k dispozici, můžeme v ní snadno testovat náležení prvků pomocí predikátu member. Ten má bohužel lineární čas, nic lepšího se seznamy ani neumíme.

Cvičení: Naprogramujte predikáty sjednoceni(+A, +B, -M), prunik(+A, +B,-M) a rozdil(+A, +B, -M) splnitelné, jestliže A a B jsou množiny a M je jejich sjednocení, respektive průnik a rozdíl. Predikáty by měly běžet v lineárním čase.

Cvičení: Naprogramujte predikáty pridej_prvek(+M, +P, -MP) a odstran_prvek(+M, +P, -MP) splnitelné, jestliže M je množina a MP je množina nově obsahující, respektive neobsahující prvek P.

Rozdílové seznamy

Ve třídění QuickSortem jsme využili predikát append, který má lineární časovou složitost. Jelikož samotné dělení má též složitost lineární, tentokrát nám to nikterak nevadí. Často se však dostaneme do situace, kde se nevyhneme častému spojování dvou seznamů a jeho lineární složitost je příliš pomalá.

Nezoufejme však, v Prologu existuje trik, jak dosáhnout konstantní složitosti při spojování seznamů.

K tomu využijeme toho, že seznamy můžeme mít částečné, kde zbytek seznamu je proměnná. Tuto proměnnou si zviditelníme ven. Pak můžeme v konstantním čase za tuto proměnnou, a tedy zbytek seznamu, kdykoliv dodatečně dosadit jiný seznam, čímž doplníme zbytek seznamu. Samozřejmě, i tento nový seznam může být částečný, který bude mít zase jeho zbytek viditelný.

Takovým seznamům říkáme rozdílové, jelikož se v Prologu standardně zapisují jako L-X. Zde je pomlčka operátor, který jsme si "zapůjčili" k našemu účelu. Stejně tak bychom mohli používat seznam_s_koncem(L, X). Správný rozdílový seznam je pak například [a, b, c|X]-X.

Převod rozdílového seznamu na obyčejný je triviální, za X dosadíme [] a pomlčku s proměnnou zahodíme. Obyčejný seznam na rozdílový musíme převést rekurzivně v lineárním čase, musíme se dopracovat k jeho "konci".

% z_rozdiloveho(+DL, -L) :- DL je rozdílový seznam převedený na obyčejný seznam L.
z_rozdiloveho(L-[], L).

% na_rozdilovy(+L, -DL) :- Seznam L je převeden na rozdílový seznam DL.
na_rozdilovy([], X-X).
na_rozdilovy([P|L], [P|DL]-X) :- na_rozdilovy(L, DL-X).

Když však máme rozdílový seznamy, je jejich spojování velmi snadné a trvá konstantní čas.

% spoj_rozdilove(?X, ?Y, ?Z) :- Z je RS vzniklý spojením RS X a Y.
spoj_rozdilove(A-B, B-C, A-C).

Jak to funguje? Uvažme zavolání spoj_rozdilove([1, 2|X]-X, [3, 4|Y]-Y, DL). Podle faktu se X zunifikuje na [3, 4|Y], tudíž první parametr se zunifikuje na [1, 2|[3, 4|Y]]-[3, 4|Y]. Následně se DL zunifikuje na [1, 2|[3, 4|Y]]-Y, což je [1 ,2, 3, 4|Y]-Y.

?- L1 = A-B, L2 = B-C, L12 = A-C, % Definice spojení
|  L1 = [1,2|X]-X, % První rozdílový seznam
|  L12 = [3,4|Y]-Y. % Druhý rozdílový seznam
L1 = [1, 2, 3, 4|Y]-[3, 4|Y],
A = [1, 2, 3, 4|Y],
B = X, X = [3, 4|Y],
L2 = [3, 4|Y]-Y,
C = Y,
L12 = [1, 2, 3, 4|Y]-Y.

Cvičení: Ukažte, jak pomocí rozdílových seznamů implementovat frontu. Její rozhraní budou obsluhovat predikáty empty_queue(?Q) splnitelná pro prázdnou frontu Q, push(?Q, ?P, ?QP) splnitelný, jestliže QP obsahuje nový prvek P na konci fronty Q, a pop(?Q, ?P, ?QP) splnitelný, jestliže fronta Q na začátku obsahovala prvek P a QP jej nyní neobsahuje.

Vlastní operátory

Zatím jsme pokaždé definovali nové predikáty. Prolog ale pro zpestření jazyka umožňuje definovat operátory. Operátory jsou syntaktickou zkratkou pro funktory, lze je tak též použít. Mnoho operátorů je definováno ve standardní knihovně.

?- X = Y, =(X, Y).
true.

Definice nových operátorů se zařizuje pomocí zavolání predikátu op(Priorita, Typ, Nazev). Priorita je číslo mezi 0 a 1200 definující sílu operátoru. Obecně platí, že operátory s vyšší prioritou se vážou slaběji (násobení má menší prioritu, než sčítání). Závorky a termy, které nejsou operátory, mají prioritu 0.

Typ operátoru je jeden z následujících atomů:

Ve skutečnosti y popisuje operand, který má stejnou nebo nižší prioritu. Operand x pak má vždy nižší prioritu. Operátory bez asociativity se tudíž nemohou řetězit. Pokud se o to pokusíme, dostaneme syntaktickou chybu.

Jestliže chceme definovat operátor v našem programu, musíme nejprve Prolog nechat op/3 vyhodnotit již při překladu. K tomu právě slouží klauzule s prázdnou hlavou. Ukažme si to na příkladě operátoru ~, který zastupuje predikát reverse/2.

:- op(600, xfx, ~).

A ~ B :- reverse(A, B).


?- [1, 2, 3] ~ X.
X = [3, 2, 1].

?- ~(X, [3, 2, 1]).
X = [1, 2, 3].

?- X ~ Y ~ Z.
ERROR: Syntax error: Operator priority clash

O tom, jak jsou definované standardní operátory, můžete najít v manuálu.

Cvičení: Nadefinujte operátor P in L splnitelný, jestliže P je prvkem seznamu L.

Ukažme si jiný příklad užití operátorů, tentokrát si pohrajeme se seznamy. Predikáty uděláme stejně, jako bychom pracovali s aritmetikou, operátor islist bude zastupovat is. Zavedeme si unární operátor @ otáčející seznam a binární operátor ~ spojující dva seznamy.

:- op(550, fy, @).
:- op(600, yfx, ~).
:- op(700, xfx, islist).

% Seznam je seznam.
[] islist [].
[L|Ls] islist [L|Ls] :- Ls islist Ls.

% @L znamená otočený seznam.
L islist @R :- RL islist R, reverse(RL, L).

% A ~ B je spojení seznamů.
L islist X ~ Y :- XL islist X, YL islist Y, append(XL, YL, L).

?- L islist [a, b] ~ @[c, d] ~ @([e, f] ~ [g, h]).
L = [a, b, d, c, h, g, f, e] ;
false.