Rekurzie v Prolog-u

Pojem rekurzie

Iterácia je ľudská,
rekurzia božská.
Programátorský folklór.
Kde začína rekurzia,
tam končí zdravý rozum.
Študentský folklór.

O rekurzívnej definícii hovoríme, keď na definovanie nejakého objektu použijeme iný (spravidla jednoduchší) variant toho istého objektu. Reťazené použitie korektnej rekurzívnej definície musí zabezpečiť, že celý postup konverguje k nejakému hraničnému prípadu, ktorý musí byť samostatne definovaný. Zamedzí sa tak vzniku nekonečnej cyklickej definície.

Známym príkladom je rekurzívna definícia faktoriálu:

  (n+1)! = (n+1)*n!      n=1,2,...(rekurzívna definícia)
    1! = 1                      (hraničný prípad)

V porovnaní s procedurálnymi jazykmi (z ktorých niektoré rekurzie ani nepripúšťajú), je v Prolog-u rekurzia používaná oveľa častejšie. Nie je snáď prehnané tvrdenie, že každý netriviálny prologovský program používa rekurziu. V podstate možno rozlíšiť dva spôsoby použitia rekurzie:

  - rekurzívna definícia predikátov - rekurzívne pravidlá
  - rekurzívna definícia údajových štruktúr - zoznamov.

Rekurzívne pravidlá

Pri rekurzívnej definícii predikátov sa v tele pravidla vyskytuje ten istý predikát ako v hlave, t.j. hlavný cieľ môže byť splnený iba vtedy, keď jeho "posunutá kópia" ako podcieľ bola splnená ("posunutím" sa tu rozumie tendencia rekurzie smerovať k hraničnému prípadu).

Príklad

Úlohou je navrhnúť predikát pre vyhľadanie potomkov v databáze rodiny z kapitoly Návrh jednoduchej databázy. Je síce možná nerekurzívna definícia:

 potomok(Dieta,Rodic)      :- rodic(Rodic,      Dieta).
 potomok(Vnuca,Staryrodic) :- rodic(Staryrodic, Rodic),
                              rodic(Rodic,      Vnuca).
 potomok(Pravnuca,Prarodic):- rodic(Prarodic,   Staryrodic),
                              rodic(Staryrodic, Rodic),
                              rodic(Rodic,      Pravnuca).
      . . .                   /* ďalšie generácie */

ale oveľa elegantnejšia je rekurzívna definícia:

 potomok(Dieta,  Rodic)     :- rodic(Rodic,    Dieta).
 potomok(Potomok,Prapredok) :- rodic(Prapredok,Predok),
                               potomok(Potomok,Predok).

Prvá klauzula ošetruje hraničnú situáciu - medzi prvým a druhým argumentom je rozdiel jednej generácie. Druhá klauzula predpokladá väčší generačný rozdiel - jej použitím sa rekurzívne "uberá" vždy jednu generáciu tak dlho, kým nenastane spomínaná hraničná situácia. Schematicky je tento postup znázornený na obrázku

         potomok(Potomok,Prapredok) :-
   |<---------------------------------------------------------|
   |     rodic(Prapredok,Predok)  ,  potomok(Potomok,Predok). |
   |<-----------------------------|<--------------------------|
   |                              |                           |
  Prapredok    --------->      Predok  ----> . . . . ----> Potomok

Použitie predikátu je znovu mnohostranné:

 ?- potomok(zuza,  jana).   'Je Zuza Janin potomok ?
 no

 ?- potomok(Kto,karol).     'Kto sú potomkovia Karola ?'
 Kto = jana -> ;
 Kto = dana -> ;
 Kto = milan -> ;
 Kto = peter -> ;
 Kto = anna -> ;
 Kto = viera -> ;
 no

 ?- potomok(milan,Kto).     'Kto sú predkovia Milana ?'
 Kto = karol -> ;
 Kto = zuza -> ;
 no

 ?- potomok(Kto,Komu).      'Kto je komu potomkom ?'
 Kto = jana ,
 Komu = karol -> ;
 Kto = dana ,
 Komu = karol ->               'stačia dve riešenia'
 yes

Použitie rekurzívnych pravidiel je v Prolog-u bežné a prirodzené, ale mnohým začiatočníkom spôsobujú rekurzie značné ťažkosti. Najčastejšími chybami sú:

cyklická definícia:

      otec(O,S) :-  syn(S,O).
      syn(S,O)  :- otec(O,S).

nesprávne poradie faktov a pravidiel v databáze (nestačí totiž uviesť všetky relevantné informácie o danej úlohe, je potrebné zohľadniť aj spôsob práce Prolog-u, najmä postup pri prehľadávaní databázy a pravidlá pre viazanie premenných, pozri kapitolu ). Keď sa napríklad prehodí poradie klauzúl v rekurzívnej definícii predikátu prvok (pozri príklad na definíciu predikátu prvok), systém sa pri pokuse o zodpovedanie otázky prvok(a,X) dostane do nekonečnej slučky
nesprávne poradie podcieľov v tele rekurzvívneho pravidla; napríklad keď v tele rekurzívneho pravidla definujúceho predikát potomok zmeníme poradie podcieľov na potomok(Potomok,Predok), rodic(PraPredok,Predok) , systém správne zodpovie otázky s kladnou odpoveďou, ale zacyklí sa, keď riešenie neexistuje.

Rekurzívne údajové štruktúry - zoznamy

Zoznam je usporiadaná postupnosť prvkov, ktorá môže mať ľubovoľnú dĺžku, pričom prvkom môže byť akýkoľvek term. "Usporiadaná" znamená, že poradie prvkov je významné. Zoznam sa hodí na zoskupenie informácií, ktoré nejak spolu súvisia, ale ich počet sa môže prípad od prípadu líšiť.

Príklad

Úlohou je navrhnúť "komprimovanú" formu definície predikátu lubi z kapitoly Dialóg používateľa so systémom. Je nevhodné sústrediť informácie o tom, kto koho/čo ľúbi nasledovne:

 lubi(peter,mara,pivo).
 lubi(jana,pivo).        lubi(dana,vino).
 lubi(mara).             /*  mara nelubi nikoho/nic */

