Cvičení 2

Kurs: Paradigmata programování IV
Přednášející: Vilém Vychodil
Cvičící: Vilém Vychodil
Téma cvičení: Termy a rekursivní pravidla. Práce se seznamy.

Atomy a termy. Nerekursivní a rekursivní pravidla. Rekursivní datové struktury. Modelování aritmetiky. Symbolická manipulace s výrazy, zjednodušování výrazů. Koncepce seznamu v jazyku PROLOG. Manipulace se seznamy. Kombinatorické úlohy nad seznamy. Reprezentace uspořádaných množin.


1.  Termy a rekursivní pravidla

V předcházejícím cvičení jsme používali fakta, která definovala relaci pouze mezi atomy. V PROLOGu však lze k označení objektů používat zcela libovolné termy. Z tohoto pohledu jsou atomy pouze nulární funkční symboly, neboli konstanty. Uvažujme následující příklad.

 %% databaze faktu
 package(apt,       props(important,base)).
 package(apt_utils, props(optional,admin)).
 package(apt_zip,   props(extra,admin)).
 
 %% jednoduche pravidlo
 section(Name,Section) :- package(Name,props(_,Section)).

Například výraz props(important,base) je term, výrazy importantbase jsou atomy. Pravidlo uvedené na posledním řádku slouží k extrakci informací o sekci, v níž se daný balík nachází. Oproti poslednímu příkladu z minulého cvičení je tedy relace package/2 pouze binární a jedná se o relaci mezi názvem balíku a jeho vlastnostmi, které jsou vyjádřeny složitějším termem. Uvedený příklad si vyzkoušejte. Předchozí ukázku lze chápat jako zpřehlednění zápisu programu, případně pokus o lepší strukturování informace zachycené v databázi. Z hlediska důsledků logického programu jsme však nic podstatného nepřidali.

Všechny doposud uvažované programy měly konečnou množinu faktů a odvozovacích pravidel, která definovala nové vztahy na základě již existujících JINÝCH vztahů. Taková pravidla se nazývají nerekursivní. Přirozeným rozšířením je uvažovat pravidla, která definují vztahy mimo jiné pomocí sebe sama. Těmto pravidlům říkáme rekursivní.

Uvažujme nyní následující databázi faktů.

 %% relace popisujici prechody KNA
 delta(q0,a,q1). delta(q0,a,q3). delta(q1,b,q0).
 delta(q1,c,q1). delta(q2,a,q0). delta(q2,a,q1).
 delta(q2,c,q3). delta(q3,b,q3). delta(q3,c,q2).
 
 %% koncove stavy
 final(q1). final(q2).

Databázi můžeme interpretovat jako definici přechodové funkce konečného nedeterministického automatu

Obrázek 1. Konečný nedeterministický automat.

Předchozí automat není deterministický, protože například ze stavu q2 je při vstupu „a“ definován přechod do stavů q0q1. Řetězce nad trojprvkovou abecedou {a,b,c} můžeme reprezentovat pomocí termů. Uvažujme následující rekursivní definici.

Například tedy řetězec „abbcaa“ lze reprezentovat termem a(b(b(c(a(a(nil)))))). Nyní můžeme vytvořit rekursivní pravidla definující výpočet KNA jakožto ternární relaci „ze stavu Q a při daném vstupu dojde KNA do stavu State“.

 %% definice vypoctu KNA
 comp(Q,nil,Q).
 comp(Q,a(X),State) :- delta(Q,a,W), comp(W,X,State).
 comp(Q,b(X),State) :- delta(Q,b,W), comp(W,X,State).
 comp(Q,c(X),State) :- delta(Q,c,W), comp(W,X,State).

Takto definované pravidlo je rekursivní a jeho význam je také zřejmý. Při prázdném vstupu se dostaneme pouze do aktuálního stavu, to říká první pravidlo a tvoří limitní podmínku rekurse. Další tři pravidla redukují problém dosažitelnosti stavu při zadaném vstupu na problém dosažitelnosti stavu v jednom kroku a na sebe sama pro řetězec zkrácený o první znak.

