Činnosť systému Prolog

... jak málo vieme a nikdy nebudeme vedieť dosť.
R.Jeffers: Epika hviezd

Doteraz sme opisovali činnosť systému Prolog pri plnení zadaného cieľa iba intuitívne. Tento prístup síce vyhovuje pre jednoduché príklady, ale pre náročnejšie programy je potrebné dôkladnejšie pochopiť jednotlivé kroky, ktoré systém pri plnení cieľov vykonáva. Nasledujúce podkapitoly pojednávajú stručne a bez nároku na korektnosť z hľadiska matematickej logiky o týchto krokoch.

Unifikácia a viazanie premenných

Výber tých informácií z databázy, ktoré systém Prolog potrebuje pri plnení zadaného cieľa, sa deje vyhľadaním prvej klauzuly, ktorá je s týmto cieľom unifikovateľná. Keď je touto klauzulou fakt, cieľ je okamžite splnený. Keď je ňou pravidlo, potom podmienkou splnenia cieľa je splnenie podcieľov v tele tohoto pravidla. Unifikácia pritom predstavuje najvšeobecnejšiu substitúciu, ztotožňujúcu dva objekty jazyka.

Na začiatku sú všetky premenné voľné, t.j. nezastupujú žiadny konkrétny objekt. K viazaniu môže dôjsť práve v procese unifikácie. Prolog má zabudovaný predikát (infixný operátor) >= ,ktorý vyvolá pokus o unifikáciu jeho dvoch argumentov. To je potrebné si uvedomiť napríklad pri dialógu typu:

  ?- 5 =  2+3.
  no

Urobili sme pokus unifikovať konštantu 5 so štruktúrou +(2,3), ktorý úplne logicky skončil neúspechom (+ je definované ako infixný operátor, preto zápisy 2+3 a +(2,3) sú ekvivalentné; niektoré implementácie vyžadujú neoperátorový zápis v tvare '+'(2,3) ). Keď požadujeme sémantické (významové) porovnanie čísla alebo premennej s hodnotou aritmetického výrazu (to už nie je unifikácia !!!), môžeme použiť zabudovaný predikát is. Na porovnanie hodnôt dvoch aritmetických výrazov slúžia ďalšie zabudované predikáty =:= a =\= :

 ?- 5  is 2+3.
 yes

 ?- X is 2+3.
 X = 5 ->
 yes

 ?- 1+4 =:=  2+3.
 yes

 ?- 3+4 =\=  2+3.
 yes

Pravidlá pre unifikáciu sú nasledovné:

dve konštanty sú unifikovateľné iba keď sú zhodné,
voľná premenná je unifikovateľná s každým objektom, pričom dochádza k viazaniu premennej na tento objekt (ktorý nemusí byť plne určený - môže obsahovať iné voľné premenné); súčasne sú viazané na tento objekt všetky výskyty premennej v rozsahu jej platnosti,
dve voľné premenné sa po unifikácii stávajú združenými, čo znamená, že keď sa niektorá z nich v ďalšom naviaže na nejaký konkrétny objekt, aj druhá bude súčasne viazaná na ten istý objekt,
dve štruktúry sú unifikovateľné, keď majú zhodný funktor a rovnaký počet argumentov, pričom všetky odpovedajúce si dvojice argumentov musia byť konzistentne unifikovateľné (slovíčkom konzistentne vylučujeme napríklad unifikovateľnosť štruktúr f(X,X) a f(3,4) ),
cieľ (resp. podcieľ) je unifikovateľný s faktom v databáze, keď sú reprezentované unifikovateľnými štruktúrami (atóm sa chápe ako štruktúra bez argumentov),
cieľ (resp. podcieľ) je unifikovateľný s pravidlom v databáze, keď cieľ a hlava pravidla sú tvorené unifikovateľnými štruktúrami.

Príklad

Úlohou je určiť, či sú nasledujúce dvojice objektov unifikovateľné, alebo nie. Keď dochádza k viazaniu premenných, požaduje sa uviesť aj príslušné objekty, na ktoré sa premenné naviažu:

alfa alfa
45 37
dievca(jana) dievca(X)
lubi(jano,Y) lubi(X,pivo)
sum(2+3) sum(5)
sum(2+3) sum(X+Y)
sum(2+3) sum(X)
lubi(jano,pivo(plzenske,12)) lubi(jano,X)
lubi(jano,pivo(plzenske,X)) lubi(Y,pivo(Z,12))
a(alfa,b(X)) a(U,b(U))
lubi(jano,X) lubi(Z,W)

Riešenie:

áno
nie
áno X =jana
áno X = jano, Y = pivo
nie
áno X = 2, Y = 3
áno X =2+3
áno X = pivo(plzenske,12)
áno X = 12, Y = jano, Z = plzenske
áno X = alfa, U = alfa
áno Z = jano;X a Wsa stali združenými premennými

Príklad

Predpokladajme, že v databáze sú uložené klauzuly

 dievca(jana).     dievca(mara).
 lubi(jana,pivo).  lubi(jano,D) :- dievca(D), lubi(D,pivo).

Úlohou je opísať postup unifikácie a odpovede systému pri splnení cieľov:
a./ ?- dievca(mara).
b./ ?- lubi(jana,X).
c./ ?- lubi(jano,X).

