推导 Y Combinator

2020-04-13 Programming Language

等了好多年，终于能听 Ian 讲课了。一会儿北京时间 20:00 马上开始。这里尝试重新推导一下 Y 算子，纪念这个我一生中历史性的时刻，也顺便找找编程感觉。现在，我已经打开各种可能需要的软件准备就绪了。

先实现不使用 Define 的情况下能正常递归

第一步，正常写出 mylength 函数作为最简单的模型。这是一个接受链表（list）作为参数，返回其长度（一个整数值，显示链表中有效负载的数量）的函数。

(define mylength
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 (mylength (cdr l)))])))

测试 mylength 函数，输出正确的话就可以继续推导。

(mylength '(9 19 29))  ;; 输出 3 (链表有 3 个有效负载：9, 19, 29)

第二步，思考如果没有 define 来绑定函数名，我们要如何递归？于是，我们只能将上面 mylength 函数绑定在参数上。于是 mylength 函数作为参数传进去，以便能被调用。因此我们多加了一层嵌套，用这个嵌套带来的参数 mylength 绑定函数体内容。这样我们就可以使用它了。

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                           ;;
    (lambda (l)                                ;;
      (cond [(null? l) 0]                      ;;
            [else (+ 1 (mylength (cdr l)))]))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (l)                                ;;
    (cond [(null? l) 0]                      ;;
          [else (+ 1 (mylength (cdr l)))]))  ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

但是，如果直接调用这个函数就会报错。因为第二小块代码的 mylength 这个变量是没有定义的。于是我们把第二步中的代码（第二小块）修改成下面这样：

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                           ;;
    (lambda (l)                                ;;
      (cond [(null? l) 0]                      ;;
            [else (+ 1 (mylength (cdr l)))]))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                           ;;
    (lambda (l)                                ;;
      (cond [(null? l) 0]                      ;;
            [else (+ 1 (mylength (cdr l)))]))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

但这样还不够，因为两块代码要求其输入参数 mylength 是个函数，不能是 (cdr l) 这种链表。运行到 (mylength (cdr l)) 这段的代码就会报错。于是我们再改代码，把 (mylength (cdr l)) 改为 (mylength mylength) 变成下面这样：

注释：
之所以要这么改动，除了让输入参数符合要求（输入需是个函数）之外，更重要的是让这个作为输入的函数携带足够的信息以便之后的递归。即每次运行到 else 这一分支，函数都会通过 (mylength mylength) 保存一次自己后再进行对 (cdr l) 的运算。而正是因为函数每次都保存了自己（的信息），所以每次都能调用自己，进而实现没有 define 的递归。

PS：使用函数打包（保存）信息后，能实现各种精妙的传递、嵌套和展开，要着重关注和练习这样的数据技巧

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                                      ;;
    (lambda (l)                                           ;;
      (cond [(null? l) 0]                                 ;;
            [else (+ 1 ((mylength mylength) (cdr l)))]))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                                      ;;
    (lambda (l)                                           ;;
      (cond [(null? l) 0]                                 ;;
            [else (+ 1 ((mylength mylength) (cdr l)))]))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

到这步，我们发现这一大块代码可以直接调用来计算链表（list）的长度了。和之前有 define 时的代码效果一样：

(
((lambda (mylength)
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 ((mylength mylength) (cdr l)))])))

 (lambda (mylength)
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 ((mylength mylength) (cdr l)))]))))

'(9 19 29))   ;; 输出 3

既然没有 define 代码也已能正确运行，就说明 Y 算子已经隐藏在其中了。于是我们可以开始各种调整，想办法提取整理出 Y 算子了。

推导 Y 算子

我们先观察一下最早有 define 的时候函数的样子：

(define mylength
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 (mylength (cdr l)))])))

我们的目标是把上一节最后看起来很多的代码转化成「一个函数的调用」，将「一块和最开始 define 的代码模式很像的代码」作为参数输入该函数。如果成功，那么该函数就是 Y 算子啦。可以用它来作用在其他更多的函数上实现递归。（如果看不明白目标，可以往下看完推导在回来看这段描述）

第 1 次转换：我们看到有两小块重复的代码，于是先提取它们