nakoľko kvôli rozdielnemu počtu argumentov sa jedná vlastne o tri naprosto rozdielne predikáty. Je ale možný zápis pomocou zoznamov:

 ma_rad(peter,[mara,pivo]).
 ma_rad(jana,[pivo]).
 ma_rad(mara,[]).

pričom posledný fakt reprezentuje výrok Mara nemá rada nič/nikoho. Použili sme úmyselne iné meno predikátu, aby bolo možné zavedením nového pravidla

 lubi(Kto,Koho):- ma_rad(Kto, ZoznamLasok),
                  prvok(Koho,ZoznamLasok).

dosiahnuť podobné správanie systému ako v príklade na generujúcu schopnosť Prolog-u (zmení sa poradie odpovedí systému na niektoré otázky). Predikát prvok odpovedá výroku "prvý argument je prvkom zoznamu v druhom argumente", a nakoľko pracuje s rekurzívnou údajovou štruktúrou, jeho definícia je tiež rekurzívna (pozri príklad na definíciu predikátu prvok).

Príklad

Úlohou je navrhnúť definíciu predikátu rodina s tromi argumentami (Matka, Otec, ZoznamDeti) tak, aby reprezentoval strom rodiny z kapitoly Návrh jednoduchej databázy .

 rodina( zuza,  karol, [jana,dana,milan] ).
 rodina( jana,  jano,  [peter,anna]      ).
 rodina( anna,  jozo,  [viera]           ).
 rodina( eva,   milan, []                ).
 rodina( viera, slob,  []                ).
 rodina( slob,  peter, []                ).
 rodina( dana,  slob,  []                ).

Aj pre takto zakódovaný rodinný strom je možné použiť väčšinu pôvodných predikátov z kapitoly Návrh jednoduchej databázy a z príkladu na vyhľadanie potomkov z databázy , keď predefinujeme predikát rodicia zo skupiny faktov na pravidlo

 rodicia(Matka,Otec,Dieta) :- rodina(Matka,Otec,ZoznamDeti),
                              prvok(Dieta,ZoznamDeti).

Niekoľko málo ďalších zmien vyplýva zo skutočnosti, že bezdetné rodiny sú charakterizované prázdnym zoznamom v treťom argumente (atóm bezdetni je už zbytočný). Predikát prvok je automaticky nesplnený pre prázdny zoznam, vďaka čomu možno vypustiť pôvodné explicitné testy na bezdetnosť:

 otec(Otec,   Dieta)  :- rodicia(  _  , Otec, Dieta).
 matka(Matka, Dieta)  :- rodicia(Matka,  _  , Dieta).

Naviac je vhodné v definícii predikátu muz nahradiť podcieľ rodicia podcieľom rodina. Odstránia sa tým "násobné" odpovede (pozri poznámku na konci kapitoly Návrh jednoduchej databázy ).

Aj v predošlom príklade bol potrebný predikát prvok. Skôr než sa ho pokúsime definovať ( príklad na definíciu predikátu prvok), je potrebné trochu bližšie pojednať o rôznych formách zápisu zoznamov.

Doteraz sme používali tzv. zoznamovú notáciu, v ktorej sa prvky zoznamu, oddelené čiarkami, uvedú v danom poradí medzi hranatými zátvorkami. V skutočnosti predstavuje neprázdny zoznam binárnu štruktúru, ktorej funktorom je bodka (je definovaný ako vpravo asociatívny infixný operátor). Prvým operandom je hlava zoznamu a druhým jeho telo. Hlava je prvý prvok zoznamu a telo je obvykle zoznam (z pôvodného zoznamu vznikne oddelením hlavy). Uvedená bodková notácia je v porovnaní so zoznamovou neprehľadnejšia. Príklady zoznamov (zápisy v jednom riadku sú rovnocenné):

 [a]     .(a,[])            a.[]          a.[]
[a,b,c]  .(a,.(b,.(c,[])))  a.(b.(c.[]))  a.b.c.[]
 -?-     .(a,.(b,.(c,d )))  a.(b.(c.d ))  a.b.c.d

Posledný zoznam nekončí prázdnym zoznamom a zatiaľ ho nevieme zapísať v zoznamovej notácii. Aj zoznamová notácia však umožňuje oddeliť Hlavu zoznamu od Tela pomocou zápisu [Hlava|Telo]. V LPA Prolog-u je symbol | deklarovaný ako infixný operátor, v Arity Prolog-u ho možno použiť iba v spojení s hranatými zátvorkami.

Príklad

Úlohou je rozložiť rôzne zoznamy na hlavu a na telo:

  ZOZNAM          HLAVA             TELO

   [a]              a                []
 [a,b,c,d]          a              [b,c,d]
[[a,b],c,d]       [a,b]             [c,d]
 [a,[b,c]]          a              [[b,c]]
  [a|b]             a                 b
[a,b,[c|d]]         a             [b,[c|d]]
    []       nedá sa rozložiť (neúspech)

Zoznam v predposlednom riadku odpovedá bodkovej notácii a.b.c.d. (Posledná bodka nie je súčasť zápisu, označuje koniec vety). Zložitejšie zoznamy je účelné názorne zobraziť binárnym stromom.

Príklad

Zobrazme zoznamy [a,b,c], [[a,b],c,d] a [a,b,[c|d]] binárnym stromom:

    .                     .                    .
   / \                   / \                  / \
  a   .                 /   \                a   .
     / \               /     \                  / \
    b   .             .       .                b   .
       / \           / \     / \                  / \
      c   []        a   .   c   .                c   d
                       / \     / \
                      b  []   d   []

    [a,b,c]           [[a,b],c,d]         [a,b,[c|d]]

Unifikácia zoznamov

Pre unifikáciu zoznamov platí v plnej miere bod 4. v kapitole Unifikácia a viazanie premenných (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é). Dva zoznamy sú teda unifikovateľné, keď sú unifikovateľné ich hlavy aj telá.

Príklad

Úlohou je určiť, či sú uvedené dvojice zoznamov unifikovateľné a keď áno, uviesť aj príslušné viazania premenných:

