Vlákno názorů k článku
Mercury: Abstrakce nad algoritmy

Mam takovy dotaz, sice se primo netyka Mercuryho, ale LISPu, nicmene tyto jazyky maji hodne spolecneho.

Tyka se to tail-recursion, ktera je take v clanku zminena. V temer kazdem clanku o LISPu autori pisou, ze nema cenu pouzivat smycky, vse se ma delat pomoci rekurze a o vlastni tvorbu smycky (pokud je to mozne) se postara tail-recursion.

Problem je, ze se uz nikde nepise, kdy se tail-recursion provede (tj. interpreter kod vlastne optimalizuje) a kdy ne. Take predpokladam, ze ne vsechny LISPy toto umi.

Jak je tomu u Mercuryho, ktere rekurzivni fce dovede "rozmotat" a u kterych selze?

Podle dokumentace je Mercury schopen rozmotat i nejméně dvojice predikátů, které se na konci volají navzájem. A dále má tušim optimalizaci v tom duchu, že predikát zůstává tail-rekurzivní i v případě, že striktně vzato po návratu z rekurzivního volání volá ještě jeden typový konstruktor (vyrobení seznamu z hlavy a ocasu, vyrobení n-tice, apod.).

Mercury má taky jeden option --warn-non-tail-recursive, který při kompilaci způsobí vypsání všech self-rekurzivních predikátů, které se nepodařilo rozmotat.

je to proste - tail recurcursion se provede v pripade, ze je zavolana ta sama funkce, ale s vysledkem tohoto volani se dal nepracuje - uvedu priklad ve Schemu (mam ho radsi) - dialekt LISPu

;; toto je faktorial klasickou rekurzi
(define (fact x)
(if (= x 0) 1 (* x (fact (- x 1)))))

;; koncovou rekurzi je to pak nejak takto
(define (fakt x)
(define (int-fact i result)
(if (> i x) result ;; vraci vysledek
(int-fact (+ i 1) (* result i))))) ;; koncova rekurze
(int-fact 1 1))

doufam, ze jde videt ze v tom druhem pripade int-fact nikde nepracuje se svym vysledkem a uklada si ho do parametru result

Ve Scheme se provede tail-call pri volani kazde funkce, pokud je dane volani v tail-pozici - nemusi se jednat o rekurzivni volani te same funkce.

tail-recursion je pak specialni pripad pouziti tail-call pro rekurzi :-)

tail-pozice je definovana jednoduse - posledni vyraz v tele funkce je v tail pozici, then a else vetev ifu je ta tail-pozice, pokud cely if je v tail-pozici a podobne, detaily viz R5RS. V podstate jde o to, ze vysledek volani funkce se nepouzije dale jako argument pri volani dalsi funkce, ale vrati se.

no vicemene se shodujem - s vysledkem se proste dal nepracuje - popsal jsem to opravdu trochu zjednodusene

Mezi Scheme a Common Lispem je jeden dramaticky rozdil - standardni Lisp negarantuje optimalizaci tail-rekurze NIKDE. Bezne implementace Lispu ve vetsi ci mensi mire TCO podporuji, ale spolehnout se na to neda. Zapomente na rekurzi, pouzijte smycku.

Tvrzení, že v Lispu se nemají používat cykly, protože vše jde dělat rekurzí, je blábol. Tvrzení, že v Common Lispu se mají místo rekurze používat cykly, protože standard jazyka nepožaduje TRO, je blábol stejně tak.

V první řadě: Jeden z podstatných rozdílů mezi Mercury a Lispem je, že Mercury definuje určitý programovací styl, zatímco Lisp nechává v otázce stylu programátorovi naprostou volnost. Takže zatímco v Mercury je rekurze zcela přirozenou technikou, v Lispu použijete cyklus nebo rekurzi v závislosti na charakteru toho, co chcete vyjádřit. Někdy je lepší použít cyklus, někdy zase rekurzi a někdy záleží čistě na vkusu.

Co se týče TRO v Lispu, každý solidní překladač ji umí, takže není nejmenší důvod ji nepoužívat. Nemluvě o tom, že v mnoha případech se rekurze používá bez ohledu na to je-li tail či netail, prostě proto, že nad zpracovávanými daty není moc hluboká.