Python 做的 lambda 演算示例

2020-04-28 23:30:30 +08:00
 atuocn

忽然惊喜的发现,自己原来写在 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=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
>>>

神奇吧。

1286 次点击
所在节点    问与答
1 条回复
VishvaWang
2020-04-29 01:04:15 +08:00
lambda 演算的重点是如何使用匿名函数实现递归

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/667116

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX