Cvičení 3

Kurs: Paradigmata programování IV
Přednášející: Vilém Vychodil
Cvičící: Vilém Vychodil
Téma cvičení: Řízení výpočtu pomocí řezů. Procedurální rysy PROLOGu.

Procedurální sémantika PROLOGu, pořadí pravidel. Mimologické predikáty. Řízení výpočtu pomocí řezů. Zelené řezy a jejich použití. Implementace binárních vyhledávacích stromů. Červené řezy. Procedurální rysy PROLOGu. Vytváření podmínek a cyklů pomocí vestavěných predikátů. Koncová rekurse. Interaktivní programy.


1.  Procedurální sémantika PROLOGu

V předcházejících dvou cvičeních jsme vytvářeli logické programy, přitom jsme se soustředili na vytváření databází faktů a pravidel bez toho, aniž bychom explicitně vyžadovali jejich přesné pořadí ve zdrojovém kódu programu. Z hlediska deklarativní sémantiky logického programu to ani není nutné. Deklarativní význam programu chápeme jako množinu všech tvrzení, která lze z programu vyplývají.

Z jiného úhlu pohledu má smysl zabývat se rovněž i procedurální sémantikou logického programu. Interpret PROLOGu se během výpočtu snaží splnit zadaný cíl, přitom probírá jednotlivá pravidla v přesně daném pořadí. Vhodné pořadí pravidel může zvýšit efektivitu výpočtu. V neposlední řadě, uživatel má v PROLOGu k disposici mimologický predikát řezu, kterým může explicitně ovlivňovat průběh výpočtu.

Vše si demonstrujme na motivačním příkladu. Uvažujme následující pravidla.

 %% odstran prvek X z daneho seznamu 
 odstran(_,[],[]).
 odstran(X,[X|Y],Z) :- odstran(X,Y,Z).
 odstran(X,[Q|Y],[Q|Z]) :- odstran(X,Y,Z).

Predikát odstran slouží k odstranění daného prvku ze seznamu. Pokud jej použijeme k odstranení prvku „a“ ze seznamu [a,b,c], obdržíme následující odpovědi.

 ?- odstran(a,[a,b,c],R).
 R = [b, c] ;
 R = [a, b, c] ;
 No

To jest kromě intuitivně očekávané odpovědi R=[b,c] jsme obdrželi ještě druhou odpověď. Druhá odpověď není nikterak překvapující, při jejím odvození bylo použito třetí pravidlo zcela správně. Kdybychom chtěli výše upravený program upravit tak, aby bylo výsledné řešení pouze jedno, máme v zásadě dvě možnosti. Můžeme použít buďto negaci, nebo řez. Negací se budeme zabývat na dalším cvičení. Řešení problému pomocí řezu si ukážeme již na tomto cvičení. V tuto chvíli je dobré předeslat, že použití řezu ve výše uvedeném případě znemožní PROLOGu najít jedno z řešení, které přirozeně plyne z výše uvedeného kódu. V takovém případě se začne deklarativní sémantika programu rozcházet s jeho procedurální sémantikou PROLOGu.

2.  Zelené řezy

Mimologický predikát řezu je v PROLOGu representován speciálním vestavěným predikátem „!“. Narazí-li PROLOG během výpočtu na řez, je okamžitě splněn a interpret pokračuje dalším cílem napravo od řezu. Řez ovšem zabraňuje navrácení k cílům nalevo od něj. Opětovné plnění řezu tedy skončí neúspěchem a neúspěchem končí i plnění všech cílů nalevo od řezu včetně hlavy pravidla. Tím dojde k odřezání jisté množiny výpočtů. Podle nebezpečnosti (a nevhodnosti) použití dělíme řezy do dvou skupin -- na zelené a červené. Zelenými řezy se budeme nyní zabývat.

