Posted at

ラムダ計算のすゝめ(勧めるとは言ってない

More than 1 year has passed since last update.

ES2015からは、アロー関数が導入されています。これによって簡潔に関数を記述できるようになりました。今更感が強いですが、このアロー関数を使って遊んでみたいと思います。


用意するもの


  • 暇な時間

  • 簡単なラムダ計算を理解できる頭脳 または ラムダ計算に関する資料(Wikipediaにもある程度の情報があったと思います)

  • 1文字の識別子を容認する寛容な心


作るもの

0以上の整数を引数にとり、その階乗を返す関数


作り方


まずは普通に

再帰を使った階乗のプログラムです。

const factorial = m => m ? m * factorial(m - 1) : 1;

これをもとに考えていこうと思います。


チャーチ数を使う

チャーチ数は、ラムダ計算のために考え出された、0以上の整数を表現する方法で、以下のように定義されています。

0 = λf x. x

1 = λf x. f x
2 = λf x. f (f x)
3 = λf x. f (f (f x))

チャーチ数mは引数として受け取った関数fm回適用する高階関数となっています。

この定義に基づいて、様々な演算を定義できるのですが、ここでは、乗算とデクリメントだけを紹介します。

//乗算

MULT = λm n. m (n f)
//デクリメント
PRED = λm f x. m (λg h. h (g f)) (λu. x) (λu. u)

TRUEやFALSEにも以下のような定義が与えられています(こちらはチャーチ真理値と呼ばれることもあるようです)。

TRUE = λx y.x

FALSE = λx y.y

この定義を使うと、条件分岐がとても簡単にできます。

TRUE a b  // => TRUEのとき a が返される

FALSE a b // => FALSEのとき b が返される

また、数mが正の数かどうかを判定する関数は簡単に書けますね。

ISPOSITIVE = λm. m (λx. TRUE) FALSE

これらを使うと、階乗のコードは次のように書けます。

factorial = λm. ISPOSITIVE m (MULT m (factorial (PRED m))) 1


再帰を排除する

実は、上記のコードは、厳密には正しいラムダ計算の式ではありません。ラムダ計算では自身を含む式は定義できないので、直接再帰をすることは避けなければなりません。

ではどうすればよいのでしょうか。

これにも、簡単な解決策が存在します。不動点コンビネータと呼ばれるもので、代表的なものにYコンビネータがあります。

Y = λf. (λx. f (x x)) (λx. f (x x))

詳細な説明はここでは割愛しますが、Y f = f (Y f)と展開されることにより、再帰を実現できます。

先程の式をYコンビネータを使ったものに書き換えてみましょう。

factorial = λm. Y (λf n. ISPOSITIVE n (MULT n (f (PRED n))) 1) m


ECMAScriptで書く

ECMAScriptでの定義は、以下のようになります。

const ZERO = f => x => x;

const ONE = f => x => f(x);
const MULT = m => n => m(n(f));
const PRED = m => f => x => m(g => h => h(g(f)))(u => x)(u => u);
const ISPOSITIVE = m => m(f => x => y => x)(x => y => y);

ECMAScriptでは、引数が先に評価されるため、Yコンビネータの一部を修正しなければ上手く再帰できません。この修正されたコンビネータはZコンビネータと呼ばれます。

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

また、条件分岐の部分も評価を遅延させるため、関数を間にかませる必要があります。

ECMAScriptのコードは以下のようになります。

const factorial = m => Z(f => i => ISPOSITIVE(i)(j => MULT(j)(f(PRED(j))))(j => ONE)(i))(m)


数値↔チャーチ数の変換をする

上の関数はチャーチ数を引数にとり、チャーチ数を返します。あとは、普通の数値とチャーチ数の間の変換ができれば完成です。

チャーチ数を数値に変換するのは簡単です。

const FROMCHURCH = c => c(n => ++n)(0);

数値をチャーチ数に変換するには、例のZコンビネータを使ってやる必要があります。

const TOCHURCH = n => Z(f => g => n-- ? f(h => x => h(g(h)(x))) : g)(ZERO);


合成・展開

階乗のコードと数値の変換の関数を組み合わせて、全ての関数を展開(アロー関数のみで記述)します。仮引数の名前がかぶらないように気を付けます。ここで一気に可読性が下がります。

const factorial = m =>

(f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))
(f => i =>
(p => x => y => p(x)(y))
(i(g => x => y => x)(x => y => y))
(j =>
(k => l => g => x => k(y => l(g)(y))(x))
(j)
(f(g => x => j(h => e => e(h(g)))(u => x)(u => u))))
(j => g => x => g(x))
(i))
((f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))
(f => g => m-- ? f(h => x => h(g(h)(x))) : g)
(f => x => x))
(n => ++n)(0);

