Kate Konczycki

Robinsonova aritmetika

Program k textu

Nyní si zkusíme v Prologu sepsat část Robinsonovy aritmetiky a budeme sledovat, jak se s ní Prolog vypořádá. Nejprve však započneme pravidlem říkajícím, co je platné číslo naší aritmetiky.

% num(X) :- X je 0 nebo X je naslednikem jineho cisla.
num(0).
num(s(X)) :- num(X).

Přirozené číslo N bude v této teorii reprezentované nulou vnořenou N-krát do s. Zkusme se nyní dotazovat na náš predikát num/1 a sledovat, co se stane vložením proměnné do prvního parametru.

?- num(s(s(s(0)))).
true.

?- num(X).
X = 0 ;
X = s(0) ;
X = s(s(0)) ;
X = s(s(s(0))) .

Jak si můžeme všimnout, dotaz na num(X) bude postupně odpovídat každým přirozeným číslem počínaje nulou. Vychází to přímo z definice predikátu, protože vždy máme možnost se buď zastavit a vrátit nulu, nebo obalit proměnnou do dalšího s a zarekurzit se.

Nyní můžeme začít porovnávat. Začneme predikátem leq(X, Y) značícím, že X ≤ Y. Víme, že 0 ≤ Y pro libovolné číslo Y. Jestliže navíc X ≤ Y, pak s(X) ≤ s(Y). Jiná možnost je však říct, že X ≤ X pro libovolné číslo X a pak X ≤ s(Y), jestliže X ≤ Y. Tuto možnost zapíšeme predikátem leq2/2.

% leq(X, Y) :- X ≤ Y.
leq(0, X) :- num(X).
leq(s(X), s(Y)) :- leq(X, Y).

leq2(X, X) :- num(X).
leq2(X, s(Y)) :- leq2(X, Y).

Cvičení: Zapište pravidla pro lt/2 značící relaci < a pomocí již existujících pravidel zapište pravidla geq/2 a gt/2.

Zkusme nyní položit dotazy na naše vytvořené porovnávací pravidla a zkoumat, v čem se liší.

?- leq(s(s(0)), s(s(s(s(0))))).
true.

?- leq2(s(s(0)), s(s(s(s(0))))).
true ;
false.

?- leq(s(s(X)), s(s(s(s(0))))).
X = 0 ;
X = s(0) ;
X = s(s(0)) ;
false.

?- leq2(s(s(X)), s(s(s(s(0))))).
X = s(s(0)) ;
X = s(0) ;
X = 0 ;
false.

Jak vidíme, na dotazy dostáváme stejné odpovědi, akorát obě varianty vracejí výsledky v jiném pořadí. Predikát leq2/2 navíc kromě true vrací i false. To proto, že po nalezení X = Y najde splňující řešení, ale podle druhé varianty může stále zkracovat Y, než dojde k Y = 0 a rekurze selže.

V Prologu tedy záleží na pořadí a způsobu zapsání predikátů. I maličké změny v definici mohou způsobit, že se při vyhodnocování změní složitost výpočtu, nebo se dokonce Prolog zacyklí.

Nejlépe můžeme tento rozdíl vidět, když v dotazu budou oba parametry porovnávání budou proměnné. Zatímco leq(X, Y) bude do nekonečna vracet X = 0 a Y zvětšovat, leq2(X, Y) vždy zvětší X i Y najednou.

Cvičení: Zkuste napsat dotaz, který postupně vrátí všechny dvojice X a Y takové, že X ≤ Y a X, Y ≤ Z. Dotaz by se neměl zacyklit.

Ladění v Prologu

SWI-Prolog má k dispozici rozhraní na ladění dotazů. Nejčastěji budeme používat jeho grafickou variantu, ve které lze vidět aktuální stav zásobníku, kontext ve zdrojovém kódu a unifikaci proměnných.

Toto ladění se spouští zadáním dotazů guitracer. následovaným trace.. Prompt Prologu se při zapnutí ladění změní na [trace] ?- a po zadání dotazu se otevře ladící okno.