Zelený řez lze chápat jako nástroj sloužící k odstranění nedeterminismu programu. Při psaní pravidel v PROLOGu často dojdeme do situace, kdy se jednotlivá pravidla „vzájemně vylučují“. PROLOG se ovšem vždy pokouší o jejich splnění i když se z hlediska nalezení řešení jedná o „mrtvé větve výpočtu,“ kde žádné řešení nalezeno být nemůže. V takovém případě je vhodné využít řez, který PROLOGu odřeže větve výpočtu, které nikam nevedou.

Pro demonstraci budeme pracovat s lineárně uspořádanými seznamy prvků. Relaci ostrého uspořádání budeme mít dánu pomocí faktů z jednoduché databáze, kterou naleznete spolu s následujícími pravidly v přiloženém souboru green-cut.prolog. Toto uspořádání budeme používat i v následujících příkladech s binárními vyhledávacími stromy.

 %% slevani usporadanych seznamu 
 slij([X|A],[Y|B],[X|C]) :- lt(X,Y), !slij(A,[Y|B],C).
 slij([X|A],[Y|B],[X,Y|C]) :- eq(X,Y), !slij(A,B,C).
 slij([X|A],[Y|B],[Y|C]) :- lt(Y,X), slij([X|A],B,C).
 slij(A,[],A).
 slij([],B,B).

Použití řezu v předchozím příkladu je zřejmé. Je-li splněn některý z prvních předpokladů v libovolném z prvních dvou pravidel, pak se již PROLOG nemusí snažit splnit další pravidla, protože pro libovolné dva prvky máme buď lt(X,Y), lt(Y,X), nebo eq(X,Y). Provedením řezu jsme neomezili množinu řešení, pouze jsme zefektivnili výpočet. Uvedením řezu jsme v podstatě odstranili nedeterminismus programu.

Úkol 1. Přiložený kód pečlivě prostudujte a vyzkoušejte.

Úkol 2. Bez použití predikátu slij/3 vytvořte pravidla definující predikát zatrid/3, jehož účelem je zatřídit prvek X do daného setříděného seznamu ale tak, aby seznam neobsahoval duplicity. Pokud se tedy již prvek v seznamu vyskytuje, nebudeme jej do něj znovu vkládat. Při vytváření predikátu využijte vhodně zelený řez analogicky, jako v předchozím ukázkovém příkladu. Snažte se o co největší efektivitu.

Úkol 3. Pomocí predikátu zatrid/3 z předchozího úkolu naprogramujte pravidla realisující „insert sort“.

Nyní se budeme zabývat opět zefektivněním výpočtu, tentokrát však budeme pracovat s binárními vyhledávacími stromy. Jelikož již byla tato látka probrána v jiných předmětech, budu předpokládat, že všichni víte, o co se jedná. Uzly binárního vyhledávacího stromu budeme representovat termy ve tvaru node(key, val, left, right), kde keyval representují klíč a hodnotu v uzlu a leftright je levý a pravý podstrom. Prázdný podstrom budeme značit atomem nil.

Například tedy term

 node(d, 10, node(c, 2, node(b, 35, nil, nil), nil),
             node(f, 5, node(e, 11, nil, nil),
                        node(g, 13, nil, nil)))

representuje binární vyhledávací strom

Obrázek 1. Binární vyhledávací strom.

Připomeňme, že klíče jsou atomy „a“ až „g“, hodnoty v uzlech jsou v tomto případě číselné. Nyní můžeme vytvářet pravidla pro práci s binárním vyhledávacím stromem, například pravidla pro vyhledávání prvků podle klíčů a vkládání nových uzlů. Při implementaci je vhodné použít zelený řez k odstranění větví výpočtu, které nikam nevedou -- například u vkládání vždy víme, do kterého podstromu budeme daný prvek vkládat, zpracování pravidla pro další podstrom již nemá smysl.

Úkol 4. S využitím zeleného řezu naprogramujte vyhledávání prvků v binárním vyhledávacím stromu. Napište pravidla pro predikát hledej/3, který pro zadaný klíč a binární vyhledávací strom vrátí hodnotu prvku s tímto klíčem. Pokud prvek neexistuje, pravidlo by mělo vrátit atomickou hodnotu none.