((lambda (f) (f f))

 (lambda (mylength)
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 ((mylength mylength) (cdr l)))]))))

观察发现，第 1 次转换之后，代码已经很像原来有 define 时候的代码了。那么是不是 (lambda (f) (f f)) 就是 Y 算子呢？不是的，因为目前还不够像。(mylength mylength) (cdr l) 这一块的代码和原来的 (mylength (cdr l)) 相比，多了一次函数调用。我们要继续提取，把它变成调用次数一样的模式。也就是一个函数将 (mylength mylength) 想办法变成 mylength 。

第 2 次转换：把 (mylength mylength) 提取出来，通过函数调用来将它传入函数体

(
  (lambda (f) (f f))

  (lambda (mylength)
    (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (lambda (g)                          ;;
      (lambda (l)                         ;;
        (cond [(null? l) 0]               ;;
              [else (+ 1 (g (cdr l)))]))) ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (mylength mylength)
    )
  )
)

我们很高兴地发现，经过第 2 次转换之后，出现了长得很像原来 define 阶段的代码块了（被注释符号“框”起来的那块）。赶紧将这次转换得到的代码输入计算机，看看对不对吧：

(
  (
    (lambda (f) (f f))

    (lambda (mylength)
      (
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
       (lambda (g)                          ;;
        (lambda (l)                         ;;
          (cond [(null? l) 0]               ;;
                [else (+ 1 (g (cdr l)))]))) ;;
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        (mylength mylength)
      )
    )
  )

'(9 19 29))   ;; 死循环

我们很遗憾发现，输入上面的这段代码，对函数进行调用，计算 (9 19 29) 的长度时，内存溢出，函数进入了死循环。到底是怎么回事呢？

中场分析

通过一步一步地拆解函数计算的过程，我们很快就找到了原因：是 (mylength mylength) 这个表达式将我们带入了死循环。但为什么 (mylength mylength) 在前面的代码中没有进入死循环，而当我们将它提取出来之后就进入死循环了呢？我们来好好看一看这个表达式的计算过程吧。

第 2 次转换之后，mylength 这个参数获取的代码内容变成了下面这样：

;;; mylength ;;;

(lambda (mylength)
  (
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (lambda (g)                          ;;
    (lambda (l)                         ;;
      (cond [(null? l) 0]               ;;
            [else (+ 1 (g (cdr l)))]))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    (mylength mylength)
  )
)

所以 (mylength mylength) 就变成：

(
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(lambda (mylength)                      ;;
  ((lambda (g)                          ;;
    (lambda (l)                         ;;
      (cond [(null? l) 0]               ;;
            [else (+ 1 (g (cdr l)))]))) ;;
    (mylength mylength)))               ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(lambda (mylength)                      ;;
  ((lambda (g)                          ;;
    (lambda (l)                         ;;
      (cond [(null? l) 0]               ;;
            [else (+ 1 (g (cdr l)))]))) ;;
    (mylength mylength)))               ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

然后变成：

(
(lambda (g)                         
  (lambda (l)                        
    (cond ((null? l) 0)              
          (else (+ 1 (g (cdr l)))))))

    (
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (mylength)                      ;;
        ((lambda (g)                          ;;
          (lambda (l)                         ;;
            (cond [(null? l) 0]               ;;
                  [else (+ 1 (g (cdr l)))]))) ;;
          (mylength mylength)))               ;;
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (mylength)                      ;;
        ((lambda (g)                          ;;
          (lambda (l)                         ;;
            (cond [(null? l) 0]               ;;
                  [else (+ 1 (g (cdr l)))]))) ;;
          (mylength mylength)))               ;;
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    )

)

展开到这一步我们发现了，由于计算机会优先对表达式求值，而 (mylength mylength) 这个表达式被提取到外部之后，每一次计算机对它求值，都会生成一个仍然处于函数体外部的表达式 (mylength mylength) 需要计算机求值。于是于是计算机又会对 (mylength mylength) 再次进行求值，结果就是出现了不断扩展的，越来越长的表达式。

而对于把 (mylength mylength) 提取出来之前的代码，(mylength mylength) 这个表达式被求值之后生成的是一个函数，没有出现暴露在函数体外部等待求值的表达式。它同样会产生表达式 (mylength mylength) ，只不过此时的 (mylength mylength) 被包裹在了所生成的函数里。更准确地说，是被包裹在了函数体中的一个条件分支里。只有计算时进入了该条分支，才会触发下一次对表达式 (mylength mylength) 的求值。

于是，「第 2 次转换」的前后所发生的关键性变化是 (mylength mylength) 表达式的求值步骤由「原来的 cond 条件分支内部」被提取到了「函数外部」。因此导致：

求值的时间点被提前了；
求值之后会生成新的，需要继续提前求值的，同样的表达式 (mylength mylength)。
递归的过程 (mylength mylength) 本来位于条件分支中，于是边界条件（Base Case）所提供的终止功能就会发挥作用：每次先要判断是否到达边界条件终止程序，然后才会进入含有递归的过程 (mylength mylength) 的分支中。这样避免进入死循环。
(mylength mylength) 这一递归过程被提出分支之后，程序运行流就再也触碰不到边界终止条件。没有了终止条件，就会导致死循环。

继续推导 Y 算子

上一节我们发现了问题所在，就是表达式 (mylength mylength) 被提取出来之后会导致计算机要先对它求值之后才能进行之后的步骤。而它又会在被求值后中生成新的「自己」，并且这个「自己」也需要同样被求值之后计算机才能进行之后的计算步骤。我们希望它像被提取出来前一样，「对其求值」的这一步骤能再次被放进函数的分支内。

第 3 次转换：将表达式 (mylength mylength) 打包进一个函数来延缓对它求值的时间。这种转换被称为 Eta-Expansion ( Eta-Conversion 的反向操作)。

(
  (lambda (f) (f f))

  (lambda (mylength)
    (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (lambda (g)                          ;;
      (lambda (l)                         ;;
        (cond [(null? l) 0]               ;;
              [else (+ 1 (g (cdr l)))]))) ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (x) ((mylength mylength) x))
    )
  )
)

