Tail recursion optimizations

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ę.