Úkol 1. Prostudujte výše uvedený kód. Otestujte, které z řetězců abbcaa, abbcacacab jsou akceptovány KNA (pro počáteční stav q0). Vytvořte pravidlo definující predikát accepted/1, který je pravdivý, právě když je daný řetězec akceptovaný KNA. Využijte přitom predikát final/1.

2.  Modelování aritmetiky

Tato část práce má za úkol procvičit práci s termy. Pomocí termů lze jednoduše reprezentovat přirozená čísla. Nulu můžeme chápat jako konstantu 0, jedničku jako term s(0), dvojku jako term s(s(0)) a tak dále. Funkční symbol s má význam následovníka. V přiložené ukázce najdete nejprve pravidla definující vlastnost natural/1 (býti přirozeným číslem). Dále je zde definován ternární predikát add/3 vyjadřující vztah „X plus Y je rovno Z“.

 %% prirozene cislo
 natural(0).
 natural(s(X)) :- natural(X).
 
 %% scitani prirozenych cisel
 add(X,0,X).
 add(X,s(Y),s(Z)) :- add(X,Y,Z).

Sčítání obvykle chápeme jako binární funkci. V PROLOGu je tedy realizováno ternárním predikátem. Definice sčítání využívá faktu, že následník součtu x+y je roven součtu x a následníka y. Připomeňme že PROLOG standardně nerozlišuje argumenty na vstupní a výstupní. Obecně lze každý z argumentů použít jako vstupní, případně výstupní. Při vhodné definici pravidel lze používat libovolný z argumentů jako výstupní. Sčítání zavedené předchozím způsobem je plně invertibilní. V důsledku tedy můžeme predikát používat rovněž k odčítání, případně k rozkladu přirozeného čísla na dva sčítance.

Úkol 2. Vyzkoušejte předchozí kód. Otestujte predikát add/3, použijte jej rovněž k odčítání čísel a k rozkladu čísla na dva sčítance.

V podobném duchu, jako byly predikáty natural/1 a add/3 budeme nyní vytvářet další. Při vytváření rekursivních pravidel je nutné dbát jisté obezřetnosti, snadno lze vytvořit pravidla, při jejichž splňování se interpret zacyklí nebo mu přeteče zásobník.

Úkol 3. Vytvořte pravidla pro predikáty even/1 (číslo je sudé), odd/1 (číslo je liché). Dále definujte predikáty leq/2 a lt/2 přirozeného uspořádání a ostrého uspořádání přirozených čísel. Predikáty otestujte.

Úkol 4. Vytvořte pravidla definující predikát mul/3 vyjadřující vztah „X krát Y je rovno Z“. Využijte známého faktu, že výsledek součinu x a následníka y je roven součinu xy plus x. Pomocí násobení dále definujte predikát pow/3 reprezentující celočíselnou mocninu.

Úkol 5. Pomocí již hotových predikátů napište pravidla pro výpočet faktoriálu a Fibonacciho čísla.

3.  Symbolická manipulace s výrazy

Termy mohou sloužit k reprezentaci symbolických výrazů, se kterými může být dále manipulováno pomocí speciálních pravidel. Typickým příkladem je problematika zjednodušování výrazů. Uvažujme například následující databázi faktů a pravidla.

 %% fakta a zjednodusovani vyrazu
 add(+(X,0),X). add(+(0,X),X). mul(*(_,0),0).
 mul(*(0,_),0). mul(*(1,X),X). mul(*(X,1),X).
 
 %% X je zjednoduseno na Y
 simplify(+(X,Y),Z) :-      simplify(X,CX), simplify(Y,CY), add(+(CX,CY),Z).
 simplify(*(X,Y),Z) :-      simplify(X,CX), simplify(Y,CY), mul(*(CX,CY),Z).
 simplify(X,X).

