継続について調べたメモ
##継続とは
計算機科学における継続（けいぞく、continuation）とは、プログラムの実行においてある時点において評価されていない残りのプログラム（the rest of the program）を意味するものであり、手続き（procedure）として表現されるものである。
文献を紐解くと、 継続とは「これから行われるであろう計算をパッケージ化したもの」とある。
今やってる計算の続きの計算という認識でいいのだろうか。
##例
普通に関数定義して、3*(1+2)を計算する。
> function add(a,b) { return a + b }
> function mul(a,b) { return a * b }
> mul(3, add(1,2))
9
継続を使った例
次の計算を関数として引数に渡すようにする。
// a+bの計算結果を、関数contに渡してその結果を返す関数
> function cadd(a,b,cont) { return cont(a+b) }
// 同掛け算版
> function cmul(a,b,cont) { return cont(a*b) }
> function empty(x) { return x }
//x*3を計算する関数をcaddの第3引数に渡しているのがミソ
> cadd(1,2, function(x) {return cmul(x,3,empty)})
9
- mulの引数にaddの計算結果を渡してmulを計算する
という関数呼び出しの流れが
- caddの引数に、mulを計算する関数を渡す
という具合に変わっている。
##継続モナド
「JavaScriptでの非同期関数合成」を継続モナドで
上記URLからそのまま引用
JSで継続モナドを書いた例
// 継続モナド
function Cont(f) { // f: a -> r -> r
this.run = f;
}
// a.k.a. '>>='
Cont.prototype.bind = function(f) { // f: a -> Cont r b
var run = this.run;
return new Cont(function(k) { return run(function(a) { return f(a).run(k) }) });
}
// a.k.a. 'return'
Cont.unit = function(a) {
return new Cont(function(k) { return k(a) });
}
Cont.callcc = function(f){ // f: a -> Cont r b -> Cont r a
return new Cont(function(k) { return f(function(a) { return new Cont(function(x) { return k(a) }) }).run(k) })
}
- 普通に書いた場合
var square = function (x) { return x*x };
console.log(square(3));
var add1 = function (x) { return x+1 };
console.log(square(add1(3)));
cSquare = function (x, cont) { return cont(x*x) };
cAdd1 = function (x, cont) { return cont(x+1) };
cAdd1(3, function (x) {
return cSquare(x, function (y) {
return y;
});
});
これ以上やると、どんどんインデントが深くなって、読むのが辛くなる予感がする。
- 継続モナドを使った場合
var squareCont = function (x) { return Cont.unit(x * x) }
squareCont(3).run(console.log); // 9
var add1Cont = function (x) { return Cont.unit(x + 1) }
// 「3に」「1を足して」「2乗して」「印字」
Cont.unit(3).bind(add1Cont).bind(squareCont).run(console.log); // 16
すっきり書ける！スゴイ！
###例1
Contの定義を読んでも、functionとnew Contがたくさんあって、パッと見何をやってるのかわかりにくかったので、例を挙げて処理を追ってみた。
// 上の方で定義したContを使うよ
var squareCont = function (x) { return Cont.unit(x * x) }
squareCont(3).run(console.log); // 9
を評価したときの処理の流れを追う。
- squareCont(3)が返しているのは
Cont.unit(3*3)
- Cont.unit(3*3)は、
Cont(function(k) { return k(9) })
を返している。
これをrun(console.log)すると、Cont.runつまりContのコンストラクタで渡した
function(k) { return k(9) }
が実行される。
引数kはconsole.logなので、
console.log(9)
が実行され、9が表示される。
###例2
同じく上のURLからもうちょっと長い式の例
var add1Cont = function (x) { return Cont.unit(x + 1) }
// 「3に」「1を足して」「2乗して」「印字」
Cont.unit(3).bind(add1Cont).bind(squareCont).run(console.log); // 16
分かりやすさのため、一個づつ変数代入する形に変更。
var a = Cont.unit(3);
//Cont(function(k) { return k(3) });
var b = a.bind(add1Cont);
//Cont(function(k) {
// return run(function(a) { return add1Cont(a).run(k) }) }
//);
//runは上のfunction(k) { return k(3) }
上の式を整理すると、
Cont(function(k) {
return add1Cont(3).run(k)
});
var c = b.bind(squareCont);
//Cont(function(k) {
// return run(function(a) {
// return squareCont(a).run(k);
// });
//});
//ここでのrunは、上のfunction(k) { return add1Cont(3).run(k) }
さっきと同じように、式整理すると、
Cont(function(k) {
return add1Cont(3).run(function(a) {
return squareCont(a).run(k)
});
});
最後に、
c.run(console.log);
すると、
またゴリゴリと式展開する作業
add1Cont(3).run(function(a) {
return squareCont(a).run(console.log)
})
add1Cont(3)を展開
Cont(function(k) { return k(4) }).run(function(a) {
return squareCont(a).run(console.log)
});
一番外側のrunを評価
squareCont(4).run(console.log)
更にsquareCont(4)
Cont(function(k) {
return k(4*4);
}).run(console.log);
console.log(16)
と、console.log(16)まで辿りつけた。