これでほぼ完成形です。


どうでもいいけど

数字の0が1つだけコードの中に入っているのが気持ち悪いので、0を(x => x > x)()に書き換えます。厳密にはこの値はfalseですが、階乗の結果は必ず1以上になるので、1回以上インクリメントされて数値になります。

これが完成形のコードです。

const factorial = m =>

(f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))
(f => i =>
(p => x => y => p(x)(y))
(i(g => x => y => x)(x => y => y))
(j =>
(k => l => g => x => k(y => l(g)(y))(x))
(j)
(f(g => x => j(h => e => e(h(g)))(u => x)(u => u))))
(j => g => x => g(x))
(i))
((f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))
(f => g => m-- ? f(h => x => h(g(h)(x))) : g)
(f => x => x))
(n => ++n)((x => x > x)());


長所


  • 面白い

  • 難読化に有効(解読にはラムダ計算に関する知識と気合いと根性が必要)


短所


  • デバッグがしにくい

  • 実行時間が遅い

  • メモリ(特にコールスタック)を無駄に消費する

  • コードが長く、複雑


結論

ラムダ計算をECMAScriptで扱うのはとても面白いです。型付けが弱い言語だからこそできることがあります。皆さん、ECMAScriptでラムダ計算を楽しみましょう。

しかし、ECMAScriptでラムダ計算を用いるのは非常に効率が悪く、実用には向きません。ラムダ計算をECMAScriptで使うのは控えるようにしましょう。


追記

FizzBuzzもやってみました。コードのみ載せます。

const fizzbuzz = m =>

(f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))
(f => i =>
(p => x => y => p(x)(y))
(i(g => x => y => x)(x => y => y))
(j =>
(a => b => g => z => g(a)(b(g)(z)))
(j)
(f(g => x => j(h => e => e(h(g)))(u => x)(u => u))))
(j => j)
(i))
((f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))
(f => g => m-- ? f(h => x => h(g(h)(x))) : g)
(f => x => x))
(i =>
(p => q => a => b => c => d => p(q(a)(b))(q(c)(d)))
((f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))
(f => k =>
(d => d(g => x => y => y)(x => y => x)
(j => k)
(j => f(j))
(g => x => d(h => e => e(h(g)))(u => x)(u => u)))
((g => x => g(g(x)))
(j => g => x => j(h => e => e(h(g)))(u => x)(u => u))
(k)))
(i)
(g => x => y => y)
(x => y => x))
((f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))
(f => k =>
(d => d(g => x => y => y)(x => y => x)
(j => k)
(j => f(j))
(g => x => d(h => e => e(h(g)))(u => x)(u => u)))
((g => x => g(g(g(g(x)))))
(j => g => x => j(h => e => e(h(g)))(u => x)(u => u))
(k)))
(i)
(g => x => y => y)
(x => y => x))
(x => console.log("FizzBuzz") || x)
(x => console.log("Fizz") || x)
(x => console.log("Buzz") || x)
(x => console.log(i(n => ++n)((y => y > y)())) || x))
(x => x)
();

とにかく長いですね。見返すだけでも頭が痛くなってきます。