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:

• opica je pri dverách
• opica je na podlahe
• krabica je pri okne
• opica nemá banán.

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:

1. zobrať banán
2. vyliezť na krabicu
3. posunúť krabicu
4. ísť po izbe

Zmenu stavu vyjadríme predikátom zmena s troma argumentmi:

zmena(Stav1, M, Stav2)

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 S dostať banán? Reprezentujme otázku cieľom

prístupný(S)

Pri definícii predikátu prístupný treba vychádzať z nasledovných skutočností:

1. pre ľubovoľný stav S, v ktorom opica už má banán, je predikát prístupný splnený a netreba vykonať žiadnu činnosť. Vyjadríme faktom:

   prístupný(stav(_,_,_,má)).

2. v ostatných prípadoch treba vykonať jednu alebo viacero činností. Opica môže dostať banán v ľubovoľnom stave S1, ak existuje nejaká činnosť M zo stavu S1 do nejakého stavu S2, takého, že opica môže dostať banán v stave S2 (vykonaním žiadnej alebo viacerých činností):

   prístupný(S1) :- zmena(S1, M, S2),
                            prístupný(S2).
   

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 zmena vyskytovali v programe. Klauzuly možno usporiadať aj menej šťastne. Dokonca tak, že opica bude chodiť po izbe donekonečna bez toho, aby sa pokúsila chytiť krabicu, ...

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.

to Homepage

to Teaching

to FLP

to the Top