トランポリンを試してみよう

## はじめに

[Scala勉強会第176回 in 本郷 : サブテーマ「Scalaで作るウェブサービス」](https://rpscala.doorkeeper.jp/events/48645)で継続渡しスタイルについて質問して、理解が深まったので今回はトランポリンを紹介したいと思います。

主に、トランポリンを使うとなぜスタックオーバーフローが起こらなくなるのかについて紹介します。

## トランポリンとは

要点だけ引用します。

> As used in some Lisp implementations, a trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style).

引用元: [Trampoline (computing) - Wikipedia, the free encyclopedia](https://en.wikipedia.org/wiki/Trampoline_(computing)#High-level_programming)

日本語に翻訳してみると「いくつかのLispの実装で使用されるように、トランポリンは反復サンクを返す関数（継続渡しスタイル）を呼び出すループです。」となります。

大雑把ですが、サンクを返す関数を呼び出す仕組みくらいで良いと思います。

## サンプルコード

継続渡しスタイルでべき乗を計算する関数を考えてみます。

``` scala
def powCps(x: Int, n: Int, f: Int => Int): Int = 
  if (n == 0) 1 else f(x * powCps(x, n - 1, f))
```

ひとまず、スタックオーバーフローを確認します。

``` scala
powCps(1, 10000, identity)
powCps(1, 100000, identity) // java.lang.StackOverflowError
```

okです :ok_hand:

この関数の定義は末尾再帰ではないのでスタックオーバーフローになります。

## 末尾再帰を試してみる

末尾再帰を試してみます。

形としては次のようになります:

``` scala
def powCps(x: Int, n: Int, f: Int => Int): Int =
  if (n == 0) f(1) else powCps(...)
```

つじつまを合わせると次のようになります:

``` scala
def powCps(x: Int, n: Int, f: Int => Int): Int =
  if (n == 0) f(1) else powCps(x, n - 1, y => f(x * y))
```

しかし、これはスタックオーバーフローになってしまいます:

``` scala
powCps(2, 3, identity) // 8
powCps(5, 2, identity) // 25
powCps(1, 100000, identity) // java.lang.StackOverflowError
```

### 特定の場合を机上デバッグしてみる

`powCps(2, 3, identity)`を机上デバッグしてみます。

以降の机上デバッグですが、見通しをよくするために無名関数の引数の型を省略します。

本来は`def f(x: Int): Int => Int = (y1: Int) => identity(x * y1)`のように型を指定する必要があります。

まず`n=3`のときに、`powCps`に`identity`が渡されます。

呼び出し先で、`n=2`となり、`powCps`に`y1 => f(2 * y1)`が渡されます。

ここでの`f`は`identity`なので、渡される関数は`y1 => (identity)(2 * y1)`となります。

次に、`n=1`となり、`powCps`に`y2 => f(2 * y2)`が渡されます。

ここでの`f`は`y1 => (identity)(2 * y1)`なので、渡される関数は`y2 => (y1 => (identity)(2 * y1))(2 * y2)`となります。

次に、`n=0`となり、`powCps`に`y3 => f(2 * y3)`が渡されます。

ここでの`f`は`y2 => (y1 => (identity)(2 * y1))(2 * y2)`なので、渡される関数は`y3 => (y2 => (y1 => (identity)(2 * y1))(2 * y2))(2 * y3)`となります。

最後に、`f(1)`が呼び出されます。これは`(y3 => (y2 => (y1 => (identity)(2 * y1))(2 * y2))(2 * y3))(1)`と同じことです。

関数が呼び出されると、スタックフレームに戻りアドレスがプッシュされます。

まず、`1`で関数が呼び出され`y3=1`となり、`(2 * 1)`が計算されます。

次に、`2`で関数が呼び出され`y2=2`となり、`(2 * 2)`が計算されます。

そして、`4`で関数が呼び出され`y1=4`となり、`(2 * 4)`が計算されます。

最後に、`8`で関数が呼び出され`y0=8`となり、計算結果が`8`となります。

あとは、この計算結果が呼び出し元に戻っていきます。

### 一般的な場合を机上デバッグしてみる

一般的な場合は次のようになります:

```
powCps(x, n - 1, y1 => identity(x * y1))
powCps(x, n - 2, y2 => (y1 => identity(x * y1))(x * y2))
powCps(x, n - 3, y3 => (y2 => (y1 => identity(x * y1))(x * y2))(x * y3))
(以下省略)
(...)(1)
```

`n`の値が大きな場合にスタックオーバーフローになることが分かります。

## トランポリンを試してみる

まず、トランポリンを用意します。

``` scala
sealed trait Trampoline[+A] {
  final def runT: A =
    this match {
      case More(k) => k().runT
      case Done(v) => v
    }
}
case class More[+A](k: () => Trampoline[A])
  extends Trampoline[A]
case class Done[+A](result: A)
  extends Trampoline[A]
```

引用元: [独習 Scalaz — Stackless Scala with Free Monads](http://eed3si9n.com/learning-scalaz/ja/Stackless+Scala+with+Free+Monads.html)

次に、トランポリンでべき乗を計算する関数を再実装します。

``` scala
def powCps(x: Int, n: Int, f: Int => Trampoline[Int]): Trampoline[Int] =
  if (n == 0) f(1) else powCps(x, n - 1, y => More(() => f(x * y)))
```

呼び出し側は次のようになります:

``` scala
powCps(2, 3, x => Done(x)).runT // 8
powCps(5, 2, x => Done(x)).runT // 25
powCps(1, 100000, x => Done(x)).runT // 1
```

### 一般的な場合を机上デバッグしてみる

ここでも机上デバッグをしてみます。

一般的な場合は次のようになります:

```
powCps(x, n - 1, y1 => More(() => (y0 => Done(y0))(x * y1)))
powCps(x, n - 2, y2 => More(() => (y1 => More(() => (y0 => Done(y0))(x * y1)))(x * y2)))
powCps(x, n - 3, y3 => More(() => (y2 => More(() => (y1 => More(() => (y0 => Done(y0))(x * y1)))(x * y2)))(x * y3)))
(以下省略)
(...)(1)
```

### 特定な場合を机上デバッグしてみる

ここでは一般的な場合の結果を利用して、いろいろな`f`を確認します。

まず`n=0`のときに`f`が`y0 => Done(y0)`である場合、`f(1)`は`Done(1)`となります。

この`Done(1)`の`runT`を呼び出すと`1`が戻ります。

次に`n=0`のときに`f`が`y1 => More(() => (y0 => Done(y0))(x * y1))`である場合、`f(1)`は`More(() => (y0 => Done(y0))(x * 1))`となります。

`More(() => (y0 => Done(y0))(x * 1))`の`runT`を呼び出すと、`((() => (y0 => Done(y0))(x * 1))()).runT`となり、次に、引数なしで呼び出され、そして、`((y0 => Done(y0))(x * 1)).runT`となり、最後に、`(x * 1)`で呼び出され、`Done(x * 1).runT`となります。

ここで関数の呼び出しが一旦途切れます。面白くありませんか!?

最後に`n=0`のときに`f`が`y2 => More(() => (y1 => More(() => (y0 => Done(y0))(x * y1)))(x * y2))`である場合、`f(1)`は`More(() => (y1 => More(() => (y0 => Done(y0))(x * y1)))(x * 1))`となります。

`More(() => (y1 => More(() => (y0 => Done(y0))(x * y1)))(x * 1))`の`runT`を呼び出すと、`((() => (y1 => More(() => (y0 => Done(y0))(x * y1)))(x * 1))()).runT`となり、次に、引数なしで呼び出され、そして、`((y1 => More(() => (y0 => Done(y0))(x * y1)))(x * 1)).runT`となり、最後に、`(x * 1)`で呼び出され、`More(() => (y0 => Done(y0))(x * x * 1)).runT`となります。

そして、ここで関数の呼び出しが一旦途切れます。

このように関数の呼び出しが一旦途切れることによってスタックオーバーフローにならない仕組みになっています。

## 参考URL

- [トランポリン化でStackOverflowの回避](http://qiita.com/yyu/items/f1601749097ba3ee03db)

- [なんでも継続](http://practical-scheme.net/docs/cont-j.html)

## まとめ

トランポリンを紹介しました。

理解を深めるために机上デバッグをしました。