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

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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号