Poradie klauzúl a cieľov Príklad: opica a banán Riešenie problému opica a banán sa často používa ako jednoduchý príklad riešenia problémov. My na ňom ukážeme ako môžeme vyvinúť program deklaratívnym spôsobom a potom ho analyzovať procedurálne a aký vplyv na odvodenie má poradie klauzúl a cieľov v programe. Problém: opica je v izbe pri dverách. V strede izby je banán, ktorý visí na strope. Opica je hladná a chce dostať banán, ale nemôže ho dostať priamo z podlahy. V izbe pri okne je krabica a opica ju môže použiť. Opica môže vykonať nasledovné činnosti: ísť po podlahe, vyliezť na krabicu, posunúť krabicu a zobrať banán, ak stojí na krabici priamo pod banánom. Môže opica dostať banán? Počiatočný stav je:
Skombinujeme tieto informácie do jedného štruktúrovaného objektu: stav(pri_dverách, na_podlahe, pri_okne, nemá) Cieľový stav je: stav(_,_,_, má) Sú povolené tieto zmeny stavu:
Zmenu stavu vyjadríme predikátom zmena(Stav1, M, Stav2)kde Stav1 je stav pred zmenou, M je vykonaná činnosť a Stav2 je stav po zmene.
Nie všetky činnosti sú povolené v ľubovoľnom stave. Napr. činnosť 'zobrať' je možná iba vtedy, ak opica stojí na krabici priamo pod banánom a ešte nemá banán. Činnosť 'zober' môžeme v prologu zapísať ako fakt: zmena(stav(v_strede, na_krabici, v_strede, nemá), %pred zmenou zober, %zmena stav(v_strede, na_krabici, v_strede, má) ). %po zmene Tento fakt hovorí, že po zmene opica má banán a zostáva na krabici v strede izby. Podobne môžeme vyjadriť aj ostatné činnosti: zmena(stav(P, na_podlahe, P, M), %vylez na krabicu vylez, stav(P, na_krabici, P, M) ). zmena(stav(P1, na_podlahe, P1, M), %posuň krabicu z P1 do P2 posuň(P1, P2), stav(P2, na_podlahe, P2, M) ). zmena(stav(P1, na_podlahe, K, M), %choď z P1 do P2 choď(P1, P2), stav(P2, na_podlahe, K, M) ). Otázka, ktorú náš program musí odpovedať je: Môže opica z počiatočného stavu prístupný(S)kde S je určitý stav.
Pri definícii predikátu
Program opica a banán sme vyvinuli neprocedurálnym spôsobom. Analyzujme teraz jeho procedurálne správanie pri riešení nasledovnej otázky: ?- prístupný(stav(pri_dverách, na_podlahe, pri_okne, nemá)). Prolog nájde správnu postupnosť činností skoro priamo. Dôvod tejto výkonnosti bol v poradí, v ktorom sa klauzuly s funktorom Dôležitosť poradia klauzúl a cieľov V programe, ktorý rieši problém opice a banán, klauzuly o zmene činnosti boli zoradené takto: zober, vylez, posuň, choď. Vzhľadom na procedurálnu sémantiku prologu poradie klauzúl indikuje, že opica dáva prednosť činnosti 'zober' pred 'vylez', 'vylez' pred 'posuň' a 'posuň' pred 'choď'. Táto priorita činností pomáha opici riešiť problém. Čo sa stane, keď bude poradie klauzúl odlišné? Predpokladajme napr. že klauzula pre činnosť 'choď' sa uvedie ako prvá. Skúste vyhodnotenie cieľa ?- prístupný(stav(pri_dverách, na_podlahe, pri_okne, nemá)). Vyhodnotenie tohto cieľa vedie k nekonečnému cyklu. Medzi jednotlivými stavmi nie je žiadny rozdiel (až na rôzne mená premenných) a teda nevykonal sa žiadny postup v riešení. Opica iba chodí po izbe bez toho, aby sa pokúsila posunúť krabicu, ... Tento príklad ukazuje prolog ako sa pokúša nájsť riešenie a nikdy ho nenájde, hoci riešenie existuje. Takéto situácie nie sú pri programovaní v prologu nezvyčajné. Nekonečné cykly bývajú aj v iných programovacích jazykoch. Čo je pri prologu iné je to, že deklaratívna sémantika programu môže byť úplne správna, ale procedurálne správanie programu je nevyhovujúce. V takomto prípade prolog nie je schopný splniť cieľ, lebo sa pokúša získať odpoveď výberom zlej cesty v stavovom priestore riešenia problému. Dôvod prečo by sme nemali zabudnúť na deklaratívnu sémantiku je, najmä vo vývoji technológie programovania, ktorý napreduje presunom od procedurálnych podrobností k deklaratívnym aspektom programov. Deklaratívne programy sú väčšinou jednoduchšie na formuláciu aj pochopenie. Systém ako taký by sa mal starať o procedurálne podrobnosti a nie programátor. Prolog nám v tomto pomáha: niekedy sa stará o procedurálne podrobnosti poriadne a niekedy však nie. Filozofia je taká, že lepšie je mať aspoň nejakú deklaratívnu sémantiku ako žiadnu. Praktický aspekt tohto pohľadu je, že často je jednoduchšie vytvoriť pracujúci program, keď už máme program deklaratívne správny.
|
|||||||||||||||||||||||||||||||||||||||||||||||
|
|