我们将上面转换完成的代码再次输入计算机进行测试：

(
  ((lambda (f) (f f))

   (lambda (mylength)
    (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (lambda (g)                          ;;
      (lambda (l)                         ;;
        (cond [(null? l) 0]               ;;
              [else (+ 1 (g (cdr l)))]))) ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (x) ((mylength mylength) x))
    )
   )
  )

'(9 19 29) )   ;; 输出 3

成功了。我们可以接着转换了（每一步转换都要保证代码能正确运行才能进行下一步）。

第 4 次转换：更改变量名，让内部被注释框选的函数更像 define 阶段的函数（Alpha-Equivalence）

(
  (lambda (f) (f f))

  (lambda (g)
    (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (lambda (mylength)                          ;;
      (lambda (l)                                ;;
        (cond [(null? l) 0]                      ;;
              [else (+ 1 (mylength (cdr l)))]))) ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (x) ((g g) x))
    )
  )
)

经过第 4 次转换（已经输入计算机测试了代码），我们得到了和 define 阶段几乎一样的函数。除了 define 的位置使用了 lambda 之外，其他部分几乎一样了。对比如下：

;;; 使用 define 的时候 ;;;
(define mylength
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 (mylength (cdr l)))])))

;;; 没有 define 的时候 ;;;
(lambda (mylength)
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 (mylength (cdr l)))])))

第 5 次转换：把和使用 define 阶段的代码很像的部分提取出来

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (y)                                  ;;
    (                                          ;;
      (lambda (f) (f f))                       ;;
                                               ;;
      (lambda (g)                              ;;
        ( y                                    ;;  这个函数（块）就是 Y 算子
          (lambda (x) ((g g) x))               ;;
        )                                      ;;
      )                                        ;;
    )                                          ;;
  )                                            ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (lambda (mylength)                          ;;
    (lambda (l)                                ;;
      (cond [(null? l) 0]                      ;;
            [else (+ 1 (mylength (cdr l)))]))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

第 5 次转换后（已经输入计算机测试了代码），我们最终获得 Y 算子，整理后（Alpha-Equivalence）如下：

;;; Y 算子 ;;;
(lambda (g)
  ((lambda (f) (f f))
   (lambda (f)
     (g (lambda (x) ((f f) x))))))

使用 Y 算子

Y 算子的使用非常简单，只需要在目标函数外再嵌套一层函数，把这层额外的函数所带来的参数名作为递归函数名就行。

比如有 define 的时候函数的样子：

(define mylength
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 (mylength (cdr l)))])))

