V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
atuocn
V2EX  ›  问与答

Python 做的 lambda 演算示例

  •  1
     
  •   atuocn · 2020-04-28 23:30:30 +08:00 · 1149 次点击
    这是一个创建于 1430 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    神奇吧。

    1 条回复    2020-04-29 01:04:15 +08:00
    VishvaWang
        1
    VishvaWang  
       2020-04-29 01:04:15 +08:00 via Android
    lambda 演算的重点是如何使用匿名函数实现递归
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1024 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 19:21 · PVG 03:21 · LAX 12:21 · JFK 15:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.