Ruby: callcc
June 3rd, 2009 — 04:04 pmcallcc, es la abreviatura de call-with-current-continuation, algo así como un goto con esteroides.
En el rdoc nos encontramos con la siguiente definición:
callcc {|cont| block } => objGenerates a Continuation object, which it passes to the associated block. Performing a cont.call will cause the callcc to return (as will falling through the end of the block). The value returned by the callcc is the value of the block, or the value passed to cont.call. See class Continuation for more details. Also see Kernel::throw for an alternative mechanism for unwinding a call stack.
Un tanto críptico, ¿No?. Basicamente, callcc almacena la dirección de memoria y el contexto (en un objeto Continuation) de donde se le llamo. Sigue siendo raro,¿No?
Mejor un ejemplo. Sea el siguiente metodo:
counter = 0 def foo exit if callcc{|$cont| } == 3 puts "hello world" end foo $cont.call(counter += 1)
(Si ya se que las variables globales son malignas : ( )
Ejecutando el ejemplo:
madtrick::madtrick::$ruby test3.rb
hello world
hello world
hello worldComo se puede apreciar, se imprimen tres “hello world” con sólo una llamada al método foo.
¿Qué podemos extraer del ejemplo anterior?
- Cada llamada a la continuación ($cont) nos vuelve a llevar a linea donde se definió.
- Si en la llamada a la continuación pasamos algun parámetro, este es devuelto por callcc
Tambien podríamos utilizar los ejemplos del post anterior (Tail Call Optimization) para explicar el funcionamiento de callcc:
Calculo del factorial de un número:
class TCOTest # tail-recursive factorial def fact( n, acc = 1 ) if n < 2 then acc else fact( n-1, n*acc ) end end def fact_cc( n, acc = 1 ) cont = callcc{|cont| cont} if n < 2 then acc else n, acc = n-1, n*acc cont.call cont end end # length of factorial def fact_size( n ) fact( n ).size rescue $! end # length of factorial def fact_size_cc( n ) fact_cc( n ).size rescue $! end end
Si lo probamos en el irb vemos que fact_size_cc no da ningún tipo de problema mientras que la función fact_size (sí, por carecer Ruby de TCO) ya que nos quedamos sin espacio en la stack.
... irb(main):009:0> t.fact_size 10000 => #<SystemStackError: stack level too deep> irb(main):010:0> t.fact_size_cc 10000 => 14808
El otro ejemplo del post anterior, la función de Fibonacci:
En el ejemplo anterior, utilizábamos la palabra reservada redo junto con un método definido ad-hoc para poder realizar el cálculo:
define_method(:acc) do |i, n, result| if i == -1 result else i, n, result = i - 1, n + result, n redo end def fib_redo(i) acc i,1,0 end
Pero tambien se podria haber hecho de esta otra forma:
def fib_call_cc(i, n = 1, result = 0) cont = callcc{|cont| cont} if i == -1 result else i, n, result = i - 1, n + result, n cont.call cont end end
En el ejemplo anterior se puede apreciar como el contexto se mantiene. En este caso para los valores i,n y result.
Si ejecutamos un simple benchmark (para n en 50000) para comparar redo vs callcc, obtenemos los siguiente:
madtrick::madtrick::$ruby test.rb Time for fib_redo: 0.390000 0.010000 0.400000 ( 0.403986) Time for fib_call_cc: 0.500000 0.000000 0.500000 ( 0.519504)
redo ( 0.403986) es un poco más rápido que callcc ( 0.519504). Echándole un vistazo rapido al codigo de la máquina virtual de Ruby se entiende rápidamente el porque. redo esta implentado utilizando goto’s mientras que callcc es una llamada a una función que se encarga de guardar toda la información necesaria en un objeto Continuation, por lo que necesita más tiempo.
Para mas información sobre callcc, su funcionamiento y los continuations:
- Continuations
- Callcc
- Setjmp/longjmp, funciones en C con las que se puede implementar un comportamiento similar
