performance - Scalaは末尾再帰の最適化をサポートしていますか？

Question

Scalaは末尾再帰の最適化をサポートしていますか？

Answer 1

他のポスターが言っているように、Scalaはコンパイル時に末尾再帰の最適化を行います。つまり、末尾再帰関数を実行するときのスタックトレースからわかるように、末尾再帰関数はコンパイラによってループに変換されます（メソッドinvokeはジャンプに変換されます）。

次のスニペットを試してください。

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)

スタックトレースを調べます。関数boomへの呼び出しは1つだけ表示されるため、コンパイルされたバイトコードは再帰的ではありません。

JVMレベルで末尾呼び出しを実装するという提案が浮かんでいます-私の意見では、JVMはコードのコンパイル時の最適化だけでなく、ランタイムの最適化を行うことができるので、これは素晴らしいことです-そしておそらくもっと意味があるかもしれません柔軟な末尾再帰。基本的に、atailcall invokeは通常のメソッドとまったく同じように動作invokeしますが、安全な場合は呼び出し元のスタックをドロップします。JVMの仕様では、スタックフレームを保持する必要があると規定されているため、JITは静的コード分析を実行して検出する必要があります。スタックフレームが使用されない場合。

現在の状況はプロト80％です。Java 7に間に合うように行われるとは思いませんが（invokedynamic優先度が高く、実装はほぼ完了しています）、Java8では実装されていると見なされる可能性があります。

Answer 2

Scala 2.8では@tailrec、コンパイラーが最適化すると予想される特定のメソッドをマークするために使用できます。

import scala.annotation.tailrec

@tailrec def factorialAcc(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else factorialAcc(n * acc, n - 1)
}

メソッドを最適化できない場合は、コンパイル時エラーが発生します。

Answer 3

Scala 2.7.xは、finalメソッドとローカル関数の自己再帰（それ自体を呼び出す関数）の末尾呼び出しの最適化をサポートしています。

Scala 2.8には、相互再帰関数を最適化する手法であるトランポリンのライブラリサポートも付属している可能性があります。

Scalaの再帰の状態に関する多くの情報は、RichDoughertyのブログにあります。

Answer 4

関数が自己再帰的である非常に単純な場合のみ。

末尾再帰能力の証明。

ただし、Scala2.8は末尾再帰の認識を改善しているようです。