[X,Y,Z] [eva,jana,pavla]
[X|[Y|Z]] [eva,jana,pavla]
[X|W] [eva,jana,pavla]
[X|W] [eva]
[X|eva] [eva,jana]
[X|W] []
[X|Z,W] [eva,jana,pavla]
[X,Z|W] [eva,jana,pavla]
[X|[Y|Z]] [eva|[jana|pavla]]

Riešenie:

áno X = eva, Y = jana, Z = pavla
áno X = eva, Y = jana, Z = [pavla]
áno X = eva, W = [jana,pavla]
áno X = eva, W = []
nie
nie
chybná syntax prvého zoznamu
áno X =eva, Y=jana, W=[pavla]
áno X =eva, Y=jana, Z = pavla

Prázdny zoznam nemožno rozdeliť na hlavu a telo (prípad f) ). V prípade i) máme zvláštny prípad, keď zoznam nekončí prázdnym zoznamom (pozri analogické prípady v príklade na rozklad zoznamov a predchádzajúcom príklade ). Prípady b) a h) ilustrujú dve možnosti prístupu k prvým dvom prvkom zoznamu (v ďalšom uprednostníme zápis podľa h) ako jednoduchší a názornejší).

Rekurzívne pravidlá pre prácu so zoznamami

Väčšina prologovských programov využíva rekurzívne údajové štruktúry. Pre prácu s nimi je potrebné navrhnúť rekurzívne definované predikáty.

Príklad

Úlohou je navrhnúť definíciu predikátu prvok, ktorého prvý argument je prvkom zoznamu, tvoriaceho druhý argument. Prvok X patrí do zoznamu, keď
a.) je jeho prvým prvkom --> prvok(X,[X|_]).
alebo
b.) je prvkom tela zoznamu --> prvok(X,[_|T]):- prvok(X,T).

Prvá klauzula reprezentuje jednu hraničnú situáciu. Druhou hraničnou situáciou je prípad, keď zoznam v druhom argumente je prázdny a nedá sa rozložiť na hlavu a na telo (neúspech). Druhá klauzula je vlastné rekurzívne pravidlo, konvergujúce pri postupnom skracovaní testovaného zoznamu k jednej z uvedených hraničných situácií. Pre označenie údajov, na ktorých "nezáleží", boli použité anonymné premenné (podčiarniky). Predikát prvok možno použiť rôznymi spôsobmi:

?- prvok(c,[a,b,c,d]).  'je c prvkom zoznamu [a,b,c,d] ?'
yes

?- prvok(q,[a,b,c]).    'je q prvkom zoznamu  [a,b,c] ?'
no

?- prvok(X,[a,b,c]).    'ktoré sú prvky zoznamu [a,b,c] ?'
X = a -> ;
X = b -> ;

no                       'ďalšie prvky neexistujú'

?- prvok(a,X).          'aké zoznamy obsahujú prvok a ?'
X = [a|Y] -> ;        'zoznam s a ako prvým prvkom'
X = [H,a|Z] -> ;      'zoznam s a ako druhým prvkom'
X = [H,J,a|W] ->     'zoznam s a ako tretím prvkom'
yes

Premenné H, J predstavujú bližšie nedefinované prvky zoznamu a Y, Z a W reprezentujú bližšie neurčené zoznamy. V skutočnom výpise sú tieto premenné v tvare čísiel s podčiarnikom (vnútorné mená premenných). Odpovede na posledné dve otázky ilustrujú generujúcu schopnosť Prolog-u.

Príklad

Úlohou je navrhnúť modifikáciu predikátu prvok, ktorá by akceptovala iba úplnú totožnosť termu z prvého argumentu s niektorým prvkom zoznamu v druhom argumente a nie ich unifikovateľnosť. V tomto zmysle premenná je totožná iba s premennou rovnakého mena ale nie je totožná s premennou iného mena a už vôbec nie s nejakou konštantou. Pre vyjadrenie totožnosti poskytuje Prolog zabudovaný predikát == :

prvok_t(Prvok,[Hlava|  _ ]) :- Prvok ==  Hlava.
prvok_t(Prvok,[  _  |Telo]) :- prvok_t(Prvok,Telo).

Kladnú odpoveď dostaneme iba na otázky typu:

?- prvok_t(d,[a,s,d,e]).
?- prvok_t(X,[a,s,X,e]).

ale na otázky typu:

?- prvok_t(X,[a,s,d,e]).
?- prvok_t(p,[a,X,d,e]).
?- prvok_t(X,[a,Y,d,e]).

je odpoveď záporná.

Príklad

Úlohou je navrhnúť predikát pre vytvorenie zoznamu L spojením zoznamov L1 a L2. Uvažujme deklaratívnu formuláciu úlohy: Keď spojením zoznamu L1 a zoznamu L2 vznikne zoznam L (telo pravidla), potom spojením zoznamu L1, pred ktorým je prvok H (teda zoznamu [H|L1]) so zoznamom L2 vznikne zoznam L, pred ktorým je prvok H (teda zoznam [H|L]). To znamená rekurzívne volanie predikátu spoj pre postupne stále kratšie zoznamy L1 a L. Tým je súčasne zaručená konvergencia k hraničnej situácii, ktorá nastane, keď sa zoznam L1 skráti až na prázdny zoznam.

Celý proces možno schematicky znázorniť, pozri obrázku

        H   L1     L2           L1    L2                L2
       |-|<-----|<-----|      <----|<-----|          |<-----|
                                              . . .
       |-|<------------|      <-----------|          |<-----|
        H      L                    L                    L

 spoj([H|L1],L2,[H|L]) :- spoj(L1, L2, L).

Ošetrenie hraničnej situácie realizuje ďalšie pravidlo:

 spoj([], L2, L ) :- L2 = L.

Posledné pravidlo môže byť nahradené faktom, ktorému odpovedá tvrdenie: keď spojíme prázdny zoznam s akýmkoľvek zoznamom L, výsledkom je zoznam L. Klauzula pre hraničnú situáciu musí byť umiestnená pred rekurzívnym pravidlom (v opačnom prípade napríklad otázka spoj(X,[a,s],Y) spôsobí zacyklenie). Výsledné riešenie má tvar:

 spoj([], L, L).
 spoj([H|L1], L2, [H|L]) :- spoj(L1, L2, L).

