CPS（継続渡し方式）変換をJavaScriptで説明してみるべ、ナーニ、たいしたことねーべよ

久々にThe n-Category Cafeを見たら、Mike Stayによる"The Continuation Passing Transform and the Yoneda Embedding"なんて記事がありました。

米田埋め込みは圏論ではお馴染み。継続渡しへの変換はコンピュータ・プログラミングではお馴染み。

この2つは、実は同じものなんだよ。なんで、誰もこのことを言わないんだろうね？

---

The Yoneda embedding is familiar in category theory. The continuation passing transform is familiar in computer programming.

They're the same thing! Why doesn't anyone ever say so?

Mike Stayのこの記事、面白いのだけど、C++とJavaと圏論の記法がたいした説明もなく混じって出てきて、どうもわかりにくい（少なくとも僕には）。そこで、JavaScriptだけを使って説明してみます。圏論と米田埋め込みの話は今回はしませんが、JavaScriptにより、米田埋め込み（知らなくていいです！！）の対応物を完全に書き下します。*1

内容：

未来のJavaScript

「みにくいアヒルの子」に書いたような理由で、今回も、説明用擬似コードとしてJavaScriptを使いたいと思います。が、しかし、現状のJavaScriptではなくて、近未来(?)のJavaScritです。その仕様は：

1. 変数、関数の引数、関数の戻り値に型宣言を付けられる。function max(x:Number, y:Number):Number のような感じ。これはJavaScript 2.0ではサポートされるはず。
2. 型パラメータが使え、総称型（型パラメータ付きの型）、総称関数（型パラメータ付きの関数）が使える。

型パラメータについてちょっと説明します。例えば、文字列の配列は Array<String> と書くことにします。このとき、Stringは型パラメータです。単にArrayと書くよりずっと正確に型を指定できますね。

Array<String> の場合は、「Stringが型パラメータ」とは言っても、Stringは既に定まった型でした。型パラメータの本領が発揮されるのは、「なんだかわからないが、とある型X」を使って Array<X> のような書き方をしたときです。このときのXは、まだ不定の型ですが、それでも「とある型を要素とする配列」という意味を持ちます。

ただし、Xが、ほんとにXという名前のユーザー定義の型である可能性もありますので、「既に定まった型ではなくて不定なんだぞ！」と強調する目的で、<X> Array<X>と、直前に<X>を付けることもあります。これは、ラムダ式 λx.f(x) において、式f(x)内の変数xをラムダ記号で束縛するのと同じです。不定の型パラメータを持つ型を総称型と呼びます*2。

総称関数とは、不定の型パラメータを含むような関数です*3。例えば、Array2<X, Y> を第1要素がX型で第2要素がY型である配列の型（型パラメータを２つもつ総称型ですね）だとして、

function
makePair(first:X, second:Y):Array2<X, Y> {
  return [first, second];
}

は、型パラメータX、Yを含む総称関数です。ここでも、XとYが「不定なんだぞ！」と示すために次の書き方を採用することにしましょう。

function<X, Y> 
makePair(first:X, second:Y):Array2<X, Y> {
  return [first, second];
}

function<X, Y>は、後続の関数定義内に登場するすべてのX、Yを束縛します -- 束縛の機構は、λ(x, y).(2x + y) なんかと同じです。

総称関数に実際の引数を渡して呼び出すには、不定の型パラメータを具体化しなくてはなりませんが、呼び出しのタイミングで、引数の型に応じて具体化がされると考えてください。上の例のmakePairでは、型を無視した1個の関数により総称関数が実現されてしまいますが、型パラメータX, Yが具体化された形の関数がイッパイあって、その全体（関数の束）が総称関数だと思ってください。

CPS（継続渡し方式）への書き換え

lengthを、文字列の長さを返す関数だとします。length:String -> Integer のような書き方で、「関数lengthは、String型引数を取り、Integer型の値を返す」ことを表すとします。String -> Integer の部分を関数のプロファイルと呼びましょう。

さて、次のコードを考えます。

var n:Integer;
n = length("Hello");
// ...
// nを使って何かする。
// ...

ここで、「nを使って何かする」の部分を、doUsefulThing(n:Integer)という関数にまとめれば、

var n:Integer;
n = length("Hello");
doUsefulThing(n);

doUsefulThingは、lengthの結果を使って続きの処理をするので、lengthに対する継続処理関数と呼ぶことにします。もちろん、前もってプログラム全体の処理がわかってないと、「lengthの後に何をやるか」も不明なので、プログラム全体との関係で「lengthに対する継続処理関数」が決まります。

ここで、次の関数を作ります。型宣言されてないcontは、関数引数です（型宣言の詳細は後述）。

function
doSomethingWithLength(cont, str:String):Void {
  var n:Integer = length(str);
  cont(n);
}

