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