Úkol 5. Naprogramujte efektivní vkládání do binárního vyhledávacího stromu. Napište pravidla pro predikát hledej/4, který má vstupní argumenty: klíč, hodnotu a strom. Výsledkem je strom vzniklý vložením nového uzlu. Pokud již ve stromu existuje uzel s daným klíčem, pouze přepište starou hodnotu v uzlu.

3.  Červené řezy

S červenými řezy je potřeba zacházet velmi obezřetně. Jedná se o řezy, jejichž přítomnost mění procedurální význam programu. Pokud je řezem odstraněno některé z řešení, deklarativní a procedurální sémantika programu v PROLOGu bude různá. Používání červených řezů rovněž dost znepřehledňuje samotný program a jejich použití se až na výjimky nedoporučuje (stejně tak, jako například nelokální skok longjmp známý z jazyka C v systému UNIX).

Červené řazy bývají používány především k vynechání některých pravidel. Při jejich použití je však nutné vždy vycházet ze známé strategie, kterou se PROLOG snaží plnit cíle. Nyní se vrátíme k úvodní ukázce pravidel pro odstranění všech výskytů prvku v seznamu a doplníme ji o řez následovně.

 %% odstran prvek X z daneho seznamu, vyuziti rezu 
 odstran(_,[],[]).
 odstran(X,[X|Y],Z) :- !odstran(X,Y,Z).
 odstran(X,[Q|Y],[Q|Z]) :- odstran(X,Y,Z).

Bude-li během výpočtu použito druhé pravidlo, pak již červený řez znemožní použití třetího pravidla, protože dojde k neúspěchu při navrácení za levou stranu řezu. Pokud tedy použijeme výše upravené pravidlo, chování interpretu bude následující.

 ?- odstran(a,[a,a,b,a,c],R).
 R = [b, c] ;
 No

Deklarativní sémantika programu zůstává nezměněna, jelikož řez je mimologický operátor. Použitím řezu jsme však zasáhli do výpočtu s úmyslem cíleně vynechat některá řešení, která z našeho pohledu nebyla zajímavá. Výše uvedený příklad byl demonstrační, v podobných situacích je mnohem vhodnější využít negaci, kterou dosáhneme téhož efektu a nesnížíme přitom čitelnost programu. Používání červených řezů je výhodné v případě, kdy je nasazení negace nevhodné z důvodu výpočetní složitosti.

Úkol 6. Prostudujte a vyzkoušejte výše uvedená pravidla.

Úkol 7. S použitím predikátu odstran/3 vytvořte pravidla pro predikáty unikatni/2 a mnozina/1. Predikát unikatni/2 pro daný seznam vrací seznam prvků bez duplicit. Predikát mnozina/1 je pravdivý, právě když je jeho argument seznam representující množinu, to jest seznam prvků bez duplicit.

Podobně jako v předchozím případě můžeme upravit i pravidla realisující predikát je_prvkem/2, který jsme používali v předchozím cvičení. Při testu, zda-li je daný prvek prvkem seznamu je možné ukončit prohledávání s úspěchem, pokud je nalezen první výskyt. Další výskyty v seznamu jsou z pohledu hledání prvku již nezajímavé.

Úkol 8. Napište pravidla definující predikát existuje_prvek/2, jehož význam je: „V dané množině existuje zadaný prvek“. Při implementaci použijte červený řez.

Úkol 9. Zamyslete se nad tím, čím se předchozí implementace liší od své bezřezové varianty. Je daný predikát invertibilní? Je možné pomocí něj získat všechny prvky seznamu?

Dalším typickým problémem, kde lze využít červený řez je nahrazování prvků v seznamu. Předpokládáme, že máme zadán výchozí seznam, dále prvek a jeho náhradu. Výstupem je seznam, který vznikne nahrazením některých výskytů (třeba všech) zadaného prvku z výchozího seznamu. Predikát pro nahrazení všech výskytů by měl pracovat například následovně.

 ?- replace([a,b,c,a,d],a,x,R).
 R = [x, b, c, x, d] ;
 No