Riešenie:

) Cieľ je unifikovateľný s druhým faktom definície predikátu dievca a systém odpovie yes.
) Cieľ je unifikovateľný s prvým faktom definície predikátu lubi, pri unifikácii dochádza k viazaniu premennej X na atóm pivo a systém odpovie výpisom tohoto viazania a yes.
) Cieľ je unifikovateľný s druhou klauzulou definície predikátu lubi, pri unifikácii sa premenné X a D stávajú združenými. Podmienkou splnenia hlavného cieľa je splnenie oboch podcieľov z tela vybraného pravidla. Podcieľ dievca(X) je unifikovateľný s faktom dievca(jana), pritom sa premenná X viaže na atóm jana (na všetkých troch miestach jej výskytu v klauzule !!). Nakoľko premenné X a D sú združené, súčasne dôjde aj k viazaniu premennej D na jana. Keď sa pri pokuse o splnenie druhého podcieľa lubi(jana,pivo) hľadá unifikovateľná klauzula, systém prehľadáva databázu Prolog-u od začiatku a zistí, že tento podcieľ je unifikovateľný s faktom v databáze. Hlavný cieľ je splnený, systém vypíše viazanie premennej X a informáciu yes.

Návrat

Doteraz uvedené poznatky o chovaní systému Prolog môžme stručne zhrnúť v dvoch bodoch:

pri prehľadávaní databázy sa postupuje zhora nadol (k nájdenej unifikovateľnej klauzule položí systém značku)
v prípade konjunkcie cieľov, či podcieľov sa postupuje zľava doprava; splnenie (pod)cieľa sa "hlási" susedovi sprava a keď už žiadny taký nie je, tak nadradenému cieľu; v prípade, že nadradený cieľ je používateľom zadaný hlavný cieľ, potom systém oznámi viazanie premenných v hlavnom cieli a odpovie yes (keď sa v tele pravidla vyskytne dvakrát ten istý predikát, v oboch prípadoch sa databáza prehľadáva od začiatku, pozri predchádzajúci príklad).

V prípade neúspešného pokusu o splnenie niektorého podcieľa (nenašla sa unifikovateľná klauzula v databáze) sa systém "vracia" naspäť k ľavému susedovi (už predtým úspešne splnenému) a pokúša sa ho opätovne splniť. Predtým sa však zrušia všetky viazania premenných, ktoré prebehli pri predošlej úspešnej unifikácii a hľadanie ďalšej unifikovateľnej klauzuly začína tentokrát od značky (t.j. za klauzulou, ktorá bola naposledy unifikovaná so podcieľom, ktorý sa pokúšame opätovne splniť). Proces "hlásenia" neúspechu ľavému susedovi sa označuje ako návrat. Návrat spolu s nasledujúcim pokusom o opätovné splnenie ľavého suseda predstavuje hľadanie novej alternatívy riešenia.

Keď je pokus o opätovné splnenie neúspešný, pokračuje sa v návrate ďalej doľava. V prípade neúspechu prvého podcieľa v konjunkcii (ten už nemá ľavého suseda) sa neúspech "hlási" nadradenému cieľu. Keď je ním používateľom zadaný hlavný cieľ, potom systém odpovie no.

V prípade úspešného pokusu o opätovné splnenie sa pokračuje znova pravým susedom (podcieľom), ktorý sa pokúšame splniť a nie opätovne splniť, t.j. databáza sa prehľadáva od začiatku. Mohlo by sa zdať, že tento pokus je už nezmyselný, veď podobný pokus v predošlej etape už skončil neúspechom. Musíme si však uvedomiť, že tentokrát sa pokus robí "inou cestou", nakoľko čiastkové riešenie ľavých susedov predstavuje inú alternatívu, než tomu bolo pri neúspešnom pokuse: prejaví sa to tým, že ľaví susedia odovzdávajú k novému pokusu spravidla odlišne viazané premenné, než pri predošlom pokuse.

Návrat môže vyvolať aj sám používateľ zadaním bodkočiarky po kladnej odpovedi systému. Inicializuje tým hľadanie inej alternatívy riešenia.

V kapitole Grafická reprezentácia činnosti Prolog-u bude prezentovaný príklad, ilustrujúci vyššieuvedené všeobecné zásady činnosti systému Prolog.

Grafická reprezentácia činnosti Prolog-u

V prípade, že systém odpovedá inak, než očakávame, alebo keď chceme poznať detailne postup, ako systém odvodzuje svoju odpoveď, je vhodné použiť trasovanie. Nakoľko ladiaci výpis je pomerne neprehľadný, je výhodné trasovanú činnosť znázorniť graficky pomocou blokových modelov.

V blokovom modeli prislúcha každému cieľu (resp. podcieľu) jeden blok. V ľavom hornom rohu bloku je uvedený cieľ a pred ním v zátvorkách jeho poradové číslo (v zhode s ladiacim výpisom). Pre prácu Prolog-u sú charakteristické štyri činnosti:

Call: začína pokus o sp lnenie cieľa (o jeho unifikáciu s klauzulou v DB)
Exit: cieľ bol splnený (unifikácia bola úspešná)
Redo: pokus o inú alternatívu riešenia
Fail: pokus bol neúspešný (nebola nájdená unifikovateľná klauzula v DB)

