Zdradzę tylko, że funkcja recur to wywołanie rekurencyjne do funkcji tworzonej w miejscu słówka loop.
Że, co? Można jaśniej?
Ok, może podam ekwiwalent w Javie:
static int factorial(int number){
return computeFactorial(1, number);
}
static int computeFactorial(int sum, int iteration){
if (iteration == 1) {
return sum;
}
return computeFactorial(sum * iteration, --iteration);
}
Aaaa, czyli rozbijasz to na dwie funkcje, tak aby druga mogła mieć dwa argumenty…
Tak, liczenie silni (rekurencyjnie) wymaga dwóch liczb, a nie chcemy przecież aby klient musiał za każdym razem wpisywać oba (z czego pierwszy to zawsze 1).
No dobrze, ale ten fragment w Javie może wywalić stos prawda?
Jak najbardziej i co więcej – w C# też może!
A w Clojure?
A w Clojure… i tak i nie…
Oryginalny przykład nie wywali stosu, ale poniższy już ma taką szansę:
(defn calcualteFactorial
[sum iteration]
(if(= iteration 1)
sum
(calcualteFactorial (* sum iteration) (dec iteration))))
(defn factorial
[x]
(calcualteFactorial 1 x))
Coraz bardziej mieszasz mi w głowie…
Ok, ok, już tłumaczę.
Clojure wspiera tail-call optimization – jednakże wymaga on użycia słówka recur.
A dla czego nie optymalizuje wszystkich tail recursions?
Szczerze? Nie wiem…
Wiem za to, że recur nie skompiluje się, jeżeli nie będzie w pozycji tail call.
Czyli kompilator Clojure coś sprawdza pod tym względem – ale nie jest w stanie sam decydować o optymalizacji.
Optymalizacja
Hmm, a jak działa sama optymalizacja?
Pomysł jest bardzo prosty. Skoro wykorzystujemy zawsze te same argumenty to zamiast wrzucać je na stos – możemy je nadpisywać tuż przed wywołaniem rekurencyjnym, a samo wywołanie zamienić na skok do początku funkcji (np. jmp, goto).
Spójrzmy na jakiś przykład. Tutaj nasza oryginalna funkcja z Clojure zdekompilowana do Javy:
Javy ja to tutaj nie widzę za bardzo, raczej jakieś komentarze przypominające assemblera…
Dokładnie! Otóż dekompilator nie poradził sobie z naszą funkcją i wypluł byte code dla JVM (do którego kompiluje się zarówno Java jak i Clojure).
To jakiś lipny dekompilator chyba użyłeś… Takiej prostej funkcji nie dał rady przeczytać?
Nieee, to nie wina dekompilatora. Tylko Javy!
Javy?
Yup, no bo jak przestawić skok w Javie? Nie da się!
Kolejna funkcjonalność (po wielodziedziczeniu) której nie dano programistom Javy wykorzystać – goto.
Nie, nie, nie! No goto to już chyba nie będziesz bronić? Kto korzysta jeszcze z goto?
Bronić goto nie będę – praktycznie wszystko co można zrobić z goto da się zastąpić innymi mechanizmami. Ale… w C# goto jest i czasami nawet może się przydać.
Nasza funkcja w wersji C#:
var x = 4;
var n = 1;
Start:
if (x == 1)
{
goto End;
}
n = n * x;
x = x - 1;
goto Start;
End:
Console.WriteLine(n);
Ok, teraz widzę. Ciekawy pomysł. To jakie języki wspierają taką optymalizację?
Wcale nie tak dużo:
Common Lisp
Clojure (recur)
JavaScript (w wersji 6.0)
Lua
Elixir
Perl
i kilka innych.
To poza Js żaden z popularnych języków nie wspiera tego?
Jak widać nie…
A dlaczego?
Dunno…
Python mógł mieć taką optymalizację, ale twórca stwierdził, że powoduje to zmianę stack trace’u przez co debugowanie jest trudniejsze – polecam lekturę.
Zdaje się, że F# wspiera tail recursion optimization, zresztą dzieje się to na poziomie CLR. Ponoć przy niektórych ustawieniach kompilacji ten mechanizm działa i w C#, ale nie w trybie debug, właśnie ze względu na łatwość debugowania.
CLR jak najbardziej wspiera tail recursion (wielodziedziczenie również).
F# generuje odpowiednie opcode’y (w określonych warunkach) jednakże, sam C# już nie.
Bardzo dobry post na stacku ktoś podlinkował: http://stackoverflow.com/a/491463/4136539
Zdaje się, że F# wspiera tail recursion optimization, zresztą dzieje się to na poziomie CLR. Ponoć przy niektórych ustawieniach kompilacji ten mechanizm działa i w C#, ale nie w trybie debug, właśnie ze względu na łatwość debugowania.
CLR jak najbardziej wspiera tail recursion (wielodziedziczenie również).
F# generuje odpowiednie opcode’y (w określonych warunkach) jednakże, sam C# już nie.
Bardzo dobry post na stacku ktoś podlinkował: http://stackoverflow.com/a/491463/4136539