JavaScriptで不動点演算子を改造してスタックオーバーフローを回避したメモ化再帰を書く


次の`fibR`はフィボナッチ数を求める再帰関数を素朴に実装したものだよ！

```.js
const fibR = n => (n === 0 || n === 1) ? n : fibR(n - 1) + fibR(n - 2);
```

謎の関数`fix`を使って、ほとんど同じように[フィボナッチ数](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0)を求める再帰関数`fibM`を定義してみるよ！！

```.js
const fibM = fix(f => n => (n === 0 || n === 1) ? n : f(n - 1) + f(n - 2));
```

あら不思議！！！`fibR`に比べて`fibM`ってば**爆速**！！！！！！

もしかして、[竹内関数](https://ja.wikipedia.org/wiki/%E7%AB%B9%E5%86%85%E9%96%A2%E6%95%B0)も早くなる？？？

```.js
const taraiR = (x, y, z) => x <= y ? y : taraiR(taraiR(x - 1, y , z), taraiR(y - 1, z, x), taraiR(z - 1, x, y));
const taraiM = fix(t => (x, y, z) => x <= y ? y : t(t(x - 1, y , z), t(y - 1, z, x), t(z - 1, x, y)));
```

やっぱり、`taraiR`に比べて`fix`を使った`taraiM`ってば**爆速**！！！
しかも、`taraiR(10000, 0, 0)`はスタックオーバーフローを起こしちゃうのに、`taraiM(10000, 0, 0)`も`taraiM(100000, 0, 0)`もちゃんと動く！！！**スタックオーバーフローが起こらない**なんてすごい！！！！！！！！


・・・といった感動を与えてくれる`fix`を実装してみます。


# とりあえず`fix`の実装を見てくれ

うん。事前知識無しに読めたもんじゃない。

試しに動かしてみたい人はコピペしてくれ。ただ、普段JavaScriptを使ってないので手元Chromeでしか動作確認してないんだ。君のところの環境で動かなかったらごめん。

```.js
const fix = f => (...args) => {
  const stack = [args];
  const memo = new Map;

  const rec = rec => f((...args) => {
    stack.push(args);
  
    const key = JSON.stringify(args);
    if (! memo.has(key)) {
      memo.set(key, rec(rec)(...args));
    }
    
    stack.pop();
    return memo.get(key);
  });

  const errKey = new Set;
  while (stack.length > 0) {
    try {
      rec(rec)(...stack.pop());
    } catch (e) {
      // 実行環境によってスタックオーバーフローか否かの判定を変えないと動かない
      if (e.name !== "RangeError" || e.message !== "Maximum call stack size exceeded") {
        throw e;
      }

      const eKey = JSON.stringify(stack[stack.length - 1]);
      if (errKey.has(eKey)) {
        throw e;
      }
      errKey.add(eKey);
    }
  }

  return rec(rec)(...args);
};
```

# 不動点演算子

世の中には[不動点演算子](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF)というものがあって。不動点演算子を使うとアロー関数式（or 無名関数）だけで再帰関数が作れることが知られている。

例えば、Zコンビネータと呼ばれる不動点演算子は次のように実装できる。

```.js
f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)));
```

このZコンビネータを使うと、階乗の再帰関数を次のように実装できる。コンソールで試すとわかるが、マジで動く。

```.js
(f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))(f => n => n < 1 ? 1 : n * f(n - 1));
```


# `fix`の導出

Zコンビネータを変形して、`fix`を導出する。


## Zコンビネータを読みやすくする

Zコンビネータはそのままだと何が何だかわからないので、少し見やすくする。

```.js
f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)));
```

まず、`x => f(y => x(x)(y))`が重複しているので、変数に格納することで冗長性を排除する。

```.js
f => {
  const x = x => f(y => x(x)(y));
  return x(x);
};
```

変数名がわかりづらいので変更する。`x(x)`が再帰関数に相当するので`x`を`rec`（recursive）に変更する。`y`が再帰関数の引数に相当するので`arg`（argument）に変更する。

```.js
f => {
  const rec = rec => f(arg => rec(rec)(arg));
  return rec(rec);
};
```



## 可変長の引数に対応する

竹内関数のように再帰関数の引数は１つとは限らない。再帰関数の引数が何個であっても対応できるよう、`arg`を`...args`（Restパラメータ、Spread構文）に変更する。

```.js
f => {
  const rec = rec => f((...args) => rec(rec)(...args));
  return rec(rec);
};
```


## メモ化する

次はメモ化を目指す。とりあえずメモ用の変数`memo`を定義しておく。

```.js
f => {
  const memo = new Map;
  const rec = rec => f((...args) => rec(rec)(...args));
  return rec(rec);
};
```

メモ化のキーとしてJSON文字列可した`args`を使うことにする。（注：JSON文字列可すると等価判定が狂う値が適用された場合、正常にメモ化できない。また、JSON文字列可に時間がかかる値が適用された場合、動作が遅くなる。）

```.js
f => {
  const memo = new Map;

  const rec = rec => f((...args) => {
    const key = JSON.stringify(args); 
    return rec(rec)(...args);
  });

  return rec(rec);
};
```

未計算であれば計算結果をメモし、メモした値を返却するよう変形する。

```.js
f => {
  const memo = new Map;

  const rec = rec => f((...args) => {
    const key = JSON.stringify(args); 
    if (! memo.has(key)) {
      memo.set(key, rec(rec)(...args));
    }

    return memo.get(key);
  });

  return rec(rec);
};
```

これでメモ化再帰を定義できるようになった。


## スタックを管理する

実行エンジンが面倒を見てくれるコールスタックがあふれてしまうのであれば、自前で管理する他ない。ということで、`stack`を用意する。

```.js
f => {
  const stack = [];
  const memo = new Map;

  const rec = rec => f((...args) => {
    const key = JSON.stringify(args); 
    if (! memo.has(key)) {
      memo.set(key, rec(rec)(...args));
    }

    return memo.get(key);
  });

  return rec(rec);
};
```

再帰関数において`stack`に積むべき情報は引数のみなので、計算を開始する前に引数を`push`し、計算が完了した後に引数を`pop`しておく。

```.js
f => {
  const stack = [];
  const memo = new Map;

  const rec = rec => f((...args) => {
    stack.push(args);

    const key = JSON.stringify(args); 
    if (! memo.has(key)) {
      memo.set(key, rec(rec)(...args));
    }

    stack.pop();
    return memo.get(key);
  });

  return rec(rec);
};
```

## スタックオーバーフローを回避する

テキトーに `(() => {let f = () => -f(); f()})()` とか動かせばスタックオーバーフローのエラーメッセージが見れるので、それを元にその環境での判定式が書ける。
下記は、Chromeでの判定例。

```.js
f => (...args) => {
  const stack = [];
  const memo = new Map;

  const rec = rec => f((...args) => {
    stack.push(args);

    const key = JSON.stringify(args); 
    if (! memo.has(key)) {
      memo.set(key, rec(rec)(...args));
    }

    stack.pop();
    return memo.get(key);
  });

  try {
    return rec(rec)(...args);
  } catch (e) {
    // 実行環境によってスタックオーバーフローか否かの判定を変えないと動かない
    if (e.name !== "RangeError" || e.message !== "Maximum call stack size exceeded") {
      throw e; // スタックオーバーフロー以外のエラー
    }

    return "スタックオーバーフロー！！！";
  }
};
```

さて、スタックオーバーフローを捕獲できたので、あとはスタックオーバーフローが起きたあとに自前の`stack`を使って計算を続行させれば良い。


```.js
f => (...args) => {
  const stack = [args];
  const memo = new Map;

  const rec = rec => f((...args) => {
    stack.push(args);

    const key = JSON.stringify(args); 
    if (! memo.has(key)) {
      memo.set(key, rec(rec)(...args));
    }

    stack.pop();
    return memo.get(key);
  });

  while(stack.length > 0) {
    try {
      rec(rec)(...stack.pop());
    } catch (e) {
      // 実行環境によってスタックオーバーフローか否かの判定を変えないと動かない
      if (e.name !== "RangeError" || e.message !== "Maximum call stack size exceeded") {
        throw e;
      }
    }
  }

  return rec(rec)(...args);
};
```

最後に`fix(f => () => f())`のように、同じ引数で２回以上スタックオーバーフローを起こす場合は諦めてスタックオーバーフローの例外を再スローしておく。

```.js
f => (...args) => {
  const stack = [args];
  const memo = new Map;

  const rec = rec => f((...args) => {
    stack.push(args);

    const key = JSON.stringify(args); 
    if (! memo.has(key)) {
      memo.set(key, rec(rec)(...args));
    }

    stack.pop();
    return memo.get(key);
  });

  const errKey = new Set;
  while (stack.length > 0) {
    try {
      rec(rec)(...stack.pop());
    } catch (e) {
      // 実行環境によってスタックオーバーフローか否かの判定を変えないと動かない
      if (e.name !== "RangeError" || e.message !== "Maximum call stack size exceeded") {
        throw e;
      }

      const eKey = JSON.stringify(stack[stack.length - 1]);
      if (errKey.has(eKey)) {
        throw e;
      }
      errKey.add(eKey);
    }
  }

  return rec(rec)(...args);
};
```

以上、導出完了。


# おわり

まぁ、実用性は皆無ですが、面白いところもあるので愛でてやってくだせぇ。