Pri každej činnosti je uvedené aj označenie, používané štandardne pri ladiacom výpise. Uvedené štyri činnosti odpovedajú vstupom a výstupom bloku - bránam - podľa schémy na obr. 2.1. V prípade úspešného pokusu o splnenie cieľa sú uvedené aj objekty, na ktoré boli naviazané jednotlivé premenné v argumentoch predikátu, reprezentujúceho vyšetrovaný cieľ. Návrat je vyvolané neúspechom pri pokuse o splnenie niektorého z nasledujúcich podcieľov, alebo v prípade globálneho cieľa priamo používateľom (zadaním bodkočiarky po výpise nájdeného riešenia).

               
     #====================#                     | (N) cieľ(X,Y, ...) |
   pokus o splnenie |                    | 1.úspech X=x1, Y=y1, ...
   ------>----------+--------->----------+----------->-----------+
  (N) Call          |                    | (N) Exit              |
                    |                    |                    návrat
                    |    Z1 -->          | 1.pokus o             |
                    |                    | opätovné splnenie     |
                    |              +--<--+-----------<-----------+
                    |              |     | (N) Redo
                    |              |     |
                    |              |     | 2.úspech X=x2, Y=y2, ...
                    |              +-->--+----------->-----------+
                    |                    | (N) Exit              |
                    |                    |                    návrat
                    |    -2 -->          | 2.pokus o             |
      neúspech      #====================# opätovné splnenie     |
      -----<-----------------------<-----------------<-----------+
                                           pokus bol neúspešný


                    #====================#
                    | (N) cieľ(X,Y, ...) |
   pokus o splnenie |                    |
   ------>----------+--------->----+     |
          (N) Call  |              |     |
                    |              |     |
     neúspech       |              |     |
   ------<----------+---------<----+     |
          (N) Fail  #====================#

Uvedené schémy odpovedajú implementácii Arity/Prolog 5 (v štandardnom Prolog-u ako aj v staršej verzii Arity/Prolog-u by sa ešte uplatnili po druhom pokuse brány Redo a Fail). V blokových modeloch sa zachovávajú smery, ktoré sleduje Prolog pri svojej činnosti: - v konjunkcii podcieľov zľava doprava pri pokuse o splnenie a sprava doľava pri návrate - zhora nadol pri pokuse o opätovné splnenie cieľa, t.j. pri hľadaní ďalšej takej klauzuly v databáze Prolog- u, ktorá je unifikovateľná s vyšetrovaným cieľom (k nájdenej klauzule - od ktorej prípadné ďalšie prehľadávanie začína - možno položiť značku Zi -->; dolný index udáva rôzne miesta uloženia značky Z ).

Príklad

Majme v databáze Prolog-u uložené informácie o tom, kto koho/čo ľúbi a kto všetko sú dievčatá:

   1L2 -->                lubi(peter,mara).
                  2L1 --> lubi(jana,pivo).

                          lubi(dana,vino).
   1L2 -->                lubi(peter,X) :- dievca(X), lubi(X,pivo).
   1L3 -->                lubi(peter,pivo).



           D2 -->       dievca(jana).
           D3 -->       dievca(mara).

Úlohou je nájsť odpoveď na otázku koho/čo ľúbi Peter a sledovať podrobne činnosť systému Prolog pri zodpovedaní tejto otázky. Ladiaci výpis má nasledujúci tvar:


    ?- lubi(peter,X).
    (0) Call: lubi(peter,X) ? >
    (0) Exit: lubi(peter,mara) ? >

    X = mara ->;
    (0) Redo: lubi(peter,mara) ? >
    (1) Call: dievca(X) ? >
    (1) Exit: dievca(dana) ? >
    (2) Call: lubi(dana,pivo) ? >
    (2) Fail: lubi(dana,pivo) ? >
    (1) Redo: dievca(dana) ? >
    (1) Exit: dievca(jana) ? >
    (3) Call: lubi(jana,pivo) ? >
    (3) Exit: lubi(jana,pivo) ? >
    (0) Exit: lubi(peter,jana) ? >


    X = jana ->;
    (0) Redo: lubi(peter,jana) ? >
#   (3) Redo: lubi(jana,pivo) ? >
#   (3) Fail: lubi(jana,pivo) ? >
    (1) Redo: dievca(jana) ? >
    (1) Exit: dievca(mara) ? >
    (4) Call: lubi(mara,pivo) ? >
    (4) Fail: lubi(mara,pivo) ? >
#   (1) Redo: dievca(mara) ? >
#   (1) Fail: dievca(X) ? >
    (0) Exit: lubi(peter,pivo) ? >


    X = pivo ->

    yes

Uvedený výpis odpovedá použitiu štandardného Prolog-u. Symbolmi # sú označené brány, ktoré sa pri použití Arity/Prolog 5 v ladiacom výpise neobjavia.

