■魔術的コード
以下のコードを見てほしい。
val = n => cont => cont(n);
add = n1 => n2 => cont => cont(n1 + n2);
(val)(2)(add)(3)(console.log);
初見では完全に魔術に見えるが、このコードは意図した通りコンソールに 5 を出力する。
一体なぜこのような動きが実現できるのだろうか？
■説明
この魔術は「継続渡しスタイル (CPS: Continuation-passing style)」という概念をもとに実現されている。
ステップ・バイ・ステップで理解していこう。
step1
継続渡しスタイルでは「この処理の後で実行する内容」を引数に渡して実行する。
渡された数に+1した後でコンソール出力を実行する、単純な例を見てみよう。
function inc(n, callback) {
const result = n + 1;
callback( result );
}
inc(1, console.log); // 1+1=2が出力される
何も不思議なところは無いように見える。
step2
では次に inc で+1した数字に、さらに inc を実行してコンソール出力するにはどうすればいいか考えてみよう。(元の数+1+1を出力する)
継続渡しスタイルでは「この処理の後で実行する内容」を引数に渡して実行する。
つまりincのcallback引数に「渡された数を+1してコンソール出力する処理」を指定すれば、incで+1した数字に対してさらに「渡された数を+1してコンソール出力する処理」を実行できる。
「渡された数を+1してconsole.logで出力する処理」のロジックは、上の例で既に作っている。
inc(1, console.log)……だ。
この例では固定値1を処理してしまっているので、少し改造して「渡された数を+1してコンソール出力する処理」を作ろう。
function (n) { inc(n, console.log); }……となる。
これをcallbackに渡せば、 inc の結果の数値に、さらに inc を実行してコンソールに結果を出力できる。
function inc(n, callback) {
const result = n + 1;
callback( result );
}
arg1 = 1;
arg2 = function (n) { inc(n, console.log); };
inc(arg1, arg2); // 1+1+1=3が出力される
ちょっと長いので、整理して、アロー関数も使って短く書き直そう。
またプログラミング言語Schemeでは、継続渡しスタイルの「この処理の後で実行する内容」＝「継続 (continuation)」をcontという引数名で書くらしいので、以降はそれに従うことにする。
inc = (n, cont) => cont( n + 1 );
inc(1, n => inc(n, console.log)); // 1+1+1=3が出力される
さらにincをもう一つ重ねるにはどうすればいいか？
ちょっと複雑だが「この処理の後で実行する内容」を関数の引数に渡して実行するというルールをもとに考えよう。
inc(1, n => inc(n, console.log));のconsole.logの部分を「渡された数を+1してコンソール出力する処理」に置き換えればよい。
inc = (n, cont) => cont( n + 1 );
inc(1, n1 => inc(n1, n2 => inc(n2, console.log))); // 1+1+1+1=4が出力される
あとはこれを好きなだけ繰り返して書けば、長い処理も実行できるし、別の演算をする関数を入れることもできる。
inc = (n, cont) => cont( n + 1 );
double = (n, cont) => cont( n * 2 );
inc(5, n1 => double(n1, n2 => inc(n2, n3 => double(n3, console.log)))); // ((5+1)*2+1)*2=26が出力される
step3
……うん。
当然まともなアタマでこんな複雑な入れ子構造を管理するのは不可能だ。
どうにかしてもっと簡単にできないか？
最初に「魔術」のコード例を出しているので既に察していると思うけれど、カリー化を使うと分かりやすい形にできる。
念のため説明すると、カリー化とは関数を以下のように形式変換することだ。
// カリー化されていない関数
function add(n1, n2) { return n1 + n2; }
add(2, 3); // 結果は5
// カリー化した関数
function add(n1) {
return function (n2) {
return n1 + n2;
};
}
add(2)(3); // 結果は5
// アロー関数を使って綺麗に書いたカリー化(functionを使って書いた場合と意味は変わらない)
add = n1 => n2 => n1 + n2;
add(2)(3); // 結果は5
さて再び簡単な例に戻って考えてみよう。
// カリー化前
inc = (n, cont) => cont(n + 1);
inc(1, console.log); // 1+1=2が出力される
// カリー化後
inc = n => cont => cont(n + 1);
inc(1)(console.log); // 1+1=2が出力される
あまり変わっていないように見える。
しかし重要なのはカリー化したことによって、incに1つ引数を渡して評価する(例えばinc(1)を評価する)と戻り値で「『cont引数＝この処理の後で実行する内容』に(1+1の結果の2)を渡して実行する関数」という関数が得られる、という点だ。
上の例の場合、得られた関数に渡す「この処理の後で実行する内容」はconsole.logである。
つまりconsole.log(2)が評価される。
次の例を見てみよう。
// カリー化前
inc = (n, cont) => cont( n + 1 );
inc(1, n => inc(n, console.log)); // 1+1+1=3が出力される
// カリー化後
inc = n => cont => cont(n + 1);
inc(1)(inc)(console.log); // 1+1+1=3が出力される
まずinc(1)が評価されて「『この処理の後で実行する内容』に(1+1の結果の2)を渡して実行する関数」になる。
今回は次に渡される「この処理の後で実行する内容」はincである。
つまりinc(2)が評価される。
評価結果は「『この処理の後で実行する内容』に(2+1の結果の3)を渡して実行する関数」になる。
さらに次に渡される「この処理の後で実行する内容」はconsole.logである。
つまりconsole.log(3)が評価される。
あとは幾つ処理を重ねようが同じことだ。
こうして無事、カリー化によって見た目の単純化が行えることになった。
step4
もうちょっとだけ見た目を綺麗にするために、単純に渡された値をそのまま使う「『この処理の後で実行する内容』にNを渡して実行する関数」を返す処理を用意する。
つまりこうだ。
val = n => cont => cont(n);
inc = n => cont => cont(n + 1);
val(1)(inc)(inc)(console.log); // 1+1+1=3が出力される
val(1)は(val)(1)と書いても同じ意味なので全部括弧でくくってしまうと綺麗に見える。
(val)(1)(inc)(inc)(console.log); // 1+1+1=3が出力される
以上で、最初に提示した魔術の理解ができるようになったと思う。
■使い所など
使い所
継続渡しスタイルは「継続を渡して実行する」を繰り返しているだけなので、途中で停止することも自由である。
再帰をステップごとに停止して処理させたい場合などに使える。
ただ現代的にはasync/awaitが「進化した継続」として便利に使えるようになっているため、実際の使い所はそんなになさそう。
val = n => cont => cont(n);
add = n1 => n2 => cont => cont(n1 + n2);
step = cont => cont;
step = step(val);
step = step(2);
step = step(add);
step = step(3);
step = step(console.log); // 5が表示される
// 1～nの合計を再帰的に求める関数
// 再帰スタイルだと計算を中断できない
function f(n) {
if (n==0) {
return 0;
} else {
return n + f(n-1);
}
}
// 継続渡しスタイルに変換（このままでは中断はできない）
function f(n, cont) {
if (n==0) {
cont(0);
} else {
f(n-1, x => cont(n + x));
}
}
// 継続渡しスタイルを少し改良して「継続を渡して実行する」を返すようにすれば１ステップごとに中断・再開できる
function f(n, cont) {
console.log(`run: f(${n})`);
if (n==0) {
cont(0);
return null;
} else {
// f(n-1, x => cont(n + x));
return () => f(n-1, x => cont(n + x));
}
}
// step = f(3, console.log); // run: f(3)
// step = step(); // run: f(2)
// step = step(); // run: f(1)
// step = step(); // run: f(0)
// // console.log出力: 6
"継続"という概念
例えば関数呼び出しのような他の処理が終わったあとで、現在の計算を続行するための情報が「継続」。
１つの実装を指す言葉ではなく、例えばそれは次に実行するべきプログラムのGOTOラベル名だったり、後で実行する処理が書かれた関数オブジェクトだったりする。
実行中だった処理内で持っていたローカル変数や、処理が別の関数から呼び出されていたら呼び出し元から渡された継続も「継続」の一部として必要である。
概念としては実はプログラミング言語の黎明期から存在していて「継続渡しスタイル」の実装も1994年にはすでに存在したようだ。
再帰の継続渡しスタイルの理解の仕方
「継続では、ある意味、自分の頭の上に立って自分自身を裏返しにするようなことをしなければならない。」
https://matarillo.com/async/cps04/
継続はただでさえアタマが混乱するが再帰だとさらに混乱する。
考え方としては「最後に実行される処理ほど内側にある、再帰的な入れ子構造の関数」である継続を作って、一番底の再帰で作られた継続を実行することで、『「入れ子構造の関数呼び出し」に渡す引数が』外側から評価されていくことで、順に実行がされる……とういうことだと思う。
継続を第二引数で渡すスタイルを、カリー化された関数に渡すスタイルに変換する説明
以下の様に、継続を第二引数で渡すスタイルは、意味を変えずに継続をカリー化された関数に渡すスタイルに変換できる。
まずは継続を第二引数で渡すスタイルが以下。
inc = (n, cont) => cont(n+1);
inc(1, n=>inc(n, console.log));
「継続」を即座に実行するのではなく、継続を実行する関数オブジェクトを返すように変える。
（呼び出し側で、戻された関数オブジェクトを実行して継続を実行する）
inc = (n, cont) => { return () => cont(n+1) };
inc(1, n=>inc(n, console.log))()();
// inc(1, n=>inc(n, console.log))……は、継続を実行する関数を返す
// その関数を「()」で実行すると、さらに継続を実行する関数を返す
// その関数を「()」で実行すると、console.logが実行される
//
// ちなみに継続を第二引数で渡すスタイルは、関数の中で関数を呼んで、その関数の中で関数を呼んで……というロジックのため
// 継続を引き継ぐ回数分ほど関数のコールスタックが深くなっていた。
// しかしこの変換により毎回関数を抜けるようになるため、コールスタックを1段階しか使わなくなった。
実行する継続を、実行時に指定できるように書き換える。
inc = (n) => { return (cont) => cont(n+1) };
inc(1)(n=>inc(n)(console.log));
意味を変えずにコードを整理する。
結果、継続をカリー化された関数に渡すスタイルになる。
inc = n => cont => cont(n+1);
inc(1)(inc)(console.log);
■メモ
// 再帰カウント・カリー化スタイル
// 考え方としては、
// fの第二引数に「次の処理関数」を書く。
// 「次の処理関数」の引数には「これまでの計算結果」が渡される。
f = n => cont => n==1 ? cont(1) : f(n-1)(x=>cont(x+n));
f(3)(console.log); // →6
// 2分岐のツリーノード数を数える再帰・カリー化スタイル
f = t => cont => !Array.isArray(t) ? cont(1) : f(t[0])( n1 => f(t[1])( n2=>cont(n1+n2) ) );
f( [ [ ["a","b"], "c" ], ["d","e"] ] )(console.log); // →5
// 以下は、最終的にはどう評価されるか
inc = (n, cont) => cont(n+1);
inc(10, x => inc(x, x => console.log(x) ) );
// こうなる
( x => ( x => ( x => console.log(x) )(x+1) )(x+1) )(10);
■参考サイト
なんでも継続
https://practical-scheme.net/docs/cont-j.html
継続渡しスタイル(CPS)と非同期構文(async/await)
https://matarillo.com/async/
CPS 変換による末尾再帰化 > カリー化
https://qiita.com/7shi/items/2d25f7afe25c3ca11acb
JavaScriptによるマルチスレッドの実現‐Concurrent.Threadの裏側 > 継続渡し形式 (CPS)
https://www.infoq.com/jp/articles/js_multithread_2/
Wikipedia: 継続
https://ja.wikipedia.org/wiki/%E7%B6%99%E7%B6%9A