「ラムダ計算 - Wikipedia」を JavaScript に落とし込みながら読む。補完的に「Church encoding - Wikipedia」、「不動点コンビネータ - Wikipedia」を参照。

01. ブール代数

二つの引数をとり左を返す関数と右を返す関数でBoolの二値 TRUE, FALSE を定義する:

const TRUE = x => y => x;
const FALSE = x => y => y;

表示関数 bisplay を以下のように定義して以降使っていく:

const bisplay = f => f('T')('F');

bisplay(TRUE); // -> T
bisplay(FALSE); // -> F

NOT, AND, OR, IFELSE を以下のように定義する:

const NOT = p => p(FALSE)(TRUE);
  // p がTRUE なら左をとるので、FALSE に評価される
  // p がFALSE なら右をとるので TRUE に評価されるので納得

const AND = p => q => p(q)(FALSE);
  // p が TRUE なら q で評価され
  // p が FALSE なら FALSE に評価されるので納得

const OR =  p => q => p(TRUE)(q);
  // p が TRUE なら TRUE に評価される
  // p が FALSE なら q に評価されるので納得

const IFELSE = p => x => y => p(x)(y);
  // p が TRUE なら 左である x に評価され
  // p が FALSE なら 右である y に評価されるので納得

動作確認:

[TRUE, FALSE].map(p => bisplay(NOT(p))); // -> [ 'F', 'T' ]

const truth = [[TRUE, TRUE], [TRUE, FALSE], [FALSE, TRUE], [FALSE, FALSE]];
truth.map(([p, q]) => bisplay(AND(p)(q))); // -> [ 'T', 'F', 'F', 'F' ]
truth.map(([p, q]) => bisplay(OR(p)(q))); // -> [ 'T', 'T', 'T', 'F' ]

[TRUE, FALSE].map(p => IFELSE(p)('koko')('doko')); // -> [ 'koko', 'doko' ]

02. 自然数

0 には与えられた関数を 0回適用する関数を割り当てる。1 には与えられた関数を 1回適用する関数を割り当てる。2 には与えられた関数を 2回適用する関数を割り当てる。このような決めごとで関数と自然数を対応付ける。ZEROと SUCC を以下に定義すれば、関数と自然数を対応付けられる:

const ZERO = f => x => x;
const SUCC = n => f => x => f(n(f)(x));
  // n(f)(x) は x に f を n 回適用した値と読める
  // この値にもう一回 f を適用してあげているので、後続を表すことになる

動作確認。例えば n => n + 1 という関数は、1 増やす関数なので、これが N 回適用されたら N 増える。そこで表示関数 display を以下のように定義する:

const display = f => f(n => n + 1)(0);

display(ZERO); // -> 0
display(SUCC(ZERO)); // -> 1
display(SUCC(SUCC(ZERO))); // -> 2
display(SUCC(SUCC(SUCC(ZERO)))); // -> 3

ゼロ判定述語 ISZERO と後続の逆 PRED を定義:

const ISZERO = n => n(x => FALSE)(TRUE);
  // x => FALSE は、「1回でも適用したらFALSEになる関数」
  // それを TRUE に n 回適用するので、 ISZERO の実装として妥当

const PRED = n => f => x => n(g => h => h(g(f)))(u => x)(u => u);
  // 考えたやつ天才やろ。わからん。

動作確認:

const range = [ZERO, SUCC(ZERO), SUCC(SUCC(ZERO)), SUCC(SUCC(SUCC(ZERO)))];

range.map(ISZERO).map(bisplay); // -> [ 'T', 'F', 'F', 'F' ]

range.map(PRED).map(display); // -> [ 0, 0, 1, 2 ]

03. 足し算と掛け算

自然数が定義できれば、あとは数学と同じ定義で足し算と掛け算を定義できる:

const PLUS = m => n => f => x => m(f)(n(f)(x));
  // n(f)(x) は x に f を n 回適用した値と読める
  // この値を X として、 m(f)(X) としている。
  // m(f)(X) は X に f を m 回適用しているのだが、
  // 先のとおり X は x に f を n回適用した値なので
  // 総合的にみると x に f を m + n 回適用した値になる

const MULT = m => n => f => m(n(f));
  // n(f) は f を n 回適用する関数とよめる
  // この関数をさらに mに渡し m(n(f)) としているので、
  // f を n回適用する関数を m回適用する関数と評価できる
  // 総合的にみると f を m*n 回適用する関数であると読める

確かめる:

const three = SUCC(SUCC(SUCC(ZERO)));
const five = SUCC(SUCC(three));

display(PLUS(three)(five)); // -> 8
display(PLUS(ZERO)(three)); // -> 3
display(MULT(three)(five)); // -> 15
display(MULT(ZERO)(five)); // -> 0

04. 再帰

Zコンビネータ:

const Z = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)));

を使うと、再帰が可能になる。階乗計算:

const facto = Z(f => i =>
  ISZERO(i)(() => SUCC(ZERO))(() => MULT(i)(f(PRED(i))))()
);

display(facto(SUCC(SUCC(SUCC(SUCC(ZERO)))))); // -> 24

05. ペア / 二つ組

const PAIR = x => y => f => f(x)(y);
const FIRST = p => p(TRUE);
const SECOND = p => p(FALSE);

動作確認:

const pisplay = p => p(x => y => [x, y]);

const pair = PAIR('first')('second');
pisplay(pair); // -> [ 'first', 'second' ]
FIRST(pair); // -> 'first'
SECOND(pair); // -> 'second'

06. リスト

const CONS = PAIR;
const HEAD = FIRST;
const TAIL = SECOND;
const NIL = FALSE;
const ISNIL = l => l(h => t => d => FALSE)(TRUE);

動作確認:

bisplay(ISNIL(NIL)); // -> 'T'

const empty = NIL;
const added = CONS('a')(empty);
const moreAdded = CONS('b')(added);
const [b, x] = [HEAD(moreAdded), TAIL(moreAdded)];
b; // -> 'b'
const [a, y] = [HEAD(x), TAIL(x)];
a; // -> 'a'
bisplay(ISNIL(y)); // -> 'T'

JavaScript でラムダ計算

01. ブール代数

02. 自然数

03. 足し算と掛け算

04. 再帰

05. ペア / 二つ組

06. リスト