Úvodní fakta se týkají zjednodušování aritmetických výrazů. Aritmetické výrazy jsou reprezentovány termy obsahujícími symboly pro sčítání (symbol „+“) a násobení (symbol „*“). Ve faktech je například zachyceno, že přičtením nuly k libovolné hodnotě se tato hodnota nezmění, etc. Predikát simplify/2 má význam „Vyraz je zjednodušen na Vysledek“. Viz příklad použití.

 ?- simplify((x+y)+(k*0),Result).
 Result = x+y 

Při zadání cíle bylo využito automatického převodu do infixové notace, které pro symboly „+“ a „*“ prování přímo interpret PROLOGu. Rovněž výstupní výraz byl vypsán v infixové notaci. Dále je dobré uvědomit si, že v předchozím cíli x, y ani k NEJSOU proměnné, jsou to atomy. Jedinou proměnnou ve výrazu je Result. Vyzkoušejte a otestujte předchozí kód.

Úkol 6. Do předchozího programu dopracujte možnost zjednodušovat výrazy obsahující odčítání a dělení.

Úkol 7. S využitím vestavěného predikátu atom/1 vytvořte pravidla definující predikát occurs/2, který je pravdivý, právě když se daný atom vyskytuje v zadaném termu. Viz příklad použití.

 ?- occurs(y,(x+y)*x).
 Yes
 ?- occurs(z,(x+y)*x).
 No

4.  Práce se seznamy

Seznamy jsou v PROLOGu reprezentovány podobně, jako jsou realizovány seznamy v dialektech LISPu, například v jazyku Scheme. Fundamentální roli tečového páru zde však přebírají termy ve speciálním tvaru. V PROLOGu existuje speciální atom „[]“ reprezentující prázdný seznam (analogie () z jazyka Scheme). Nyní lze definovat seznamy induktivně.

Při konstrukci seznamů tedy hraje roli speciální funkční symbol „.“. Pro zjednodušení zápisu lze psát [expr|list] místo .(expr,list), symbol „|“ zde odděluje hlavu seznamu od jeho zbytku. Seznam je možné definovat také výčtem ve tvaru [expr1,...,expr1]. Následující příklad ukazuje jednoduchá pravidla pro práci se seznamy.

 %% priklad nalezeni prvku
 je_prvkem(X,[X|_]).
 je_prvkem(X,[_|List]) :- je_prvkem(X,List).
 
 %% priklad spojeni seznamu
 spoj([],L2,L2).
 spoj([X|L1],L2,[X|Y]) :- spoj(L1,L2,Y).

U predikátu je_prvkem/2 je první argument výstupní, druhý argument je vstupní. V případě predikátu spoj/3 mohou být buďto první dva argumenty vstupní, rovněž první a třetí, případně druhý a třetí mohou být vstupní. Viz příklad.

 ?- spoj([a,b,c],[1,2,3],X).
 X = [a, b, c, 1, 2, 3]
 Yes
 ?- spoj([a,b],X,[a,b,c,d,e]).
 X = [c, d, e]
 Yes

Úkol 8. Otestujte předchozí dva predikáty.

Úkol 9. S využitím aritmetiky z předchozích příkladů naprogramujte pravidla definující predikát delka/2 mající význam: „N je délka daného seznamu List“.

Úkol 10. Vytvořte pravidla pro predikáty prefix/2, suffix/2 s významem „seznam L1 je prefixem/suffixem seznamu L2“. Vyjděte z faktu, že prázdný seznam je prefixem libovolného seznamu a libovolný seznam je svým vlastním suffixem.

Úkol 11. Pomocí predikátů z předchozí úlohy napište pravidla definující predikát podseznam/2 s významem: „seznam L1 je podseznam seznamu L2“.

