当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

lambda Calculus

发表于: 2012-01-30   作者:bookjovi   来源:转载   浏览次数:
摘要: 发现了一个好的blog:Good Math/Bad Math,里面关于lambda calculus的讲解真是佩服,只要耐心足够,有一定的抽象能力,从头读到尾基本上就看理解lambda了,起码比维基百科上容易理解的多。     Alonzo Church的lambda的核心思想是一切计算都可用lambda表示,就连最基本的number也是用lambda表示,进而衍生出choi

发现了一个好的blog:Good Math/Bad Math,里面关于lambda calculus的讲解真是佩服,只要耐心足够,有一定的抽象能力,从头读到尾基本上就看理解lambda了,起码比维基百科上容易理解的多。

    Alonzo Church的lambda的核心思想是一切计算都可用lambda表示,就连最基本的number也是用lambda表示,进而衍生出choice,递归等复杂运算模型。

    lambda演算中number用church numerals表示:

    0:lambda s z . z

    1:lambda s z . s z

    2:lambda s z . s (s z)

两个数相加add的lambda运算式是:

let add = lambda s z x y . x s (y s z)

也可表示为:

let add = lambda x y. (lambda s z . (x s (y s z)))

 

从上面几个lambda的运算式可以简单的证明2+3=5,blog上有证明过程。

类似,Boolean和choice也有相应的lambda:

let TRUE = lambda x y . x

let FALSE = lambda x y . y

let IfThenElse = lambda cond true_expr false_expr . cond true_expr false_expr

let BoolAnd = lambda x y .x y FALSE

let BoolOr = lambda x y. x TRUE y

let BoolNot = lambda x . x FALSE TRUE

 

递归则有点复杂,在lambda表达式中仅可引用绑定变量和自由变量,引用自己则不可以,但这也难不倒天才的church。

church用了Y combinatorlet Y = lambda y . (lambda x . y (x x)) (lambda x . y (x x))

Y的最诡异特性就是自己生成自己:(Y Y) = Y (Y Y)

用Y表示fib递归函数如下:

let metafact = lambda fact . (lambda n . IsZero n 1 (Mult n (fact (Pred n))))

fact n = (metafact metafact) n

 

 

lambda对于FP语言有着深远的影响,如最早的lisp。如果看过SICP后,对lambda和FP的理解会更深刻一些,如FP中常用的pairs用lambda可表示为(scheme版本):

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))

这也符合church的思想,一切皆可用lambda表示,SICP中也略提到了类似观点,SICP中在data抽象一章也说到data的本质,data到底是什么? OO语言中的Object的本质又是什么呢?看了SICP就明白为什么FP的很多人不喜欢OO,毕竟从lisp的角度看OO,Object仅仅是lambda而已。

 

lambda Calculus

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
dic = {'a':31, 'bc':5, 'c':3, 'asd':4, '33':56, 'd':0} 想把dic的value按照从大到小排序(value
复习以前学过的东西 发现大部分东西都忘记了。悲剧。后来总结发现应该记个记号,以后没事的时候翻出
什么是Lambda表达式? 随VS 2005发布的C#2.0引进了匿名方法的概念,允许在预期代理(delegate)值的地
源自: http://www.cnblogs.com/kingmoon/archive/2011/05/03/2035696.html Lambda表达式 "Lambda表
 lambda表达式是对匿名方法的一种改进,具有更加简洁的语法和更易理解的形式,lambda表达式可以包
Lambda应用模式 前言 在使用 Lambda 表达式时,我们常会碰到一些典型的应用场景,而从常用场景中抽
遇见C++ Lambda Written by Allen Lee If you die when there's no one watching, and your ratings
关于委托,肯定是要有问题的。 第一个问题,委托用来干什么? 看.net中的表述:在.net平台下,委托
什么是Lambda表达式? 随VS 2005发布的C#2.0引进了匿名方法的概念,允许在预期代理(delegate)值的地
lambda表达式是对匿名方法的一种改进,具有更加简洁的语法和更易理解的形式,lambda表达式可以包括
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号