Úkol 10. S využitím červeného řezu naprogramujte predikát replace/4 tak, aby pracoval jako v předchozí ukázce. To jest ve výsledném seznamu budou nahrazeny všechny výskyty vzorového prvku druhým zadaným prvkem.

Úkol 11. S pomocí předchozích predikátů a vhodným využitím řezů napište pravidla definující predikáty replace_first/4, replace_last/4, které se chovají analogicky jako predikát replace/4 pouze s tím rozdílem, že provádějí náhradu jen prvního a posledního výskytu zadaného prvku.

4.  Další predikáty pro řízení výpočtu

Na řezy se lze dívat jako na prostředek PROLOGu, který uživateli umožňuje řídit proces navrácení (backtracking). Kromě řezů PROLOG disponuje řadou dalších vestavěných predikátů, pomocí nichž lze do PROLOGu zavést některé rysy typické pro procedurální programovací jazyky. V poslední části tohoto cvičení se budeme věnovat právě těmto predikátům.

Mezi často používané predikáty umožňující ovlivňovat navrácení patří vestavěné nulární predikáty fail/0 a true/0. Predikát fail/0 je vždy nesplněn a tím pádem vyvolává navrácení. Predikát true/0 je splněn, ale pokus o jeho opětovné plnění vždy selže. Predikát fail/0 je dostačující aparát pro nalezení všech alternativních řešení. Problematiku si demonstrujme příkladem, ve kterém je definováno pravidlo pro výpis všech prefixů zadaného seznamu.

 %% nalezeni vsech prefixu daneho seznamu 
 prefix(L) :- append(X,_,L), write(X), nlfail.

Poznamenejme, že predikát append/3 je zabudovaný v PROLOGu a slouží ke spojování seznamů -- jeho chování je identické s predikátem spoj z minulého cvičení. V příkladu byl dále použit vestavěný unární predikát write/1 a nulární predikát nl/0. Jejich význam je zřejmý. Predikát write/1 je vždy splněn a jako vedlejší efekt zobrazí hodnotu argumentu. Opětovné plnění predikátu write/1 selže. Predikát nl/0 se chová analogicky, pouze na výstup zapíše znak „nový řádek“.

Úkol 12. Vyzkoušejte předchozí příklad.

Nyní se pokusíme předchozí program zobecnit tak, abychom získali pravidlo vypisující všechna řešení cílu, který zadáme jako argument.

 %% obecny vypis vsech reseni 
 reseni(Goal) :- Goalwrite(Goal), nlfail.
 reseni(Goal,X) :- Goalwrite(X), nlfail.

Nyní si můžeme vytvořené predikáty vyzkoušet, například takto:

 %% vypis vsech suffixu 
 ?- reseni(append(_,X,[a,b,c,d,e]),X).

V předchozím příkladu si všimněte cílu, který je zadán uvedením proměnné „Goal“. Pokud bude na proměnnou navázán term, PROLOG se jej bude snažit plnit jako cíl. Pokud by ovšem proměnná byla nenavázaná, chování interpretu nelze předvídat -- PROLOG by se proměnnou snažil unifikovat s objektem representujícím „cokoliv“. V některých implementacích PROLOGu je nutné interpretaci termu jako cílu vynutit vestavěným metalogickým predikátem call/1.

V PROLOGu lze pomocí řezu vytvořit predikát umožňující vyhodnocovat podmíněné výrazy typu „if ~ then ~ else“. Základní myšlenka je snadná, pokud uspěje podmínka, pak je vyhodnocen výraz, ale pomocí řezu musíme zamezit následnému vyhodnocení alternativního výrazu. Ten by měl být vyhodnocen pouze v případě, kdy je podmínka nesplněna. Viz ukázkový kód.

 %% vytvoreni podminky pomoci cerveneho rezu 
 if_then_else(Cond,Then,_) :- Cond!Then.
 if_then_else(_,_,Else) :- Else.

