martes, marzo 11, 2008

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.

1 comentario:

jpemberthy dijo...

Mi rey lo primero te quedo bien la nueva imagen del blog, por el otro espero que te haya ido bien en el viaje, me salte todo el código en f# (>_<) y al final capte la idea rofl XD en fin ... por otro lado que hpta man tan cacorro sale en la imagen que tenes ahi de vs ...