Tag: callcc


Ruby: callcc

callcc, 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 } => obj

Generates 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 world

Como 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:

Comment » | programacion, ruby