Ladič se ovládá přes tlačítka nahoře (jejichž význam lze přečíst najetím ukazatele) nebo jejich klávesové zkratky. Podobně jako u jiných ladičů máme k dispozici krokování a breakpointy. Jakmile je dotaz splněn, výsledek se normálně vypíše do příkazové řádky, která očekává, zda chceme pokračovat. Ladící okno v tuto chvíli nereaguje.

Od porovnávání se přesuneme ke sčítání. Predikát add(X, Y, Z) bude splněn, jestliže X + Y = Z. Víme, že 0 + Y = Y a jestliže zvětšíme X o jedna, zvětší se o jedna i Z.

add(0, X, X) :- num(X).
add(s(X), Y, s(Z)) :- add(X, Y, Z).

Jestliže v dotazu na add(X, Y, Z) dosadíme za X i Y, dostaneme právě jeden výsledek, a to jejich součet Z. Pokud zafixujeme pouze jeden sčítanec, Prolog bude postupně generovat druhý sčítanec a jeho součet přičítáním o 1. Naopak, zafixováním Z Prolog postupně vygeneruje všechny možnosti sčítanců.

Cvičení: Napište predikát sub(X, Y, Z) splnitelný, jestliže X - Y = Z.

Nakonec si zkusíme zapsat násobení. Tentokrát 0 krát cokoliv bude 0 a přičtením k prvnímu činiteli se nám zvětší součin o druhý činitel. Stejným postupem jako u sčítání tedy dojdeme k tomuto:

mul(0, Y, 0) :- num(Y).
mul(s(X), Y, Z) :- mul(X, Y, Z2), add(Y, Z2, Z).

Tento predikát má však háček. Jestliže se dotážeme na mul(X, Y, Z), kde X i Y jsou dosazená čísla, vše je v pořádku a dostaneme odpověď. Když zafixujeme Y a necháme X a Z volné, vygenerované Z budou postupně všechny násobky Y. Bohužel, jestliže necháme zafixovat Z a necháme X nebo Y volné, dostaneme nejvýše jednu variantu, pak se výpočet zacyklí.

Kde se schovává problém? Uvažme dotaz mul(X, s(s(0)), s(s(s(0))))., který se zacyklí. V druhém pravidle voláme mul/3 s volným X a Z2 a Prolog najde z tohoto volání nekonečno variant X a Z2 libovolně velkých. Tudíž nic Prolog nezastavuje zvyšovat X do nekonečna, ale žádné X > Z nesplní add.

Notace parametrů

Z tohoto důvodu budeme u některých predikátů chtít omezovat, jaké parametry mohou dostat. K tomuto účelu si zavedeme notaci pro parametry v definici predikátu, kterou též používá SWI-Prolog ve své dokumentaci. Podle toho, jakým způsobem můžeme daný parametr použít, před tento parametr přidáme:

Podle této notace tedy v Robinsonově aritmetice zapíšeme definice naších predikátů takto:

num(?N) :- N je číslo (0 nebo následník čísla).
leq(?X, ?Y) :- X ≤ Y.
lt(?X, ?Y) :- X < Y.
add(?X, ?Y, ?Z) :- X + Y = Z.
mul(?X, ?Y, -Z) :- X × Y = Z.

V takové notaci je pak dotaz mul(s(s(0)), Y, s(Z)) dobrý, avšak mul(s(X), Y, s(s(s(s(0))))). je nesprávné použití predikátu.

Cvičení: Zkuste napsat predikát factor(-X, -Y, +Z), který pro Z najde X a Y taková, že Z = X × Y. Stačí, když predikát bude fungovat pro volná X, Y.

Jestliže si chcete přečíst, jak zapsat násobení tak, aby se vždy zastavilo a fungovalo všemi směry, můžete si o tom přečíst v tomto článku.

Cvičení: Naprogramujte predikát half(?X, ?Y) :- X je polovina Y a even(?X) :- X je sudé.

Seznamy v Prologu

Program k textu

Prolog má jako jazyk podporu pro seznamy. Jedná se však o jednosměrné spojové seznamy, ve kterých máme rychlý přístup pouze k prvním prvkům.

Seznamy se zapisují pomocí nezáporného počtu termů oddělených čárkou uvnitř hranatých závorek. Do seznamu můžeme kdykoliv přidat svislítko |, které nám rozdělí seznam na dvě části. První část je seznam všech prvků nalevo, druhá část je pak zbytek seznamu.