Problém invertování seznamu lze řešit několikerými způsoby. Jednou z metod je využít již existujícího predikátu spoj/3. Druhou možností je nejprve naprogramovat pravidla pro pomocný predikát revspoj/3, který provádí spojení dvou seznamů, ale ve výsledném seznamu je první z nich obráceně. Viz příklad.

 ?- revspoj([1,2,3],[a,b,c],X).
 X = [3, 2, 1, a, b, c]
 Yes

Problém reverse seznamu pak lze jednoduše vyřešit s využitím predikátu revspoj/3.

Úkol 12. Naprogramujte predikát pro reversi seznamu využívající predikátu spoj/3. Bez využití predikátu spoj/3 naprogramujte pravidla definující predikát revspoj/3.

Dalším klasickým kombinatorickým problémem nad seznamy je generování permutací daného seznamu. K vyřešení tohoto problému si stačí uvědomit, že máme-li k disposici permutaci (n-1)-prvkového seznamu, permutace n-prvkového seznamu získáme zatříděním nového prvku na „libovolnou pozici“ této permutace. V první fázi tedy stačí vytvořit predikát zatrid/3 s výše uvedeným významem. Viz příklad použití predikátu.

 ?- zatrid(x,[a,b],Result).
 Result = [x, a, b] ;
 Result = [a, x, b] ;
 Result = [a, b, x] ;
 No

Úkol 13. S využitím predikátů prefix/2, suffix/2 a spoj spoj/3 naprogramujte pravidla definující výše popsaný predikát zatrid/3.

Úkol 14. Pomocí predikátu zatrid/3 napište pravidla definující predikát permutace/2 s významem: „seznam L1 je permutací seznamu L2“. Zkuste vygenerovat všechny permutace čtyřprvkového seznamu.

5.  Reprezentace uspořádaných množin

Poslední z okruhů úloh tohoto cvičení se věnuje vytvoření reprezentace uspořádané množiny a naprogramování pravidel realizujících běžné operace s uspořádanými množinami. Uspořádanou množinu lze reprezentovat mnoha způsoby. Nyní zvolíme reprezentaci pomocí relace pokrytí. Následující databáze faktů definuje pokrytí.

 %% relace pokryti definujici svaz
 covers(b,a). covers(c,b). covers(d,a).
 covers(e,c). covers(e,d). covers(f,d).
 covers(g,e). covers(g,f).

Této databázi odpovídá následující svaz.

Obrázek 2. Svaz reprezentovaný pokrytím.

Úkol 15. Naprogramujte pravidla definující predikát leq/2, který reprezentuje svazové uspořádání indukované touto relací pokrytí. Dále naprogramujte pravidla definující predikát lt/2 definující ostrou variantu tohoto svazového uspořádání.

Úkol 16. Vytvořte pravidla pro predikáty least_forall/2, greatest_forall/2 s významem: „prvek X je menší/větší roven než vešechny prvky z dané množiny“. Viz příklad použití.

 ?- least_forall(X,[e,f]).
 X = d ;
 X = a ;
 No

V některých případech je výhodné zaznamenat všechna řešení daného problému ve formě seznamu. K tomuto účelu slouží vestavěný predikát setof/3. Predikát setof/3 má za argumenty po řadě term (vstupní), cíl (vstupní) a množinu (výstupní). Výsledná množina (seznam bez duplicit) se skládá z instancí termu, pro který je splněn daný cíl. Viz ukázku.

 ?- setof(X,permutace(X,[a,b,c]),X).
 X = [[a, b, c], [a, c, b], [b, a, c],
      [b, c, a], [c, a, b], [c, b, a]]
 Yes

Úkol 17. S využitím vestavěného predikátu setof/3 a predikátu je_prvkem/2 naprogramujte pravidla definující predikáty infimum/2 a supremum/2 s významem: „element X je infimem/supremem množiny reprezentované daným seznamem“. Viz ukázku použití predikátu.

 ?- supremum(X,[b,c,d]).
 X = e
 Yes