python做的lambda 演算示例

jopen 10年前

所有关于函数式编程的介绍中都指明 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=lambda 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  >>>

来自：http://my.oschina.net/u/947271/blog/287483