Nie je účelné snažiť sa pochopiť túto definíciu "procedurálne", nakoľko každá z ôsmych možných možností použitia (toľko je kombinácií viazaných/voľných argumentov) má inú procedurálnu interpretáciu. V ďalšom uvedieme niektoré z možných spôsobov použitia predikátu spoj:

 ?- spoj([a,b,c], [d,e], [f,g]).
 no

 ?- spoj([a,b,c],[d,e],X).
 X = [a,b,c,d,e] -> ;
 no

 ?- spoj(X,Y,[a,b,c]).
 X = []        Y = [a,b,c] -> ;
 X = [a],      Y = [b,c] -> ;
 X = [a,b]     Y = [c] -> ;
 X = [a,b,c],  Y = [] -> ;
 no

Príklad

Úlohou je použiť predikát spoj v definícii ďalších "rodinných" predikátov pre vyhľadanie:

zoznamu mladších a starších súrodencov ZM, ZS dieťaťa D
najstaršieho dieťaťa NajSt rodiča R (je posledným v zozname detí)
dvojice bezprostredne po sebe narodených súrodencov Mladsi a Starsi

za predpokladu, že deti sa po narodení zaradia vždy na začiatok zoznamu detí (pozri príklad na zaradenie narodeného dieťaťa do databázy). Riešenie:

 surodenci(ZM,ZS,D)     :- rodina(_,_,ZozDeti),
                                 spoj(ZM,[D|ZS],ZozDeti).

 najstarsi(NajSt,R)     :- (rodina(R,_,ZD) ; rodina(_,R,ZD)),
                                 R \= slob, spoj(_,[NajSt],ZD).

 po_sebe(Mladsi,Starsi) :- rodina(_,_,ZozDeti),
                                 spoj(_,[Mladsi,Starsi|_],ZozDeti).

Príklad

V Prolog-u máme priamy prístup k prvkom zoznamu iba smerom od hlavy. Preto je často potrebné získať k zoznamu L z oznam R s prvkami v obrátenom poradí. Úlohou je navrhnúť predikát, realizujúci naznačenú činnosť. Pri riešení možno postupovať nasledovne: oddelíme hlavu H zoznamu L, obrátime poradie prvkov tela T tohoto zoznamu (rekurzia !) a za takto získaný zoznam X pripojíme prvok H, čo je možné znázorniť graficky:

             L            H      T               H
         <---------|     |-|<-------|           |-|

         |---------      |-||-------    . . .   |-|
              R           H      X               H

                         |----------            |-
                               R                 R

Zoznamy T a X sa postupne skracujú až na prázdne zoznamy, rekurzia teda smeruje k hraničnému stavu, reprezentovanému faktom, že obrátením prázdneho zoznamu sa získa prázdny zoznam. Tento fakt spolu s rekurzívnym pravidlom pre vyššie uvedený postup dáva riešenie úlohy :

 obrat([],[]).
 obrat([H|T],R) :- obrat(T,X), spoj(X,[H],R).

Dialóg so systémom pre rôzne spôsoby použitia navrhnutého predikátu je nasledovný :

 ?- obrat([a,b,c],[c,b]).
 no

 ?- obrat([a,b,c],X).
 X = [c,b,a] -> ;
 no

Je však možné definovať aj efektívnejší predikát pre obrátenie poradia prvkov v zozname:

 obrat(L,R) :- obrat0(L,[],R).

 obrat0([],J,J).
 obrat0([H|A],B,R) :- obrat0(A,[H|B],R).

Predikát obrat0 v každom rekurzívnom kroku odoberá hlavu zoznamu z prvého argumentu a pripája ho na začiatok budovaného zoznamu v druhom argumente. Proces začína prázdnym zoznamom v druhom argumente a končí, keď sa stáva prázdnym zoznam v prvom argumente. Vtedy sa výsledok prenáša do tretieho argumentu a jeho prostredníctvom aj do nadradeného predikátu obrat:

     1.arg                   2.arg            3.arg

[a,b,c, ... ,x,y,z]                   []         R
  [b,c, ... ,x,y,z]                  [a]         R
    [c, ... ,x,y,z]                [b,a]         R
          .....
              [y,z]      [x, ... ,c,b,a]         R
                [z]    [y,x, ... ,c,b,a]         R
                 []  [z,y,x, ... ,c,b,a]  [z,y,x, ... ,c,b,a]

Často je potrebné zistiť džžku zoznamu (počet prvkov). Štandardný Prolog ponúka zabudovaný predikát length(Zoznam,Dlzka). Pri niektorých symbolických manipuláciách je potrebné pracovať s jednotlivými znakmi, tvoriacimi atóm. To umožňuje zabudovaný predikát name(Atom,ZozASCII), kde ZozASCII je zoznam ASCII kódov znakov, ktoré tvoria atóm Atom.

Príklad

Úlohou je navrhnúť predikát na určenie počtu detí v rodine ( príklad rodiny):

 pocet_deti(Rodic,Pocet) :- rodic_deti(Rodic,ZoznamDeti),
                          length(ZoznamDeti,Pocet).

 rodic_deti(Rodic,ZoznamDeti) :-
                       (rodina(Rodic,Partner,ZoznamDeti);
                         rodina(Partner,Rodic,ZoznamDeti)),
                        Partner \= slob, Rodic \= slob.

Pomocou navrhnutého predikátu je možné zistiť, koľko detí má zadaný rodič. Je ale možné zistiť aj to, ktorý rodič má zadaný počet detí. Túto druhú možnosť zabezpečí generujúci predikát rodic_deti. Samotný predikát length nie je možné volať s voľným prvým argumentom.

Príklad

Úlohou je navrhnúť predikát analogický zabudovanému predikátu length, ktorý by však naviac mal schopnosť vygenerovať zoznam zadanej dĺžky (jeho prvky budú voľné premenné):

 dlzka( [],  0).
 dlzka([H|T],D) :- dlzka(T,D0), D  is D0 + 1.

Príklad