このdoSomethingWithLengthを使うと、先のコードは次のように書き換えられます。

doSomethingWithLength(doUsefulThing, "Hello");

ここで、doSomethingWithLengthの第1引数が継続処理関数であり、第2引数がlengthに渡す文字列であることに注目してください。継続処理関数を単に継続（continuation）とも呼ぶので、次の書き換えを継続渡し方式（continuation passing style; CPS）への書き換えと呼びます。

• 「lengthの呼び出し＋継続処理」 → 「doSomethingWithLength(継続処理関数, lengthへの引数)」

もっと系統的にCPSへと変換する

前節のdoSomethingWithLengthの定義で、第1引数のcont（継続でした）の型宣言がありません。それをここで考えましょう。cont（に入るべきもの）は、関数であり、lengthの戻り値である整数を引数にとり、戻り値はありません。つまり、cont:Integer -> Void です。contのプロファイルである Integer -> Void は関数の型（高階の型）なので、プロファイルの記法をそのまま“型の表現”としても採用しましょう。

すると、doSomethingWithLength(cont:Integer->Void, str:String):Void となります。

いや、待ってください。contはいつでも戻り値なし（戻り値Void型）でいいのでしょうか？ 例えば、次のコードを継続渡し方式に変換することを考えてください。

var n:Integer;
n = length("Hello");
var x:Integer;
x = n - 1;

当然これは次のようにしたいですよね。

var x:Integer;
x = doSomethingWithLength(decrement, "Hello");

となると、関数doSomethingWithLengthは、その第1引数（継続です）の型に応じて戻り値の型が変動するような関数です。型が変動する -- そう、型パラメータの出番ですぜ、ダンナ。

function<X>
doSomethingWithLength(cont:Integer->X, str:String):X {
  return cont(length(str));
}

ここまでの話に出てきた未来JavaScriptのコードは、型宣言を省くと今のJavaScriptでも動きます。試してください。

function
doSomethingWithLength(cont, str) {
  return cont(length(str));
}

function
decrement(n) {
  return n -1;
}

var x;
x = doSomethingWithLength(decrement, "Hello");

// x == 4

もっともっと系統的にCPSへと変換する

前節までの話は、length:String -> Integer という関数を固定してのことです。length以外の関数に対しても、CPSへの変換（書き換え）をできるようにしましょう。

その前に言葉の準備； ここだけの用語法ですが、lengthのように、継続処理関数の直前に呼び出される（そして、その値は継続に渡される）関数を先行関数と呼びましょう。先行関数を呼び出し、その値を継続処理関数に渡す仕事をするdoSomethingWithLengthのような関数（高階関数）を継続処理メタ関数と呼ぶことにします。

この言葉使いで、前節でやったことをまとめると：

• 先行関数はlength:String -> Integer だけを考えた。
• lengthを先行関数とする継続（継続処理の実行関数）は、引数の型がIntegerであり、戻り値型は任意。
• 以上の前提で、総称関数doSomethingWithLengthを書いた。

ここからは、任意の先行関数hogeに対して、継続処理メタ関数doSomethingWith_hogeを書くのが目的です。実はこれは簡単で、先行関数hogeが hoge:A -> B というプロファイルを持つなら、

function<X>
doSomethingWith_hoge(cont:B->X, arg:A):X {
  return cont(hoge(arg));
}

とするだけです。

もし、次のtwice:String -> String という関数に対してdoSomethingWith_twiceを書くなら、下のようになります。

function
twice(str:String):String {
  return str + str;
}

function<X>
doSomethingWith_twice(cont:String->X, arg:String):X {
  return cont(twice(arg));
}

今のJavaScriptに直してのコンソール実行例は：

js> doSomethingWith_twice(length, "Hello")
10

カリー化登場

理論的な扱いを単純化するために、すべての関数を1引数にしましょう。そう、カリー化すればいいんですね。継続処理メタ関数であるdoSomethingWith_length（話の流れ上、Lengthから_lengthに変更）、doSomethingWith_twiceが2引数関数だったんで、これを継続だけを受け取る1引数関数に書き直しましょう。

なーに、たいしたことありません。

function<X>
doSomethingWith_length(cont:Integer->X):String->X {
  return function(str:String) {return cont(length(str))};
}

function<X>
doSomethingWith_twice(cont:String->X):String->X {
  return function(arg:String) {return cont(twice(arg))};
}

今のJavaScriptで書くなら：

function
doSomethingWith_length(cont) {
  return function(str) {return cont(length(str))};
}

function
doSomethingWith_twice(cont) {
  return function(arg) {return cont(twice(arg))};
}

ちゃんと動きますよ。

js> doSomethingWith_length(decrement)("Hello")
4
js> doSomethingWith_twice(length)("Hello")
10

CPS変換を行うメタメタ関数

