チャーチ数とラムダ計算

検索していたら、きしだのはてな・おとうさん、ぼくにもYコンビネータがわかりましたよ! という記事にめぐり逢って面白かったので Scheme 写経してみました。

ラムダ関数の表記

ラムダ関数は λx.x のように表記します。

λx.x
λx.x*2

(λx.x*2)y という関数は xの部分をyでおきかえると

(λx.x*2)y → y * 2  

となります。これを簡約といいます。

;; scheme
(lambda(x) x)          ;=> #<closure #f>
((lambda(x) x) 2)      ;=> 2
# ruby
lambda{|x| x}          #=> #<Proc:0xb77e75a4@(irb):1>
lambda{|x| x}.call(2)  #=> 2
-- Haskell
> (\x -> x) 2  -- => 2
> :t (\x -> x) -- => (\x -> x) :: t -> t
カリー化

関数には複数の引数をとるものがあります。

;; scheme
(define func  (lambda(x y) (+ x y)) )
# ruby
irb(main):001:0> lambda{|x,y| x+y}.call(2,3) # => 5
-- Haskell
>  (\x y ->  x + y) 5 6
-- => 11
>  :t (\x y ->  x + y) 
-- => (\x y ->  x + y) :: Num a => a -> a -> a

ここで、yを3に固定すると、引数ひとつの関数がつくれます。

(define add3  (lambda(x) (+ x 3)))
(add3 3) ;=> 6

3の部分も指定できるようにしたいので、引数ひとつとる関数を返すようにします。

(define add  (lambda(x) (lambda(y)(func x y))))
(add 3)       ; => #<closure (add add)>
((add 3) 3)   ;=>6

クロージャで書くと。

(define add  (lambda(x) (lambda(y) (+ x y))) )
(add 1)      ;=> #<closure (add add)>
((add 1) 2)  ;=> 3
# ruby
add = lambda{|x| lambda{|y| x + y}}   # => #<Proc:0xb77c2e0c@(irb):5>
# x が与えられたのでlambda{|y| 1 + y}の関数が返る。
add.call(1)                           # => #<Proc:0xb77c2e48@(irb):5>
# lambda{|y| 1 + y}のyに2が与えられている。
add.call(1).call(2)                   # => 3
-- Haskell
> :t (\x -> (\y -> x + y))       -- => (\x -> (\y -> x + y)) :: Num a => a -> a -> a
-- 引数をひとつ与えるとNum型の引数をひとつとって、Num型の値を返す関数を返します。
> :t (\x -> (\y -> x + y)) 5     -- => (\x -> (\y -> x + y)) 5 :: Num a => a -> a
> :t ((\x -> (\y -> x + y)) 5)   -- => ((\x -> (\y -> x + y)) 5) :: Num a => a -> a
> :t ((\x -> (\y -> x + y)) 5) 6 -- => ((\x -> (\y -> x + y)) 5) 6 :: Num a => a
> ((\x -> (\y -> x + y)) 5) 6    -- => 11


複数の引数をとる関数を1つの引数の関数に変換することをカリー化といいます。

(define add3 (lambda(x) (lambda(y)(lambda(z)(+ x y z)))))

;; 引数を与えないと引数を3回適用する関数を返します。
add3             ;=> #<closure add3>

;; 引数を1回適用すると引数を2回適用する関数を返します。
(add3 1)         ;=> #<closure (add3 add3)>

;; 引数を2回適用すると引数を1回適用する関数を返します。
((add3 1) 2)     ;=> #<closure (add3 add3 add3)>

;; 引数を3回適用すると結果を返します。
(((add3 1) 2) 3) ;=> 6

カリー化された関数は一部の引数を適用して、残りをあとで適用ということができます。

(let ((add ((add3 1)2)))  (add 3))   ;=> 6

Haskell の関数は全てカリー化されています。

ghci> let add3 x y z = x + y + z
ghci> add3 1 2 3                 -- => 6
ghci> let add2 x = add3 x
ghci> add2 1 2 3                 -- => 6
ghci> let add1 y = add2 y
ghci> add1 1 2 3                 -- => 6
ラムダで条件分岐

