ECMAScript
ネタ
ラムダ計算

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

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)
   ();

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