チャーチ数であそぼ

チャーチ数の演算をコンビネータで表すと
(^) はλabcd.bacd = λab.ba = CI（引数の順序を気にしないなら I ）
(*) はλabcd.a(bc)d = λabc.a(bc) = B
(+) はλabcd.ac(bcd) = λabcd.B(ac)(bc)d = λabc.(BBac)(bc) = λabc.S(BBa)bc = λa.BS(BB)a = BS(BB)
(+) がけっこう複雑なのが意外。
まず Haskell で確認。

two f = f.f
three f = f.f.f

plus m n s x = m s (n s x)
multi m n s x = m (n s) x
power m n s x = n m s x

b = (.)
c = flip
s a b c = a c (b c)
i = id

*Main> plus two three succ 0
5
*Main> multi two three succ 0
6
*Main> power two three succ 0
8
*Main> b s (b b) two three succ 0
5
*Main> b two three succ 0
6
*Main> c i two three succ 0
8

うん、あってる。でも s = (<*>) だとエラーになっちゃう。なぜだろう？
Grassでもやってみよう。
関数定義で引数が１つ以上必要なので、BS(BB)ではなくてλx.BS(BB)x と書かなくてはならない。ちょっと冗長。
ウソ。↓みたいに書けばいいだけ。

wwwWWwWWWWwv	: B = (*) = (\ a b c -> a (b c))
wwwWWWwWWWwwWWwv	: S = (\ a b c -> a c (b c))
WWwwWWWwwWwwv	: (+) = BS(BB)
wwWWwWWWwWWWWwv	: 3
WWwWwwWwwwwwwwwwWwwwwwwwwwwww : (+) 3 3 out du

関係ないけどチャーチ数の 2 = SBI = S(S(KS)K)I ですね。
1 = I は簡単だけど、0 = CK をSKI で表すのは大変だ。