¿Ruby realiza optimización de llamadas de cola?

Question

Los lenguajes funcionales conducen al uso de la recursión para resolver muchos problemas, y por lo tanto, muchos de ellos realizan la Optimización de llamadas en cola (TCO). TCO provoca llamadas a una función desde otra función (o ella misma, en cuyo caso esta función también se conoce como eliminación de recursión de cola, que es un subconjunto de TCO), como el último paso de esa función, para no necesitar un nuevo marco de pila, que disminuye el uso de la sobrecarga y la memoria.

Ruby obviamente ha "tomado prestados" varios conceptos de los lenguajes funcionales (lambdas, funciones como mapas, etc.), lo que me da curiosidad: ¿Ruby realiza la optimización de la cola de llamada?

Answer 1

No, Ruby no realiza TCO. Sin embargo, tampoco no realiza TCO.

La especificación de lenguaje Ruby no dice nada sobre TCO. No dice que tiene que hacerlo, pero tampoco dice que no puede hacerlo. Simplemente no puede confiar en él.

Esto es a diferencia esquema, donde el Lenguaje de Especificación de requiere que todos los Implementaciones debe realizar el TCO. Pero también es diferente a Python, donde Guido van Rossum dejó muy claro en múltiples ocasiones (la última vez hace apenas un par de días) que las implementaciones de Python no deberían realizar TCO.

Yukihiro Matsumoto simpatiza con TCO, simplemente no quiere forzar todos Implementaciones para apoyarlo. Desafortunadamente, esto significa que no puede confiar en TCO, o si lo hace, su código ya no será transferible a otras Implementaciones de Ruby.

Por lo tanto, algunas implementaciones de Ruby realizan TCO, pero la mayoría no. YARV, por ejemplo, admite TCO, aunque (por el momento) tiene que descomentar explícitamente una línea en el código fuente y recompilar la máquina virtual, para activar el TCO; en versiones futuras estará activado por defecto, después de que la implementación pruebe estable. La máquina virtual Parrot admite TCO de forma nativa, por lo tanto, Cardinal también podría soportarla fácilmente. El CLR tiene algo de apoyo para TCO, lo que significa que IronRuby y Ruby.NET podrían hacerlo. Rubinius probablemente podría hacerlo también.

Pero JRuby y XRuby no son compatibles con TCO, y probablemente no lo hagan, a menos que la JVM en sí obtenga soporte para TCO. El problema es el siguiente: si desea una implementación rápida y una integración rápida y sin problemas con Java, entonces debe ser compatible con la pila con Java y usar la pila de la JVM tanto como sea posible. Puede implementar fácilmente TCO con trampolines o estilo de continuación de paso explícito, pero ya no está utilizando la pila JVM, lo que significa que cada vez que desea llamar a Java o llamar desde Java a Ruby, debe realizar algún tipo de conversión, que es lenta Entonces, XRuby y JRuby eligieron ir con velocidad e integración de Java sobre TCO y continuaciones (que básicamente tienen el mismo problema).

Esto se aplica a todas las implementaciones de Ruby que desean integrarse estrechamente con alguna plataforma host que no admita TCO de forma nativa. Por ejemplo, supongo que MacRuby tendrá el mismo problema.

Answer 2

Puede tener pero no se garantiza que:

https://bugs.ruby-lang.org/issues/1256

Answer 3

Actualización: Aquí hay buena explicación de TCO en Ruby: http://nithinbekal.com/posts/ruby-tco/

Actualización: Es posible que desee también echa un vistazo a la tco_method joya: http://blog.tdg5.com/introducing-the-tco_method-gem/

En Rubí resonancia magnética (1.9, 2.0 y 2.1) puede activar el TCO con:

RubyVM::InstructionSequence.compile_option = { 
    :tailcall_optimization => true, 
    :trace_instruction => false 
} 

Hubo una propuesta para activar TCO activado por defecto en Ruby 2.0. También explica algunos problemas que vienen con eso: Tail call optimization: enable by default?.

fragmento corto desde el enlace:

En general, la optimización de la cola-recursividad incluye otra técnica de optimización - "llamada" a "saltar" traducción. En mi opinión, es difícil aplicar esta optimización porque el reconocimiento de "recursividad" es difícil en el mundo de Ruby.

Siguiente ejemplo. La invocación del método fact() en la cláusula "else" no es una "llamada de cola ".

def fact(n) 
    if n < 2 
    1 
else 
    n * fact(n-1) 
end 
end 

Si desea utilizar la optimización de llamada en hechos método(), necesita para cambiar el método de hecho() de la siguiente manera (estilo que pasa continuación).

def fact(n, r) 
    if n < 2 
    r 
    else 
    fact(n-1, n*r) 
    end 
end 

Answer 4

TCO también puede ser compilado por ajustar en un par de variables en vm_opts.h antes de compilar: https://github.com/ruby/ruby/blob/trunk/vm_opts.h#L21

// vm_opts.h 
#define OPT_TRACE_INSTRUCTION  0 // default 1 
#define OPT_TAILCALL_OPTIMIZATION 1 // default 0 

Answer 5

Esto se basa en Jörg de respuestas y de Ernest. Básicamente depende de la implementación.

No pude obtener la respuesta de Ernest para trabajar en MRI, pero es factible. Encontré this example que funciona para MRI 1.9 a 2.1. Esto debería imprimir un número muy grande. Si no configura la opción TCO en verdadero, debería aparecer el error "stack too deep".

source = <<-SOURCE 
def fact n, acc = 1 
    if n.zero? 
    acc 
    else 
    fact n - 1, acc * n 
    end 
end 

fact 10000 
SOURCE 

i_seq = RubyVM::InstructionSequence.new source, nil, nil, nil, 
    tailcall_optimization: true, trace_instruction: false 

#puts i_seq.disasm 

begin 
    value = i_seq.eval 

    p value 
rescue SystemStackError => e 
    p e 
end