[Python]使用Python中的Lambda演算功能：Y-Combinator的Python实现

最近接触的东西都比较杂。不过感觉好几个方面比较有收获。一是使用PyQt感觉Qt平台的强大和华丽。对我来说它最大的好处是跨平台：我的Mac和Ubuntu都可以很好的支持，程序不用修改就能顺利的运行在不同平台上。二是可以使用Python， 这个好处就不多说了。

由于这个学期选得Type Systems课，接触了一些Lambda演算和ML语言（想歪的同学请自觉面壁）。前半个学期由于赶paper的缘故都没有花时间在上面，况且前面的内容也不是那么有趣（Constructive Logic算是一个小亮点）。现在讲到了Polymorphism（应该是多态吧？）以后，才发觉这里面的博大精深。Lambda演算是一种与被大家熟知的Turing Machine不同的计算模型，事实上它的历史甚至可以追随到Turing Machine之前。Turing本人也对Lambda演算做出过贡献。比起Turing Machine，Lambda演算在形式上要“简单”，思维更接近数学。但是Lambda演算的计算能力被证明是和Turing Machine的计算能力是等价的。Turing Machine上著名的停机问题也有其Lambda 演算版本。而且这个版本其实由Church比Turing更早提出

Lambda演算的基本形式为λx.body。 这里可以把x看成一个函数的输入参数，body看成这个函数的返回值。不过与普通编程语言中的函数不同的是， x可以为一个普通的值变量，也可以为一个函数，还可以是一个类型。简简单单的定义却有无穷的变化。比如Church在Lambda演算的基础上重新定义了正整数。还可以在Lambda演算的基础上把布尔类型以及正整数类型推广化。比如List就是一种generalized的正整数。

Python提供了Lambda算子的功能。下面我就用Python的Lambda算子来实现不动点算子Y-Combinator。有关什么是Y-Combinator可以看一下wiki。简单的说来，给定一个函数g以及不动点算子Y，我们有Y(g) = g(Y(g))。从而我们可以用不动点算子Y来实现g的递归调用。

Y-Combinator in Python:

Y = lambda f: (lambda x: f(lambda n:x(x)(n)))(lambda x: f(lambda n:x(x)(n)))

这样如果你定义了非递归函数，比如阶乘

g =  lambda factorial, k : 1 if k == 1 else factorial(k-1)*k

或者更容易理解的方式是这样：

def g(factorial, k):
if k == 1:
return 1
else:
return factorial(k-1)*k

就可以用 Y(g) (k) 来递归求k的阶乘。

Ref: http://siddhi.blogspot.com/2007/08/y-combinator-in-python.html