93

関数型言語は、多くの問題を解決するために再帰を使用することにつながるため、それらの多くは末尾呼び出し最適化（TCO）を実行します。TCOは、その関数の最後のステップとして、別の関数（またはそれ自体。この場合、この機能はTCOのサブセットである末尾再帰除去とも呼ばれます）から関数を呼び出し、新しいスタックフレームを必要としません。これにより、オーバーヘッドとメモリ使用量が減少します。

Rubyは明らかに関数型言語（ラムダ、マップなどの関数など）から多くの概念を「借用」しており、興味をそそられます。Rubyは末尾呼び出しの最適化を実行しますか？

4

5 に答える 5

131

いいえ、RubyはTCOを実行しません。ただし、 TCOも実行しません。

Ruby言語仕様はTCOについて何も述べていません。それはあなたがそれをしなければならないとは言いませんが、あなたがそれをすることができないとも言いません。あなたはそれに頼ることができません。

これは、言語仕様ですべての実装がTCOを実行する必要があるSchemeとは異なります。しかし、Pythonの実装がTCOを実行するべきではないことを、Guido van Rossumが何度も（前回はほんの数日前に）非常に明確にしたPythonとは異なります。

まつもとゆきひろはTCOに同情しており、すべての実装にTCOのサポートを強制したくはありません。残念ながら、これはTCOに依存できないことを意味します。信頼すると、コードは他のRuby実装に移植できなくなります。

したがって、一部のRuby実装はTCOを実行しますが、ほとんどは実行しません。たとえば、YARVはTCOをサポートしていますが、（現時点では）ソースコードの行のコメントを明示的に解除してVMを再コンパイルし、TCOをアクティブ化する必要があります。将来のバージョンでは、実装が証明された後、デフォルトでオンになります。安定。Parrot仮想マシンはTCOをネイティブにサポートしているため、Cardinalも非常に簡単にサポートできます。CLRはTCOをある程度サポートしています。つまり、IronRubyとRuby.NETでTCOをサポートできる可能性があります。ルビニウスもおそらくそれを行うことができます。

ただし、JRubyとXRubyはTCOをサポートしておらず、JVM自体がTCOのサポートを取得しない限り、おそらくサポートしません。問題はこれです。高速な実装とJavaとの高速でシームレスな統合が必要な場合は、Javaとスタック互換性があり、JVMのスタックを可能な限り使用する必要があります。トランポリンまたは明示的な継続渡しスタイルを使用してTCOを非常に簡単に実装できますが、JVMスタックを使用しなくなります。つまり、Javaを呼び出したり、JavaからRubyを呼び出したりするたびに、何らかの実行が必要になります。変換は遅いです。そのため、XRubyとJRubyは、TCOと継続（基本的に同じ問題があります）よりも速度とJavaの統合を選択しました。

これは、TCOをネイティブにサポートしていないホストプラットフォームと緊密に統合したいRubyのすべての実装に適用されます。たとえば、MacRubyでも同じ問題が発生すると思います。

于 2009-05-05T13:21:34.130 に答える
43

更新: Ruby の TCO についてのわかりやすい説明があります: http://nithinbekal.com/posts/ruby-tco/

更新: tco_method gemも確認してください: http://blog.tdg5.com/introducing-the-tco_method-gem/

Ruby MRI (1.9、2.0、および 2.1) では、次のコマンドで TCO をオンにできます。

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

Ruby 2.0 ではデフォルトで TCO を有効にするという提案がありました。また、それに伴ういくつかの問題についても説明しています:テール コールの最適化: デフォルトで有効にしますか?.

リンクからの短い抜粋:

一般に、末尾再帰の最適化には別の最適化手法、つまり「呼び出し」から「ジャンプ」への変換が含まれます。私の意見では、Ruby の世界では「再帰」の認識が難しいため、この最適化を適用するのは難しいと思います。

次の例。「else」節での fact() メソッドの呼び出しは「末尾呼び出し」ではありません。

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

fact() メソッドで末尾呼び出し最適化を使用する場合は、fact() メソッドを次のように変更する必要があります (継続渡しスタイル)。

def fact(n, r) 
  if n < 2 
    r
  else
    fact(n-1, n*r)
  end
end
于 2012-11-12T19:46:40.507 に答える
12

It can have but is not guaranteed to:

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

于 2009-05-05T12:09:19.607 に答える
4

TCO は、コンパイルする前に vm_opts.h でいくつかの変数を微調整することによってコンパイルすることもできます: 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
于 2014-03-12T20:26:14.560 に答える
2

これは、JörgとErnestの回答に基づいています。基本的には実装に依存します。

Ernest の答えを MRI で動作させることはできませんでしたが、実行可能です。MRI 1.9 から 2.1 で機能するこの例を見つけました。これは非常に大きな数を出力するはずです。TCO オプションを true に設定しないと、「スタックが深すぎます」というエラーが発生するはずです。

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
于 2014-05-02T20:54:59.670 に答える