Est-ce que Ruby effectue l'optimisation de l'appel de la queue?

Question

Les langages fonctionnels conduisent à l'utilisation de la récursivité pour résoudre beaucoup de problèmes, et donc beaucoup d'entre eux effectuent l'optimisation de l'appel de queue (TCO). TCO provoque des appels à une fonction à partir d'une autre fonction (ou elle-même, auquel cas cette fonctionnalité est également connue sous le nom Tail Recursion Elimination, qui est un sous-ensemble de TCO), comme dernière étape de cette fonction, ce qui réduit les frais généraux et l'utilisation de la mémoire. Ruby a évidemment "emprunté" un certain nombre de concepts à partir de langages fonctionnels (lambdas, fonctions comme map et ainsi de suite, etc.), ce qui me rend curieux: Ruby effectue-t-il l'optimisation des appels?

Answer 1

Non, Ruby ne fonctionne pas TCO. Cependant, il ne fait pas pas effectuer TCO.

La spécification de langage Ruby ne dit rien sur le coût total de possession. Il ne dit pas que vous devez le faire, mais il ne vous dit pas non plus ne peut pas le faire. Vous ne pouvez pas compter dessus.

Ce schéma est différent, où la spécification du langage exige que tous Implémentations doit effectuer TCO. Mais il est également différent de Python, où Guido van Rossum a fait savoir très clairement à plusieurs reprises (la dernière fois il y a quelques jours) que Python Implémentations ne devrait pas effectuer TCO.

Yukihiro Matsumoto est sympathique à TCO, il ne veut juste pas forcer tous les Implémentations pour le soutenir. Malheureusement, cela signifie que vous ne pouvez pas compter sur TCO, ou si vous le faites, votre code ne sera plus portable pour d'autres implémentations Ruby. Par conséquent, certaines implémentations Ruby exécutent le coût total de possession, mais la plupart ne le font pas. YARV, par exemple, supporte TCO, bien que (pour le moment) vous devez explicitement décommenter une ligne dans le code source et recompiler la VM, pour activer TCO - dans les futures versions, elle sera activée par défaut, après que l'implémentation prouve stable. La machine virtuelle Parrot prend en charge le TCO en mode natif, donc Cardinal pourrait très bien le supporter aussi. Le CLR a un certain support pour TCO, ce qui signifie que IronRuby et Ruby.NET pourraient probablement le faire. Rubinius pourrait probablement le faire aussi.

Mais JRuby et XRuby ne supportent pas le TCO, et ils ne le feront probablement pas, à moins que la JVM elle-même ne prenne en charge le TCO. Le problème est le suivant: si vous voulez une implémentation rapide et une intégration rapide et transparente avec Java, vous devriez être compatible avec Java et utiliser autant que possible la pile de la JVM. Vous pouvez facilement implémenter le TCO avec des trampolines ou un style de continuation-passing explicite, mais vous n'utilisez plus la pile JVM, ce qui signifie que chaque fois que vous voulez appeler Java ou appeler Java depuis Ruby, vous devez effectuer une sorte de conversion, ce qui est lent. Ainsi, XRuby et JRuby ont choisi d'aller avec la vitesse et l'intégration Java sur TCO et les continuations (qui ont essentiellement le même problème).

Cela s'applique à toutes les implémentations de Ruby qui souhaitent s'intégrer étroitement avec une plate-forme hôte qui ne prend pas en charge le TCO de manière native. Par exemple, je suppose que MacRuby va avoir le même problème.

Answer 2

Il peut avoir mais n'est pas garanti:

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

Answer 3

Mise à jour: est ici belle explication du coût total de possession en Ruby: http://nithinbekal.com/posts/ruby-tco/

Mise à jour: Vous pouvez également vérifier le tco_method bijou: http://blog.tdg5.com/introducing-the-tco_method-gem/

En Ruby IRM (1.9, 2.0 et 2.1) vous pouvez activer TCO avec:

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

Il y avait une proposition pour tourner TCO activé par défaut dans Ruby 2.0. Il explique également quelques problèmes qui viennent avec qui: Tail call optimization: enable by default?.

extrait court du lien:

En général, l'optimisation de la queue-récursion comprend une autre technique d'optimisation - traduction « appel » à « sauter ». À mon avis, il est difficile d'appliquer cette optimisation, car reconnaître "récursion" est difficile dans le monde de Ruby.

Exemple suivant. L'appel de la méthode fact() dans la clause "else" n'est pas un "appel ".

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

Si vous voulez utiliser l'optimisation d'appel de la queue sur la méthode fait(), vous avez besoin changer de méthode fait() comme suit (style passage de continuation).

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

Answer 4

TCO peuvent également être compilés par un peaufinage des variables couple dans vm_opts.h avant de compiler: 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

Cela s'ajoute Jörg et de réponses d'Ernest. Fondamentalement, cela dépend de la mise en œuvre.

Je ne pouvais pas obtenir la réponse d'Ernest pour travailler sur l'IRM, mais c'est faisable. J'ai trouvé this example qui fonctionne pour l'IRM 1.9 à 2.1. Cela devrait imprimer un très grand nombre. Si vous ne définissez pas l'option TCO sur true, vous devriez obtenir l'erreur "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