函数的互相调用

Scheme中，函数在内存中是以闭包的形式存在，闭包有以下部分：

  1. 定义时的环境变量
  2. 形式参数列表
  3. 函数体

当一个函数被运行的时候，我们会执行以下步骤：

  1. 求值所有的实参
  2. 读取闭包中的形式参数列表，把形式参数和实参的值绑定
  3. 读取闭包中的环境变量，并且把第二步中的参数扩展到环境变量中
  4. 在第三步的环境变量中运行函数体

这个过程非常的直观。但在实际的运行当中有一些问题：当一个函数需要调用自己的时候以上的步骤就没有办法实现了。因为这个函数能拿到的所有变量都在定义时的环境变量里。而递归调用自己需要函数自己的闭包也存在于定义时的环境变量中。这就会产生一个循环引用：

Closure A {
  Parameters [a b]
  Body {
    if b == 0
      return a
    return A(b, a % b)
  }
  Env { A: Closure A { ... } }
}

这就需要在函数定义之后做一些特殊处理，把返回的闭包设置进闭包内的环境变量。这样的特殊处理无法满足更为复杂的情况。比如函数的互相调用问题。有两个函数A和B他们需要互相调用。这个时候我们需要在A的环境变量中插入Closure B，在B的环境变量中插入Closure A。

在JS中函数的声明会被提前到上下文的最前面，所有的函数在上下文的任意一个地方都可以访问。这样就解决了函数互相调用的问题。

这个问题也可以通过Y Combinator来解决。YC可以用来递归一个匿名函数，我们可以改造一下他的实现，让他能支持多个函数互相调用。

我们可以用判断奇数偶数的函数来作为例子：

odd: (lambda (n) (cond ((= n 1) #t) ((= n 0) #f) (#t (even (- n 1)))))
even: (lambda (n) (cond ((= n 0) #t) ((= n 1) #f) (#t (odd (- n 1)))))

这段代码的大致意思是：如果一个数是1那他就是奇数，是0那他就是偶数，如果都不是，那就判断n - 1。这里even会调用odd，odd会调用even。需要解决这个问题，我们需要一个YC的变种，他能接受两个函数为输入，这两个函数就是奇数和偶数的判断函数。但是我们需要递归调用，所以我们需要在外面包装一个函数，把可能用到的函数都作为参数传入。当然由于我们包装了一层函数，我们调用的时候也需要做相应的更改：

(YC' 
 (lambda (even odd) (lambda (n) (cond ((= n 0) #t) ((= n 1) #f) (#t ((odd even odd) (- n 1))))))
 (lambda (even odd) (lambda (n) (cond ((= n 1) #t) ((= n 0) #t) (#t ((even even odd) (- n 1)))))))

可以看到，我们在递归调用的时候把even和odd传入，因为我们在外面包装了这一层。

而我们的YC'函数的结构类似于YC

((lambda f (f f))
 (lambda self ((lambda (even odd) (even even odd)))))

这样我们就完成了一个最初的版本，可以达到不引入新的机制而做到互相递归。

但是这个版本并不完美，因为我们需要在所有递归调用上传入所有的函数，原本的(even (- n 1))变成了((even even odd) (- n 1))。所以我们可以更改一下even和odd的定义。他们就是原本的接受一个数字，返回一个布尔值的函数。而为了获取这个函数我们需要一个函数来专门把函数进行处理：

((lambda f (f f))


(lambda (self)
 (lambda (fn) (fn ((self self) even) ((self self) odd))))


)

上面的函数递归的构造一个fn把处理过的两个函数传入到这个待处理的函数中去。self是为了能够递归。

但是实际上这个函数是无法停止的因为他在不停的调用自己。所以我们这边需要对他进行修改，通过添加一层lambda来惰性的生成内部的函数

((lambda f (f f))


(lambda (self)
 (lambda (fn) (fn (lambda (x) (((self self) even) x))  (lambda (x) (((self self) odd) x))))


)

到这里我们就能在一个表达式中定义多个能够互相调用的函数啦~

这里是最终的代码：

(((lambda (even odd) (
                      (
                       (lambda (f) (f f))
                       (lambda (self)
                         (lambda (fn) (fn
                                        (lambda (x) (((self self) even) x))
                                        (lambda (x) (((self self) odd) x))))))
                      even))
  (lambda (even odd) (lambda (n) (cond ((= n 0) #t) ((= n 1) #f) (#t (odd (- n 1))))))
  (lambda (even odd) (lambda (n) (cond ((= n 1) #t) ((= n 0) #t) (#t (even (- n 1)))))))
 98)

以上是我在实现一个scheme解释器中遇到的问题。如果感兴趣的话可以看这里

⌂