忽然惊喜的发现，自己原来写在 oschina 上的文章，找到入口了。自从它要求绑定手机后，因不想提供手机号，我再也没找到原来的文章。既然失而复得，转几个还有点价值的文章到这里，以免再次丢失。
原文写于 2014/07/04 20:55
所有关于函数式编程的介绍中都指明 lambda 演算是函数式编程的数学基础。死了不少脑细胞研究了一下维基百科上关于 lambda 演算的介绍文章。
参考： http://en.wikipedia.org/wiki/Lambda_calculus
普通的数学运算用这个纯抽象的符号演算来定义，计算结果只能在脑子里存在。所以写了点代码，来验证文章中介绍的演算规则。
我们来验证文章里介绍的自然数及自然数运算规则。说到自然数，今天还百度了一下，据度娘说，1993 年后国家规定 0 是属于自然数。先定义自然数及自然数的运算规则：
用 lambda 表达式定义自然数（邱齐数）
0 := λf.λx.x 1 := λf.λx.f x 2 := λf.λx.f (f x) 3 := λf.λx.f (f (f x)) ... 上面定义直观的意思就是数字 n, 是 f(x)的 n 阶函数。1 就是 f(x), 2 就是 f(f(x))....，严格来说，这样表述并不准确。其实每个邱奇数都是一个二阶函数，它有两个变量 f 和 x 。用二元命名函数来表达就是：
0 -> num0(f,x)=x 1 -> num1(f, x)=f(x) 2 -> num2(f,x)=f(f(x)) 3 -> num3(f,x)=f(f(f(x))) ... 其中参数 f 是一个函数。这一段有点绕，但是不能理解这个，对后面的 lambda 演算理解会比较困难。
首先用递归法，定义邱齐数（自然数）
0 是自然数， 度娘说 1993 年后，国家规定 0 是属于自然数。 每个自然数，都有一个后续。 用代码表达就是：
NUM0=lambda f: lambda x:x SUCC=lambda n: lambda f: lambda x: f(n(f)(x)) 后面则是定义运算符，包括加法，乘法，减法和幂。维基文章里没有介绍除法，估摸着除法定义比较复杂，一时讲不清楚。那我们也不验证了。
################################################ #define number calculus rules ################################################ #define Church numeral inductively. #0 := λf.λx.x #1 := λf.λx.f x #2 := λf.λx.f (f x) #3 := λf.λx.f (f (f x)) #... NUM0=lambda f: lambda x:x SUCC=lambda n: lambda f: lambda x: f(n(f)(x)) #define Operator PLUS=lambda m: lambda n: m(SUCC)(n) MULT= lambda m: lambda n: m(PLUS(n))(NUM0) #define predecessor to obtain the previous number. PRED= lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda u:x)(lambda u:u) SUB=lambda m: lambda n: n(PRED)(m) POW=lambd b: lambda e: e(b) 定义完了什么是自然数和自然数的运算子。那么自然数的运算，就可以用 lambda 演算的方式计算了。
问题是上面的定义都是抽象的符号演算，我们需要有一个编码器来把上面的抽象的 Church numeral 符号编码成可以人来阅读的形式，还需把人输入的数字解码成抽象符号。
################################################ #create encoder to input/output Church numeral ################################################ class LambdaEncoding: @staticmethod def encoding(exp,encoder): return encoder().encoding(exp) @staticmethod def decoding(s, decoder): return decoder().decoding(s) class NumEncoder: def encoding(self,num): f=lambda x:x+1 return str(num(f)(0)) def decoding(self,s): n=int(s) num=NUM0 for i in range(n): num=SUCC(num) return num 嗯，有了编码器，就可以方便的来验证了。
################################################ #calculus demo ################################################ print("demo number calculus.\n" "don't input large number," "it will cause to exceed maximum recursion depth!\n") n1=input('input a number: ') n2=input('input anohter number: ') #decode string to Church numeral num1=LambdaEncoding.decoding(n1,NumEncoder) num2=LambdaEncoding.decoding(n2,NumEncoder) #add result=PLUS(num1)(num2) print('{0} + {1} = {2}'.format( n1, n2, LambdaEncoding.encoding(result, NumEncoder))) #mult result=MULT(num1)(num2) print('{0} X {1} = {2}'.format( n1, n2, LambdaEncoding.encoding(result, NumEncoder))) #sub result=SUB(num1)(num2) print('{0} - {1} = {2}'.format( n1, n2, LambdaEncoding.encoding(result, NumEncoder))) #POW result=POW(num1)(num2) print('{0} ^ {1} = {2}'.format( n1, n2, LambdaEncoding.encoding(result, NumEncoder))) 测试结果如下：
>>> demo number calculus. don't input large number,it will cause to exceed maximum recursion depth! input a number: 4 input anohter number: 3 4 + 3 = 7 4 X 3 = 12 4 - 3 = 1 4 ^ 3 = 64 >>> 神奇吧。
Select Language