Úlohou je navrhnúť predikát, ktorý otestuje, či posledný znak atómu v argumente predikátu je a. Keď budeme predpokladať, že všetky ženské mená končia na toto písmeno a mužské nie (výnimky je možné ošetriť zvlášť), môžeme ho použiť napríklad na určenie pohlavia novorodenca v príklade na zaradenie narodeného dieťaťa pri pôrode:

 zenske_meno(Meno) :- name(Meno,ASCII),
                      spoj(_,[97],ASCII).

Použili sme predikát spoj na otestovanie, či posledný prvok zoznamu ASCII je ASCII kód písmena a, teda 97 (pozri príklad použitia predikátu prvok pre vyhľadávanie). Arity/Prolog umožňuje zadať ASCII kód znaku tak, že tento znak zapíšeme za opačným apostrofom: `a.

Akumulačné cykly

Niekedy je potrebné odovzdávať medzivýsledky z jedného kroku cyklu do druhého (častý je prípad akumulácie medzivýsledkov). Cykly typu repeat-fail sa pre tento účel nehodia, nakoľko pri návrate sa rušia väzby premenných a tým sa strácajú informácie z predchádzajúcich krokov cyklu. Pri realizácii tohoto typu cyklu pomocou rekurzie je potrebné vyhradiť pre odovzdávanie medzivýsledkov ďalší argument predikátu.

Príklad

Úlohou je navrhnúť predikát pre určenie generačného rozdielu medzi členmi rodiny z kapitoly 1.8. Medzi rodičom a dieťaťom je rozdiel jednej generácie, medzi starým rodičom a vnúčaťom dve generácie, atď. V podstate sa jedná o doplnenie rekurzívne definovaného predikátu potomok (v príklade na vyhľadávanie potomkov v databáze ) o počítadlo rekurzívnych volaní v treťom argumente. Inkrementáciu počítadla sme umiestnili až za podcieľ generacia, ktorý zabezpečí viazanie premennej G1 v druhom argumente predikátu is:

 generacia(Potomok,Predok, 1 ) :- rodic(Predok,Potomok).
 generacia(Potomok,Predok,Gen) :- rodic(Predok,   X   ),
                                  generacia(Potomok,X,G1), Gen is G1+1.

Dialóg so systémom vyzerá nasledovne:

 ?- generacia(peter,karol,G).
 G = 2 ->
 yes

 ?- generacia(Potomok,jano,G).
 Potomok = peter, G = 1  -> ;
 Potomok = anna,  G = 1  -> ;
 Potomok = viera, G = 2  -> ;
 no

 ?- generacia(peter,Predok,G).
 Predok = jano,  G = 1 -> ;
 Predok = jana,  G = 1 -> ;
 Predok = karol, G = 2 -> ;
 Predok = zuza,  G = 2 -> ;
 no

 ?- generacia(Potomok,Predok,3).
 Potomok = viera, Predok = karol -> ;
 Potomok = viera, Predok = zuza -> ;
 no

Dôležitým príkladom akumulačných cyklov je budovanie zoznamov, alebo iných štruktúr. V zásade možno postupovať dvojakým spôsobom: priamo (pri vnáraní sa do rekurzie) alebo obrátene (pri vynáraní sa z rekurzie). V prvom prípade je potrebné použiť dva argumenty: v jednom sa buduje štruktúra (od nejakej počiatočnej - tú zadáme ako vstup pri volaní predikátu) a do druhého sa prenesie výsledok vo chvíli, keď rekurzia dosiahla hraničný prípad.

Pri obrátenom spôsobe vystačíme s jediným argumentom. Ten získa svoju počiatočnú "hodnotu" keď rekurzia pri vnáraní dosiahne hraničný prípad a štruktúra sa buduje "obrátene" pri vynáraní sa z rekurzie.

Príklad

Predpokladajme, že v databáze sú uložené nasledujúce fakty:

   p(a).   p(b).

Úlohou je navrhnúť predikát, ktorý vytvorí zo znam, tvorený argumentami jednotlivých faktov. Predpokladáme, že príslušné fakty môžme v priebehu budovania zoznamu odstrániť z databázy. Obrátené budovanie zoznamu realizuje predikát:

 buduj([Hlava|Telo]) :- retract(p(Hlava)), buduj(Telo), !.
 buduj([]).

Priamy spôsob budovania vyžaduje pomocný argument:

 buduj(Telo,Vysledok):-  retract(p(Hlava)),
 buduj([Hlava|Telo],Vysledok), !.
 buduj(Vysledok,Vysledok).

Ak by sme neboli v uvedených definíciách použili symboly rezu, prípadné návrat by generovalo ako ďalšie riešenia čiastkové zoznamy. Rozdiel v činnosti oboch predikátov ilustruje dialóg:

 ?- buduj(Zoznam).
 Zoznam = [a,b] -> ;
 no

 ........

'predpokladáme obnovenie databázy'

 ?- buduj([],Zoznam).
 Zoznam = [b,a] -> ;
 no

Druhý z uvedených spôsobov je vhodné použiť nielen vtedy, keď sa z nejakého dôvodu požaduje opačné poradie prvkov, ale najmä v prípade, keď je potrebné pripájať prvky pred nejaký iný zoznam:

 ?- buduj([f,g],Zoznam).
 Zoznam = [b,a,f,g] -> ;
 no

V blokových modeloch možno veľmi názorne sledovať vplyv symbolu rezu na činnosť systému Prolog. Pri návrate cez blok rezu sa pokračuje z jeho brány Fail priamo na bránu Fail nadradeného cieľa.

Príklad

Úlohou je vyšetriť činnosť Prolog-u pri budovaní zoznamu pomocou jednoargumentového predikátu buduj z predchádzajúceho príkladu . Príslušný blokový model je na obrázku

  #=================================================================#
  |(0)buduj(X)       #========================================#     |
  |                  | (2)buduj(Y)      #================#    |     |
  |                  |                  | (4)buduj(W)    |    |     |
  |#=============#   |#=============#   | #=============#|    |     |
  ||(1)          |   ||(3)          |   | |(5)          ||    |     |
?-||retract(p(A))|A=a||retract(p(B))|B=b| |retract(p(C))||    |     |
>-++----->-------+->-++------>------+->-+>+---->----+   ||    |     |
  ||             |   ||             |   |++----<----+   ||    |     |
  ||             |   ||             |   ||#=============#|W=[]|Y=[b]|X = [a,b]
  ||             |   ||             |   ||               |#=# | #=# |
  ||             |   ||             |   |+----->---------++-+-+>+-+-+->-+
  ||             |   ||             |   |                ||!| | |!| |   |
  ||             |   |#=============#   #================##=# | | | |   |;
  |#=============#   #========================================# #=# |   |
no#=================================================================#   |
<-----------------------<---------------------------------------------<-+

                       obrázok 1


   #===================================================================#
   | (0)buduj(X)       #=========================================#     |
   |                   | (2)buduj(Y)       #================#    |     |
   |                   |                   | (4)buduj(W)    |    |     |
   | #=============#   | #=============#   | #=============#|    |     |
   | |(1)          |   | |(3)          |   | |(5)          ||    |     |
?- | |retract(p(A))|A=a| |retract(p(B))|B=b| |retract(p(C))||    |     |
->-+>+------>------+->-+-+------>------+->-+>+----->----+  ||    |     |
   | |             |   | |             |   |++-----<----+  ||    |     |
   | |             |   | |             |   ||#=============#|    |     |
   | |             |   | |             |   ||               |W=[]|Y=[b]| X=[a,b]
   | |             |   | |             |   |+------>--------+-->-+-->--+->-+
   | |             |   | #=============#   #================#    |     |   |;
   | |             |   |   +------<-----------------<---------<--+--<--+-<-+
   | |             |   |   |                                     |Y=[] | X=[a]
   | |             |   |   +------>----------------->------------+-->--+---->-
   | #=============#   #=========================================#     | yes
   #===================================================================#

                         obrázok 2

Príklad

Úlohou je vyšetriť vplyv vynechania symbolu rezu, umiestneného na konci prvej klauzuly v definícii predikátu buduj v predchádzajúcom príklade . Blokový model riešenej úlohy je na obrázku 2.. Ako je vidieť, pri návrate sa zbytočne generuje ďalšia "alternatíva" - čiastkový zoznam, ktorý predstavuje medzivýsledok predošlého kroku rekurzie. Z blokového modelu na obrázku 1 je patrné, že sa použitím rezu odstránilo nežiadúce generovanie falošných výsledkov.

Príklad

Úlohou je vyšetriť činnosť Prolog-u pri budovaní zoznamu pomocou dvojargumentového predikátu buduj z príkladu príklad na tvorbu zoznamov. Príslušný blokový model je na nasledujúcom obrázku. Je dobre vidieť, že zoznam sa buduje priamo v procese vnárania sa do rekurzie a že nesplnenie cieľa (5) spôsobí prenesenie výsledku z prvého do druhého argumentu. Tento výsledok sa objaví na výstupe cieľa (4) a okamžite sa prenáša aj na výstupy cieľov (2) a(0).

  #================================================================#
  |(0)buduj([],X)    #=========================================#   |
  |                  | (2)buduj([a],X)  #==================#   |   |
  |                  |                  | (4)buduj([b,a],X)|   |   |
  |#=============#   |#=============#   | #=============#  |   |   |
  ||(1)          |   ||(3)          |   | |(5)          |  |   |   |
?-||retract(p(A))|A=a||retract(p(B))|B=b| |retract(p(C))|  |   |   |
>-++------>------+->-++------>------+->-+>+---->----+   |  |   |   |
  ||             |   ||             |   |++----<----+   |  |   |   |
  ||             |   ||             |   ||#=============#  |   |   |
  ||             |   ||             |   ||                 |#=#|#=#|X=[b,a]
  ||             |   ||             |   |+----->-----------++-+++-++->-+
  ||             |   ||             |   |                  ||!|||!||   |
  ||             |   |#=============#   #==================##=#|| ||   |;
  |#=============#   #=========================================##=#|   |
no#================================================================#   |
<-----------------------<--------------------------------------------<-

Príklad

Úlohou je navrhnúť nové predikáty pre budovanie zoznamu z faktov databáze. Od predikátov buduj, navrhnutých v príklade na tvornu zoznamov sa majú líšiť v tom, že obnovia pôvodný stav databázy. Obrátené budovanie zoznamu realizuje predikát:

 utvor([Hlava|Telo]) :- retract(p(Hlava)),utvor(Telo),
                        asserta(p(Hlava)),!.
 utvor([]).

Priamy spôsob budovania vyžaduje pomocný argument:

 utvor(Telo,Vysledok) :- retract(p(Hlava)),
            utvor([Hlava|Telo],Vysledok),asserta(p(Hlava)),!.
 utvor(Vysledok,Vysledok).

V úlohách, ktoré používajú databázu Prolog-u na ukladanie medzivýsledkov, potrebujeme mať k dispozícii predikát na čistenie predikát. V Arity/Prolog-u aj v LPA Prolog-u je to abolish.

Príklad

Úlohou je navrhnúť predikát (analógiu abolish z Arity/Prolog-u), ktorý odstráni z databázy Prolog-u všetky klauzuly, ktoré sú unifikovateľné so štruktúrou s menom Meno a s aritou Arita:

 odstran_vsetko(Meno/Arita) :-functor(Struktura,Meno,Arita),
                              o_vsetko(Struktura).

 o_vsetko(S) :- retract( S    ), fail.   % fakty
 o_vsetko(S) :- retract((S:-_)), fail.   % pravidla
 o_vsetko(_).                            % splnenie ciela

Kumulovanie všetkých riešení

Obvykle používateľa zaujímajú všetky riešenia danej otázky a je mu na obtiaž vyžadovať tieto riešenia opakovaným zadávaním bodkočiarok. Naviac mu nemusí vyhovovať forma, v ktorej Prolog vypisuje viazanie premenných pre jednotlivé riešenia. Príklad (na riadenie návratu) naznačil možnosť ako navrhnúť predikát pre cyklický výpis riešení. Je možné definovať všeobecnejšie koncipovaný predikát pre tieto účely.

Príklad

Úlohou je navrhnúť predikát, ktorý by kumuloval do zoznamu všetky termy, pre ktoré má daná otázka riešenie:

 riesenia(Term,Otazka,Zoznam) :- vsetky(Otazka,Term),
                                   vytvor(Zoznam), !.

Predikát vsetky ukladá do databázy fakty o vyhovujúcich termoch a predikát vytvor (pozri buduj v príklade na tvorbu zoznamov) z nich na konci vytvorí zoznam:

 vsetky(Otazka,Term)   :- Otazka, assertz(term(Term)), fail.
 vsetky(  _  ,  _ ).
 vytvor([Term|Zoznam]) :- retract(term(Term)), vytvor(Zoznam).
 vytvor( [] ).

Keď sú v databáze napríklad fakty:

 pivo(saris,10).        pivo(bazant,12).    pivo(kozel,12).
 pivo(staropramen,10).  pivo(prazdroj,12).

potom dialóg so systémom môže byť nasledovný:

 ?- riesenia(Znacka,pivo(Znacka,_),L).
 Znacka = _25, L = [saris,bazant,kozel,staropramen,
                                  prazdroj]-> ;
   no

Arity/Prolog poskytuje niekoľko zabudovaných predikátov na riešenie podobných úloh. Predikát bagof(T,C,ZR) vyhľadá (v procese návratu, ktorý sám vyvoláva) všetky termy T, pre ktoré je zadaný cieľ C splnený a vytvorí z nich neusporiadaný zoznam ZR v treťom argumente (opakovaný výskyt prvkov zoznamu je možný). Argument T musí byť voľnou premennou, alebo takúto premennú musí obsahovať a táto premenná musí byť obsiahnutá v cieli C. Ostatné premenné v cieli C môžu byť voľné (potom systém zostavuje pre ich rôzne viazania rôzne zoznamy ZR v procese návratu, vyvolaného zvonku - tým sa líši od predikátu riesenia):

 ?-  bagof(Znacka,pivo(Znacka,_),L).
 Znacka = _25, L = [saris,staropramen] -> ;
 Znacka = _25, L = [bazant,kozel,prazdroj] -> ;
 no

Je možné tieto premenné existenčne kvantifikovať zápisom P^C (v prípade jednej premennej P ) alebo (P1,P2, ... PN)^C ( N premenných Pi ). Zápis P^C reprezentuje výrok "existuje také viazanie premennej P, pre ktoré je cieľ C splnený".

Predikát setof pracuje podobne ako bagof, len s tým rozdielom, že výsledný zoznam riešení je zotriedený a sú z neho vylúčené opakované výskyty "úspešných" termov. Predikát findall pracuje podobne ako bagof, ale všetky premenné v cieli chápe ako existenčne kvantifikované. Pre ilustráciu poslúži databáza:

 lubi(jano,pivo).  lubi(jano,rum).  lubi(jano,vino).
 lubi(fero,pivo).  lubi(fero,vino). lubi(jozo,pivo).

a nasledujúci dialóg:

 ?- bagof(Kto,lubi(Kto,Co),L).
 Co = pivo, L = [jano,fero,jozo] -> ;
 Co = rum,  L = [jano] -> ;
 Co = vino, L = [jano,fero] -> ;
 no

 ?-  setof(Kto,lubi(Kto,Co),L).
 Co = pivo, L = [fero,jano,jozo] -> ;
 Co = rum,  L = [jano] -> ;
 Co = vino, L = [fero,jano] -> ;
 no

 ?-  findall(Kto,lubi(Kto,Co),L).
 L = [jano,jano,jano,fero,fero,jozo] -> ;
 no

 ?- bagof(Kto,Co^lubi(Kto,Co),L).
 L = [jano,jano,jano,fero,fero,jozo] -> ;
 no

 ?- setof(Kto,Co^lubi(Kto,Co),L).
 L = [fero,jano,jozo] -> ;
 no

 ?- setof(Co-Pijani,setof(Kto,lubi(Kto,Co),Pijani),L).
 L=[pivo-[fero,jano,jozo],rum-[jano],vino-[fero,jano]] - >;
 no

Okrem vyššie uvedených viazaní premenných sa v skutočnej odpovedi systému objavia ešte priradenia vnútorných mien premenných (podčiarnik a číslo) ostatným premenným otázky (napr. Kto v prvých dvoch, Kto, Co v ďalších troch, ...). Pre pozmenenú databázu dostávame ďalšie typy dialógov:

 lubi(jano,pivo,10).         lubi(jano,pivo,12).
 lubi(jano,vino,cervene).    lubi(fero,vino,biele).
 lubi(fero,vino,cervene).    lubi(duro,pivo,12).

 ?- setof(Kto,lubi(Kto,Co,Druh),L).
 Co = pivo, Druh = 10, L = [jano] -> ;
 Co = pivo, Druh = 12, L = [duro,jano] -> ;
 Co = vino, Druh = biele, L = [fero] -> ;
 Co = vino, Druh = cervene, L = [fero,jano] -> ;
 no

 ?- setof(Kto,Druh^lubi(Kto,Co,Druh),L).
 Co = pivo, L = [duro,jano] -> ;
 Co = vino, L = [fero,jano] -> ;
 no

 ?- bagof(Kto,Druh^lubi(Kto,Co,Druh),L).
 Co = pivo, L = [jano,jano,duro] -> ;
 Co = vino, L = [jano,fero,fero] -> ;
 no

 ?- setof(Kto,(Co,Druh)^lubi(Kto,Co,Druh),L).
 L = [duro,fero,jano] -> ;
 no

Práca so zložitejšími rekurzívnymi štruktúrami

Okrem zoznamov je možné použiť aj iné rekurzívne štruktúry. Je potrebné definovať vhodný binárny funktor (analógia bodka-operátora zoznamov) a konštantu, reprezentujúcu hraničnú situáciu (analógia prázdneho zoznamu).

Príklad

Úlohou je navrhnúť vhodnú rekurzívnu štruktúru pre reprezentovanie rozdielneho počtu detí pri opise rodinných vzťahov (porovnaj s príkladom ( definícia rodiny )). Binárnym funktorom pre tvorbu rekurzívnej štruktúry nech je funktor deti a konštantou hraničného prípadu nech je atóm bezdetni:

 rodina( zuza,  karol, deti(jana,deti(dana,deti(milan,bezdetni)))).
 rodina( jana,  jano,  deti(peter,deti(anna,bezdetni))).
 rodina( anna,  jozo,  deti(viera,bezdetni)).
 rodina( eva,   milan, bezdetni          ).
 rodina( viera, slob,  bezdetni          ).
 rodina( slob,  peter, bezdetni          ).
 rodina( dana,  slob,  bezdetni          ).

 otec(O,D) :- rodina(_,O,SD), clen(D,SD).

 clen(X, deti(X,_) ).
 clen(X, deti(_,S) ) :- clen(X,S).

Predikát clen je analógiou predikátu prvok (pozri príklad - definícia predikátu prvok).

V prípade rodiny sme použili reprezentáciu hierarchickej štruktúry pomocou čiastkových faktov. Niekedy je výhodné reprezentovať celú štruktúru kompaktnejšie ako jediný zložený term. Umožní to jednotnú manipuláciu so všetkými prvkami tejto štruktúry.

Príklad

Úlohou je zobraziť povodia niektorých riek pomocou jedinej štruktúry a navrhnúť predikát pre určenie všetkých riek z daného povodia. Povodím rieky rozumieme stromovú štruktúru, tvorenú na prvej úrovni všetkými prítokmi danej rieky, na druhej úrovni prítokmi týchto prítokov, atď.:

 veltok(labe(vltava)).
 veltok(dunaj(vah(turiec,kysuca,bela(rackova,bystra,
       brezinka),orava,revuca),ipel,hron(slatina, bystrica))).
 rieka(R,M) :- veltok(S),  functor(S,M,_),
                         povodie(R,S).
 povodie(M,S) :- S=..[M|_].
 povodie(X,S) :- S=.. [_|Pritoky],
 vtekaju(X,Pritoky).
 vtekaju(X,[H|_]) :- povodie(X,H).
 vtekaju(X,[_|T]) :- vtekaju(X,T).

Pomocou zabudovaného operátora =.. získame zo štruktúry S meno funktora M a zoznam argumentov Pritoky. Keď potrebujeme iba meno funktora, môžme použiť efektívnejší zabudovaný predikát functor. Predikát rieka je možné použiť viacerými spôsobmi:

 ?- rieka(rackova,dunaj).   'patrí rackova do povodia rieky dunaj ?'
 ?- rieka(rackova,  P  ).  'do akého povodia patrí rackova ?'
 ?- rieka(   R,   dunaj).  'ktoré rieky patria do povodia dunaja ?'
 ?- rieka(   R,     P  ).  'ktoré rieky patria do ktorého povodia?'

Príklad

Úlohou je vizualizovať stromové štruktúry, prislúchajúce jednotlivým povodiam z predchádzajúceho príkladu):

 mapa(R) :- veltok(V), functor(V,R,_), nl, mapa(V ,0), fail.
 mapa(_).
 mapa(V,Odsad) :- V=..[X|Pritoky],  tab(Odsad),
                  write(X), nl,
                  Odsad1 is Odsad+5, kresli(Pritoky,Odsad1),!.
 kresli([H|T],O) :- mapa(H,O), kresli(T,O), !.
 kresli(  [], _).

Zabudovaný predikát tab(N) vypíše N medzier. Nasledujúci dialóg ilustruje použitie navrhnutého predikátu:

 ?- mapa(dunaj).
         dunaj
          vah
                     turiec
                     kysuca
                     bela
                            rackova
                            bystra
                            brezinka
                     orava
                     revuca
              ipel
              hron
                     slatina
                     bystrica
       yes

Príklad

Nech sú povodia zadané v tvare čiastkových faktov, reprezentujúcich prítoky tej ktorej rieky:

 pritok(labe,  [vltava]).
 pritok(vah,   [turiec,kysuca,bela,orava,revuca]).
 pritok(dunaj, [vah,ipel,hron]).
 pritok(bela,  [rackova,bystra,brezinka]).
 pritok(hron,  [slatina,bystrica]).

Úlohou je vytvoriť z týchto faktov štruktúry, uvedené v príklade - povodia riek :

 gen :-  abolish(veltok/1), koren(X),
        pritok(X,Z), gen(Z,Z1), S =.. [X|Z1], assertz(veltok(S)),
        fail.
 gen :-  listing(veltok).   /* výpis vygenerovaných štruktúr */
 koren(X) :- pritok(X,_),  not(( pritok(_,Z), prvok(X,Z) )).
 gen([H|T],[H1|T1])  :- pritok(H,P), !, gen(P,P1),
                        gen(T,T1), H1=.. [H|P1].
 gen([H|T],[ H|T1]) :- gen(T,T1).
 gen( [],     []  ).

Predikát abolish je zabudovaným predikátom Arity/Prolog- u. Analogický predikát je naprogramovaný štandardnými prostriedkami jazyka Prolog v príklade na odstránenie klauzuly z databázy .

Príklad

Úlohou je navrhnúť predikát ktorý v danej štruktúre nahradí všetky výskyty zvoleného termu iným termom:

 nahrad(TermNovyTerm, NovyTerm) :- !.
 nahrad(  _ , Term,     _   ,   Term  )       :-  atomic(Term), !.
 nahrad(Term, Term, NovyTerm, NovyTerm) :- !.
 nahrad(  _ , Term,     _   ,   Term  )       :-  atomic(Term), !.
 nahrad(ZaCo, Term,    Co   , NovyTerm) :-
              Term =.. [F|Argumenty],
              nahrad_v_argumentoch(ZaCo,Argumenty,
              Co,NoveArgumenty),
              NovyTerm=..[F|NoveArgumenty].

 nahrad_v_argumentoch( _  ,     []      , _ , [] ).
 nahrad_v_argumentoch(ZaCo, [Term|Termy], Co,[NovyTerm|NoveTermy]) :-
              nahrad(ZaCo, Term , Co, NovyTerm),
              nahrad_v_argumentoch( ZaCo, Termy, Co,NoveTermy).

Použitie navrhnutého predikátu ilustruje dialóg:

 ?- nahrad(a, 3*a* (a^2-b)+sin(a)*sqrt(log(a/b)),q, N).
 N = 3 * q * (q ^ 2 - b) + sin(q) * sqrt(log(q / b)) ->
 yes