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
järglane(Esivanem, Järglane):-
laps(Esivanem,Järglane).
järglane(Esivanem, Järglane):-
järglane(Esivanem, Järglane1),
laps(Järglane1, J ärglane).
Kõik tundub loomulik olevat. Vaatame, mis juhtub, kui esitame päringu
?- järglane(uranos, Järglane).
Päringut lahendades asendab Prolog eesmärke alameesmärkidega, kuni jõuab muutujate väärtusteni (selle jälgimiseks lülitage sisse Prologi Debug-reziim):
?- järglane(uranos, Järglane).
?- laps(uranos, Järglane).
?- poeg_on(uranos, Järglane).
?- poeg_on(uranos, okeanos)
Järglane = okeanos
?- poeg_on(uranos, iapetos)
Järglane = iapetos
?- poeg_on(uranos, kronos)
Järglane = kronos
Kuna poegi rohkem ei ole, toimub tagurdus ja hakatakse vaatlema predikaadi laps teist võimalust tytar_on:
?- tytar_on(uranos, rhea), Järglane = rhea
Kuna Uranosel tütreid rohkem ei ole, tuleb veel kord tagurdada ja hakata järglasi otsima
predikaadi järglane teise lause abil:
järglane(uranos, Järglane):-
järglane(uranos, Järglane1),
laps(Järglane1, Järglane).
Nüüd asendab Prolog eesmärgi
?-järglane(uranos, Järglane).
eesmärkidega
?- laps(uranos, Järglane1), laps(Järglane1, Järglane).
?- poeg_on(uranos, Järglane1), laps(Järglane1, Järglane) .
Siit jätkates jõutakse lahenditeni
Järglane = atlas
Järglane = zeus
Järglane = hera
Nüüd on leitud kõik lahendid, mis on võimalik saada eesmärgist
järglane(uranos, Järglane1) predikaadi järglane esimest lauset kasutades, ja
Prolog asendab eesmärgi (I) eesmärgiga
?- järglane(uranos, Järglane2), laps(Järglane2, Järglane1), laps(Järglane1, Järglane).
Nüüd ei anna predikaadi järglane esimene lause laps(uranos, Järglane2) 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
?- järglane(uranos, Järglane3), laps(Järglane3, Järglane2),
laps(Järglane2, Järglane1), laps(Järglane1, Järglane).
jne, jne, kuni peagi teatab
Fatal Error : Control stack full
See juhtus sellepärast, et
predikaat järglane oli kirjeldatud valesti, selle kirjelduses oli
kohe alguses (paremal pool) rekursiivne pöördumine sama predikaadi poole - Prolog peab käivitama alameesmärgi, kuid jätma mällu ka kogu praeguse situatsiooni, sest pärast alameesmärgi sooritamist tuleb siia tagasi pöörduda - midagi jäi veel teha.
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):-
pääseb(Ruum, Ruum1)),
not(käidud(Ruum1)),
lisa(käidud(Ruum)),
write('Ruumist '),
write(Ruum),
write(' lähen ruumi '),
write(Ruum1),
nl,
otsi(Ruum1).
ja predikaat matk:
matk(Linn, Linn, Teepikkus, Läbitud):-
!,
esita_tee(Teepikkus, Läbitud).
matk(Linn1, Linn2, Teepikkus, Läbitud):-
pääseb(Linn1, Linn, Teepikkus1),
not esineb(Linn, Linnad),
Teepikkus2 is Teepikkus + Teepikkus1,
matk(Linn, Linn2, Teepikkus2, [Linn|Linnad]).
Ka predikaadi järglane saab kirjeldada lõpprekursiivsena:
järglane(Esivanem, Järglane):-
laps(Esivanem, Järglane).
järglane(Esivanem, Järglane):-
laps(Järglane1, Järglane),
järglane(Esivanem, Järglane1).
Prologi predikaate saab alati kirjeldada lõpprekursiivsetena,
kuid mõnikord nõuab see predikaadi tunduvat muutmist, uute muutujate sissetoomist jne.
Näiteks faktoriaali arvutamine matemaatilise definitsiooni alusel
(arvu 0 faktoriaal´ on 1; 0-st suurema täisarvu N faktoriaal saadakse sellest arvust
ühe võrra väiksema arvu faktoriaali, korrutamisel N-ga, s.t. N!
= (N-1)! * N )
saame predikaadi, mis ei ole lõpprekursiivne:
faktoriaal(0,1):-!.
faktoriaal(N,Nfac):-
N1 is N-1,
faktoriaal(N1,N1fac),
Nfac is N1fac*N.
Lõpprekursiivse predikaadi saame, kui hakkame järjest arve korrutama, kuni jõuame arvuni, mille
faktoriaali tahame teada; see on sama arvutusviis, mida tegelikult faktoriaali arvutades kasutatakse
ja saraneb väga kaardil linnade vahelise tee otsimise predikaadi ideele (liigume edasi niikaua, kuni
oleme kohal):
faktoriaal1(N,Nfac):-
korruta(0,1,N,Nfac).
Predikaadi korruta(N1,N1fac,N,Nfac) esimene argument näitab,
millise arvuni oleme juba jõudnud, teine - mis on senine korrutis (s.t. esimese argumendi fatoriaal),
kolmas - milleni peame jõudma ja viimane - milline tuleb otsitav faktoriaal. Käivitamisel
salvestatakse kahes esimeses argumendis fakt 0!=1.
korruta(N,Nfac,N,Nfac):-!. !
korruta(N1,N1fac,N,Nfac):-
N2 is N1+1,
N2fac is N1fac*N2,
korruta(N2,N2fac,N,Nfac).
See predikaat on juba lõpprekursiivne.
Ülesandeid:
1.
Binoomkoefitsiendid on arvujadad [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] jne, kus iga järgmine jada
saadakse eelmise algusesse ja lõppu nulli lisamisel ja siis järjestikuste jadaliikmete kahekaupa
liitmisel (sageli esitatakse arvutusprotsess nn. Pascali kolmnurga abil).
Tee (lõpprekursiivne) programm N-da binoomkoefitsientide jada leidmiseks.
Küsimused, probleemid:
©2004
Jaak Henno