这时候我们把 define 改成 lambda（这样就去掉了 define）变成：

(lambda (mylength)
  (lambda (l)
    (cond [(null? l) 0]
          [else (+ 1 (mylength (cdr l)))])))

然后再用 Y 算子作用于这个 lambda 匿名函数就可以得到相应的递归函数 F 了：

(define Y
  (lambda (g)
    ((lambda (f) (f f))
     (lambda (f)
       (g (lambda (x) ((f f) x)))))))

(define F
  (Y (lambda (mylength)
       (lambda (l)
         (cond [(null? l) 0]
               [else (+ 1 (mylength (cdr l)))])))))

(F '(9 19 29))  ;; 输出 3 (链表有 3 个有效负载：9, 19, 29)

注释:
Alpha-Equivalence：不同的变量名可以等价地替换。即 (lambda (x) (+ x x)) 和 (lambda (y) (+ y y)) 效果一样。
Eta-Expansion：函数 (lambda (x) (+ x 1)) 可以扩展为 (lambda (y) ((lambda (x) (+ x 1)) y))，效果一样。

用 Javascript 的语法来写出 Y 算子

在 Javascript 的语法下， Y 算子的定义如下，可以利用上面的经验尝试推导

// Y combinator 的定义
var Y = f => 
  (x => f(v => x(x)(v)))
  (x => f(v => x(x)(v)));

提示：

;;; 上面推导出的 Y 算子 ;;;
(lambda (g)
  ((lambda (f) (f f))
   (lambda (f)
     (g (lambda (x) ((f f) x))))))


;;; 改一下变量名（Alpha-Equivalence）可以得到 ;;;
(lambda (f)
  ((lambda (f) (f f))
   (lambda (x)
     (f (lambda (v) ((x x) v))))))

进一步推导针对 Mutual Recursive 的 Y 算子

上面所推导的 Y 算子只对 mylength 这样的 Directly Recursive 函数有用，对下面这种 Mutually Recursive 函数就没用了：

;; 这里容易下意识认为要判断 0 和 1 这两个边界，其实只需要判断 0 这一个边界即可。
;; 简洁带来严密。

(define odd?
  (lambda (n)
    (cond [(= n 0) #f]
          [else (even? (- n 1))])))

(define even?
  (lambda (n)
    (cond [(= n 0) #t]
          [else (odd? (- n 1))])))

根据上面的结果，我们来继续推导适用于 Mutually Recursive 函数的 Y 算子。

分析

先明确我们的目的是什么：我们的目的是在没有 define 的情况下实现函数 odd? 和 even? ，然后从这个实现中提取出 Y 算子。

和上面同样的思路，没有了 define ，我们只能将上面 odd? 和 even? 函数绑定在参数上。下面我们先来尝试实现 odd? 函数。

(define odd?
  (lambda (n)
    (cond [(= n 0) #f]
          [else (even? (- n 1))])))

推导

首先我们很容易知道需要在新的 odd? 的函数体内储存 even? 函数的信息，可以得到：

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (even?)                       ;;
    (lambda (n)                         ;; (这是没有 define 的 odd? 函数)
      (cond [(= n 0) #f]                ;;
            [else (even? (- n 1))])))   ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (odd?)                        ;;
    (lambda (n)                         ;; (这是没有 define 的 even? 函数)
      (cond [(= n 0) #t]                ;;
            [else (odd? (- n 1))])))    ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

然后我们要像前面的 (mylength mylength) 一样，设法让 odd? 和 even? 两个函数在进入递归（ else 分支）的时候都打包保存一次自己，以供之后的递归（ else 分支）可以继续保存和调用“自己”。于是代码先做如下修改：

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (even?)                              ;;
    (lambda (n)                                ;; (这是没有 define 的 odd? 函数)
      (cond [(= n 0) #f]                       ;;
            [else ((even? even?) (- n 1))])))  ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (odd?)                               ;;
    (lambda (n)                                ;; (这是没有 define 的 even? 函数)
      (cond [(= n 0) #t]                       ;;
            [else ((odd? odd?) (- n 1))])))    ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

观察上面的 odd? 函数体内的 else 分支，可以看到当进入此分支，就要使用 even? 对 (- n 1) 进行计算了。而 even? 函数是要接收 odd?函数作为输入的，这样它的函数体内才有 odd? 函数的信息来实现它的 else 递归分支。所以这里的 (even? even?) 要改成 (even? odd?) ，这样 odd? 函数才能作为参数被输入进 even? ，进而实现传递（保存）。代码修改如下：

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (even?)                              ;;
    (lambda (n)                                ;; (这是没有 define 的 odd? 函数)
      (cond [(= n 0) #f]                       ;;
            [else ((even? odd?) (- n 1))])))   ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (odd?)                               ;;
    (lambda (n)                                ;; (这是没有 define 的 even? 函数)
      (cond [(= n 0) #t]                       ;;
            [else ((odd? odd?) (- n 1))])))    ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

到这步后，目前的代码仍然有问题。因为现在面对的是 Mutual Recursion ，两个函数相互定义彼此。要想办法在 else 递归分支处保存双方信息。继续观察 odd?（当前正在尝试实现的是没有 define 的 odd? 函数），发现 odd? 函数在获得输入后，已经包含了 even? 函数的信息，还差它自己。所以我们修改代码，让 odd? 函数把包含 even? 的自己一起存入下一次递归，这样下一次递归就同时有了 odd? 和 even?，进而一直传递和递归调用下去，直到触碰边界条件停止。代码如下：

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (even?)                                 ;;
   ((lambda (f) (f f))                            ;; (这是没有 define 的 odd? 函数)
    (lambda (odd?)                                ;;
      (lambda (n)                                 ;;
        (cond [(= n 0) #f]                        ;;
              [else ((even? odd?) (- n 1))])))))  ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (odd?)                               ;;
    (lambda (n)                                ;; (这是没有 define 的 even? 函数)
      (cond [(= n 0) #t]                       ;;
            [else ((odd? odd?) (- n 1))])))    ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

现在，我们得到了没有 define 的 odd? 函数。可以使用上面这个代码测试一下各种奇偶数了。于是再一次，Y 算子已经隐藏在其中，可以开始各种转化提取整理出 Y 算子了。

整理和提取 Y 算子 - Mutual Recursion

有了之前的经验，接下来的整理和提取轻车熟路，同样是 Alpha-Equivalence 和 Eta-Expansion 。
记得每一步变换都要确认代码能正确运行才继续哈。

第一步，分别把 (even? odd?) 和 (odd? odd?) 提取出来：

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (even?)                        ;;
   ((lambda (f) (f f))                   ;;
    (lambda (odd?)                       ;;
      ((lambda (g)                       ;; (这是没有 define 的 odd? 函数)
         (lambda (n)                     ;;
           (cond [(= n 0) #f]            ;;
                 [else (g (- n 1))])))   ;;
       (even? odd?)))))                  ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (odd?)                         ;;
       ((lambda (j)                      ;;
          (lambda (n)                    ;;
            (cond [(= n 0) #t]           ;; (这是没有 define 的 even? 函数)
                  [else (j (- n 1))])))  ;;
        (lambda (n) ((odd? odd?) n))))   ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

第二步，分别两块很像 odd? 和 even? 函数的代码提取出来。

(
 (lambda (even?)
   ((lambda (f) (f f))
    (lambda (odd?)
      (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
       (lambda (j)                       ;; (很像 odd? 的代码块)
         (lambda (n)                     ;;
           (cond [(= n 0) #f]            ;;
                 [else (j (- n 1))])))   ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
       (even? odd?)))))                  
  
  (lambda (odd?)
       (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        (lambda (k)                      ;; (很像 even? 的代码块)
          (lambda (n)                    ;;
            (cond [(= n 0) #t]           ;; 
                  [else (k (- n 1))])))  ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        (lambda (n) ((odd? odd?) n))))
)

提取后：

(
  (
   ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (lambda (j)                             ;;
     (lambda (k)                           ;;
       (                                   ;;
        (lambda (even?)                    ;;
          ((lambda (f) (f f))              ;; (Y 算子)
           (lambda (odd?)                  ;;
             (j                            ;;
              (even? odd?)))))             ;;                  
                                           ;;
        (lambda (odd?)                     ;;
          (k                               ;;
           (lambda (n) ((odd? odd?) n))))  ;;
        )))                                ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   
   ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (lambda (j)                       ;; (很像 odd? 的代码块)
     (lambda (n)                     ;;
       (cond [(= n 0) #f]            ;;
             [else (j (- n 1))])))   ;;
   ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  )
  
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (k)                      ;; (很像 even? 的代码块)
    (lambda (n)                    ;;
      (cond [(= n 0) #t]           ;; 
            [else (k (- n 1))])))  ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

第三步，修改变量名（Alpha-Equivalence），让 Y 算子还有 odd? 和 even? 函数都更加明显：

((
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (j)                            ;;
    (lambda (k)                          ;;
      ((lambda (g)                       ;;
         ((lambda (f) (f f))             ;; (Y 算子)
          (lambda (h)                    ;;
            (j (g h)))))                 ;;
       (lambda (h)                       ;;
         (k (lambda (x) ((h h) x)))))))  ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (even?)                      ;; (很像 odd? 的代码块)
    (lambda (n)                        ;;
      (cond [(= n 0) #f]               ;;
            [else (even? (- n 1))])))  ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  )
  
 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 (lambda (odd?)                       ;; (很像 even? 的代码块)
   (lambda (n)                        ;;
     (cond [(= n 0) #t]               ;; 
           [else (odd? (- n 1))])))   ;;
 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

最终，针对 Mutual Recursions 的 Y 算子为：

;;; Mutual Recursions 的 Y 算子 ;;;
(lambda (j)
  (lambda (k)
    ((lambda (g)
       ((lambda (f) (f f)) 
        (lambda (h)
          (j (g h)))))
     (lambda (h)
       (k (lambda (x) ((h h) x)))))))

可以对比一下 Direct Recursions 的 Y 算子：

;;; Direct Recursions 的 Y 算子 ;;;
(lambda (g)
  ((lambda (f) (f f))
    (lambda (f)
      (g (lambda (x) ((f f) x))))))

观察这两个 Y 算子，是不是感觉 Mutual Recursion 似乎实际上就相当于两个相互定义的函数跑完（递归完？）一个「来回（周期）」之后，再进行针对这个「来回（周期）」的 Direct Recursion？

使用 Y 算子 - For Mutually Recursive Functions

为了方便，用 define 来帮助定义，以减少代码符号，让演示更直观：

;;; Mutual Recursions 的 Y 算子 ;;;
(define Ym
  (lambda (j)
    (lambda (k)
      ((lambda (g)
         ((lambda (f) (f f)) 
          (lambda (h)
            (j (g h)))))
       (lambda (h)
         (k (lambda (x) ((h h) x))))))))

;;; 把函数的 define 换成 lambda 然后把参数名变为对方 ;;;
;;; 注释：此操作可以理解为自己需要对方来定义所以对方要作为输入 ;;;
(define o
  (lambda (even?)
    (lambda (n)                        
      (cond [(= n 0) #f]               
            [else (even? (- n 1))]))))

(define e
  (lambda (odd?)
    (lambda (n)                        
      (cond [(= n 0) #t]               
            [else (odd? (- n 1))]))))


;;; 通过 Y 算子可以很容易得到 odd? 和 even? 函数 ;;;
;;; 输入 Y 算子的先后顺序决定了函数的效果是 odd? 还是 even? ;;;
(map ((Ym o) e) '(0 1 2 3))          ;; odd? 函数判断是否为奇，输出 (#f #t #f #t)
(map ((Ym e) o) '(0 1 2 3))          ;; even? 函数判断是否为偶，输出 (#t #f #t #f)

PS：
更多关于 Mutual Recursion 的信息可查阅维基百科 Mutual Recursion

`打赏`