さて、今までの話で僕たちは、与えられた先行関数（例えばlengthやtwice）から、それに対応する継続処理メタ関数を書き下しました。先行関数lengthに対してメタ関数doSomethingWith_length、先行関数twiceに対してはメタ関数doSomethingWith_twice、という具合に。

人手でCPSへの変換ができるなら、その手順を関数として書き下すこともできるはずですね。つまり、先行関数を引数にとって対応する継続処理メタ関数を作り出す関数（値がメタ関数ですからメタメタ関数ですね）を書いてみます。

その関数を cpsTransformだとすると、cpsTransformのプロファイルは

• (A->B) -> ((B->X)->(A->X))

です。わかりますか？ (A->B)が先行関数の型です。先行関数がlengthなら、(String->Integer)と具体化されます。継続処理メタ関数は、型が(B->X)である継続を受け取って、型が(A->X)である関数を返します（カリー化していますよ）。つまり、継続処理メタ関数の型は ((B->X)->(A->X) ですね。よって、CPS変換を行うメタメタ関数のプロファイルは (A->B) -> ((B->X)->(A->X)) ってわけです。念のためまとめれば：

1. 先行関数 : (A->B)
2. 継続 : (B->X)
3. 継続処理メタ関数の戻り値 : (A->X)
4. 継続処理メタ関数 : ((B->X)->(A->X))
5. CPS変換メタメタ関数 : (A->B) -> ((B->X)->(A->X))

function<A, B, X>
cpsTransform(prec:A->B):(B->X)->(A->X) {
  return function(cont:B->X):A->X {
           return function(arg:A):X {return cont(prec(arg))};
         };
}

今のJavaScriptならば次です。

function
cpsTransform(prec) {
  return function(cont) {
           return function(arg) {return cont(prec(arg))};
         };
}

js> var cps_length = cpsTransform(length)
js> cps_length(decrement)("Hello")
4
js> var cps_twice = cpsTransform(twice)
js> cps_twice(length)("Hello")
10

そしてそれから

ここまで来れば、cpsTransformが、集合圏の適当な部分圏Cから、関手圏[C^op, Set]への関手を表現していることを確認するのは容易です（定義を知っていれば）。型はCの対象、関数はCの射、メタ関数は関手圏の対象、メタメタ関数が関手圏の射になります。

そして、cpsTransformの定義をていねいに追いかければ、それが米田埋め込みとまったく同じであることが判明するわけですが、それはまたの機会に。

最後に一言注意： この記事では、カレント継続をキャプチャする機能にはまったく触れませんでした。現実のプログラミング言語では、このキャプチャ機能が重要になります。

参考：

• ラムダ計算 →JavaScriptで学ぶ・プログラマのためのラムダ計算 - 檜山正幸のキマイラ飼育記 (はてなBlog)
• ラムダ計算 →絵を描いて学ぶ・プログラマのためのラムダ計算 - 檜山正幸のキマイラ飼育記 (はてなBlog)
• 圏論 →はじめての圏論 その第1歩：しりとりの圏 - 檜山正幸のキマイラ飼育記 (はてなBlog)
• 米田の補題 →圏論番外：米田の補題に向けてのオシャベリ - 檜山正幸のキマイラ飼育記 (はてなBlog)
• 米田の補題 →圏論番外：米田の補題の周辺から - 檜山正幸のキマイラ飼育記 (はてなBlog)
• 米田埋め込み →圏論番外：米田埋め込み (前編) - 檜山正幸のキマイラ飼育記 (はてなBlog)
• 継続 →非同期呼び出しって継続っぽい -- 時間軸を加工する話 - 檜山正幸のキマイラ飼育記 (はてなBlog)
• カリー化 →JavaScriptでカリー化 - 檜山正幸のキマイラ飼育記 (はてなBlog)
• カリー化 →もっとかしこいカリー化 - 檜山正幸のキマイラ飼育記 (はてなBlog)
• デカルト圏 →なぜ「光が影を作ること」と「主張の一部を再主張すること」が関係するのか；あるいは、デカルト圏入門 - 檜山正幸のキマイラ飼育記 (はてなBlog)
• デカルト閉圏 →圏論的指数の周辺：ラムダ計算、デカルト閉圏、ノイマン型コンピュータ - 檜山正幸のキマイラ飼育記 (はてなBlog)
• デカルト閉圏 →モノイド圏、豊饒圏、閉圏と内部ホム - 檜山正幸のキマイラ飼育記 (はてなBlog)

*1:僕は栃木県出身なので、タイトルの北関東弁が本物であることに自信があります。

*2:不定の型パラメータを持たない場合でも、不定の型パラメータが0個の総称型と考えることもあります。定数を引数なし関数とみなすのと同じです。

*3:「総称関数」という言葉を別な意味で使うこともありますが、この記事内では具体化されてない型パラメータを含む関数です。