JavaScriptを使ってチャーチ数で遊ぼう

JavaScriptを使って、チャーチ数で遊びましょう。
チャーチ数とは、関数で自然数を表現したものです。
ここでは、JavaScriptを使ってチャーチ数を定義し、初等的な計算を行います。

# チャーチ数

**チャーチ数 (Church numerals)** とは、自然数 $n$ を
「関数 $f$ を『$f$ を $n$ 回適用する関数』に写す関数」
として定義するものです。

例えばJavaScriptを使って `2` をチャーチ数として表すと

```js
const two = f => x => f(f(x));
```

となります。`two(f)` は、`f` を `2` 回適用する関数となっていますね。
(`=>` について知らない方は「JavaScript アロー関数」で検索してみてください)

`0` から `3` までをチャーチ数として表すと

```js
const zero  = f => x => x;
const one   = f => x => f(x);
const two   = f => x => f(f(x));
const three = f => x => f(f(f(x)));
```

となります。

# チャーチ数の確認

チャーチ数は関数ですので、そのままコンソールに出力しても値がよくわかりません。
チャーチ数を自然数に変換するため、以下の関数を使いましょう。

```js
const evaluate = n => n(x => x + 1)(0);
```

例えば `evaluate(two)` は、 `0` に対し `x => x + 1` を `2` 回適用した結果ですから、結果は `2` となります。

```js
console.log(evaluate(two));  // 2
```

# 注意

以降、チャーチ数 `n` とこれに対応する自然数を同一視して「`n` 回」という表現を使うことがあります。

# チャーチ数の後者(successor)

まず、自然数の **後者 (successor)** とは、平たく言うと「次の自然数」のことです。
自然数 `n` の後者は `n + 1` です。

チャーチ数の後者は、以下の関数で定義できます。

```js
const succ = n => f => x => f(n(f)(x));
```

チャーチ数 `n` の後者が `succ(n)` で得られることを確認しましょう。
`n(f)` は、 `f` を `n` 回適用する関数でしたね。
一方 `succ(n)(f)`、つまり `x => f(n(f)(x))` は `f` を `n + 1` 回適用する関数です。
このことから `succ(n)` は `n` の後者であるといえます。

`succ` を使うと、`1` から `3` までのチャーチ数は以下のように書き直すことができます。

```js
const zero  = f => x => x;
const one   = succ(zero);
const two   = succ(one);
const three = succ(two);
```

# チャーチ数の計算

チャーチ数同士で初等的な計算をしてみましょう。
結論から書くと、チャーチ数の和、積、べき乗は以下の関数で定義できます。

```js
const add = m => n => f => x => n(f)(m(f)(x));
const mul = m => n => f => x => n(m(f))(x);
const pow = m => n => f => x => n(m)(f)(x);
```

順を追って説明します。

## チャーチ数の和

チャーチ数の和は以下の関数で定義できます。

```js
const add = m => n => f => x => n(f)(m(f)(x));
```

チャーチ数 `m` と `n` の和が `add(m)(n)` で得られることを確認しましょう。
`n(f)(m(f)(x))` は、 `x` に対し `f` を `m` 回適用し、さらに `n` 回適用したもの、つまり `f`を `m + n` 回適用したものです。
このことから `add(m)(n)`、つまり `f => x => n(f)(m(f)(x))` は `m` と `n` の和であるといえます。

実際にチャーチ数の和を計算してみましょう。

```js
console.log(evaluate(add(two)(three)));  // 2 + 3 = 5
```

## チャーチ数の積

チャーチ数の積は以下の関数で定義できます。

```js
const mul = m => n => f => x => n(m(f))(x);
```

より簡潔に書くと

```js
const mul = m => n => f => n(m(f));
```

となります。

チャーチ数 `m` と `n` の積が `mul(m)(n)` で得られることを確認しましょう。

`n(m(f))` は『「`f` を `m` 回適用する関数」を `n` 回適用する関数』です。
`m` 回を `n` 回、これはつまり 「`f` を `m * n` 回適用する関数」ですね。
このことから `mul(m)(n)`、つまり `f => n(m(f))` は `m` と `n` の積であるといえます。

実際にチャーチ数の積を計算してみましょう。

```js
console.log(evaluate(mul(two)(three)));  // 2 * 3 = 6
```

## チャーチ数のべき乗

チャーチ数のべき乗は以下の関数で定義できます。

```js
const pow = m => n => f => x => n(m)(f)(x);
```

より簡潔に書くと

```js
const pow = m => n => n(m);
```

となります。
和や積と比べて複雑かと思いきや、定義自体は驚くほどシンプルですね。

チャーチ数 `m` の `n` 乗が `pow(m)(n)` で得られることを確認しましょう。

`n(m)` は「`m` を `n` 回適用する関数」です。
`m` を `1` 回適用するごとに関数 `f` の個数は `m` 倍になりますから、
`m` を `n` 回適用すると `f` は `m` の `n` 乗個に増えます。
このことから `pow(m)(n)`、つまり `n(m)` は `m` の `n` 乗であるといえます。

定義自体はシンプルですが、頭が痛くなりますね。

実際にチャーチ数のべき乗を計算してみましょう。

```js
console.log(evaluate(pow(two)(three)));  // 2 ^ 3 = 8
```

# まとめ

これまでやったことを1つのコードにまとめると、以下のようになります。

```js
const succ = n => f => x => f(n(f)(x));

const zero  = f => x => x;
const one   = succ(zero);
const two   = succ(one);
const three = succ(two);

const evaluate = n => n(x => x + 1)(0);

console.log(evaluate(two));  // 2

const add = m => n => f => x => n(f)(m(f)(x));
const mul = m => n => f => x => n(m(f))(x);
const pow = m => n => f => x => n(m)(f)(x);

console.log(evaluate(add(two)(three)));  // 2 + 3 = 5
console.log(evaluate(mul(two)(three)));  // 2 * 3 = 6
console.log(evaluate(pow(two)(three)));  // 2 ^ 3 = 8
```

チャーチ数への興味が出た方は、これを機に「チャーチ数」や「ラムダ計算」で検索してみてください。

# 参考文献

- [第47回　Swiftに足りないものは何か？：書いて覚えるSwift入門｜gihyo.jp … 技術評論社](https://gihyo.jp/dev/serial/01/swift-introduction/0047?page=2)
- [ラムダ計算 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%A0%E3%83%80%E8%A8%88%E7%AE%97)