トランポリン
スタックセーフな再帰です。
「トランポリン」はCoddyKit上の無料Scala for Backend Engineering & Functional Programmingレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはScala for Backend Engineering & Functional Programming学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Scala for Backend Engineering & Functional Programmingコースには全4レッスンが含まれています。
@tailrecの限界
@tailrecが最適化できるのは、関数が直接自分自身を呼び出す場合だけです。相互再帰（2つの関数が互いに呼び出し合う場合）には使えず、スタックは増加し続けます。これを解決するのがトランポリンです。
相互再帰の問題
isEvenとisOddが互いを使って定義されている場合を考えます。大きな数ではスタックオーバーフローが発生し、どちらにも@tailrecを付けられません。
object Main {
def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
def isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)
def main(args: Array[String]): Unit = {
println(isEven(10))
}
}トランポリンとは
トランポリンは、再帰呼び出しをデータに変換します。自分自身を呼び出す代わりに、次のステップの説明を返します。ドライバーループがこれらのステップを繰り返し実行することで、スタックを一定に保ちます。
標準ライブラリのTailRec
Scalaはscala.util.control.TailCallsとTailRec型を提供しています。最終結果にはdone(x)を使い、次の呼び出しを遅延させるにはtailcall(...)を使います。
import scala.util.control.TailCalls._
object Main {
def isEven(n: Int): TailRec[Boolean] =
if (n == 0) done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean] =
if (n == 0) done(false) else tailcall(isEven(n - 1))
def main(args: Array[String]): Unit = {
println(isEven(100000).result)
}
}doneとtailcall
2つの基本要素は次のとおりです。
done(value)は最終的な答えをラップします。tailcall(expr)は、TailRecを返す呼び出しを遅延させます。
.resultを呼び出すと、トランポリンループが実行され、値が生成されます。
スタックセーフ性
各tailcallはJavaの呼び出しをネストする代わりにドライバーループへ制御を戻すため、再帰の深さに応じてJVMスタックが増えることはありません。上の例では、オーバーフローを起こさずに100,000ステップを処理できます。
自己再帰をトランポリン化する
アキュムレーターを簡単には使えない通常の深い自己再帰にも、トランポリンを使用できます。ここでは、深いカウントダウンをスタックセーフに保ちます。
import scala.util.control.TailCalls._
object Main {
def countDown(n: Int): TailRec[Int] =
if (n == 0) done(0) else tailcall(countDown(n - 1))
def main(args: Array[String]): Unit = {
println(countDown(500000).result)
}
}flatMapで結果を組み合わせる
TailRecはmapとflatMapをサポートしているため、遅延させた呼び出しの後に処理を行いながら、スタックセーフ性を維持できます。
import scala.util.control.TailCalls._
object Main {
def sum(n: Int): TailRec[Int] =
if (n == 0) done(0)
else tailcall(sum(n - 1)).map(_ + n)
def main(args: Array[String]): Unit = {
println(sum(100000).result)
}
}ドライバーループの仕組み
概念的には、.resultはループを実行します。現在のステップを取り出し、それがdoneなら値を返し、遅延された呼び出しなら1層分を評価して続行します。これらはすべて、一定のスタック領域で行われます。
Effectライブラリでのトランポリン化
Cats EffectやZIOなどのライブラリは、内部でflatMapチェーンをトランポリン化しています。そのため、スタックオーバーフローを起こさずに深くネストされたeffectプログラムを構築できます。トランポリン化は、スタックセーフな関数型effectの基盤です。
トランポリンを使う場面
トランポリンを使うのは次の場合です。
- 単一の末尾再帰関数にはできない相互再帰がある場合。
- 再帰が深すぎてスタックに収まらず、アキュムレーターも適さない場合。
単純な自己再帰では、まずアキュムレーター付きの@tailrecを優先してください。
クイックチェック
トランポリンについての理解を確認しましょう。
まとめ
トランポニーングについて学びました。
- 相互再帰や非常に深い再帰を、スタックセーフにできます。
TailCallsでdone(x)とtailcall(...)を使い、その後.resultを使用します。TailRecはmap/flatMapをサポートします。- スタックセーフなエフェクトライブラリの基盤となっています。
よくある質問
「トランポリン」レッスンは無料ですか？
はい。「トランポリン」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Scala for Backend Engineering & Functional Programmingコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Scala for Backend Engineering & Functional Programmingコースには全4レッスンが含まれています。
「トランポリン」で何を学びますか？
スタックセーフな再帰です。 ブラウザで直接実行するハンズオンコードでScala for Backend Engineering & Functional Programmingを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Scala for Backend Engineering & Functional Programmingを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのScala for Backend Engineering & Functional Programmingは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「トランポリン」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このScala for Backend Engineering & Functional Programmingレッスンでコードを書いて実行できますか？
はい。すべてのScala for Backend Engineering & Functional Programmingレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。