13


Lõpprekursioon

Enamus "tööd tegevatest" predikaaatidest on rekursiivsed, st. määratletav predikaat (lause vasakul pool olev predikaat) esineb uuesti lause kehas (lause paremal pool). Sellised olid labürindis teed otsiv predikaat otsi(Ruum), matka kirjeldav predikaat matk(Linn1, Linn2, Teepikkus, Läbitud) jne.
Rekursiiselt kirjeldatud predikaadid on ohtlikud, sest Prologi otsimismehhanism võib rekursiivse predikaadiga määratud eesmärki lahendades tekitada niipalju alameesmärke, et Prolog "lämbub" ja vastuse asemel saame teate Fatal Error : Control stack full.
Vaatame näiteks, mis juhtub, kui isad-lapsed on kirjeldatud nagu eespool:

tytar_on(uranos,rhea).
tytar_on(kronos,hera).
poeg_on(uranos,okeanos).
poeg_on(uranos,iapetos).
poeg_on(uranos,kronos).
poeg_on(kronos,zeus).
poeg_on(iapetos,atlas).

laps(Vanem, Laps):-

poeg_on(Vanem, Laps).
laps(Vanem, Laps):-
tytar_on(Vanem, Laps).

ja järglased on kirjeldatud predikaadiga

jarglane(Esivanem, Jarglane):-

laps(Esivanem,Jarglane). %Esimese astme järglased on lapsed

jarglane(Esivanem, Jarglane):-

jarglane(Esivanem, Jarglane1),
laps(Jarglane1, Jarglane). %Ka järglaste lapsed on järglased

Kõik tundub loomulik olevat. Vaatame, mis juhtub, kui esitame päringu

?- jarglane(uranos, Jarglane).

Päringut lahendades asendab Prolog eesmärke alameesmärkidega, kuni jõuab muutujate väärtusteni (selle jälgimiseks lülitage sisse Prologi Debug-reziim):

?- jarglane(uranos, Jarglane).

?- laps(uranos, Jarglane).
?- poeg_on(uranos, Jarglane).
?- poeg_on(uranos, okeanos)
Jarglane = okeanos
% hakatakse otsima järgmist lahendit
?- poeg_on(uranos, iapetos)
Jarglane = iapetos
?- poeg_on(uranos, kronos)
Jarglane = kronos


Kuna poegi rohkem ei ole, toimub tagurdus ja hakatakse vaatlema predikaadi laps teist võimalust tytar_on:

?- tytar_on(uranos, rhea), Jarglane = rhea

Kuna Uranosel tütreid rohkem ei ole, tuleb veel kord tagurdada ja hakata järglasi otsima predikaadi jarglane teise lause abil:

jarglane(uranos, Jarglane):-

jarglane(uranos, Jarglane1),

laps(Jarglane1, Jarglane).

Nüüd asendab Prolog eesmärgi
?-jarglane(uranos, Jarglane).

eesmärkidega
?- laps(uranos, Jarglane1), laps(Jarglane1, Jarglane). % (I)

?- poeg_on(uranos, Jarglane1), laps(Jarglane1, Jarglane) .

Siit jätkates jõutakse lahenditeni
Jarglane = atlas
Jarglane = zeus
Jarglane = hera

Nüüd on leitud kõik lahendid, mis on võimalik saada eesmärgist jarglane(uranos, Jarglane1) predikaadi jarglane esimest lauset kasutades, ja Prolog asendab eesmärgi (I) eesmärgiga

?- jarglane(uranos, Jarglane2), laps(Jarglane2, Jarglane1), laps(Jarglane1, Jarglane). % (II)

Nüüd ei anna predikaadi jarglane esimene lause laps(uranos, Jarglane2) enam ühtki lahendit (sest eespool toodud predikaatide poeg_on, tytar_on kirjelduses ei ole ühtki lapse-lapse-last), sellepärast hakkab Prolog vaatlema teist võimalust, s.t. ta asendab eesmärgi (II) eesmärgiga

?- jarglane(uranos, Jarglane3), laps(Jarglane3, Jarglane2), laps( Jarglane2, Jarglane 1), laps(Jarglane1, Jarglane).

jne, jne, kuni peagi teatab

Fatal Error : Control stack full

See juhtus sellepärast, et predikaat jarglane oli kirjeldatud valesti. Rekursiivsete predikaatide käsitlemisel ei teki probleeme, kui predikaat on lõpprekursiivne, s.t. esineb oma kirjelduse paremal pool ainult viimases lauses viimasena. Selline oli näiteks predikaat otsi:

otsi(Ruum):-

paaseb(Ruum, Ruum1)),
ei(kaidud(Ruum1)),
lisa(kaidud(Ruum)),
kirjuta('Ruumist '),
kirjuta(Ruum),
kirjuta(' lähen ruumi '),
kirjuta(Ruum1),
rv,
otsi(Ruum1).

ja predikaat matk

matk(Linn, Linn, Teepikkus, Läbitud):-

!,
esita_tee(Teepikkus, Läbitud).
matk(Linn1, Linn2, Teepikkus, Läbitud):-
paaseb(Linn1, Linn, Teepikkus1),
ei esineb(Linn, Linnad),
Teepikkus2 oleks Teepikkus + Teepikkus1,
matk(Linn, Linn2, Teepikkus2, [Linn|Linnad]).

Ka predikaadi jarglane saab kirjeldada lõpprekursiivsena:

jarglane(Esivanem, Jarglane):-

laps(Esivanem, Jarglane).
jarglane(Esivanem, Jarglane):-
laps(Jarglane1, Jarglane),
jarglane(Esivanem, Jarglane1).

Prologi predikaate saab alati kirjeldada lõpprekursiivsetena, kuid mõnikord nõuab see predikaadi tunduvat muutmist, uute muutujate sissetoomist jne.

Ülesanne

Fibbonacci arvud 0, 1, 1, 2, 3, 5, 8, 13,... defineeritakse järgmiselt: esimesed kaks Fibbonacci arvu on 0,1 ja edasi iga järgmine arv on kahe eelmise arvu summa. n-da Fibbonacci arvu leidmiseks võib defineerida kahekohalise predikaadi:

fibbonacci(1,0).

fibbonacci(2,1).
fibbonacci(N, F):-
N1 oleks N-1,
N2 oleks N-2,
fibbonacci(N1, F1),
fibbonacci(N2, F2),
F oleks F1 + F2.

kuid see predikaat ei ole lõpprekursiivne ja sellepärast ei sa sellega arvutada kuigi suuri Fibbonacci arve (lihtne on näha, et n-da Fibbonacci arvu arvutamisel genereerib see predikaat 2n alameesmärki). Kirjelda lõpprekursiivne predikaat Fibbonnacci arvude leidmiseks!


Küsimused, probleemid:

jaak@cc.ttu.ee

Tagasi loengute sisukorra juurde