Systém nájde fakt lubi(peter,mara) ako prvú klauzulu unifikovateľnú s hlavným cieľom (položí sem značku 1L1) odpovie X = mara. Zadaním bodkočiarky vyžiada používateľ ďalšie riešenie. Jedná sa o pokus o opätovné splnenie cieľa (0)lubi => systém začne hľadať unifikovateľnú klauzulu od značky 1L1. Systém nájde pravidlo ako ďalšiu unifikovateľnú klauzulu s hlavným cieľom (položí sem značku 1L2) a pokúsi sa postupne splniť obidva podciele. Podcieľ dievca(X) splní unifikáciou s faktom dievca(dana) (položí sem značku D1), ale neuspeje pri pokuse o splnenie druhého podcieľa lubi(dana,pivo) (pokus o splnenie => prehľadáva sa od začiatku). Vyvolá sa návrat a pokus o opätovné splnenie prvého podcieľa začína od značky D1. Nová alternatíva je X = jana, pre ktorú je druhý podcieľ splnený a tým je splnený aj nadradený (a súčasne hlavný) cieľ lubi(peter,jana) a systém odpovie X = jana (položí značku D2). Zadaním bodkočiarky vyžiada používateľ ďalšie riešenie: podcieľ dievca(X) je opätovne splniteľný, ale jeho riešenie X = mara spôsobí nesplnenie nasledujúceho podcieľa lubi(mara,pivo). Po neúspešnom pokuse o ďalšie opätovné splnenie podcieľa dievca(X) (za značkou D3 už ďalšia unifikovateľná klauzula s týmto podieľom neexistuje) systém začína prehľadávať databázu od značky 1L2 a nájde ďalšiu unifikovateľnú klauzulu lubi(peter,pivo) a položí sem značku 1L3. Tým sa úspešne skončil pokus o opätovné splnenie hlavného cieľa a systém odpovie X = pivo. Zadaním dá používateľ najavo, že nemá záujem o ďalšie riešenia a systém odpovie yes.

Blokový model uvedeného riešenia je na nasledujúcom obrázku. Sú v ňom uvedené aj príslušné značky. Keď sa vyskytne opakované volanie predikátu, potom číslo pred značkou označuje jej poradové číslo (pri rekurzívnom volaní je to vlastne hĺbka rekurzie).


        #==================================================#
     ?- | (0)lubi(peter,X)                                 | X=mara
     ->-+----------------------->--------------------------+--->--+
        |  1L1 -->                                         |      |;
        | +---------------------<--------------------------+---<--+
        | |   #=============#        #===================# |
        | |   | (1)dievca(X)| X=dana | (2)lubi(dana,pivo)| |
        | +->-+----->-------+--->----+-->--+             | |
        |     |  D1 -->     |        |     |             | |
        |     |       +--<--+---<----+--<--+             | |
        |     |       |     |        #===================# |
        |     |       |     |        #===================# |
        |     |       |     | X=jana | (3)lubi(jana,pivo)| | X=jana
        | 1L2 |       +-->--+--->----+--------->---------+-+--->--+
        | --> |  D2 -->     |        | 2L1 -->           | |      | ;
        |     |             |        #===================# |      |
        |     |       +--<--+---<--------------<-----------+---<--+
        |     |       |     |        #===================# |
        |     |       |     | X=mara | (4)lubi(mara,pivo)| |
        |     |       +-->--+---->---+-->--+             | |
        |     |  D3 -->     |        |     |             | |
        |     #=============#        |     |             | |
        | +----------<-----------<---+--<--+             | |
        | |                          #===================# | X=pivo
        | +---------------------->-------------------------+---->----
        |  1L3 -->                                         |  yes
        #==================================================#

Negácia podcieľov

Prologovská negácia nie je negáciou v pravom slova zmysle, tak ako ju používame v matematickej logike: podcieľ not(G) (pripúšťa sa aj operátorový zápis not G) je splnený, keď cieľ G neuspeje - negácia pomocou neúspechu (pozri príklad negácie pomocou neúspechu (not goal) a príklad negácie pomocou neúspechu (chlapec = nie dievca)). Pri programovaní sa táto skutočnosť prejaví najmarkantnejšie v tom, že negáciu nemožno použiť bezprostredne na generovanie alternatív.

Majme v databáze uložené fakty

 lubi(peter,jana).  lubi(fero,jana).   lubi(jozo,jana).
 lubi(peter,maria). lubi(fero,maria).  lubi(jozo,maria).
 lubi(peter,pavla).                    lubi(jozo,pavla).

 lubi(peter,pivo).  lubi(fero,pivo).

 dievca(jana).      dievca(pavla).     dievca(maria).
 chlapec(peter).    chlapec(fero).     chlapec(jozo).

Úlohou je formulovať prologovské ciele, vyjadrujúce nasledovné otázky:

Koho nemá rád Fero ?
Kto nemá rád pivo ?
Kto nemá rád žiadne dievča ?
Kto má rád všetky dievčatá ?

Riešenie:

Začiatočník by pravdepodobne navrhol príslušný cieľ v tvare
```
 ?- not lubi(fero,Koho).
  no
```
Systém našiel unifikovateľnú klauzulu lubi(fero,jana) a tým je hlavný cieľ nesplnený. Správne riešenie musí obsahovať najprv nenegovaný "generujúci" podcieľ a až za ním môže byť test, obsahujúci negáciu:
```
  ?- dievca(D),  not lubi(fero,D).
  D = pavla -> ;
  no
```
Analogicky s prípadom a./ nemožno formulovať hlavný cieľ iba negáciou predikátu
```
lubi(Kto,pivo), ale takto:
?- (chlapec(Kto) ; dievca(Kto)), not
lubi(Kto,pivo).
```
Otázku sme koncipovali trochu všeobecnejšie aj pre prípad, keby sa v databáze nachádzali nejaké údaje o "pivárkach".
Aj tu zlyháva intuitívna "začiatočnícka" formulácia:
```
  ?- chlapec(CH), dievca(D), not lubi(CH,D).
  CH = fero, D = pavla -> ;
  no
```
Tej totiž prislúcha otázka existuje aspoň jedno dievča, ktoré tento chlapec nemá rád ?. Správne zadaný cieľ pre pôvodnú otázku je:
```
  ?- chlapec(CH), not(( dievca(D), lubi(CH,D) )).
  no
```
Dvojité zátvorky sú potrebné kvôli tomu, aby systém správne interpretoval čiarku medzi podcieľmi dievca a lubi ako operátor konjunkcie a nie ako oddeľovač parametrov neexistujúceho binárneho predikátu not.
Otázkam tohoto typu prislúcha v matematickej logike kvantifikátor všeobecnosti, ktorý v Prolog-u nemožno priamo vyjadriť (prologovské zápisy vyjadrujú výroky s existenčným kvantifikátorom). Preformulujme preto pôvodnú otázku na ekvivalentný, ale existenčne kvantifikovaný tvar: pre ktorého chlapca neexistuje také dievča, ktoré by tento chlapec nemal rád. Prepis do Prolog-u je potom nasledovný
```
  ?- chlapec(CH), not((  dievca(D), not lubi(CH,D))).
  CH = peter -> ;
  CH = jozo -> ;
  no
```
Premenné v negovanom podcieli (v našom príklade D) ostávajú aj po splnení podcieľa not voľné.

