ラムダ計算

ラムダ計算での操作対象は関数しかない。ラムダ式の中に数字が登場することもあるが、それは「数字をラムダ式で表したもの」を便宜的に数字で表記しているという立場らしい。プラスやマイナスといった演算子も同様。つまり、これらはラムダ式で表現しうるということだ。ではまず数字をラムダ式ではどのように表現するのか見てみよう。以下は「チャーチ数」と呼ばれるものだ。

\large{0:= \lambda f . \lambda x . x}
\large{1:= \lambda f . \lambda x . f x}
\large{2:= \lambda f . \lambda x . f \left( f x \right)}
\large{3:= \lambda f . \lambda x . f \left( f \left(f x\right)\right)}

単に関数の適用回数と数字が対応している。これを踏まえて数をチャーチ数に変換する手続をSchemeで記述したのが以下だ。ついでに逆の変換手続も書いておく。

(define (num->church num)
  (lambda(f)
    (lambda(x)
      (let loop ((n num))
	(if(> n 0)
	   (f (loop (- n 1)))
	   x)))))

(define (church->num church)
  ((church (lambda(x)(+ x 1))) 0))

更に生成したチャーチ数に対して和、乗、羃を計算する手続は以下のように書ける。

(define (church-add p q)
  (lambda (f) (lambda (x) ((q f) ((p f) x)))))

(define (church-mult p q)
  (lambda (f) (lambda (x) ((q (p f)) x))))

(define (church-power p q)
  (lambda (f) (lambda (x) (((p q) f) x))))

見事としか言いようがない。ラムダの適用だけで演算を定義できるわけだ。残念なことにチャーチ数では負数を除く整数しか扱えないという欠点はあるのだけれど。
整数が扱えるからには論理演算など余裕。

(define ((lambda-true x) y) x)
(define ((lambda-false x) y) y)

(define (lambda-if condition true-case false-case)
  ((((lambda(c)
       (lambda(t)
	 (lambda(e)
	   ((c t) e))))
     condition) true-case) false-case))

(define (lambda-and arg1 arg2)
  (((lambda(p)
      (lambda(q)
	((p q) lambda-false)))
    arg1) arg2))

(define (lambda-or arg1 arg2)
  (((lambda(p)
      (lambda(q)
	((p lambda-true) q)))
    arg1) arg2))

(define (lambda-not p)
  ((p lambda-false) lambda-true))

ワンステップずづ追っていけば納得はできるけど、普通は思いつかないよね。チャーチさんテラスゴス。