はじめに
前回、スタックオーバーフローで遊んだときに継続渡しスタイルが少し出てきました。
今回は継続渡しスタイルについて紹介したいと思います。
と言っても難しいことはわからないので入門的な内容になります。
継続渡しスタイルとは
要点だけ引用します。
継続渡しスタイルとは、関数が、値を返す代わりに、計算した値をどの関数に渡すのかを明示的に指定する 方法です。
継続渡しスタイル (continuation passing style) は略して CPS と呼ばれることがあります。
サンプルコード
早速、簡単なサンプルコードを試してみます。
def add(x: Int, y: Int): Int = x + y
def mul(x: Int, y: Int): Int = x * y
def addCps[A](x: Int, y: Int, f: Int => A): A = f(add(x, y))
def mulCps[A](x: Int, y: Int, f: Int => A): A = f(mul(x, y))
これらの関数を使って1 + 2 * 5を計算してみます。
ダイレクトスタイルの場合
CPSと比べるために用意します。
add(1, mul(2, 5))
手続きの場合
CPSと比べるために用意します。
val x = mul(2, 5)
add(1, x)
継続渡しスタイルの場合
無名関数を使います。
mulCps(2, 5, (x: Int) => addCps(1, x, identity))
こういうものなのかというほかにありませんね。
サンプルコード2
先ほどのサンプルコードを少し編集してみます。
def add(x: Int)(y: Int): Int = x + y
def mul(x: Int)(y: Int): Int = x * y
def addCps[A](x: Int)(y: Int)(f: Int => A): A = f(add(x)(y))
def mulCps[A](x: Int)(y: Int)(f: Int => A): A = f(mul(x)(y))
これらの関数を使って、継承渡しスタイルで計算してみます。
mulCps(2)(5) ((x: Int) => addCps(1)(x)(_: Int => Int)) (identity)
mulCps(2)(5) ((x: Int) => addCps(1)(x)(_: Int => Unit)) ((y: Int) => println(y))
無名関数がネストしていません。面白くありませんか!?
Scalaは_で部分適応すると、型パラメータの型がNothingになります。
そのため型推論が期待しない結果になり、コンパイルエラーになることがあります。
下記はコンパイルエラーになる例です:
scala> mulCps(2)(5) ((x: Int) => addCps(1)(x)_) ((y: Int) => println(y))
<console>:12: error: type mismatch;
found : Unit
required: Nothing
mulCps(2)(5) ((x: Int) => addCps(1)(x)_) ((y: Int) => println(y))
今回は型を明示的に指定してコンパイルエラーを回避しています。
一点気をつける点として、ネストしていないのでスコープが別々になっています。
そのため、スコープ外の変数を参照しようとするとエラーになります。
下記はコンパイルエラーになる例です:
scala> mulCps(2)(5) ((x: Int) => addCps(1)(x)(_: Int => Unit)) ((y: Int) => println(x))
<console>:12: error: not found: value x
mulCps(2)(5) ((x: Int) => addCps(1)(x)(_: Int => Unit)) ((y: Int) => println(x))
参考URL
冒頭にcallCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) kとあり、来るところ間違えちゃったかなと思ったのですが、簡潔で丁寧な内容でオススメです。
Schemeのサンプルコードがあるのですが、それをHaskellで書き直す、もしくは、Scalaで書き直すと理解が深まります。
まとめ
継続渡しスタイルについて紹介しました。
簡単な例からはじめれば、それほど取り扱いに困ることはありません。