巧妙的Y运算符

在完成SICP 4.21时接触到Y运算符，感觉很巧妙，这里加以总结，大部分内容来自于第二份讲义，这里只做了翻译以及总结的工作。

参考资料：

https://liujiacai.net/blog/2016/02/22/recursion-without-name/

https://mvanier.livejournal.com/2897.html

问题的引入

问题来自于sicp习题4.21，基本问题是，如何不使用递归来定义递归函数？答案是，使用Y运算符。后续会一步步引入Y运算符，为了叙述方便，这里以阶乘函数为例：

(define factorial
  (lambda (n)
    (if (= n 0)
        1
        (* n (factorial (- n 1))))))

简单的想法

为了消除递归定义，只要将函数内factorial替换即可：

(define sort-of-factorial
  (lambda (n)
    (if (= n 0)
        1
        (* n (<???> (- n 1))))))

那么???处应该也是个函数，我们将其设为f，作为参数传入：

(define almost-factorial
	(lambda (f)
		(lambda (n)
			(if (= n 0)
			1
			(* n (f (- n 1)))))))

注意almost-factorial并不是阶乘函数，事实上，它是一个高阶函数，需要传入f，后续的问题是，如何找到f，使得

(almost-factorial f)

为阶乘函数。

假设我们现在已有一个阶乘函数factorialA（不管其是否由递归定义），那么通过定义不难验证通过almost-factorial定义的factorialB也是阶乘函数

(define factorialB (almost-factorial factorialA))

但是问题是如何找到factorialA？一个很巧妙的想法是考虑

(define factorialA (almost-factorial factorialA))

如果程序语言支持惰性求值，那么上述定义是没有问题的，反之则会报错（循环定义），后续的目标是通过一个方式绕开这点，使之对不支持惰性求值的程序语言依然有效。

不动点

不动点的定义

假设$f:\mathbb R\to \mathbb R$，那么$x$为函数$f$的不动点，如果其满足

$$x=f(x)$$

后续会使用不动点的概念。

引入不动点

考虑函数：

(define identity (lambda (x) x))
(define factorial0 (almost-factorial identity))

那么

(factorial0 0)
==> ((almost-factorial identity) 0)
==> 1

(factorial0 1)
==> ((almost-factorial identity) 1)
==> (* 1 (identity 0))
==> 0

接着定义

(define factorial1 (almost-factorial factorial0))

那么

(factorial1 0)
==> 1

(factorial1 1)
==> ((almost-factorial factorial0) 0)
==> (* 1 (factorial0 0))
==> 1

(factorial1 2)
==> ((almost-factorial factorial0) 1)
==> (* 2 (factorial0 1))
==> 0

一般的，定义

(define factorial{k} (almost-factorial factorial{k-1}))

不难验证，factorialk对于$n < k$均满足阶乘函数的定义，所以，要得到正确的阶乘函数，我们应该令$k\to \infty$，即定义

(define factorial-infinity
  (almost-factorial
   (almost-factorial
    (almost-factorial
     ...))))

但是显然不可能用上述方式定义。

现在换一个角度考虑，不难发现factorial-infinity满足

factorial-infinity = (almost-factorial factorial-infinity)

这个形式是很熟悉的，即factorial-infinity为高阶函数almost-factorial的不动点。

Y运算符

引入Y运算符

现在引入Y运算符：

(Y f) = fixpoint-of-f

其中fixpoint-of-f满足

(f fixpoint-of-f) = fixpoint-of-f

那么

factorial-infinity = (Y almost-factorial)

更一般的，对于递归函数f，如果我们可以找到f对应的almost-f（这部分还需要查阅相关资料来补充almost-f的存在性），那么

f = (Y almost-f)

现在的问题是如何定义Y？

定义（惰性求值）

根据定义可得

(Y f) = fixpoint-of-f = (f fixpoint-of-f) = (f (Y f))

因此可以定义

(define (Y f) (f (Y f)))

; lambda表达式
(define Y
  (lambda (f)
    (f (Y f))))

注意到

(Y f) = (lambda (x) ((Y f) x))

那么Y表达式可以修改为

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

根据该定义，不难给出阶乘函数的定义

(define almost-factorial
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))

(define factorial (Y almost-factorial))

(define factorial
  ((lambda (f) (f (lambda (x) ((Y f) x))))
   almost-factorial))

==>

(define factorial
  (almost-factorial (lambda (x) ((Y almost-factorial) x))))

==>