Úkol 13. Otestujte předchozí příklad. Napište cíl, kterým ověříte příslušnost prvku k seznamu, využít můžete vestavěný predikát member/2. Definujte různé akce.

Cyklus lze v PROLOGu realisovat pomocí vestavěného predikátu repeat/0. Predikát repeat/0 je vždy splněn a vždy uspívá i jeho opakované plnění. Kdyby predikát nebyl v interpretu zahrnut, mohli bychom si jej snadno naprogramovat. Následující predikát opakuj/0 se chová identicky jako predikát repeat/0.

 %% predikat pro vytvareni cyklu 
 opakuj.
 opakuj :- opakuj.

Predikát repeat/0 v podstatě „obrací směr průchodu programem“, protože umožňuje opětovné plnění cílů, bez ohledu na to, že již byly nalezeny všechny alternativy. Typickou ukázkou použití predikátu je vytvoření nekonečného cyklu.

 %% ukazka nekonecneho cyklu 
 ?- opakujwrite('Blah'), nlfail.

Po prvním výpisu textu a při návratu k výrazu write('Blah') predikát write/1 neuspívá. PROLOG se tedy snaží opětovně plnit cíl opakuj. Díky druhému pravidlu a následně i prvnímu pravidlu definujícímu predikát opakuj/0 je však tento cíl opět splněn a vše se opakuje.

Nekonečný cyklus není sám o sobě příliš užitečný. Pomocí predikátu repeat/0 lze však konstruovat i podmíněný cyklus typu „repeat ~ until“ a to opět pomocí řezu. V předchozí ukázce nekonečného cyklu byl na konec dotazu umístěn predikát fail/0, který vždy způsobil navrácení. Místo něj však můžeme uvést limitní podmínku a za ni můžeme umístit řez. Pokud bude limitní podmínka splněna, bude splněn i řez a po pokusu o jeho opětovné plnění bude cyklus ukončen. Viz ukázku použití.

 %% vypsani vsech neprazdnych prefixu bez daneho prvku 
 hledej(List,Member) :-
     opakuj,
     append(Y,X,List),
     if_then_else(Y = [], true, (write(Y), nl)),
     X = [Member|_], !.

V ukázce byl použit binární predikát =/2, který se pokusí unifikovat dva termy a je splněn, právě když unifikace proběhne s úspěchem. Podmíněné cykly jsou s oblibou využívány při vytváření interaktivních programů. Načítání uživatelského vstupu lze provést vestavěným predikátem read/1. Predikát načte term z uživatelského vstupu a naváže jej na proměnnou, která je mu předána jako argument. Při opětovném plnění predikát neuspívá. Každý vstup je potřeba ukončit tečkou. Ukázku interakce s uživatelem nalezete v souboru xmas.prolog.

Úkol 14. Vyzkoušejte předchozí programy.

Úkol 15. Pomocí řezu naprogramujte pravidlo pro unární predikát jednou/1. Predikát bere jako argument výraz, který má být splněn jakožto cíl. Predikát jednou/1 slouží k nalezení nejvýše jednoho řešení. Při pokusu o opětovné plnění neuspívá. Pokud řešení neexistuje, činnost skončí neúspěchem. Viz ukázku.

 ?- jednou(member(X,[a,b,c,d,e])).
 X = a ;
 No

Úkol 16. Pomocí řezu naprogramujte pravidlo pro unární predikát  proved/1. Predikát bere jako argument výraz, který má být splněn jakožto cíl. Predikát proved/1 slouží k nalezení nejvýše jednoho řešení. Narozdíl od predikátu jednou/1, je však pravdivý i v případě, kdy žádné řešení neexistuje. Při implementaci vhodně využijte anonymní proměnnou. Viz ukázku.

 ?- proved(member(k,[a,b,c,d,e])).
 Yes