¿Ruby realiza la optimización Tail Call?

92

Los lenguajes funcionales llevan al uso de la recursividad para resolver muchos problemas y, por lo tanto, muchos de ellos realizan Tail Call Optimization (TCO). El TCO hace que las llamadas a una función desde otra función (o ella misma, en cuyo caso esta característica también se conoce como Eliminación de recursividad de cola, que es un subconjunto de TCO), como último paso de esa función, no necesita un nuevo marco de pila, lo que reduce la sobrecarga y el uso de memoria.

Obviamente, Ruby ha "tomado prestados" una serie de conceptos de lenguajes funcionales (lambdas, funciones como mapa, etc.), lo que me da curiosidad: ¿Ruby realiza optimización de llamadas finales?

Charlie Flores
fuente

Respuestas:

127

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

La especificación del lenguaje Ruby no dice nada sobre el TCO. No dice que tengas que hacerlo, pero tampoco dice que no puedas hacerlo. Simplemente no puedes confiar en eso.

Esto es diferente a Scheme, donde la especificación de lenguaje requiere que todas las implementaciones deben realizar TCO. Pero también es diferente de Python, donde Guido van Rossum ha dejado muy claro en múltiples ocasiones (la última vez hace 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 a que lo respalden. Desafortunadamente, esto significa que no puede confiar en el TCO o, si lo hace, su código ya no será portátil a otras implementaciones de Ruby.

Por lo tanto, algunas implementaciones de Ruby realizan TCO, pero la mayoría no. YARV, por ejemplo, es compatible con TCO, aunque (por el momento) debe descomentar explícitamente una línea en el código fuente y volver a compilar la VM para activar el TCO; en futuras versiones estará activado de forma predeterminada, una vez que la implementación lo demuestre. estable. Parrot Virtual Machine admite TCO de forma nativa, por lo que Cardinal también podría admitirlo con bastante facilidad. El CLR tiene cierto soporte para TCO, lo que significa que IronRuby y Ruby.NET probablemente podrían hacerlo. Probablemente Rubinius también podría hacerlo.

Pero JRuby y XRuby no admiten TCO, y probablemente no lo harán, a menos que la propia JVM obtenga soporte para TCO. El problema es este: si desea tener una implementación rápida y una integración rápida y sin problemas con Java, entonces debe ser compatible con Java y usar la pila de JVM tanto como sea posible. Puede implementar TCO con bastante facilidad con trampolines o un estilo de paso de continuación explícito, pero luego 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 optaron por la velocidad y la integración de Java sobre el TCO y las continuaciones (que básicamente tienen el mismo problema).

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

Jörg W Mittag
fuente
2
Podría estar equivocado (por favor, infórmeme si es así), pero dudo que el TCO tenga algún sentido en los verdaderos lenguajes OO, ya que la llamada de cola debe poder reutilizar el marco de pila del llamador. Dado que con el enlace tardío, no se sabe en tiempo de compilación qué método será invocado por el envío de un mensaje, parece difícil asegurar que (tal vez con un JIT de retroalimentación de tipo, o forzando a todos los implementadores de un mensaje a usar marcos de pila del mismo tamaño, o restringiendo el TCO a los autoenvíos del mismo mensaje ...).
Damien Pollet
2
Esa es una gran respuesta. Esa información no se encuentra fácilmente a través de Google. Es interesante que yarv lo apoye.
Charlie Flowers
15
Damien, resulta que el TCO es realmente necesario para los verdaderos idiomas OO: consulte projectfortress.sun.com/Projects/Community/blog/… . No se preocupe demasiado por el tema del marco de la pila: es perfectamente posible diseñar marcos de la pila con sensatez para que funcionen bien con el TCO.
Tony Garnock-Jones
2
tonyg salvó de la extinción la publicación referenciada de GLS, reflejándola aquí: eighty-twenty.org/index.cgi/tech/oo-tail-calls-20111001.html
Frank Shearar
Estoy haciendo una tarea que requiere que desmonte un conjunto de matrices anidadas de profundidad arbitraria. La forma obvia de hacerlo es recursivamente, y casos de uso similares en línea (que puedo encontrar) usan la recursividad. Es muy poco probable que mi problema particular explote, incluso sin TCO, pero el hecho de que no pueda escribir una solución completamente general sin cambiar a la iteración me molesta.
Isaac Rabinovitch
42

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

Actualización: es posible que también desee consultar la gema tco_method : http://blog.tdg5.com/introducing-the-tco_method-gem/

En Ruby MRI (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 el TCO de forma predeterminada en Ruby 2.0. También explica algunos problemas que vienen con eso: Optimización de la llamada de cola: ¿habilitar por defecto ?.

Extracto breve del enlace:

Generalmente, la optimización de recursividad de cola incluye otra técnica de optimización: "llamar" a "saltar" la traducción. En mi opinión, es difícil aplicar esta optimización porque reconocer la "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 final".

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

Si desea utilizar la optimización de llamada de cola en el método fact (), debe cambiar el método fact () de la siguiente manera (estilo de paso de continuación).

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

Puede tener, pero no se garantiza que lo haga:

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

Steve Jessop
fuente
El enlace está muerto a partir de ahora.
karatedog
@karatedog: gracias, actualizado. Aunque para ser honesto, la referencia probablemente esté desactualizada, ya que el error tiene ahora 5 años y ha habido actividad sobre el mismo tema desde entonces.
Steve Jessop
Sí :-) Acabo de leer sobre el tema y vi que en Ruby 2.0 se puede habilitar desde el código fuente (no más modificación y recompilación de la fuente C).
karatedog
2

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

No pude conseguir que la respuesta de Ernest funcionara en la resonancia magnética, pero es factible. Encontré este ejemplo que funciona para MRI 1.9 a 2.1. Esto debería imprimir un número muy grande. Si no establece 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
Kelvin
fuente