Zacznijmy od tego czym jest “Tail call”.
Tail call jest to wywołanie funkcji w ostatniej linijce danej procedury.
Np.:
var x = 7; var y = 2; return Sum(x, y); //Tail call
A jeżeli funkcja którą wywołujemy to ta sama funkcja w której jesteśmy – to mamy wtedy tail recursion.
Np.:
int Sum(int accumulator, int[] array) { if (array.Length < 1) return accumulator; return Sum(accumulator + array[0], array.Skip(1)); //Tail recursion }
Rekurencja
A po co mi wiedzieć takie rzeczy?
Bo warto wiedzieć, czy język w którym piszemy wspiera optymalizację owych tail recursions.
Ale to chyba dotyczy tylko rekurencji? Ja praktycznie nigdy nie korzystam z rekurencji…
Och, ciekawe… A czemuż to?
No bo jest mało czytelna i może wywalić stos.
Hmmm, kwestia czytelności jest raczej sporna – są algorytmy/języki które o wiele naturalniej czyta się przy wykorzystaniu rekurencji…
A co stosu – to masz rację. Źle napisana rekurencja może spowodować przeładowanie stosu.
Nie tylko źle napisana – nawet dobrze napisana może! Wystarczy podać odpowiednio duże dane wejściowe przecież!
No właśnie – tutaj wracamy do naszych rekurencji ogonowych.
Otóż są języki które optymalizują takie wywołania i gwarantują niewypierdzielalność stosu.
To tak się da?
No pewnie! I to od dawien dawna możliwe.
Weźmy sobie na warsztat oklepaną wszędzie funkcję – liczenie silni (występującej dzisiaj w barwach Clojure)
(defn factorial [x] (loop[sum 1 iteration x] (if (= iteration 1) sum (recur (* iteration sum) (dec iteration)))))
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:
public final class core$factorial extends AFunction { /* Error */ public static Object invokeStatic(Object x) { // Byte code: // 0: aload_0 // 1: aconst_null // 2: astore_0 // 3: astore_1 // 4: lconst_1 // 5: invokestatic 17 clojure/lang/RT:box (J)Ljava/lang/Number; // 8: astore_2 // 9: aload_1 // 10: lconst_1 // 11: invokestatic 23 clojure/lang/Util:equiv (Ljava/lang/Object;J)Z // 14: ifeq +10 -> 24 // 17: aload_2 // 18: aconst_null // 19: astore_2 // 20: goto +22 -> 42 // 23: pop // 24: aload_1 // 25: invokestatic 29 clojure/lang/Numbers:dec (Ljava/lang/Object;)Ljava/lang/Number; // 28: aload_2 // 29: aconst_null // 30: astore_2 // 31: aload_1 // 32: aconst_null // 33: astore_1 // 34: invokestatic 33 clojure/lang/Numbers:multiply (Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Number; // 37: astore_2 // 38: astore_1 // 39: goto -30 -> 9 // 42: areturn } }
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?
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