lambda表达式的递归

我们知道,一般的lambda表达式会将let实现为:

\[(let\ x\ =\ expr1 \ in\ expr2) \equiv (\lambda x.expr2)expr1\]

这样一来,在expr1中,x的绑定不是expr1. 【递归】似乎也就无从谈起了,因为在expr1中,无法得到一个绑定,使得x被绑定为expr1.

那么,难道用lambda表达式是无法实现递归的吗?当然不是,不过我们首先要明确一个事实 – 一切递归都可以实现为循环

如果我们可以实现循环,那么就可以实现递归。但不幸的是,如果你用过scheme一类语言的话,你会知道在scheme中,循环被实现为尾递归。在lambda表达式中也没有循环的概念,我们无法用这个方法来解决问题。

回到【实现递归】这个目标上来。如果我们想要在expr1中调用expr1自己,就必须在expr1中得到对expr1的一个绑定。

这个绑定是【绑定变量】还是【自由变量】呢?刚才我们已经用let的实现宣告了【自由变量】这个思路不太可行,我们要用【绑定变量】的思路。

也就是说,expr1的形式应该是

\[expr1:\lambda f.\lambda x. expr\]

其中f会被绑定为

\[\lambda x.expr\]

或者说

\[(expr1\ f)\]

这个时候我们惊奇地发现,f竟然会满足这个式子:

\[f \equiv (expr1\ f)\]

如果把f写作参数常用的x,把expr1写作函数常用的f,我们会发现上式变成了:

\[x \equiv (f\ x)\]

这就是所谓的【不动点】。比如说cos函数的不动点是:

\[x = \cos(x)\]

解方程,得到

\[x = 0.739085\]

那么,只要我们找到 \(expr1\) 这个函数的【不动点】f,\((expr1\ f)\)就会是一个递归函数。

应该如何寻找这个不动点呢?这是一件非常困难的事。我们注意到一个事实:

\[(\lambda x.xx)(\lambda x.xx)\]

这个式子的\(\beta-reduction\)形式永远是它自己。

试着给前面的式子加一个f,我们会得到:

\[(\lambda x.f (xx))(\lambda x.xx) \equiv f((\lambda x.xx)(\lambda x.xx))\]

我们惊喜地发现,如果给后面的式子也如法炮制,那么就会有:

\[(\lambda x.f(xx))(\lambda x.f(xx)) \equiv f((\lambda x.f(xx))(\lambda x.f(xx)))\]

如果把

\[(\lambda x.f(xx))(\lambda x.f(xx))\]

记作f

f记作expr1,那么就会有:

\[(\lambda x.expr1(xx))(\lambda x.expr1(xx)) \equiv expr1((\lambda x.expr1(xx))(\lambda x.expr1(xx))) \\ f \equiv (expr1\ f) \\\]

看来,

\[(\lambda x.expr1(xx))(\lambda x.expr1(xx))\]

就是我们所要找到的式子了!

而且,因为

\[f \equiv (expr1\ f)\]

所以\(f\)本身就是递归函数,我们构造一个新的lambda表达式:

\[\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))\] \[(\lambda f.(\lambda x.f(xx))(\lambda x.f(xx)))expr1\]

就会是递归函数本身。上面的新表达式就是大名鼎鼎的y-combinator.

但问题还没有完全解决。如果你真的把这个东西输入到scheme中,会发现这个构造是不成功的。因为它会不断对\(f\)求值得到\((expr1\ f)\),从而陷入无限循环中。

如果语言是【惰性求值】的,那么上面的构造将会是成功的。根据这个思路,我们可以给出真正可用的y-combinator.

首先,上面的构造最应该【惰性】的地方,是

\[(\lambda x.f(xx))(\lambda x.f(xx))\]

中前一个式子的\((xx)\)调用。如果能把它【惰性化】,那么问题就解决了。

如何把它【惰性化】呢?我们用老套路:

  1. 一个调用被(lambda () ...)包住后,不会立刻求值,而是会得到一个函数对象late
  2. (late)可以进行求值

根据这个套路,我们写出:

(define (y-combinator1 f)
  (λ ()
    ((λ (x) (f (λ () (x x))))
     (λ (x) (f (λ () (x x)))))))

不过这样一来,参数位置上的\(f\)就会被变成(λ () ... ),我们需要显式地对它求值:

(define (factor-f f)
  (λ (x)
    (if (= x 0)
        1
        (* x ((f) (- x 1))))))

(define factor
  (y-combinator1 factor-f))

((factor) 10)

有没有能【无损】地进行【惰性求值】的方法呢?

我在初学scheme时,曾经有过这样的疑问:

cos ;形式1
(lambda (x) (cos x)) ;形式2