Riadenie návratu

Niekedy je potrebné zmeniť štandardný mechanizmus návratu (dôvody uvedieme pozdejšie). Hlavným prostriedkom riadenia návratu je symbol rezu, označovaný výkričníkom. Je to cieľ, ktorý je pri pokuse o splnenie okamžite splnený, ale pokus o jeho opätovné splnenie je vždy neúspešný. Naviac znemožní pokusy o opätovné splnenie podcieľov, ležiace naľavo od neho. Spôsobí tým okamžité nesplnenie nadradeného cieľa, t.j. nedovolí ani hľadať v databáze nejakú ďalšiu unifikovateľnú klauzulu pre tento cieľ. Všetky uvedené činnosti sa realizujú odstránením príslušných značiek z databázy (pozri kapitolu Návrat ).
Spôsob práce systému pri vyhodnocovaní symbolu rezu možno názorne demonštrovať na jednoduchom príklade:

  hc :- x, nc, y.
  nc :- a, b, !, c, d.
  nc :- e, f.

Po zadaní otázky hc a splnení podcieľa x sa systém snaží splniť podcieľ nc. Pri následnom vyhodnocovaní podcieľov a a b pracuje systém tak, ako bolo uvedené v kapitolách: Unifikácia a viazanie premenných a Návrat . Po splnení podcieľa b je cieľ ! ihneď splnený a systém "normálne" vyhodnocuje podciele c a d. Keď je ale podcieľ c neúspešný, potom pokus o opätovné splnenie podcieľa ! je neúspešný a nie je možný ani pokus o opätovné splnenie podcieľa b ani o unifikáciu nadradeného cieľa nc s druhým pravidlom (nc :- e, f.) a systém sa pokúša opätovne splniť podcieľ x. Druhé pravidlo pre nc však nie je zbytočné: pri neúspechu konjunkcie a, b (t.j pred dosiahnutím symbolu rezu) sa systém pokúša použiť aj toto pravidlo.

"Zákaz" hľadania ďalších alternatív sa vzťahuje aj na použitie symbolu rezu v zápisoch, využívajúcich operátor disjunkcie. Napríklad aj pri použití pravidla nc :- a, b, !, c, d ; e, f. by sa systém choval vyššie uvedeným spôsobom.

repeat: je vždy splnený a je nekonečne krát opätovne splniteľný; používa sa na programovanie cyklov (pozri príklad na cyklus (načítanie z databázy a otestovanie )),
true: je vždy splnený ale nie je opätovne splniteľný,
fail: je vždy nesplnený; používa sa na realizáciu cyklov (pozri príklad na opakovaný výpis mužov bez stlačenia ' ; ' ) a v kombinácii so symbolom rezu na realizáciu negácie pomocou neúspechu (pozri príklad negácie pomocou neúspechu (not goal) a príklad negácie pomocou neúspechu (chlapec = nie dievca )).

Príklad

Úlohou je navrhnúť predikát, ktorý vypíše všetkých mužov z príkladu - rodinnej databázy bez toho, aby sme si museli vyžiadať jednotlivé riešenia bodkočiarkami:


       muzi :- muz(M), write(M),  nl, fail.
       muzi :-  write('Viac muzov nieto').

Druhá klauzula slúži na korektné ukončenie činnosti predikátu muz (inak by skončila odpoveďou no).

Príklad

Úlohou je navrhnúť predikát, ktorý načíta meno a otestuje, či odpovedá nejakému mužovi v databáze rodiny z príkladu - rodinnej databázy . V opačnom prípade sa čítanie opakuje tak dlho, kým nezadáme korektné meno.

 zadaj_muza(M) :-  repeat, write('Meno: '),  read(M), muz(M), ! .

Nesplnenie podcieľa muz(M) vyvolá návrat. Nakoľko však predikáty read a write nie sú opätovne splniteľné, na rozdiel od predchádzajúceho príkladu sme museli pre realizáciu cyklu použiť predikát repeat. Bez symbolu rezu na konci pravidla by sa predikát zadaj_muza, použitý v tele nadradeného predikátu, mohol chovať nekorektne. Po úspešnom načítaní mena a po prípadnom návrate dochádza totiž vďaka repeat k opakovanému čítaniu.

Predikáty muzi a zadaj_muza realizujú vlastne cyklus, označovaný ako cyklus typu repeat-fail. Uvedené príklady ilustrujú skutočnosť, že sa v definícii cyklu nemusia nachádzať oba riadiace predikáty. V prípade predikátu muzi "otočenie" cyklu zľava doprava realizuje podcieľ muz(M) (ako generátor) a v prípade predikátu zadaj_muza "otočenie" sprava doľava realizuje zhodou okolností tiež podcieľ muz(M) (tentokrát ako test).

