¿Ruby realiza la optimización de llamadas de cola?

functional-programming tail-recursion

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 de 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

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

No pude obtener la respuesta de Ernest para trabajar en MRI, 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 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

Answer 2

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

La Especificación del lenguaje Ruby no dice nada sobre TCO. No dice que tiene que hacerlo, pero tampoco dice que no puede hacerlo. Usted simplemente no puede confiar en eso.

Esto es diferente de Scheme, donde la Especificación del lenguaje requiere que todas las implementaciones deben realizar 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 Python Implementations no debería realizar TCO.

Yukihiro Matsumoto simpatiza con TCO, simplemente no quiere obligar a todas las implementaciones a que lo respalden. 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 misma gane 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 quieran integrarse estrechamente con alguna plataforma de host que no admita TCO de forma nativa. Por ejemplo, supongo que MacRuby tendrá el mismo problema.

Answer 3

Puede tener pero no se garantiza que:

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

Answer 4

TCO también se puede compilar ajustando 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

Actualización: Aquí hay una buena explicación de 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 TCO por defecto en Ruby 2.0. También explica algunos problemas que vienen con eso: Optimización de llamada de cola: habilitar por defecto ?.

Breve extracto del enlace:

En general, la optimización de recursión de cola incluye otra técnica de optimización: la traducción de "llamada" a "salto". En mi opinión, es difícil aplicar esta optimización porque reconocer la "recursión" 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 la llamada final en el método fact (), debe cambiar el método fact () de la siguiente manera (estilo de continuación de paso).

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