株式会社G・B・Sこんにちは。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が起こらなくなります。これについては、また別の機会で触れたいと思います。