JavaScriptのジェネレータ関数もトランポリンでスタックレス再起できるのか気になったのでやってみた

# 先に結論

**できる。というか、遅延リストじゃん、これ**

例えば、次のようなコードで、非負偶数を無限にコンソールに出力できる。

```.js
const arith = (a, d) => () => GMore(a, arith(a + d, d));
for (const x of gRun(arith(0, 2))) console.log(x);
// 0
// 2
// ...
```


# トランポリンのおさらい

三角数（1 ～ n の総和）を求める関数を、次のような**再帰関数で実装**したとする。

```通常の再帰関数.js
const rTri = n => _rTri(n, 0);
const _rTri = (n, acc) =>
    n <= 0 ? acc : _rTri(n - 1, acc + n);
```

すると、大きな値を渡した瞬間**スタックオーバフローで落ちる**[^1] :innocent:

[^1]: 末尾再帰最適化が有効な場合は、スタックオーバーフローしないが、ここでは無効なものとする

```スタックオーバーフロー.js
rTri(10000); // 50005000
rTri(100000); // スタックオーバフロー
```

どうにか再帰関数っぽく書きつつ**スタックオーバーフローを避ける**ことはできないのか？

そこで颯爽と登場するのが**トランポリン**である。トランポリンを実現する関数は、例えば次のように実装できる。

```トランポリン.js
const TDone = value => (f, _) => f(value);

const TMore = more => (_, f) => f(more);

const tRun = more => {
    let done = false;
    let value;
    while (!done) {
        more()(
            v => {done = true; value = v;},
            m => {more = m;}
        );
    }
    return value;
};
```

さっそく三角数を求める関数を**トランポリンで実装**してみる。
どでかい値を渡しても正しい値が返ってくる。
成功だ、`_tTri`は自分自身を呼び出し**再起しているが、スタックオーバーフローはしない** :tada:


```トランポリンを使った実装.js
const tTri = n => tRun(_tTri(n, 0));
const _tTri = (n, acc) => () =>
    n <= 0 ? TDone(acc) : TMore(_tTri(n - 1, acc + n));

tTri(10000); // 50005000
tTri(100000); // 5000050000
tTri(1000000); // 500000500000
```

これが**トランポリンの魔法**である。魔法の中身については、他の記事に譲ろう。[「トランポリン」の検索結果 - Qiita](https://qiita.com/search?q=%E3%83%88%E3%83%A9%E3%83%B3%E3%83%9D%E3%83%AA%E3%83%B3)。


# ジェネレータ関数のトランポリン

0 ～ n-1 番までの三角数を生成するジェネレータ関数を、次のような**再帰ジェネレータ関数で実装**したとする。

```通常の再帰ジェネレータ関数.js
const rTriGen = n => _rTriGen(n, 0, 0);
const _rTriGen = function* (n, i, acc) {
    if (n <= i) return;
    yield acc;
    yield* _rTriGen(n, i + 1, acc + i + 1);
};
```

すると、大きな値を渡した瞬間**スタックオーバフローで落ちる**。

```スタックオーバーフロー.js
[...rTriGen(10)];
// [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

for (const x of rTriGen(100001)) {}
// スタックオーバーフロー
```

さて、通常の再帰関数と同じように、**ジェネレータ再起関数もトランポリンによってスタックオーバーフローを避ける（スタックレスにする）**ことはできるのだろうか？

通常の再起関数と、ジェネレータ再起関数の違いは値を返却するタイミングである。

* 通常の再帰関数：**再起が終了した最後に**値を返却する
* ジェネレータ再帰関数：**再起するたびに**値を返却する。

上記を考慮して通常のトランポリンを、うまいこと**ジェネレータ関数用のトランポリン**に書き直せばよさそうだ。早速、やってみよう。


```ジェネレータ関数用のトランポリン.js
const GDone = () => (f, _) => f();

const GMore = (value, more) => (_, f) => f(value, more);

const gRun = function* (more) {
    let done = false;
    let value;
    for (;;) {
        more()(
            () => {done = true;},
            (v, m) => {value = v; more = m;}
        )
        if (done) return;
        yield value;
    }
};
```

0 ～ n-1 番までの三角数を生成するジェネレータ関数を**トランポリンで実装**してみる。
どでかい値を渡しても正しい値が返ってくるようになった。
成功だ、`_gTri`は自分自身を呼び出し**再起しているが、スタックオーバーフローはしない** :confetti_ball:

```トランポリンを使ったジェネレータ再帰の実装.js
const gTri = n => gRun(_gTri(n, 0, 0));
const _gTri = (n, i, acc) => () =>
    n <= i ? GDone() : GMore(acc + i, _gTri(n, i + 1, acc + i));

[...gTri(10)];
// [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

let x;
for (x of gTri(100001)) {}
x; // 5000050000
```

# 結論

できる。


# おまけ：遅延リスト

誤解を恐れずに言えば、`GDone`は遅延リストの`Nil`、`GMore`は遅延リストの`Cons`と読み替えられる。

```遅延リスト.js
// [1, 2, 3]
[...gRun(() => GMore(1, () => GMore(2, () => GMore(3, () => GDone()))))]

// 初項 a 、公差 d の等差数列
const arith = (a, d) => () => GMore(a, arith(a + d, d));

// 各項に関数 f を適用した新たな列を得る
const gMap = f => more => () => more()(
    () => GDone(),
    (v, m) => GMore(f(v), gMap(f)(m))
);

// 最初の 0 ～ n - 1 項を取得する
const gTake = n => more => () => n <= 0 ? GDone() : more()(
    () => GDone(),
    (v, m) => GMore(v, gTake(n - 1)(m))
);

// 0 ～ 9 項までの非負偶数
// [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
[...gRun(gTake(10)(arith(0, 2)))]

// 0 ～ 9 項までの非負偶数の自乗数
//  [0, 4, 16, 36, 64, 100, 144, 196, 256, 324]
[...gRun(gTake(10)(gMap(x => x * x)(arith(0, 2))))]
```

以上