素心如何天上月 (Yong Sun's Blog): Yong Sun's Blog

在lambda系统中实现递归，需要借用Y组合算子（combinator）。下面是Python中的一个实作。

Y = lambda F: (lambda f: F(lambda x: f(f)(x))) (lambda f: F(lambda x: f(f)(x)))
F = lambda f: (lambda x: 1 if x==0 else x*f(x-1))

fact = Y(F)
print fact(10)

感觉这个Y combinator实在是令人头晕目眩，不知所以。具体的推导过程和相关理论，请参见刘未鹏先生的宏文，以及负暄琐话相关的blog（1、2）。读了几遍，仍然只是朦朦胧胧地明白了一点点，特别是后面的对角线，再读、再读... ...

⁞

最近对FP（Functional Programming）很感兴趣，这两天在看SICP，见到一个很有意思的练习题2.6，是关于Church计数的。用函数来表示数字，对我来说太抽象了。查找了一些资料，稍稍理解了一些。

• 表示自然数 n 的高阶函数是把任何其他函数 f 映射到它的 n 重函数复合 的函数。

0 ≡ λf.λx. x	(define zero (lambda (f) (lambda (x) x)))
1 ≡ λf.λx. f x	(define one (lambda (f) (lambda (x) (f x))))
2 ≡ λf.λx. f (f x)	(define two (lambda (f) (lambda (x) ( f (f x)))))
3 ≡ λf.λx. f (f (f x))	(define three (lambda (f) (lambda (x) (f (f (f x))))))
...	...
n ≡ λf.λx. fn x	...

• 加法函数 plus(m,n) = m + n 利用了恒等式 f^{(m + n)}(x) = f^m(fⁿ(x))。

plus ≡ λm.λn.λf.λx. m f (n f x) =>

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

• 後继函数 succ(n) = n + 1 (plus 1)。

succ ≡ λn.λf.λx. f (n f x) =>

(define (succ n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

• 乘法函数 times(m,n) = m * n 利用了恒等式 f^{(m * n)} = (f^m)ⁿ。

mult ≡ λm.λn.λf. n (m f) =>


(define mult
  (lambda (m)
    (lambda (n)
      (lambda (f) (m (n f)))))) 

在参考[3]中，有另外一种写法，和上面的所谓“经典”写法略有不同， 例如：

(define two (lambda (f) (lambda (x) (f (f x)))))
(define two (lambda (f x) (f (f x))))

这两种写法等价么？首先我们知道two是f的2次复合函数。假定f(x) = x²，即

(define (f x) (* x x))。

第一种写法中，two是一个函数，它以另一个函数f为参数，而f的参数为x，(two f)可以运算得到f的2次复合函数, ((two f) 2) => f(f(2)) => 16。在第二种写法中，two的参数为，函数f以及函数f的参数x，(two f 2) => f(f(2)) => 16，而(two f)是无效的。意义上稍有不同。

参考：

1. Wikipedia [zh]
2. http://www.mactech.com/articles...
3. http://www.cs.cmu.edu/afs/cs/project...