Fleurer.Lee

众所周知，lambda演算通过递归就可以图灵完备。好，用纯lambda演算写个递归吧。

等等，要递归必须得有名字，而lambda演算里赋予名字的唯一方式就是传递参数。像lisp那样define可不行啊。只能这样绕个圈子：

(\f.\x.
    (if  (= x 1)
        1
        (* x (f f  (- x 1)))))

这里把函数本身作为第一个参数传递给自己，从而实现的递归。要调用这个递归函数，还得套一个let（当然，换成lambda形式）:

((\fac. (fac fac 5))
        (\f.\x.
              (if (= x 1)
                    1
                    (* x (f f (- x 1))))))

真难看！每次递归都得把自己当作参数传递一遍，很机械！机械的活不应由人类做！想下，如果将递归函数里的(f f (- x 1))换成(f (- x 1))，或许还可以接受…好，Y组合子应运而生，现在你可以这样自然地递归了：

Y (\f.\x
     (if (= x 1)
          1
          (* x (f (- x 1))))) 5

数学家在追求美感上可是不遗余力啊。不过Y是如何做到的？

想想，Y组合子又叫不动点函数。什么是不动点？x=f(x)=f(f(x))…，这个x就是不动点：不管套多少层函数调用，在不动点上的值总是相等。Y f = f (Y f)=f (f (Y f))，这个Y f就是个不动点，高阶函数的不动点。什么是组合子？很简单，可以柯里化、没有自由变量的函数就是组合子 :)

便于理解，我们给(\f.\x (if (= x 1) 1 (* x (f (- x 1)))))这个lambda一个名字fac，看看一步步的递归是怎么来的：

Y fac 3
> fac (Y fac) 3         	//transform, Y!
> 3 * ((Y fac) 2)        	//3 !=1 so recurse
> 3 * (fac (Y fac) 2)    	//Y transform again
> 3 * (2 * ((Y fac) 1))       //2 !=1 so recurse
> 3 * (2 * (fac (Y fac) 1))   	//Y transform again
> 3 * (2 * 1)             	//1=1, so recursion ends.
> 6

就是这样了。里面有柯里化，也有惰性求值（缺一不可！）。一环套一环，然后就递归了。

Y组合子的定义：Y = \y. (\x.y (x x)) (\x.y (x x))，天知道大神（大神的名字叫做Haskell Curry! -v-）是怎么想出来的 =v=

不妨自己在纸上推倒一下(也只能在纸上推倒，这东西在实际的编程中貌似是没有应用的 :D)

看了几天wikipedia, 记一点自己的理解. 当然, 理解能力有限, 不一定正确.

还是关于lambda演算, 貌似church发明这东西是为了解决可计算性问题的判定, 也就是那个传说中的church-图灵论题. 同为形式系统(什么是形式系统…囧), 人们都说这东西跟图灵机的运算能力等价, 我觉得这种等价关系应该是在数学上, 而且是忽略中间的演算步骤的, 如1+1与1+34-78+96-51貌似就可以算是等价的.

lambda演算貌似有三个性质, 即alpha替换, beta规约, eta替换, 在函数式语言编译器的优化中貌似有很多用处, 具体就不了解了. 那帮数学家大胡子貌似专好用希腊字母吓唬人, 数学里貌似从来就没有过命名规范! … alpha替换貌似用来表示一个lambda表达式的等价关系, 如 λx.x+1与λy.y+1就是等价关系, 把x换成y, 依然还是那个lambda表达式; beta规约貌似易理解些, 拿程序做类比的话貌似就是函数调用了, 如((λ.x.λy.x+y) 2)就可以规约成λy.2+y, 即把函数的参数替换成另一个表达式, 去掉一阶lambda; eta替换貌似也是用来表示lambda表达式的等价关系, 如果 λx.f(x)==λx.g(x), 那么f==g.

一个lambda就是一个只有一个参数的函数, 要多个参数的函数就套多个阶的lambda, 像这样 λa.λb.a+b . 在(λb.a+b)中, a貌似就是自由变量, 不受这个lambda的约束. 由于(λb.a+b)这个函数中含有自由变量a, 所以这个函数只能在提供a这一自由变量的函数中存在而不能被自由传递或者调用. 而haskell curry大人发明的所谓组合子, 貌似就是没有自由变量的函数, 由于没有自由变量, 函数的自由传递就有了保证. 靠, map, filter, foldr, fst …. 你们全家都是组合子! 用有限数量的组合子就可以表示出特定范畴的所有运算, 也就是组合子语言, 传说中有个SK组合子语言, 只用S和K两个组合子就图灵完备了. map reduce filter貌似也可也看作是一门组合子语言, 单靠它们貌似就可以完成几乎所有的list操作. 呃, 还有那个一直以来让我闻之色变的monad, 貌似也是个组合子语言, 它里面只有>>=和return两个组合子…

貌似不需要把它们看得太复杂吧…概念都很简单…就像在学的高数和线代, 知道里面就那点东西, 可就是一个题都不会做…囧

作为人类历史上第二门编程语言, lisp的语法是公认的简单了, 函数套函数, 括号套括号.  不谈应用, 学lisp就是为了娱乐的, 最有意思的东西莫过于lambda, 简单至极又无处不在, 而且几乎无所不能.

读过sicp的同学们都知道定义函数的define语句

(define (func p1 p2) (…))

是(define func (lambda (p1 p2) (…)))的语法糖, 在lisp中, 函数就是个值, 跟普通变量一样可以传来传去. 

在当前作用域声明变量的define语句

 (define var1 val1)

又是let语句的缩写

(let ((var1 val1)

 (var2 val2))

(…))

而sicp中貌似没说, let语句实际上也就是lambda的语法糖

((lambda (var1 var2)

(…) val1 val2)

可以说, lisp中所谓的变量都是参数的变形罢了.

如果高兴, 你可以用lambda来表示pair

(define (cons x y) (lambda (f) (f x y)))

(define (car pair) (pair (lambda (x y) x)))

(define (cdr pair) (pair (lambda (x y) y)))

函数式编程的优势高阶函数与惰性编程可都是lambda带来的大礼. lambda返回一个函数而其中的语句并不会立即运行, 通过这一特性可以轻而易举地创造出无限长度的List以及很多不同的玩法, 具体内容请见sicp中关于流的那章.

用cons,car和cdr就可以构造出逻辑判断, 像这样:

(define new-true car)

(define new-false cdr)

(define (new-if condition exp1 exp2)

    (condition (cons exp1 exp2)))