Posted at

Scala関数型プログラミング トランポリン化でのStackOverflowError回避

前回の記事「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を実行した場合のイメージは以下のような感じです。


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...")が実行されます。


run(f(r()))のrを評価

Suspend(() => println("Stillgoing...")) // サンクであったrが評価されprintlnが実行される


そして、その結果に対し、fが適用されます。ここで(_ => t)が評価されます。


r()の結果に対して、fを適用し評価

(_ => t)


上記の(_ => t)のうち、-println("Stillgoing...")の結果とみなせます。(このコードではrの結果を無視しています)

ここでtFlatMap(Suspend(() => println("Stillgoing..."), (_ => t))です。

よって、この段階のコードの状態のイメージは以下のようになります。

run(FlatMap(Suspend(() => println("Stillgoing..."), (_ => t)))

最初の状態に戻りましたね。

このコードを実行するためには、runの引数のFlatMap(Suspend(() => println("Stillgoing..."), (_ => t))を評価する必要があります。

なので、以下のパターンマッチングが実行されます。


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))
}

以下、無限に同様の評価が繰り返されます。

上記のrunの評価では以下の動作が繰り返されています。

1. runを実行するために、データコンストラクタの種類(Return, Suspend, FlatMap)に応じた処理を実行

2. データコンストラクタ内の値が評価される。

3. 1~2の繰り返し。

run自体の評価(処理に必要なパターンマッチングの実行) <-> (runの引数である)FlatMap[Suspend, Return]の値の評価のように、各々の評価が交互に行われて計算を継続させています。

制御が行ったり来たりする様はまるでトランポリンのようですね。

ちなみに、このトランポリン化はIOモナドに限定されるものではなく、書籍「Scala関数型デザイン&プログラミング」ではTailRecといった汎用的な実装を再定義しています。ここら辺は余裕があればまた今度。