注:阅读本文可能需要一定 LISP或 Racket的基础知识,若没有相关基础则可查阅 Racket官方文档 来进行对照学习。
概述
在Rakect中存在一个特性叫“Y Combinator”, 它可以使你在不使用 letrec 或正常使用 define 来定义一个过程(procedure)的情况下以匿名过程 (anonymous procedures)的方式写出递归函数。我们可以先从介绍它的使用方式作为开头。例如,在Racket中,我们可以使用Y Combinator来书写一个求整数n阶乘的过程如下:
(def Fact
(Y (λ (fact)
(λ (n)
(if (zero? n)
1
(* n (fact (- n 1))))))))
由上面的例子我们可以看出,对于一个过程 f, Y Combinator的使用方式是 (Y f) , 且由于我们使用匿名过程的原因,我们需要将一个我们想使用的过程名字作为 f 的参数, 然后将对应问题的输入作为 f 所返回的过程的参数。在求阶乘的问题里,我们选用整数 n 作为我们返回的过程的参数。
原理
那么, 接下来的问题是,为什么我们可以这么做?Y Combinator的运作原理又是什么?简单来说,Y Combinator的理论来自于Lambda Calculus中的Eta-Reduction,其相关内容在这里不做讲述。我们主要从Y Combinator的实现来解决该疑问。下面是Y Combinator的具体实现:
(define Y
(λ (f)
((λ (g) (f (g g)))
(λ (g) (f (g g))))))
这段代码可能阅读与理解起来有些困难,但我们可以把它进行一些简化之后再进行分析。我们首先添加如下的定义:
(define p (λ (g) (f (g g))))
利用上述定义,我们就可以讲Y Combinator的实现简化为如下形式:
(define Y (λ (f) (p p)))
通过简化后的代码我们不难看出,Y 是一个过程,且这个过程返回的是将上文定义的过程p作为参数传入自己本身后得出的结果,即 (p p)。接下来,我们可以尝试给过程 Y 传入一个过程 k 作为参数,看一看会发生什么。
(Y k) = (λ (g) (k (g g)))
(λ (g) (k (g g)))
= (k (λ (g) (k (g g)))
(λ (g) (k (g g))))
= (k (Y k))
由此,我们不难得出,对于任意过程 f,(Y f) = (f (Y f))。根据这点,我们也可以知晓Y Combinator就是利用了 (Y f) = (f (Y f)) 的特性来实现递归。
Z/Z* Combinator
在Racket中Y Combinator的确很巧妙,但是在Scheme中,使用Y Combinator则会导致Scheme先解析 (Y f) 而陷入死循环。于是,我们便有了Z Combinator作为契合Scheme特点的Y Combinator。我在这里放出Z Combinator的实现,大家可以依照上文的分析来推导出Z Combinator的原理。
(define Z
(λ (f)
((λ (g) (f (λ (v) ((g g) v)))
(λ (g) (f (λ (v) ((g g) v))))))
在Z Combinator中, v是作为问题要求的输入存在的。
除了Z Combinator,我们还有针对不确定数量参数的过程的Z* Combinator,由于它和Z Combinator除了构造上有所不同其他方面并无太大差别,所以在此只给出实现代码,具体原理与特性可以依照上一节的内容进行推理。
(define Z*
(λ (f)
((λ (g) (f (λ args (apply (g g) args)))
(λ (g) (f (λ args (apply (g g) args))))))
References
- 3.11 Theory in Racket Official Document.
- Sildes of CS275 at Oberlin College.