「継続渡しスタイル」の魔術

■魔術的コード
------------------------------

以下のコードを見てほしい。

```javascript
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した後でコンソール出力を実行する、単純な例を見てみよう。

```javascript
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` を実行してコンソールに結果を出力できる。

```javascript
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`という引数名で書くらしいので、以降はそれに従うことにする。

```javascript
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してコンソール出力する処理」に置き換えればよい。

```javascript
inc = (n, cont) => cont( n + 1 );
inc(1, n1 => inc(n1, n2 => inc(n2, console.log))); // 1+1+1+1=4が出力される
```

あとはこれを好きなだけ繰り返して書けば、長い処理も実行できるし、別の演算をする関数を入れることもできる。

```javascript
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

……うん。
当然まともなアタマでこんな複雑な入れ子構造を管理するのは不可能だ。
どうにかしてもっと簡単にできないか？

最初に「魔術」のコード例を出しているので既に察していると思うけれど、カリー化を使うと分かりやすい形にできる。
念のため説明すると、カリー化とは関数を以下のように形式変換することだ。

```javascript
// カリー化されていない関数
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
```

さて再び簡単な例に戻って考えてみよう。

```javascript
// カリー化前
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)`が評価される。

次の例を見てみよう。

```javascript
// カリー化前
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を渡して実行する関数」を返す処理を用意する。
つまりこうだ。

```javascript
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)`と書いても同じ意味なので全部括弧でくくってしまうと綺麗に見える。

```javascript
(val)(1)(inc)(inc)(console.log); // 1+1+1=3が出力される
```

以上で、最初に提示した魔術の理解ができるようになったと思う。



■使い所など
------------------------------

### 使い所

継続渡しスタイルは「継続を渡して実行する」を繰り返しているだけなので、途中で停止することも自由である。
再帰をステップごとに停止して処理させたい場合などに使える。

ただ現代的にはasync/awaitが「進化した継続」として便利に使えるようになっているため、実際の使い所はそんなになさそう。

```javascript
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が表示される
```

```javascript
// 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/

継続はただでさえアタマが混乱するが再帰だとさらに混乱する。
考え方としては「最後に実行される処理ほど内側にある、再帰的な入れ子構造の関数」である継続を作って、一番底の再帰で作られた継続を実行することで、『「入れ子構造の関数呼び出し」に渡す引数が』外側から評価されていくことで、順に実行がされる……とういうことだと思う。


### 継続を第二引数で渡すスタイルを、カリー化された関数に渡すスタイルに変換する説明

以下の様に、継続を第二引数で渡すスタイルは、意味を変えずに継続をカリー化された関数に渡すスタイルに変換できる。
まずは継続を第二引数で渡すスタイルが以下。

```javascript
inc = (n, cont) => cont(n+1);
inc(1, n=>inc(n, console.log));
```

「継続」を即座に実行するのではなく、継続を実行する関数オブジェクトを返すように変える。
（呼び出し側で、戻された関数オブジェクトを実行して継続を実行する）

```javascript
inc = (n, cont) => { return () => cont(n+1) };
inc(1, n=>inc(n, console.log))()();
// inc(1, n=>inc(n, console.log))……は、継続を実行する関数を返す
// その関数を「()」で実行すると、さらに継続を実行する関数を返す
// その関数を「()」で実行すると、console.logが実行される
//
// ちなみに継続を第二引数で渡すスタイルは、関数の中で関数を呼んで、その関数の中で関数を呼んで……というロジックのため
// 継続を引き継ぐ回数分ほど関数のコールスタックが深くなっていた。
// しかしこの変換により毎回関数を抜けるようになるため、コールスタックを1段階しか使わなくなった。
```

実行する継続を、実行時に指定できるように書き換える。

```javascript
inc = (n) => { return (cont) => cont(n+1) };
inc(1)(n=>inc(n)(console.log));
```

意味を変えずにコードを整理する。
結果、継続をカリー化された関数に渡すスタイルになる。

```javascript
inc = n => cont => cont(n+1);
inc(1)(inc)(console.log);
```



■メモ
------------------------------

```javascript
// 再帰カウント・カリー化スタイル
// 考え方としては、
// 　fの第二引数に「次の処理関数」を書く。
// 　「次の処理関数」の引数には「これまでの計算結果」が渡される。
f = n => cont => n==1 ? cont(1) : f(n-1)(x=>cont(x+n));
f(3)(console.log); // →6
```

```javascript
// 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
```

```javascript
// 以下は、最終的にはどう評価されるか
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