Použitia symbolu rezu možno rozdeliť do dvoch skupín:

zelený rez, ktorý nemá vplyv na deklaratívnu sémantiku programu, teda po jeho odstránení sa získajú rovnaké výsledky,
červený rez, ktorý ovplyvňuje deklaratívnu sémantiku programu, teda program po odstránení rezu dáva odlišné výsledky.

Zelený rez sa používa výhradne pre zvýšenie efektivity programu. Červený rez slúži na úmyselnú zmenu štandardnej činnosti Prolog-u a má okrem toho ešte aj ďalšiu, veľmi dôležitú funkciu: pomocou neho je v Prolog-u definovaný predikát not, teda tzv. negácia pomocou neúspechu (pozri príklad negácie pomocou neúspechu (not goal) a príklad negácie pomocou neúspechu (chlapec = nie dievca)).

Možno vysloviť niekoľko všeobecných zásad o použití rezu:

Použitie rezu je možné (zelený rez) všade tam, kde ďalšie riešenie už neexistuje (resp. existuje, ale nás už nezaujíma) a Prolog by sa napriek tomu pokúšal unifikovať ďalšie klauzuly, prípadne splniť ďalšie ciele; pritom je potrebné rozlíšiť dva prípady:

podľa argumentov v hlave pravidla je možné unifikáciou rozdeliť klauzuly na disjunktné skupiny (väčšinou je v takejto skupine jediná klauzula); rez položíme na koniec tela posledného pravidla každej skupiny; dobrým príkladom je definícia predikátu teplota2 (táto optimalizácia je zbytočná v tých verziách Prolog-u, ktoré majú indexáciu klauzúl, napr. DEC-10 Prolog, QUINTUS Prolog),
výber danej klauzuly bol okrem unifikácie v hlave pravidla potvrdený aj splnením "testovacieho" podcieľa v tele klauzuly; rez zaradíme za tento test (túto optimalizáciu už indexácia klauzúl nevie urobiť).

Použitie rezu je nevyhnutné (červený rez) v týchto prípadoch:

keď použijeme znalosť, vyplývajúcu z neúspechu predošlej klauzuly pre vynechanie testu v tele niektorej nasledujúcej klauzuly; rez umiestnime za testom (pozri predikát teplota3 ),

pri programovaní vetvenia IF-THEN-ELSE ,

pre zastavenie cyklu generuj & testuj po nájdení riešenia (keď vieme, že existuje viacero riešení a nás ďalšie riešenia už nezaujímajú); rez bude za testom,

v definícii negácie pomocou neúspechu ( príklad negácie pomocou neúspechu (not goal) ) a vo všetkých predikátoch, ktoré používajú negáciu pomocou neúspechu a pritom nevolajú zabudovaný predikát not ( príklad negácie pomocou neúspechu (chlapec = nie dievca)); spravidla sa pre tento účel používa kombinácia !, fail,

pre zastavenie cyklu s repeat; rez umiestnime za podmienku ukončenia cyklu (každé repeat musí mať svoj rez, inak sa program môže dostať do nekonečnej slučky; pozri predchádzajúci príklad ),

na konci akumulačného cyklu, aby sme zabránili generovaniu chybných výsledkov (jedná sa o medzivýsledky jednotlivých krokov cyklu, pozri príklad na tvorbu zoznamu a najmä príklad na vyšetrenie činnosti Prolog-u pri budovaní zoznamu, príklad - upravený predchádzajci príklad a príklad na vyšetrenie činnosti Prolog-u pri budovaní zoznamu - pomocou predikátu buduj ),

pri vytvorení reverzibilnej operácie z operácie, ktorá je ireverzibilná (pozri všeobecný príklad a jeho konkrétne aplikácie v príklade na tvorbu predikátov tak, aby umožnili rekonštrukciu pôvodného stavu databázy a príklade na vyhľadanie cesty v grafe).

Príklad

Úlohou je definovať predikát not tak, aby realizoval negáciu pomocou neúspechu, t.j. funkciu, opisovanú v kapitole Negácia podcieľov .

     not Goal :- Goal, !,  fail.
     not Goal.

Príklad

Úlohou je navrhnúť predikát definujúci reláciu X je chlapec, pričom sa majú využiť informácie o tom, kto všetko sú dievčatá:

  dievca(jana).   dievca(dana).   dievca(mara).   dievca(zuza).

Využijeme negáciu pomocou neúspechu, ale bez použitia predikátu not:

  chlapec(X) :- dievca(X), !, fail.
  chlapec(_).

Dialóg môže mať nasledujúcu podobu:

 ?-chlapec(mara).
 no

 ?-chlapec(jano).
 yes

 ?-chlapec(anastazia).
 yes

 ?-chlapec(Kto).

Prvá odpoveď je naprosto korektná,zakladajúca sa na "opačnej" informácii z databázy. Dve kladné odpovede odvodil systém na základe toho, že dotyčné osoby podľa informácií v databáze nie sú dievčatami. Použitie predikátov tohoto typu teda predpokladá uzavretý svet (všetky potrebné informácie sú v databáze). Odpoveď na štvrtú otázku upozorňuje na skutočnosť, že sa jedná o negáciu pomocou neúspechu a že túto nemožno použiť bezprostredne na generovanie alternatív.