Pojďme se podívat, jak se seznamy chovají a jak lze využít tato pravidla.

?- [a,b,c] = [a|[b|[c|[]]]].
true.

?- [a,b,c] = [X|Zbytek].
X = a,
Zbytek = [b, c].

?- [a,b,c] = [X, b|Y].
X = a,
Y = [c].

?- L = [a,b | X], X = [c,a].
L = [a, b, c, a],
X = [c, a].

?- [a,b,c] = [a,b,c|X].
X = [].

?- [a,b,c] = [b|X].
false.

?- [] = [X|Y].
false.

?- [a] = [X,Y|Z].
false.

?- L = [a|X], X = b.
L = [a|b].

Tato definice seznamu nám tudíž umožňuje vytvořit částečné seznamy, kde zbytek seznamu je proměnná. Za tu pak můžeme dosadit seznam pomocí jiného predikátu. Tuto vlastnost budeme používat velmi často.

Nic nám též nebrání za zbytek seznamu dosadit něco jiného, než je seznam, ale pak s takovým "podivným seznamem" nebude většina obecných predikátů fungovat.

Celý systém seznamů je pouze syntaktická zkratka. Jestli bychom chtěli, mohli bychom si vytvořit "vlastní" seznamy. Za prázdný seznam [] si zvolíme atom l a konstrukci [X | Xs] přeložíme na l(X, Xs). Jediné, co neumíme říci přímo, je jednoduchý zápis více prvků za sebou.

Z našeho postupu pak jednoduše vyplývá, jak převádět Prologovský seznam na ten náš.

% nas_seznam(?PL, ?NL) :- NL je naše reprezentace seznamu PL.
nas_seznam([], l).
nas_seznam([X|Xs], l(X, Ys)) :- nas_seznam(Xs, Ys).

Napišme si nyní predikát prvek(X, L), který je splnitelný, jestliže seznam L obsahuje prvek X. Ukážeme si i variantu pro naši reprezentaci seznamu.

% prvek(?X, ?L) :- L je seznam obsahující prvek X.
prvek(X, [X|_]).
prvek(X, [_|L]) :- prvek(X, L).

prvek_nas(X, l(X, _)).
prvek_nas(X, l(_, L)) :- prvek_nas(X, L).

Všimněte si použitého výrazu _. Ten říká, že nás daný parametr nezajímá a Prolog za něj může dosadit cokoliv. Dosazení za tento parametr pak Prolog neudržuje.

Tento predikát má Prologu ekvivalent member/2. Otestujme teď, jak se náš predikát chová. 

?- prvek(b, [a, b, c]).
true ;
false.

?- prvek(X, [a, b, c]).
X = a ;
X = b ;
X = c ;
false.

?- prvek(_, []).
false.

?- nas_seznam([a, b, c], L), prvek_nas(b, L).
L = l(a, l(b, l(c, l))) .

?- prvek(a, L).
L = [a|_2692] ;
L = [_2690, a|_2698] ;
L = [_2690, _2696, a|_2704].

Co se stalo u posledního dotazu? V odpovědi se objevily nové volné proměnné, pojmenované podtržítkem a číslem. Prolog totiž našel seznam L takový, že pokud za tyto proměnné dosadíme cokoliv, formuli jistě splníme.

U této odpovědi to speciálně znamená, že když zvolíme libovolné prvky před a a libovolný zbytek seznamu, pak L stále bude obsahovat a. Tudíž můžeme generovat seznamy, které jistě budou obsahovat náš prvek, ale zbytek obsahu nás nezajímá.

Cvičení: Napište predikáty lichy(?L) a sudy(?L) splnitelné, jestliže seznam L má lichou nebo sudou délku.

Už umíme v seznamu hledat, pojďme začít s ním manipulovat. Začneme přidáváním prvku na začátek seznamu, které zvládneme velmi jednoduše.

% pridej_zacatek(?P, ?L, ?PL) :- PL je seznam L navíc s P na začátku.
pridej_zacatek(P, L, [P|L]).

