【技術ブログ】Scala関数型デザイン＆プログラミング forever関数でのStackOverflowErrorについて

こんにちは。G・B・S第２システム開発部の小路です。

書籍Scala関数型デザイン＆プログラミング」の第13章「StackOverflowErrorの回避」の冒頭でlazyを利用したforever関数の実装が例として出されているのですが、この箇所(だけとは言わず書籍全体を通して）は頭の中だけで理解しようとすると難解なので、処理イメージをまとめてみました。

書籍では次のコードが記載され、以下のように述べられています。
（以下、Scala関数型デザイン＆プログラミングの第13章「StackOverflowErrorの回避」より引用）

val p = IO.forever(PrintLine("Stillgoing..."))

p.runを評価すると、数百行の情報が出力された後、プログラムがStackOverflowErrorでクラッシュします。スタックトレースを調べてみると、runが自身を繰り返し呼び出していることがわかります。問題はflatMapの定義にあります。

def flatMap[B](f:A => IO[B]): IO[B] = new IO[B] { def run = f(self.run).run }

ここで、上記のforever関数は以下のように定義されています。

def forever[A, B](a: F[A]): F[B] = {
    lazy val t: F[B] = a flatMap (_ => t)
    t
}

また、PrintLineは以下のように定義されています。

def PrintLine(msg: String): IO[Unit] = IO { println(msg) }

なので、上記のIO.foreverは次のように展開できます。

lazy val t = PrintLine("Stillgoing...") flatMap (_ => t)
t

=>

lazy val t = new IO[Unit] { def run = println("Stillgoing...") } flatMap (_ => t)
t

以下の説明では、上記のnew IO[Unit] { def run = println(“Stillgoing…”) }を便宜上、selfと置きます。
また、forever関数内で呼び出されるflatMapの引数(f:A => IO[B])に渡される実引数は(_ => t)です。(_ => t)の”_”は、self.runの結果とみなせるので、”_”をself.runに置き換えてみます。（実際はコンパイルエラーとなりますが、self.runが呼び出されることをイメージするため、このように表記します）
そうすると、上記の式は以下のように置き換えられます。

lazy val t = new IO[B] { def run = ((self.run) => t).run }
t

なので、IO.foreverで取得したIOモナドのrunは以下のように読み替えられます。

IO.forever(PrintLine("Stillgoing...").run

=>

new IO[B] { def run = ((self.run) => t).run }.run

ここで、tはlazyによる宣言がなされています。lazy修飾子がついた変数は初回アクセス時の結果をキャッシュし、以降の参照ではそのキャッシュした値を返します。

lazyにより、new IO[B]のインスタンス生成は一度しか行われないので、２回目以降のIO[B]は便宜上、cachedIOと置きます。これまた便宜上、呼び出し回数を表すためにcachedIOの後ろに数字を付け足して、cachedIO(N)のように表記します(Nは呼び出し回数）。(cachedIOのインスタンス自体は全て同一インスタンス）
そうすると、上記の式は以下のように置き換えられます。

new IO[B] /* ( = cachedIO(0)) */ { def run = ((self.run) => cachedIO(1) { def run = ((self.run) => cachedIO(2) { def run = ((self.run) => cachedIO(N)...)...).run }).run }).run }.run

new IO[B]のrunを実行するには、cachedIO(1)のrunを実行する必要があります。
cachedIO(1)のrunを実行するには、cachedIO(2)のrunを実行する必要があります。
以下同様に、cachedIO(N)のrunを実行するには、cachedIO(N+1)のrunを実行する必要があります。
このようにnew IO[B]のrunを実行するためには、自身のrunを内部で繰り返し呼ぶ必要があります。その結果、入れ子のrun呼び出しがスタックに積み上げられていくことになります。
これがStackOverflowErrorが発生する原因です。

これを回避するためにトランポリン化という手法があり、それを使えばStackOverflowErrorが起こらなくなります。これについては、また別の機会で触れたいと思います。