Y/Z Combinator in Racket & Scheme

注:阅读本文可能需要一定 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

  1. 3.11 Theory in Racket Official Document.
  2. Sildes of CS275 at Oberlin College.