Tail Recursion y Continuations

Pues en el post anterior mostré como se puede traducir un código recursivo a uno iterativo por medio de optimización de recursión de Cola. Ésta técnica es muy importante en lenguajes funcionales ya que este depende enormemente de la recursión.

En F# es importante tener en cuenta cuando se realiza alguna función recursiva, que efectivamente la última llamada sea a la función. Sin embargo en algunos casos no es tan fácil realizar ésto. Por ejemplo veamos el caso "naive" de Fibonacci sin recursión de cola.

   14 let rec fibNonTR n = 

   15     match n with

   16     | 0 -> 1

   17     | 1 -> 1

   18     | n -> fibNonTR (n - 1) + fibNonTR (n - 2)

Como puede uno tener una definición que haga una sola llamada a la función de Fibonacci si esta es en si misma contiene 2 llamadas? La opción es usar un "acumulador" que tiene la particularidad de ir armando una función (Continuation) que calcule Fibonacci:

    3 let fibTR n = 

    4     let rec fibCont n cont =

    5         match n with

    6         | 0 -> cont 1

    7         | 1 -> cont 1

    8         | n -> fibCont (n-1) (fun n1 ->

    9                fibCont (n-2) (fun n2 ->

   10                (cont (n1 + n2) )))

   11     fibCont n (fun x -> x)

Veamos los casos triviales:

   36 fibCont 0 x->x = (fun x -> x) 1

   37 1

   38 

   39 fibCont 1 x->x = (fun x -> x) 1

   40 1

Ahora entendamos como se arma la función (parece magia :P)

El caso de fib 2:

   42 fibCont 2 x->x =

   43 fibCont 1 (fun n1 -> fibCont 0 (fun n2 -> (fun x -> x) (n1 + n2) ))

   44 fibCont 1 (fun n1 -> fibCont 0 (fun n2 -> (n1 + n2)))

   45 fibCont 1 (fun n1 -> (n1 + 1)))

   46 (1 + 1)

   47 2

fib 3:

   49 fibCont 3 x->x =

   50 fibCont 2 (fun n1 -> fibCont 1 (fun n2 -> (fun x -> x) (n1 + n2)))

   51 fibCont 2 (fun n1 -> fibCont 1 (fun n2 -> (n1 + n2)))

   52 fibCont 2 (fun n1 -> (n1 + 1))

   53 fibCont 1 (fun n1' -> fibCont 0 (fun n2' -> (fun n1 -> n1 + 1) (n1' + n2')))

   54 fibCont 1 (fun n1' -> fibCont 0 (fun n2' -> (n1' + n2') + 1))

   55 fibCont 1 (fun n1' -> (n1' + 1 ) + 1)

   56 ((1 + 1 ) + 1)

   57 3

Cuestión de Rendimiento

Pese a que se elimina la utilización de la pila... ¿Es mas eficiente?
Pues hagamos una prueba:

   20 let benchmark (f:'a lazy) =

   21     let before = System.DateTime.Now

   22     f.Force() |> ignore

   23     printfn "%A"  (System.DateTime.Now - before)

   24 

   25 let list = [0..40]

   26 

   27 benchmark (lazy List.map fibTR list)

   28 

   29 benchmark (lazy List.map fibNonTR list)

   30 

Ésto da como resultado:

//Tail Recursive
00:02:58.6250000
//Non Tail Recursive
00:00:19.0312500

Porque el que tiene la "optimización" es mas "lento"?

La continuación que estamos pasando es realmente una referencia a una función. Las funciones en F# son alojadas en Heap. Ésto quiere decir que se hacen continuas llamadas a sistema para alojar en memoria dichas estructuras. Alojar en Heap es mucho mas costoso que usar la pila.