JavaScript で原始再帰計算するじゃん

素数判定できるじゃん
 
- [原始再帰関数(Wikipedia)](https://ja.wikipedia.org/wiki/%E5%8E%9F%E5%A7%8B%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0)
- [再帰的関数論 照井一成(京大の資料)](http://www.kurims.kyoto-u.ac.jp/~cs/cs2011_terui.pdf)


### 表記
- 原始再帰関数を略して PRF と呼ぶじゃん
- PRF は大文字で表すじゃん(`SUCC`, `ZERO`, ...)。

### さいしょの3つ
定数関数と、後続関数と、i番目を取り出す関数は PRF らしいじゃん

```js
const ZERO = () => 0;
const ONE = () => 1;
const TWO = () => 2;
const SUCC = n => n + 1;
const FIRST = (...args) => args[0];
const SECOND = (...args) => args[1];
const THIRD = (...args) => args[2];
```

### つくりかた（合成 と 再帰定義）
PRF を関数合成したのも PRF らしいじゃん

```js
const comp = (f, gs) => (...args) => f(...gs.map(g => g(...args)));
```

ふたつの PRFを使って帰納的に定義したのも PRF らしいじゃん

```js
const pr = (f, g) => {
  const rfn = (...args) => { // args = [...xs, y]
    const xs = args.slice(0, -1);
    const y = args[args.length - 1];
    return y === 0 ? f(...xs) : g(...xs, y - 1, rfn(...xs, y - 1));
  };
  return rfn;
};
```

### どんどん作る
だったらどんどん作れるじゃん

```js
const PLUS = pr(FIRST, comp(SUCC, [THIRD])); // x+(y+1) = (x+y) + 1
const MULT = pr(ZERO, comp(PLUS, [FIRST, THIRD])); // x*(y+1) = x + x*y
const POWER = pr(ONE, comp(MULT, [FIRST, THIRD])); // x^(y+1) = x * x^y
const PRED = pr(ZERO, FIRST); // xs empty, so y-1 is the first
const CSUB = pr(FIRST, comp(PRED, [THIRD])); // x-(y+1) = (x-y) -1
const ABS = comp(PLUS, [CSUB, comp(CSUB, [SECOND, FIRST])]);
const ISZERO = pr(ONE, ZERO); // cfn
const SG = pr(ZERO, ONE); // cfn
const INEQUAL = comp(SG, [ABS]); // cfn
const EQUAL = comp(ISZERO, [ABS]); // cfn
const GE = comp(SG, [comp(CSUB, [comp(SUCC, [SECOND]), FIRST])]); // test b+1-a. cfn
```

### サブルール
作ったのを使って 論理演算や限定量化を扱うルールがつくれるじゃん

```js
const not = cf => comp(ISZERO, [cf]);
const and = (cf1, cf2) => comp(MULT, [cf1, cf2]);
const or = (cf1, cf2) => comp(SG, [comp(PLUS, [cf1, cf2])]);
// someB and everyB are to be derived by induction 
const someB = (bf, cf) => (...args) => {
  let result = 0;
  for (let i = 0; i < bf(...args); i++) result += cf(...args, i);
  return result > 0 ? 1 : 0;
};
const everyB = (bf, cf) => (...args) => {
  let result = 1;
  for (let i = 0; i < bf(...args); i++) result *= cf(...args, i);
  return result;
};
```

### 素数判定
だったら素数判定できるじゃん

```js
const DIVTEST = comp(EQUAL, [FIRST, comp(MULT, [SECOND, THIRD])]); // (a,b,k) => a === kb
const DIV = someB(comp(SUCC, [FIRST]), DIVTEST);
const PTEST = or(comp(EQUAL, [SECOND, ONE]), not(DIV)); // (x,y) -> y=2 or x is not divisible by y
const ISPRIME = and(comp(GE, [TWO, FIRST]), everyB(FIRST, PTEST));
```

### 確認
```js
const range = end => [...Array(end).keys()];
range(20).forEach(i => range(20).forEach(j =>
  console.assert(PLUS(i, j) === i + j, 'oops:plus')));
range(20).forEach(i => range(20).forEach(j =>
  console.assert(MULT(i, j) === i * j, 'oops:mult')));
range(10).forEach(i =>
  console.assert(POWER(2, i) === 2 ** i, 'oops:power'));
range(20).forEach(i =>
  console.assert(PRED(i) === Math.max(i - 1, 0), 'oops:pred'));
range(20).forEach(i => range(20).forEach(j =>
  console.assert(CSUB(i, j) === Math.max(i - j, 0), 'oops:minus')));
range(20).forEach(i => range(20).forEach(j =>
  console.assert(ABS(i, j) === Math.abs(i - j), 'oops:abs')));
range(20).forEach(i =>
  console.assert(ISZERO(i) === (i === 0 ? 1 : 0), 'oops:iszero'));
range(20).forEach(i =>
  console.assert(SG(i) === (i === 0 ? 0 : 1), 'oops:sg'));
range(20).forEach(i => range(20).forEach(j =>
  console.assert(EQUAL(i, j) === (i === j ? 1 : 0), 'oops:eq')));
range(20).forEach(i => range(20).forEach(j =>
  console.assert(INEQUAL(i, j) === (i !== j ? 1 : 0), 'oops:eqn')));
range(20).forEach(i => range(20).forEach(j =>
  console.assert(GE(i, j) === (i <= j ? 1 : 0), 'oops:ge')));
range(20).forEach(i => range(20).forEach(j => // j should not be zero
  console.assert(DIV(i, j + 1) === (i % (j + 1) === 0 ? 1 : 0), `oops:div${i},${j + 1}`)));
const primes = [2, 3, 5, 7, 11, 13, 17, 19];
range(20).forEach(n =>
  console.assert(ISPRIME(n) === (primes.includes(n) ? 1 : 0), `oops:prime${n}`));
```

### おまけ

```js
const byCase = (f1, f2, cfn) => comp(PLUS, [
  comp(MULT, [f1, cfn]),
  comp(MULT, [f2, comp(ISZERO, [cfn])]),
]);
const MAX = byCase(SECOND, FIRST, GE);

range(20).forEach(i => range(20).forEach(j =>
  console.assert(MAX(i, j) === Math.max(i, j), 'oops:max')));
```