Java テール コールの最適化
このチュートリアルでは、テール コールの最適化 (TCO とも呼ばれる) と、Java に存在しない理由について説明します。 また、Java で TCO をシミュレートするために使用できる他の方法についても説明します。
テールコール最適化とは
末尾呼び出しの最適化は、呼び出し元の関数が呼び出し先の関数から受け取った値を返すため、関数に 1つの新しいスタック フレームを割り当てることを回避できるプロセスです。
最も一般的な用途の 1つは、末尾再帰 (関数が最後/末尾で自分自身を呼び出す再帰関数) です。この再帰メソッドは、末尾呼び出しの最適化を利用するように記述されており、一定のスタック スペースを使用できます。
Scheme は、実装がこの最適化を提供する必要があることを仕様で保証するプログラミング言語の 1つです。 以下は、Scheme プログラミング言語での階乗法の 2つの例です。
コード例 1 (末尾再帰なし):
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
コード例 2 (末尾再帰を使用):
(define (factorial n)
(define (factorial-tail n accum)
(if (= n 0) accum
(factorial-tail (- n 1) (* n accum))))
(factorial-tail n 1))
コード例 1 では、関数は末尾再帰ではありません。 これは、再帰呼び出しが行われるたびに (階乗の例を考えると)、メソッドは、呼び出しが返された後に結果を処理するために必要な乗算を追跡する必要があるためです。
そのため、スタックは次のようになります。
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
対照的に、末尾再帰階乗のスタック トレースは次のようになります。
(factorial 3)
(factorial-tail 3 1)
(factorial-tail 2 3)
(factorial-tail 1 6)
(factorial-tail 0 6)
6
factorial-tail の呼び出しごとに同じデータを追跡する必要があるだけです。
これは、たとえ (factorial 1000000) を呼び出したとしても、( 階乗 3).
これは、非末尾再帰 factorial を考慮する場合には当てはまりません。大きな値はスタック オーバーフローを引き起こす可能性があります。
Java で末尾呼び出しの最適化がない理由
現在、コンパイラ レベルでは、Java テール コールの最適化はプレーン Java ではサポートされていません。 継承が存在するため、呼び出されているメソッドを見つけるのは簡単ではないかもしれません。
さらに、現在のスタック カウント メカニズムでは、この種の最適化をすぐに実装することはできません。 言語の仕組みが毎年劇的に変化するのを避ける理由があるかもしれません。
1つ目の理由は、テール コールの最適化にはコストがかかることです。 次に、Java のルールに従って、エラーが発生するたびにスタック トレースを取得します。
また、スタック トレースは明確に定義された概念であり、論理呼び出しごとに 1つのスタック フレームを追跡することはほとんどできません。 Java にテール コールの最適化が存在する場合、これは不可能です。
第三に、モデルとしてのテールコールの最適化は、物事を行う方法ですが、唯一の方法ではありません。 一般に、TCO 再帰アプリとして記述できるものについて、ループベースの非再帰アルゴリズムにリファクタリングすることはそれほど難しくありません。
だから何をすべきか？ 代わりに、while または for ループを使用できます。
Java で末尾呼び出しの最適化をシミュレートする方法はありますか
仮想マシンである Java には、他のユーザーにとって作業を容易にする新機能がありますが、Java 以外のプログラミング言語はクラス ファイルにコンパイルされ、Java ランタイムで実行され、テール コールの最適化がサポートされます。
以下の 2つのビデオを視聴して全体像を理解することをお勧めします。特に言語が最も人気のある言語の 1つである場合は、すべての機能が常に正当化されるとは限らないためです。
そのため、Java で TCO を使用するためにどのアプローチを使用する必要があるかはわかりません。 Project Loom の提案でよく説明されています。
ただし、Java でテール コールの最適化をシミュレートするために使用できる方法は他にもいくつかあると考えています。 1つ目は、Scala などの他の JVM 言語を使用することです。
2 番目の解決策は、lambda 式を使用することです。 または、勇気があれば、これ のような危険なことを試すことができます。
