1. ホーム
  2. ruby

[解決済み] RubyはTail Call Optimizationを行うのか?

2023-02-22 11:22:51

質問

関数型言語では、多くの問題を解決するために再帰を使用します。そのため、多くの関数がテールコール最適化(TCO)を実行します。TCOは、他の関数 (またはそれ自身。この場合、この機能はTCOのサブセットであるTail Recursion Eliminationとしても知られています) からその関数への呼び出しを、その関数の最後のステップとして、新しいスタックフレームを必要とせず、オーバーヘッドとメモリ使用量を減少させるようにします。

Ruby は明らかに関数型言語から多くの概念 (ラムダ、map などの関数) を借用しており、Ruby はテールコールの最適化を行うのでしょうか。

どのように解決するのですか?

いいえ、RubyはTCOを行いません。しかし ではない もありません。

Ruby言語仕様には、TCOについて何も書かれていません。やらなければならないとは書いていませんが、同時に できない とは書いていません。ただ、あなたは 頼る に頼ることはできません。

これはSchemeとは異なり、言語仕様書では が必要です。 という すべて 実装について は TCO を実行します。しかし、それは Python とも異なります。Guido van Rossum は何度も (最後はほんの数日前)、Python の実装は を実行しなければならないと明言しています。 を行うべきではありません。 は TCO を実行すべきではないと明言しています。

まつもとゆきひろはTCOに共感している、ただ、無理に すべて 実装にそれをサポートすることを強制したくないだけです。残念ながら、これは TCO に依存できない、あるいは依存した場合、そのコードは他の Ruby 実装に対してもはや移植できないことを意味します。

そのため、一部の Ruby 実装は TCO を実行しますが、ほとんどは実行しません。例えば YARV は TCO をサポートしていますが、(現時点では) TCO を有効にするには、ソースコードの行を明示的にアンコメントして VM を再コンパイルする必要があります - 将来のバージョンでは、実装が安定した後にデフォルトで有効になる予定です。Parrot Virtual MachineはTCOをネイティブにサポートしているので、Cardinalも簡単にサポートできるだろう。CLRはTCOをある程度サポートしているので、IronRubyやRuby.NETでもおそらく可能でしょう。Rubiniusもおそらく可能でしょう。

しかし、JRubyとXRubyはTCOをサポートしていませんし、JVM自体がTCOのサポートを獲得しない限り、おそらくそうならないでしょう。問題はこうです。もし、高速な実装を行い、Javaと高速かつシームレスに統合したいのであれば、Javaとスタック互換性を持ち、JVMのスタックを可能な限り使用すべきなのです。トランポリンや明示的な継続パッシングのスタイルでTCOを実装することは非常に簡単ですが、そうするとJVMのスタックを使わなくなるので、Javaに呼び出したり、JavaからRubyに呼び出すたびに、何らかの変換をしなければならず、時間がかかってしまうのです。そこで、XRubyとJRubyは、TCOと連続性(基本的に同じ問題を持つ)よりも、速度とJavaとの統合を選択しました。

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