Príklad

Úlohou je navrhnúť rôzne verzie predikátu, ktorý podľa zadanej teploty zistí, či má pacient horúčku alebo nie. Jedná sa o analógiu " vetviacej" riadiacej štruktúry IF THEN ELSE, známej z procedurálnych jazykov. Pre jednoduchosť predpokladáme, že argument Teplota je vždy celočíselný (nie je ho nutné testovať pomocou zabudovaného predikátu integer).

 horucka1(Teplota) :- Teplota >= 37, write(ano).
 horucka1(Teplota) :- Teplota  < 37, write(nie).

 horucka2(Teplota) :- Teplota >= 37, !, write(ano).
 horucka2(Teplota) :-                   write(nie).

 horucka3 :- write('Teplota: '),read(Teplota),
             (Teplota >= 37, !, write(ano) ; write(nie) ).

 horucka4 :- write('Teplota: '),read(Teplota),
             (Teplota >= 37,  ! ; fail).

V definícii predikátu horucka1 sa vyskytujú komplementárne testy. Je totiž zrejmé že po vykonaní prvého testu Teplota >= 37 je výsledok druhého testu Teplota < 37 evidentný aj bez jeho vykonania. To umožní stručnejšiu definíciu predikátu horucka2. Keby sme však vynechali symbol rezu, potom by sme na otázku horucka2(40), fail dostali po prvom správnom výpise ano aj druhý nesprávny - nie. Uvedená otázka sa môže zdať na prvý pohľad nelogická. Simulujeme ňou však situáciu, keď bude predikát horucka1 použitý v tele iného pravidla a po nesplnení niektorého z ďalších podcieľov sa vyvolá návrat. Vynechanie symbolu rezu môžu spôsobiť v takejto situácii veľmi nekorektné výsledky.

Keď je potrebné urobiť "vetvenie" v kombinácii s predikátom čítania read, musíme spojiť obe klauzuly a použiť disjunkciu - predikát horucka3. Nakoľko sa jedná o často sa vyskytujúci úsek programu, je dobré si zapamätať jeho štandardný tvar:

 ...,  (podmienka, !, činnosť_pri_splnení_podmienky   ;
        činnosť_pri_nesplnení_podmienky ), ...

V prípade predikátu horucka4 sú obe činnosti "prázdne". Keď je podmienka splnená, je splnený aj tento predikát, keď je nesplnená, tak nie je splnený ani predikát horucka4.

Príklad

Úlohou je vylepšiť predikát zadaj_muza z príkladu na načítanie mena a otestovanie jeho výskytu v databáze tak, aby okrem zopakovania pôvodnej nápovede vypísal aj chybové hlásenie. Na ukončenie repeat-fail cyklu použijeme analógiu riadiacej štruktúry IF THEN ELSE:

meno_muza(M) :-  repeat, write('Meno: '), read(M),
                (muz(M), !, write(ok) ; write('Chyba !!'), nl, fail ).

Predikát fail musí byť vždy v "ELSE vetvi", nakoľko v "THEN vetvi" by v kombinácii so symbolom rezu spôsobil namiesto požadovaného vykonania ďalšieho kroku cyklu okamžité ukončenie cyklu. Naviac by sa v tomto prípade pri stlačení bodkočiarky po dobrom riešení (po výskoku z cyklu) zopakovala nápoveď a cyklus by pokračoval ďalej.

Príklad

Úlohou je navrhnúť predikát pre klasifikáciu teploty do niekoľkých disjunktných skupín (predikát má teda vždy jediné riešenie - analógia riadiacej štruktúry CASE):

   teplota1(T, mrtvola )  :- T < 35.
   teplota1(T, normal  )  :- T >= 35, T =< 37.
   teplota1(T, horucka )  :-          T >  37.

Pre jednoduchosť predpokladáme, že argument T je vždy celočíselný a že nie je nutné testovať túto skutočnosť pomocou zabudovaného predikátu integer. Blokový model pre otázku

teplota1(36, X) je na obrázku

      #========================================#
      | (0) teplota1(36, X)                    |
      |   #=============#                      |
   ?- |   |(1) 36 < 35  |                      |
   ->-+---+-->-+        |                      |
      | +-+--<-+        |                      |
      | | #=============#                      |
      | | #=============#    #=============#   |
      | | |(2) 36 >= 35 |    |(3) 36 =< 37 |   | X = normal
      | +-+------>------+----+------>------+---+----->----+
      |   #=============#    #=============#   |          |  ;
      | +---------<-----------------<----------+-----<----+
      | | #=============#                      |
      | | |(4) 36 > 37  |                      |
   no | +-+-->--+       |                      |
   -<-+---+--<--+       |                      |
      |   #=============#                      |
      #========================================#

Použitím zelených rezov možno program zefektívniť:

  teplota2(T, mrtvola ) :- T <  35,          !.
  teplota2(T, normal  ) :- T >= 35, T =< 37, !.
  teplota2(T, horucka ) :-          T >  37, !.

Blokový model pre otázku teplota2(36, X) je na obrázku

      #================================================#
      | (0) teplota2(36, X)                            |
      |   #=============#                              |
   ?- |   |(1) 36 < 35  |                              |
   ->-+---+-->-+        |                              |
      | +-+--<-+        |                              |
      | | #=============#                              |
      | | #=============#    #=============#           |
      | | |(2) 36 >= 35 |    |(3) 36 =< 37 |   #===#   | X =normal
      | +-+------>------+----+------>------+---+---+---+----->----+
      |   #=============#    #=============#   | ! |   |          |
      |                                        #===#   |          |;
   no #================================================#          |
   -<--------------------------------<----------------------------+

