Posted at

Scala関数型デザイン&プログラミング forever関数でのStackOverflowErrorについて

書籍「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

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

lazyにより、new IO[B]のインスタンス生成は一度しか行われないので、2回目以降の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が起こらなくなります。これについては、また別の機会で触れたいと思います。