Ruby répète-t-il queue appeler optimisation ?

Question

Les langages fonctionnels conduire à l'utilisation de la récursivité à résoudre beaucoup de problèmes, et, par conséquent, beaucoup d'entre eux d'effectuer la Queue d'Appel d'Optimisation (TCO). TCO causes les appels à une fonction dans une autre fonction (ou lui-même, auquel cas cette fonctionnalité est également connu comme la Queue de la Récursivité à l'Élimination, qui est un sous-ensemble de la norme TCO), la dernière étape de cette fonction, pour ne pas avoir besoin d'un nouveau bloc de pile, ce qui diminue les frais généraux et l'utilisation de la mémoire.

Ruby évidemment a "emprunté" un certain nombre de concepts de langages fonctionnels (lambdas, comme les fonctions de la carte et ainsi de suite, etc.), ce qui me rend curieux: Ruby effectuer queue appel d'optimisation?

Answer 1

Non, Ruby n'effectue pas de coût total de possession. Cependant, c'est aussi ne pas effectuer le coût total de possession.

Le Langage Ruby Spécification ne dit rien sur le coût total de possession. Cela ne veut pas dire que vous avez à faire, mais il ne dis pas que vous ne pouvez pas le faire. Vous ne pouvez pas simplement compter sur elle.

C'est la différence de Régime, où le Langage de Spécification exige que toutes les Implémentations doivent effectuer le coût total de possession. Mais c'est aussi, contrairement à Python, où Guido van Rossum a fait savoir très clairement à plusieurs reprises (la dernière fois, juste une couple de jours il ya) que les Implémentations de Python ne devrait pas effectuer le coût total de possession.

Yukihiro Matsumoto est de la sympathie pour le coût total de possession, il ne veut tout simplement pas la force de toutes les Implémentations de le soutenir. Malheureusement, cela signifie que vous ne pouvez pas compter sur le coût total de possession, ou si vous le faites, votre code ne sera plus portable à d'autres Ruby Implémentations.

Ainsi, certains de Ruby Implémentations effectuer le coût total de possession, mais la plupart ne le font pas. YARV, par exemple, prend en charge le coût total de possession bien que (pour le moment), vous devez explicitement dé-commenter une ligne dans le code source et recompiler le VM, pour activer TCO – dans de futures versions, il va être activée par défaut, après la mise en œuvre s'avère stable. La Machine Virtuelle Parrot prend en charge coût total de possession en natif, donc le Cardinal pourrait assez facilement soutenir, trop. Le CLR a un certain appui pour le coût total de possession, ce qui signifie que IronRuby et Ruby.NET pourrait probablement le faire. Rubinius pourrait probablement le faire, trop.

Mais JRuby et XRuby ne supportent pas le coût total de possession, et ils ne le feront probablement pas, à moins que la JVM elle-même gains de soutien pour le coût total de possession. Le problème, c'est ceci: si vous voulez avoir une mise en œuvre rapide et rapide et une intégration transparente avec Java, alors vous devriez être pile-compatible avec Java et utiliser la JVM pile autant que possible. Vous pouvez très facilement mettre en œuvre coût total de possession avec des trampolines ou explicite continuation passing style, mais alors vous n'êtes plus à l'aide de la JVM de la pile, ce qui signifie que chaque fois que vous voulez l'appeler en Java ou en appel à partir de Java en Ruby, vous devez effectuer un certain type de conversion, qui est lent. Donc, XRuby et JRuby choisi d'y aller avec de la vitesse et de l'intégration Java plus de TCO et les continuations (qui, en gros, ont le même problème).

Cela s'applique à toutes les implémentations de Ruby qui veulent intégrer étroitement avec certains d'accueil de la plateforme qui ne supporte pas le coût total de possession en mode natif. Par exemple, je suppose que MacRuby va avoir le même problème.

Answer 2

En Ruby IRM (1.9, 2.0 et 2.1), vous pouvez vous tourner coût total de possession sur avec:

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

Il y avait une proposition à son tour TCO sur par défaut dans Ruby 2.0. Il explique aussi en partie les problèmes qui en découlent: la Queue d'appel d'optimisation: activer par défaut?.

Court extrait du lien:

Généralement, la queue-de récursivité optimisation comprend une autre technique d'optimisation - "appel" à "sauter" de la traduction. À mon avis, il est difficile d'appliquer cette optimisation parce que reconnaissant "récursivité" est difficile dans le Rubis du monde.

L'exemple suivant. fait() invocation de méthode dans le "else" clause n'est pas une "queue l'appel".

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

Si vous souhaitez utiliser la queue-appel d'optimisation sur les faits() la méthode, vous avez besoin pour changer de fait() la méthode comme suit (continuation passing style).

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

Answer 3

Il peut avoir mais n'est pas garanti pour:

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

Answer 4

Le coût total de possession peut également être compilé en modifiant 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
 

Answer 5

Cela s'appuie sur les réponses de Jörg et 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é cet exemple qui fonctionne pour les 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