true と false を表す関数は以下のようなものだそうです。

true=λx.λy.x
false=λx.λy.y

何のことだか分かりにくいのですが、Scheme で書き直してみると true は常に2つの引数のうち第1引数を返し、false は常に2つの引数のうち第2引数を返す関数です。

;; scheme
(define true  (lambda(x) (lambda(y) x)))
(define false (lambda(x) (lambda(y) y)))
((true  0) 1)    ;=> 0
((false 0) 1)    ;=> 1
# ruby
t = lambda{|x| lambda{|y| x}}
f = lambda{|x| lambda{|y| y}}
t.call(0).call(1)     #=> 0
f.call(0).call(1)     #=> 1

booleanから true/false に変換するboolという関数を作っておきます。

(define bool (lambda(b)(if b true false)))

条件分岐が確認できます。

(((bool (> 3 4)) 2) 5)      ;=> 5
(((bool (< 3 4)) 2) 5)      ;=> 2
# ruby
t    = lambda{|x| lambda{|y| x}}
f    = lambda{|x| lambda{|y| y}}
bool = lambda{|b| if b then t else f end}
bool.call(3>4).call(2).call(5)         # => 5
bool.call(3<4).call(2).call(5)         # => 2
論理演算(はてなキーワード λ計算)
(define not (lambda(p)((p false) true)))
(((not true)   0) 1)          ;=> 1
(((not false)  0) 1)          ;=> 0

(define and (lambda(p)(lambda(q) ((p q) false))))
((and true)true)        ;=> #<closure true>
((and true)false)       ;=> #<closure false>
((and false)false)      ;=> #<closure false>

(define or (lambda(p)(lambda(q) ((p true) q))))
((or true)true)         ;=> #<closure true>
((or true)false)        ;=> #<closure true>
((or false)false)       ;=> #<closure false>
数字をラムダで表現する。

チャーチ数というのがあって数字は関数で以下のように定義されています。

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

このままだと分かりにくくて Scheme で書くと以下のようになっています。0 を引数として、引数に1を加算する関数(lambda(x)(+ x 1))を何回適用するかによって数が決まります。

(define zero (lambda(f) (lambda(x) x)))
(define one  (lambda(f) (lambda(x) (f x))))
(define two  (lambda(f) (lambda(x) (f (f x)))))

((zero (lambda(x)(+ x 1))) 0)  ;=> 0
((one  (lambda(x)(+ x 1))) 0)  ;=> 1
((two  (lambda(x)(+ x 1))) 0)  ;=> 2

チャーチ数から整数への変換する関数を作ります。
関数 toInt は数字を表現する関数を受け取り、0 を引数として1を加算する関数を渡します。
数字を表現する関数がその数字の回数だけ1を加算します。

(define toInt (lambda(n) ((n (lambda(x)(+ x 1)))0)))

(toInt zero)     ;=> 0
(toInt one)      ;=> 1
(toInt two)      ;=> 2

1増やす関数・・・数字を表現する関数は受け取った関数を数字の回数適用する関数であるから、適用回数を増やせば良いはず・・・。

(define succ (lambda(n)(lambda (f) (lambda (x) (f ((n f) x)))) ))
(toInt (succ one))     ;=> 2

加算・・・動いているけどよく分からない・・・。

(define plus 
   (lambda(m)(lambda(n)(lambda (f) (lambda (x) ((m f) ((n f) x)))))))

(define toInt (lambda(n) ((n (lambda(x)(+ x 1)))0)))

(toInt ((plus one) two))  ;;=> 3

ループもあってフィボナッチやYコンビネータも出てきますが、今回理解出来たのはここまで。

チャーチ数 を使った add (加算), multiply (乗算), power (冪乗)

(define (%add n m)
      (lambda (f) (lambda (x) ((m f) ((n f) x)))) )

(define (%multiply n m)
      (lambda (f) (lambda (x) ((n (m f)) x))) )

(define (%power n m)
      (lambda (f) (lambda (x) (((m n) f) x))) )