前回の記事「Scala関数型デザイン＆プログラミング forever関数でのStackOverflowErrorについて」で、Scala関数型デザイン＆プログラミングで説明されているforever関数でのStackOverflowErrorについて説明しました。
今回はそれを回避するためのトランポリン化について、現状の理解をまとめてみようと思います。
Scalaについてはあまり詳しくないので間違いがあればご指摘ください。
書籍「Scala関数型デザイン＆プログラミング」の292ページ目において、以下のコードで得られたpにおいて、p.runを実行するとStackOverflowErrorが発生するとの記載があります。（StackOverflowErrorが起こる原因について、概要は前回の記事で触れています）
（Scala関数型デザイン＆プログラミングより引用）
val p = IO.forever(PrintLine("Stillgoing..."))
これを回避するための手段として、「トランポリン化」という手法があります。
Wikipediaによると、トランポリン化の説明は以下のようになっています。
(Wikipedia「Trampoline (computing)より)
a trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style).
トランポリン化は、「サンクを返す関数を反復して呼び出すループ」と説明され、CPS(continuation-passing-style）のプログラミング手法を使って実現されます。
文章だけ見ると、なんのこっちゃって感じなので、実際の使用例を見てみましょう。
まず、StackOverflowErrorが起こるIOの実装を抜粋します。
Github fpinscala/answers/src/main/scala/fpinscala/iomonad/IO.scala object IO1
より抜粋
object IO1 { ... sealed trait IO[A] { self => def run: A def map[B](f: A => B): IO[B] = new IO[B] { def run = f(self.run) } def flatMap[B](f: A => IO[B]): IO[B] = new IO[B] { def run = f(self.run).run } } ...
上記の実装を以下のように書き換えます。
Github fpinscala/answers/src/main/scala/fpinscala/iomonad/IO.scala object IO2a
より抜粋
object IO2a { ... sealed trait IO[A] { def flatMap[B](f: A => IO[B]): IO[B] = FlatMap(this, f) // we do not interpret the `flatMap` here, just return it as a value def map[B](f: A => B): IO[B] = flatMap(f andThen (Return(_))) } case class Return[A](a: A) extends IO[A] case class Suspend[A](resume: () => A) extends IO[A] case class FlatMap[A,B](sub: IO[A], k: A => IO[B]) extends IO[B] ... @annotation.tailrec def run[A](io: IO[A]): A = io match { case Return(a) => a case Suspend(r) => r() case FlatMap(x, f) => x match { case Return(a) => run(f(a)) case Suspend(r) => run(f(r())) case FlatMap(y, g) => run(y flatMap (a => g(a) flatMap f)) } ... def printLine(s: String): IO[Unit] = Suspend(() => Return(println(s))) val p = IO.forever(printLine("Still going...")) }
変更後のflatMapの実装では、新しいIOインスタンスを生成するのではなく、IOデータ型のデータコンストラクタとなっています。新しい実装で、IO.forever(printLine("Stillgoing..."))をrunした場合、どのように評価されるのでしょうか。
評価のイメージを以下に書いてみます。
まず、IO.forever(printLine("Stillgoing..."))は以下のように展開されます。
IO.forever(printLine("Stillgoing..."))
=>
lazy val t = Suspend(() => println("Stillgoing...")) flatMap (_ => t)
t
=>
lazy val t = FlatMap(Suspend(() => println("Stillgoing..."), (_ => t))
t
なので、IO.foreverにより得られたIO型に対して、runを実行した場合のイメージは以下のような感じです。
@annotation.tailrec def run[A](io: IO[A]): A = io match {
case Return(a) => a
case Suspend(r) => r()
case FlatMap(x, f) => x match {
case Return(a) => run(f(a))
case Suspend(r) => run(f(r()))
case FlatMap(y, g) => run(y flatMap (a => g(a) flatMap f))
}
IO.foreverにより得られたIO型に対してrunを実行
//runの実行
run(FlatMap(Suspend(() => println("Stillgoing..."), (_ => t)))
run関数の実装において、上記のケースはrun(f(r()))を実行することとなっています。
ここで、サンクであるrが評価され、println("Stillgoing...")が実行されます。
Suspend(() => println("Stillgoing...")) // サンクであったrが評価されprintlnが実行される
そして、その結果に対し、fが適用されます。ここで(_ => t)が評価されます。
(_ => t)
上記の(_ => t)のうち、-がprintln("Stillgoing...")の結果とみなせます。（このコードではrの結果を無視しています）
ここでtはFlatMap(Suspend(() => println("Stillgoing..."), (_ => t))です。
よって、この段階のコードの状態のイメージは以下のようになります。
run(FlatMap(Suspend(() => println("Stillgoing..."), (_ => t)))
最初の状態に戻りましたね。
このコードを実行するためには、runの引数のFlatMap(Suspend(() => println("Stillgoing..."), (_ => t))を評価する必要があります。
なので、以下のパターンマッチングが実行されます。
@annotation.tailrec def run[A](io: IO[A]): A = io match {
case Return(a) => a
case Suspend(r) => r()
case FlatMap(x, f) => x match {
case Return(a) => run(f(a))
case Suspend(r) => run(f(r()))
case FlatMap(y, g) => run(y flatMap (a => g(a) flatMap f))
}
以下、無限に同様の評価が繰り返されます。
上記のrunの評価では以下の動作が繰り返されています。
1. runを実行するために、データコンストラクタの種類(Return, Suspend, FlatMap)に応じた処理を実行
2. データコンストラクタ内の値が評価される。
3. 1~2の繰り返し。
run自体の評価(処理に必要なパターンマッチングの実行） <-> (runの引数である）FlatMap[Suspend, Return]の値の評価のように、各々の評価が交互に行われて計算を継続させています。
制御が行ったり来たりする様はまるでトランポリンのようですね。
ちなみに、このトランポリン化はIOモナドに限定されるものではなく、書籍「Scala関数型デザイン＆プログラミング」ではTailRecといった汎用的な実装を再定義しています。ここら辺は余裕があればまた今度。