Ruby effectue-t-il une optimisation des appels de queue?

Les langages fonctionnels conduisent à l'utilisation de la récursivité pour résoudre de nombreux problèmes, et donc beaucoup d'entre eux effectuent une optimisation des appels de queue (TCO). TCO provoque les appels à une fonction à partir d'une autre fonction (ou elle-même, auquel cas cette fonctionnalité est également connue sous le nom d'élimination de la récurrence de la queue, qui est un sous-ensemble de TCO), comme dernière étape de cette fonction, pour ne pas avoir besoin d'un nouveau cadre de pile, ce qui réduit la surcharge et l'utilisation de la mémoire.

Ruby a évidemment "emprunté" un certain nombre de concepts à des langages fonctionnels (lambdas, fonctions comme map, etc.), ce qui me rend curieux: Ruby effectue-t-il une optimisation des appels de queue?

Non, Ruby n'effectue pas le TCO. Cependant, il n'effectue pas non plus le TCO.

La spécification du langage Ruby ne dit rien sur le TCO. Cela ne dit pas que vous devez le faire, mais cela ne dit pas non plus que vous ne pouvez pas le faire. Vous ne pouvez pas vous y fier .

Ceci est différent de Scheme, où la spécification de langage exige que toutes les implémentations doivent effectuer le TCO. Mais c'est également différent de Python, où Guido van Rossum a indiqué très clairement à plusieurs reprises (la dernière fois il y a quelques jours à peine) que les implémentations Python ne devraient pas effectuer le TCO.

Yukihiro Matsumoto est sympathique à TCO, il ne veut tout simplement pas forcer toutes les implémentations à le supporter. Malheureusement, cela signifie que vous ne pouvez pas compter sur le TCO, ou si vous le faites, votre code ne sera plus portable vers d'autres implémentations Ruby.

Ainsi, certaines implémentations Ruby effectuent le TCO, mais la plupart ne le font pas. YARV, par exemple, prend en charge le TCO, même si (pour le moment) vous devez explicitement décommenter une ligne dans le code source et recompiler la VM, pour activer le TCO - dans les versions futures, il sera activé par défaut, après que l'implémentation prouve stable. La machine virtuelle Parrot prend en charge le TCO de manière native, donc Cardinal pourrait également le supporter assez facilement. Le CLR prend en charge le TCO, ce qui signifie qu'IronRuby et Ruby.NET pourraient probablement le faire. Rubinius pourrait probablement le faire aussi.

Mais JRuby et XRuby ne prennent pas en charge 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 avoir une implémentation rapide et une intégration rapide et transparente avec Java, vous devez être compatible avec la pile 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 passage de continuation explicite, mais vous n'utilisez plus la pile JVM, ce qui signifie que chaque fois que vous voulez appeler Java ou appeler de Java vers Ruby, vous devez effectuer une sorte de conversion, qui est lente. Ainsi, XRuby et JRuby ont choisi d'aller avec la vitesse et l'intégration Java sur le TCO et les continuations (qui ont fondamentalement le même problème).

Cela s'applique à toutes les implémentations de Ruby qui souhaitent s'intégrer étroitement à 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.

Mise à jour: Voici une belle explication du TCO dans Ruby: http://nithinbekal.com/posts/ruby-tco/

Mise à jour: vous voudrez peut-être également consulter le gem tco_method : http://blog.tdg5.com/introducing-the-tco_method-gem/

Dans Ruby MRI (1.9, 2.0 et 2.1), vous pouvez activer le TCO avec:

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

Il a été proposé d'activer le TCO par défaut dans Ruby 2.0. Il explique également certains problèmes qui viennent avec cela: Optimisation des appels de queue: activer par défaut ?.

Court extrait du lien:

Généralement, l'optimisation de la récursivité de la queue comprend une autre technique d'optimisation - la traduction «appel» à «sauter». A mon avis, il est difficile d'appliquer cette optimisation car reconnaître la "récursivité" 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 de fin".

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

Si vous souhaitez utiliser l'optimisation des appels de fin sur la méthode fact (), vous devez changer la méthode fact () comme suit (style de passage de continuation).

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

Il peut avoir, mais n'est pas garanti:

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

Le TCO peut également être compilé en ajustant quelques variables dans vm_opts.h avant la compilation: 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

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

Je n'ai pas pu obtenir la réponse d'Ernest pour travailler sur l'IRM, mais c'est faisable. J'ai trouvé cet exemple 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 «pile trop profonde».

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