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

前回の記事[「Scala関数型デザイン＆プログラミング forever関数でのStackOverflowErrorについて」](https://qiita.com/masaki_shoji/items/5f3d5192fb5a215d3c84)で、[Scala関数型デザイン＆プログラミング](https://book.impress.co.jp/books/1114101091)で説明されているforever関数でのStackOverflowErrorについて説明しました。
今回はそれを回避するためのトランポリン化について、現状の理解をまとめてみようと思います。
Scalaについてはあまり詳しくないので間違いがあればご指摘ください。

書籍「[Scala関数型デザイン＆プログラミング](https://book.impress.co.jp/books/1114101091)」の292ページ目において、以下のコードで得られたpにおいて、p.runを実行するとStackOverflowErrorが発生するとの記載があります。（StackOverflowErrorが起こる原因について、概要は[前回の記事](https://qiita.com/masaki_shoji/items/5f3d5192fb5a215d3c84)で触れています）

（[Scala関数型デザイン＆プログラミング](https://book.impress.co.jp/books/1114101091)より引用）
>
```scala
val p = IO.forever(PrintLine("Stillgoing..."))
```

これを回避するための手段として、「トランポリン化」という手法があります。
Wikipediaによると、トランポリン化の説明は以下のようになっています。

([Wikipedia「Trampoline (computing)より]( https://en.wikipedia.org/wiki/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](https://github.com/fpinscala/fpinscala/blob/master/answers/src/main/scala/fpinscala/iomonad/IO.scala)
より抜粋
>
```scala
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](https://github.com/fpinscala/fpinscala/blob/master/answers/src/main/scala/fpinscala/iomonad/IO.scala)
より抜粋

>
```scala
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..."))```は以下のように展開されます。

```scala
IO.forever(printLine("Stillgoing..."))
```

=>

```scala
lazy val t = Suspend(() => println("Stillgoing...")) flatMap (_ => t)
t
```

=>

```scala
lazy val t = FlatMap(Suspend(() => println("Stillgoing..."), (_ => t))
t
```

なので、```IO.forever```により得られたIO型に対して、runを実行した場合のイメージは以下のような感じです。

```scala: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を実行**

```scala
//runの実行
run(FlatMap(Suspend(() => println("Stillgoing..."), (_ => t)))
```

run関数の実装において、上記のケースは```run(f(r()))```を実行することとなっています。
ここで、サンクである```r```が評価され、```println("Stillgoing...")```が実行されます。

```scala:run(f(r()))のrを評価
Suspend(() => println("Stillgoing...")) // サンクであったrが評価されprintlnが実行される
```

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

```scala:r()の結果に対して、fを適用し評価
(_ => t)
```

上記の```(_ => t)```のうち、```-```が```println("Stillgoing...")```の結果とみなせます。（このコードではrの結果を無視しています）
ここで```t```は```FlatMap(Suspend(() => println("Stillgoing..."), (_ => t))```です。
よって、この段階のコードの状態のイメージは以下のようになります。

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

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

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

```scala: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関数型デザイン＆プログラミング](https://book.impress.co.jp/books/1114101091)」ではTailRecといった汎用的な実装を再定義しています。ここら辺は余裕があればまた今度。