はじめに
Scala勉強会第176回 in 本郷 : サブテーマ「Scalaで作るウェブサービス」で継続渡しスタイルについて質問して、理解が深まったので今回はトランポリンを紹介したいと思います。
主に、トランポリンを使うとなぜスタックオーバーフローが起こらなくなるのかについて紹介します。
トランポリンとは
要点だけ引用します。
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
日本語に翻訳してみると「いくつかのLispの実装で使用されるように、トランポリンは反復サンクを返す関数（継続渡しスタイル）を呼び出すループです。」となります。
大雑把ですが、サンクを返す関数を呼び出す仕組みくらいで良いと思います。
サンプルコード
継続渡しスタイルでべき乗を計算する関数を考えてみます。
def powCps(x: Int, n: Int, f: Int => Int): Int =
if (n == 0) 1 else f(x * powCps(x, n - 1, f))
ひとまず、スタックオーバーフローを確認します。
powCps(1, 10000, identity)
powCps(1, 100000, identity) // java.lang.StackOverflowError
okです 
この関数の定義は末尾再帰ではないのでスタックオーバーフローになります。
末尾再帰を試してみる
末尾再帰を試してみます。
形としては次のようになります:
def powCps(x: Int, n: Int, f: Int => Int): Int =
if (n == 0) f(1) else powCps(...)
つじつまを合わせると次のようになります:
def powCps(x: Int, n: Int, f: Int => Int): Int =
if (n == 0) f(1) else powCps(x, n - 1, y => f(x * y))
しかし、これはスタックオーバーフローになってしまいます:
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の値が大きな場合にスタックオーバーフローになることが分かります。
トランポリンを試してみる
まず、トランポリンを用意します。
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
次に、トランポリンでべき乗を計算する関数を再実装します。
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)))
呼び出し側は次のようになります:
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
まとめ
トランポリンを紹介しました。
理解を深めるために机上デバッグをしました。