这两个形式究竟有什么区别呢?

在真正地思考过后,我们会发现,形式1是在【得到函数对象的值】,而形式2只有当【函数对象的参数给出后】才会【得到函数对象的值】.

简单地说,在形式2中,cos这个函数被【惰性化】了!

那么在

\[(\lambda x.f(xx))(\lambda x.f(xx))\]

中,有没有可以按照上面的策略进行【惰性化】的地方呢?

当然有,\((f (xx))\)最终会得到一个有参数的函数,我们可以把这个参数写出来:

\[(\lambda x\lambda a.f(xx)a)(\lambda x.f(xx))\]

为了保持不动点的性质,实际上应该写出:

\[\lambda a.f((\lambda x.\lambda a.f(xx)a)(\lambda x.\lambda a.f(xx)a))a\]

而这,就是所谓的Z-combinator. 利用它,我们可以实现我们的真正目标:

(define (y-combinator2 f)
  ((λ (x) (λ (a) ((f (x x)) a)))
   (λ (x) (λ (a) ((f (x x)) a)))))

(define (y-combinator2-let f)
  (let ([d (λ (x)
             (λ (a)
               ((f (x x)) a)))])
    (d d))) 

(define (factor-f2 f)
  (λ (x)
    (if (= x 0)
        1
        (* x (f (- x 1))))))

(define factor2
  (y-combinator2-let factor-f2))

(factor2 10)

Essentials of Programming Languages中,还有一种办法可以得到递归函数,而且更好理解一些:

(define (factor-f f)
  (lambda (x)
    (if (= x 0)
        1
        (* x ((f f) (- x 1))))))

(define factor
  (factor-f factor-f))

(factor 10)

在解释器中实现递归

虽说可以用y-combinator或者z-combinator构造递归,但是这样的东西在性能能不是最优解。最优解当然是在语言内支持递归。

其实,无论是scheme还是ML、Haskell,都是在语言层面上实现了递归的。 例如说

(letrec ((factor
          (lambda (x) 
            (if (= x 0)
                1
                (* x (factor (- x 1))))))
  (factor 10))
let rec factor x = if x = 0 then 1 else x * (factor x - 1)

那么,我们应该也可以在语言中实现递归。Essentials of Programming Languages里定义了letrec关键字:

1

我们如何对letrec-exp进行求值呢?方法当然是无限多的,这里给出两种方式。

extend-environment-rec

如果你也试着去实现了对此表达式的求值,那么你会发现,最麻烦的问题是,我们需要使得env中存在对这个函数的绑定,但是要构造这个函数的值却需要已经构造好的env,这成了一个【先有鸡还是先有蛋】的无限递归问题。

为了解决这个问题,我们考虑这样的一个事实:

假设

letrec f(x) = if zero?(x) then 1 else x * f(x - 1) in f(10)

这里的fenv已经被构造好了,那么,我们一定有:

(apply-environment env f) = 
	(procedure var exp env)

根据这个分析,如果我们的函数

(extend-environment-rec env-old var body proc-name)

会得到env的话,那么f一定可以被表示为:

(procedure exp (extend-environment-rec env-old var body proc-name) var)

根据这个想法,我们直接可以写出extend-environment-rec的实现:

(define extend-environment-rec
  (λ (env var body proc-name)
    (λ(what)
      (if (equal? what proc-name)
          (proc-val (procedure var body
                               (extend-environment-rec env var body proc-name)))
          (apply-environment env what)))))

这样一来,我们就直接实现了递归函数。

改变procedure的定义

我们原来是这样定义procedure的:

(define procedure
  (λ(var body env)
    (λ(val)
      (value-of body
                (extend-environment env var val)))))

这里,我们把它的函数名也加进去:

(define procedure
  (λ(var body env proc-name)
    (λ(val)
      (let ([env1
             (extend-environment env
                                 proc-name
                                 (proc-val (procedure var body env proc-name)))])
      (value-of body
                (extend-environment env1 var val))))))

每当要求值的时候,我们临时构造一个相同的函数即可。

支持引用的语言

对于支持引用的语言来说,递归函数的实现就不这么麻烦了。例如说C语言:

int factor(int x){
	if (x == 0){
		return 1;
	}
	else{
		return x * factor(x - 1);
	}
}

这里的factor会被解释成一个函数指针,实际上是一个地址,编译出来会是这样:

factor:
	...
	call factor(0x...)
	...

通过引用,我们也可以在scheme中以另一种方式实现递归:

(define (solve3 n)
  (define temp 10)
  (define (inner x)
    (if (= x 0)
        1
        (* x (temp (- x 1)))))
  (set! temp inner)
  (inner n))

(solve3 10) ;3628800