トランポリン化でStackOverflowの回避

[Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド](http://www.amazon.co.jp/dp/4844337769)という本を買って、Scalaを勉強していますが、ちょっと驚いた部分があったので記事にしました。

# StackOverflowが発生するコード

本の中で、代数的データ型の説明に際して`List`を作るという部分があり、次のようなサンプルコードが載っています。

```scala:List.scala
package fpinscala.datastructures

sealed trait List[+A]
case object Nil  extends List[Nothing]
case class Cons[+A](head : A, tail : List[A]) extends List[A]

object List {
  def apply[A](as : A*) : List[A] =
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail : _*))
}
```

```scala:TestList.scala
import fpinscala.datastructures.List

object TestList {
  def main(args : Array[String]) : Unit = {
    val xs = List(1, 2, 3, 4)
    println(xs)
  }
}
```

https://ideone.com/eaKKZ5

次のような出力になります。

```console
Cons(1,Cons(2,Cons(3,Cons(4,Nil))))
```

ただし、次のようにたくさんの引数を注入するとStackOverflowが発生します。

```scala:TestListWithStackOverflow.scala
import fpinscala.datastructures.List

object TestListWithStackOverflow {
  def main(args : Array[String]) : Unit = {
    val xs = List( (1 to 10000).toSeq : _* )
    println(xs)
  }
}
```

https://ideone.com/zvzLh9


# 継続渡しスタイル（CPS）で末尾再帰最適化？

_List.scala_ の`apply`関数は`else`文で最後に行う処理が`Cons(as.head, apply(as.tail : _*))`となっており、末尾再帰ではありません。これにより処理系の末尾再帰最適化（Tail call elimination）が受けられなくなり、結果StackOverflowに陥ったというのが単純な仮説です。この関数を **継続渡しスタイル（CPS）** を用いて末尾再帰な関数にすれば、末尾再帰最適化によってStackOverflowを回避できるように思われます。先程の関数をCPSで書き直すと次のようになります。

```scala:
def apply[A](as : A*) : List[A] = {
  def loop(k : List[A] => List[A], xs : Seq[A]) : List[A] =
    if (xs.isEmpty) k(Nil)
    else loop(x => k(Cons(xs.head, x)), xs.tail)

  loop(x => x, as)
}
```

https://ideone.com/k3rMd3

ここで`loop`関数は`k(Nil)`か`loop(x => k(Cons(xs.head, x)), xs.tail)`のどちらかであり、`loop`関数の最後に呼び出されるのが自分自身なので末尾再帰関数となります。
こちらのバージョンで _TestList.scala_ を再び実行してみると同じ結果となり、ひとまず機能的にはCPS変換した後と前とで同じであることを確かめられると思います。さて、肝心のStackOverflowは解決されたのかを確かめるために、 _TestListWithStackOverflow.scala_ を実行してみましょう。実はこれを行ってもStackOverflowが表示されて失敗してしまいます。

どうしてこのような結果になったかというと、CPS変換の際に用いる関数`k`に問題があります。この関数`k`は、呼び出されると前に生成された関数`k`を呼び出します。つまり関数`k`は関数`apply`の引数$n$に対して$n$数珠つなぎになっているということになり、これがScalaのコールスタックを逼迫させます。

# トランポリン化による末尾再帰最適化

**トランポリン化** と呼ばれる次のような方法を用いて、数珠つなぎになった関数を切断してStackOverflowを回避します。

```scala:TailRec.scala
package fpinscala.tailrec

sealed trait TailRec[A] {
  final def run : A = this match {
    case Return(v)  => v
    case Suspend(k) => k().run
  }
}

case class Return[A](v : A) extends TailRec[A]
case class Suspend[A](resume : () => TailRec[A]) extends TailRec[A]
```

```scala
def apply[A] (as : A*) : List[A] = {
  def loop(k : List[A] => TailRec[List[A]], xs : Seq[A]) : TailRec[List[A]] =
    if (xs.isEmpty) k(Nil)
    else loop( x => Suspend(() => k(Cons(xs.head, x))), xs.tail)

  loop( x => Return(x), as ).run
}
```

https://ideone.com/HeySJT

無事に動くものが完成しました。ストリーム（遅延リスト）を作ったことがある人がいれば、あれに似ていると思ったのではないでしょうか。

# まとめ

[Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド](http://www.amazon.co.jp/dp/4844337769)や後に紹介する参考文献では、これをさらにFreeモナドへ拡張して話を進めていましたが、まだそこまで読んでいないので読んだらまたまとめようかなと思います。

# 参考文献

- [Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド](http://www.amazon.co.jp/dp/4844337769)
- [お気楽 Scala プログラミング入門](http://www.geocities.jp/m_hiroi/java/scala23.html)
- [why scala doesn't make tail call optimization?](http://stackoverflow.com/questions/16539488/why-scala-doesnt-make-tail-call-optimization)
- [TailCall](http://www.scala-lang.org/api/2.11.4/index.html#scala.util.control.TailCalls$)
- [独習 Scalaz — Stackless Scala with Free Monads](http://eed3si9n.com/learning-scalaz/ja/Stackless+Scala+with+Free+Monads.html)