V prvej klauzule definície predikátu teplota2 sme ošetrili prípad, keď T je menšie ako 35 a v ďalšej klauzule už môžeme využiť túto informáciu. Zelený rez sa však zmení na červený. Na základe rovnakej úvahy môžeme vynechať aj test T > 37 v tretej klauzule. Tým sa zmení aj druhý rez na červený a program bude mať tvar:

  teplota3(T, mrtvola ) :- T <  35, !.
  teplota3(T, normal  ) :- T =< 37, !.
  teplota3(T, horucka ).

Blokový model pre otázku teplota3(36, X) je na obrázku

            #=================================#
            | (0) teplota3(36, X)             |
            |   #=============#               |
         ?- |   |(1) 36 < 35  |               |
         ->-+---+-->-+        |               |
            | +-+--<-+        |               |
            | | #=============#               |
            | | #=============#               |
            | | |(2) 36 =< 37 |       #===#   | X = normal
            | +-+------>------+--->---+---+---+----->-----+
            |   #=============#       | ! |   |           |
            |                         #===#   |           | ;
         no #=================================#           |
        --<--------------------<--------------------<-----+

V prípade, že teplotu získavame načítaním, je potrebné jednotlivé možnosti spojiť do disjunkcie:

   teplota(Stav) :- write('Teplota > '), read(T),
                    ( T <  35, !, Stav = mrtvola   ;
                      T =< 37, !, Stav = normal    ;
                                    Stav = horucka   ).

Príklad

Úlohou je navrhnúť predikát, ktorý by určil aký term je uvedený v jeho prvom argumente:

  typ_termu( X, premenna)     :-  var(X),      !.
  typ_termu( X, atom)         :-  atom(X),     !.
  typ_termu( X, cele_cislo)   :-  integer(X),  !.
  typ_termu( _, struktura).

Druhú a tretiu klauzulu predchádzajúcej definície môžeme nahradiť jediným pravidlom:

  typ_termu( X, konstanta )   :-  atomic(X),   !.

Modifikácia databázy Prolog-u

Prolog umožňuje modifikovať aktuálne definície predikátov v priebehu vykonávania programu. Predikát retract(K) odstráni z aktuálnej databázy prvú klauzulu, unifikovateľnú so štruktúrou K. V prípade pravidla musí teda mať aj štruktúra K funktor :- a neunifikuje sa iba hlava pravidla s K (je tu teda rozdiel oproti unifikácii cieľa/podcieľa s pravidlom v databáze - porovnaj s bodom 6 ).

Predikáty asserta(K) / assertz(K) ukladajú klauzulu K pred/za ostatné klauzuly, definujúce príslušný predikát. Uvedené predikáty nie sú opätovne splniteľné a tak neobnovia pri návrate pôvodný stav databázy. Keď požadujeme, aby sa tak stalo, musíme si príslušné predikáty naprogramovať (pozri napr. predikát uloz v príklade na vyhľadanie cesty v grafe).

Vykonané zmeny platia iba v aktuálnej databáze Prolog-u, neprejavia sa teda v zdrojovom texte (v bufferi editora, či dokonca v súbore na disku). Jednotlivé implementácie umožňujú uložiť zmenenú databázu do súboru (v Arity/Prolog-u pomocou predikátu file_list).

Príklad

Úlohou je navrhnúť predikát, ktorý vykoná potrebné modifikácie v databáze rodiny Prologovcov (pozri príklad - rodinnej databázy ), keď sa narodí nejaké dieťa. Predpokladáme, že matka je jednou zo žien aktuálnej databázy (môže byť aj bezdetná alebo slobodná). Budeme sledovať, aby sa v rodine nejaké meno neopakovalo. Riešenie má tvar:

 porod(Matka,Dieta,Pohlavie):-
             nove(Dieta,Pohlavie),  rodicia(Matka,Otec),
             zarad(Dieta,Pohlavie), 
             assertz(rodicia(Matka,Otec,Dieta)).
 nove(D,P)    :-rodicia(D,_,_),!,fail.
 nove(D,P)    :-rodicia(_,D,_),!,fail.
 nove(D,ch).
 nove(D,d).
 rodicia(M,O) :- retract(rodicia(M,O,bezdet)),!.
 rodicia(M,O) :- rodicia(M,O,_).
 zarad(D,ch)  :- assertz(rodicia(slob,D,bezdet)).
 zarad(D,d )  :- assertz(rodicia(D,slob,bezdet)).

Navrhnuté riešenie najprv otestuje, či vstupné argumenty Dieta a Pohlavie sú korektné a až potom realizuje zásahy do databázy. V prvej klauzule predikátu rodicia nebolo potrebné vopred otestovať, či Matka sa nachádza v databáze, nakoľko predikát retract je súčasne aj testom. Keď je tento test neúspešný príslušná klauzula sa neodstráni a retract je nesplnený. V tom prípade sa použije druhá klauzula, v ktorej už test je.

Modifikácia databázy je použitá aj v ďalších príkladoch, napr. príklad na tvorbu predikátov tak, aby umožnili rekonštrukciu pôvodného stavu databázy a príklade na vyhľadanie cesty v grafe, príklad na obrátené budovanie zoznamu, príklade na zobrazenie povodia riek .