(define factorial
  (lambda (n)
    (if (= n 0)
        1
        (* n ((lambda (x) ((Y almost-factorial) x)) (- n 1))))))

和之前的讨论类似，该定义只有在惰性求值下才有意义，我们希望给出一个在非惰性求值依然适用的情形。

定义（非惰性求值）

引入Y运算符

回顾在惰性求值下，我们可以定义

(define (Y f) (f (Y f)))

我们的目标是不使用递归的方式定义Y。

依然回到最开始的例子：

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

要使得该函数不是递归定义，可以使用类似之前的方法引入参数self，注意这里self出现的位置不同：

(define (part-factorial self n)
  (if (= n 0)
      1
      (* n (self (- n 1)))))

注意该定义是有问题的，因为如下调用会报错

(part-factorial part-factorial n)
; 参数数量不匹配
(* n (part-factorial (- n 1)))

为了解决这点，对函数内部做修改即可

(define (part-factorial self n)
  (if (= n 0)
      1
      (* n (self self (- n 1)))))

不难验证

(define factorial (part-factorial part-factorial))
(factorial n) = n!

为了使得part-factorial的定义和最初版本类似，做如下变换

(define (part-factorial self)
  (lambda (n)
    (if (= n 0)
        1
        (* n ((self self) (- n 1))))))

注意到这里我们没有使用递归来定义阶乘函数。

为了使part-factorial向almost形式靠齐，做如下变换

(define (part-factorial self)
  (let ((f (self self)))
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))

注意到

(let ((x <expr1>)) <expr2>)
==> ((lambda (x) <expr2>) <expr1>)

那么上述形式也等价于

(define (part-factorial self)
  ((lambda (f)
     (lambda (n)
       (if (= n 0)
           1
           (* n (f (- n 1))))))
   (self self)))

回顾almost-factorial的定义，

(define almost-factorial
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))

不难发现part-factorial可以使用如下方式定义

(define (part-factorial self)
  (almost-factorial
   (self self)))

那么

(define factorial (part-factorial part-factorial))

为了做进一步的变换，使用lambda表达式重写part-factorial

(define part-factorial
  (lambda (self)
    (almost-factorial
     (self self))))

代入到factorial的定义中可得

(define factorial
  (let ((part-factorial (lambda (self) 
                          (almost-factorial 
                           (self self)))))
    (part-factorial part-factorial)))

; 用x替换part-factorial
(define factorial
  (let ((x (lambda (self) 
             (almost-factorial (self self)))))
    (x x)))

消除let可得

(define factorial
  ((lambda (x) (x x))
   (lambda (self) 
     (almost-factorial (self self)))))

; 用x替换self
(define factorial
  ((lambda (x) (x x))
   (lambda (x) 
     (almost-factorial (x x)))))

提取核心部分，定义

(define (make-recursive f)
  ((lambda (x) (x x))
   (lambda (x) (f (x x)))))

那么

(define factorial (make-recursive almost-factorial))

事实上，make-recursive就是Y运算符：

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

等价定义

使用lambda表达式进行改写得到

(define Y
  (lambda (f)
    (f (Y f))))

注意到

(Y f) = (lambda (x) ((Y f) x))

那么Y表达式可以修改为

; (define (Y f) (f (Y f)))
(define Y
  (lambda (f)
    (f (lambda (x) ((Y f) x)))))

; (define (Y f)
;   ((lambda (x) (x x))
;    (lambda (x) (f (x x)))))
(define Y 
  (lambda (f)
    ((lambda (x) (x x))
     (lambda (x) (f (x x))))))

现在考虑如下事实：

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

==>
(let (y (lambda (x) (f (x x))))
  (y y))

==>
((lambda (x) (f (x x))
 (lambda (x) (f (x x)))

所以Y的等价定义为

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

验证不动点性质

最后我们来验证Y满足

(Y f) = (f (Y f))

注意到

(Y f)
= ((lambda (x) (f (x x)))
   (lambda (x) (f (x x))))
= (let (y (lambda (x) (f (x x))))
		(f y y))
= (f ((lambda (x) (f (x x)))
      (lambda (x) (f (x x)))))
= (f (Y f))

小结

对于递归函数

(define f (F1 f))

假设我们可以找到一个函数F2，使其满足

f = (F2 f)

那么利用Y算子即可得到y：

(define f (Y F2))

其中Y算子的定义如下：

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

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

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

后续问题，如何找到递归函数F1对应的F2，此问题似乎比较难，目前只找到如下资料：

• https://en.wikipedia.org/wiki/Denotational_semantics

之后学习相关资料后再加以补充。