Nyní napíšeme predikát, který naopak přidá prvek na konec seznamu. Ten už bude muset být rekurzivní, protože se nejprve budeme muset dostat ke konci (spojového) seznamu. Jakmile ale už máme v ruce nový seznam s prvkem na konci, rekurzí jej doplníme o zbytek prvků původního seznamu. Přidávání na konec seznamu bude tedy na rozdíl od přidávání na začátek trvat alespoň lineární čas.

% pridej_konec(?P, ?L, ?PL) :- PL je seznam L navíc s P na konci.
pridej_konec(X, [], [X]).
pridej_konec(X, [L|Ls], [L|PLs]) :- pridej_konec(X, Ls, PLs).

Cvičení: Napište predikát liche_prvky(?L, ?OL) :- splnitelný, jestliže seznam OL vznikne ze seznamu L vypuštěním každého druhého prvku. Dotaz liche_prvky([a, b, c], [a, c]) je pravdivý.

Predikát pridej_konec/3 lze zobecnit na spojování dvou seznamů jednoduchou úpravou základního případu. Tento predikát též najdete jako standardní append/3.

% spoj(?A, ?B, ?L) :- L je seznam vzniklý spojením A a B.
spoj([], X, X).
spoj([A|As], X, [A|Ls]) :- spoj(As, X, Ls).

Cvičení: Napište predikáty pridej_zacatek/3 a pridej_konec/3 pomocí predikátu spoj/3.

Cvičení: Napište predikát prefix(?P, ?L) splnitelný, jestliže seznam P je prefixem seznamu L.

Nyní, když umíme přidávat prvky na začátek i na konec seznamu, zkusme napsat predikát otoc(Seznam,Manzes), který obrátí pořadí prvků v seznamu. Budeme tedy postupovat přímočaře. Vždy vezmeme první prvek Seznamu a přidáme jej na konec Manzesu, prázdný seznam se neotáčí.

% otoc(?L, ?LR) :- LR má pořadí prvků obráceně oproti L.
otoc([], []).
otoc([X | Ls], LR) :- otoc(Ls, LRs), pridej_konec(X, LRs, LR).

Tento predikát je jistě korektní, ale není vůbec efektivní. Každé zavolání pridej_konec/3 trvá lineárně dlouho, celkově tedy strávíme kvadratický čas.

Cvičení: Naprogramujte predikát suffix(?S, ?L) splnitelný, jestliže seznam S je suffixem seznamu L.

Cvičení: Naprogramujte predikát prostredni(?L, ?P) splnitelný, jestliže P je prostřední prvek seznamu L. V případě seznamu sudé délky je prostřední prvek ten bližší hlavě.

Akumulátory

Zatím jsme ve všech rekurzivních predikátech postupně zmenšovali seznamy, které do nich šly jako parametry. V mnoha případech je však mnohem efektivnější mít seznam, který se s hloubkou rekurze zvětšuje, a na konci jej celý vybublat ven.

Takový seznam je příkladem akumulátoru -- objektu, který v průběhu rekurze upravujeme a jeho konečnou podobu v základním případě pak vytáhneme ven.

Ukážeme si techniku použití akumulátoru na otáčení seznamu:

% otoc_acc(?L, ?LR) :- otoc/2 s použitím akumulátoru.
otoc_acc(L, LR) :- otoc(L, [], LR).

% otoc(?L, @A, ?LR)
    % Jestliže je seznam prázdný, vrať akumulátor
otoc([], A, A).
    % Odebereme první prvek seznamu a vložíme jej do akumulátoru
otoc([X|Ls], A, LR) :- otoc(Ls, [X|A], LR).

Jak vidíme, v každém kroku rekurze otoc/3 odebereme první prvek ze seznamu L, vložíme jej na začátek A a pokračujeme dále. Druhý prvek seznamu, pokud existuje, se v následujícím kroku rekurze dostane do A před ten první. Jakmile nám dojdou prvky, prohlásíme v základním případě akumulátor, obsahující prvky pozpátku, za výsledný seznam LR.

Nejprve však ještě musíme inicializovat A na prázdný seznam, k tomu slouží predikát otoc_acc/2. Kdybychom se rozhodli, že A začneme jako neprázdný seznam, jako výsledek dostaneme otočený seznam L, za kterým dostaneme původní prvky A.