由于主要涉及无类型 λ 演算，因此这里不使用类型系统较复杂的函数式编程语言作为示例，仅选用 Racket、Erlang 和 C++，并保证函数均柯里化。

Y 组合子

以下内容主要来自 Lambda-Calculus and Combinators (An Introduction) 2nd Edition。

在 λ 演算/组合子逻辑中，组合子 Y 满足以下条件。

\[{\bf{Y}} =_{β,w} x({\bf{Y}}x)\]

因此其也被称为不动点组合子。

柯里和 Paul Rosenbloom 发现的 Y 组合子为 \({\bf{Y}}_{Curry-Ros} {\equiv} {\lambda}x.VV\)，其中 \(V {\equiv} {\lambda}y.x(yy)\)。

图灵发现的 Y 组合子为 \({\bf{Y}}_{Turing} {\equiv} UU\)，其中 \(U {\equiv} {\lambda}ux.x(uux)\)。

证明略。

代入，并统一一下其中的变量名，即可得到如下形式的 Y 组合子。

  • \[{\bf{Y}}_{Curry-Ros} {\equiv} {\lambda}x({\lambda}y.x(yy))({\lambda}y.x(yy))\]
  • \[{\bf{Y}}_{Turing} {\equiv} ({\lambda}xy.y(xxy))({\lambda}xy.y(xxy))\]

Y 组合子可以用来消除 λ 演算中的“函数名”，从而可用于构建递归结构。

递归——栈溢出

这样的 Y 组合子形式并不困难，也很容易找到使用 Y 组合子实现阶乘、斐波那契数列等的例子。试试阶乘？

但正当我准备写了几行 Erlang 代码准备跑一跑时，我发现——死机了。

打开 htop，发现 beam 进程的 CPU 占用和内存占用飙升，大概是触发死循环了。啊，不对，现在并没有循环这个结构，应该叫无限递归。

那么问题出在哪里呢？找了找其它语言的示例，还有稀少的 Erlang 的示例，我发现他们的代码大都只有一个 Y 组合子实现，而且和上面两个 Y 组合子都不太一样……

Racket

可能是 Erlang 代码中太多 end 和参数应用混淆在一起出了问题，那么换一个语言吧，比如示例中的 Racket。

#lang lazy

(define Fact (λ (f) (λ (n) (if (zero? n) 1 (* n (f (- n 1)))))))

(define Yc (λ (x) ((λ (y) (x (y y))) (λ (y) (x (y y))))))

(define Yt ((λ (x) (λ (y) (y ((x x) y)))) (λ (x) (λ (y) (y ((x x) y))))))

((Yc Fact) 5)

((Yt Fact) 5)

这里，将开头惰性求值的 #lang lazy 换成 #lang racket 后也可以在 Racket IDE 中看到内存飙升的情况。那么，应该是求值策略的问题。

这里有两个参考链接：wiki、reddit。

惰性求值的方式下这种写法没有问题，但 Racket 的 #lang racket 和 Erlang 都是采用的严格求值策略，因此会无限展开直到栈溢出。

通过手动代入观察，以及参考其它语言的示例，不难发现，只需要进行简单的 η-变换即可回避这种问题。变换后的 Y 组合子也被称为 Z 组合子。

η-变换

简单的 η-变换可表示为 \(f {\equiv} {\lambda}x.fx\)。

变换后的两个 Y 组合子的形式如下。

  • \[{\bf{Y}}_{Curry-Ros} {\equiv} {\lambda}x({\lambda}y.x(yy))({\lambda}y.x(yy))\]
  • \[{\bf{Z}}_{Curry-Ros} {\equiv} {\lambda}x({\lambda}y.x({\lambda}z.(yyz)))({\lambda}y.x({\lambda}z.(yyz)))\]
  • \[{\bf{Y}}_{Turing} {\equiv} ({\lambda}xy.y(xxy))({\lambda}xy.y(xxy))\]
  • \[{\bf{Z}}_{Turing} {\equiv} ({\lambda}xy.y({\lambda}z.xxyz))({\lambda}xy.y({\lambda}z.xxyz))\]

换用严格求值的 Racket 试试。

#lang racket

(define Fact (λ (f) (λ (n) (if (zero? n) 1 (* n (f (- n 1)))))))

(define Zc (λ (x) ((λ (y) (x (λ (z) ((y y) z)))) (λ (y) (x (λ (z) ((y y) z)))))))

(define Zt ((λ (x) (λ (y) (y (λ (z) (((x x) y) z))))) (λ (x) (λ (y) (y (λ (z) (((x x) y) z)))))))

((Zc Fact) 5)
((Zt Fact) 5)

代码可以精简一下，λ 一样的地方可以合并进去，改写成 Erlang 如下。

-module(y).
-export([main/1]).

main(_) ->
    Yc = fun(X) -> fun(F) -> F(F) end(fun(Y) -> X(fun(Z) -> (Y(Y))(Z) end) end)end,
    Yt = fun(F) -> F(F) end(fun(X) -> fun(Y) -> Y(fun(Z) -> ((X(X))(Y))(Z) end) end end),
    Fac = fun (F) ->
                  fun (N) -> if N == 0 -> 1; true -> N * F(N - 1) end end
          end,
    (Yc(Fac))(5),
    (Yt(Fac))(5).

大功告成！

顺便一提，在 OTP 17 支持具名 fun 之前，在 Erlang shell 里写递归的 fun 都需要借助 Y 组合子。当然，不需要柯里化的话，形式比起上面一串代码简洁易懂一些。

最后，换一个好玩的语言尝试一下放飞自我吧~

#include <functional>

int main()
{
    auto yc = [](auto&& x) {
        return [](auto&& f) {
            return f(f);
        }([=](auto&& y) { return x([=](auto&& z) { return y(y)(z); }); });
    };

    auto yt = [](auto&& f) { return f(f); }([](auto&& x) {
        return
            [=](auto&& y) { return y([=](auto&& z) { return x(x)(y)(z); }); };
    });

    auto fac = []<typename T = int>(auto&& f)->std::function<T(T)>
    {
        return [=](T&& n) -> T { return n == 0 ? 1 : n * f(n - 1); };
    };

    yc(fac)(5.0);
    yt(fac)(5);
}

C++ 是个好东西，嗯，可以直接翻译过来。然而，各编译器行为开始不一致了。

  • g++ -std=c++20，正常编译通过
  • clang++ -std=c++20，error: function XXX with deduced return type cannot be used before it is defined
  • MSVC，提示缺少模板参数

肯定只有一个编译器行为正确，查阅了一番，stackoverflow 上的回答大概说明了只有 clang 的行为正确。

因此，上述直译得到的确实是不合规的 C++ 代码。因为本文并不打算过多涉及类型，这里也就暂不去写比较好看的合规翻译版本了。

组合子逻辑

既然叫做 Y 组合子，那么它也可以使用组合子逻辑表示，大致可理解为消除了约束变量的 λ 演算。常见的有 SKI 组合子系统，也有使用 B, C, K, W 的，大体类似。最简的组合子逻辑只需要 \({\bf{S}}\) 和 \({\bf{K}}\) 两个组合子，\({\bf{I}}\) 可用 \({\bf{SKK}}\) 表达。

由于求值策略要求，此处选用惰性求值的语言。基本的几个组合子定义如下。

#lang lazy

(define I (λ (x) x))
(define K (λ (x) (λ (y) x)))
(define S (λ (x) (λ (y) (λ (z) ((x z) (y z))))))
(define B (λ (x) (λ (y) (λ (z) (x (y z))))))
(define C (λ (x) (λ (y) (λ (z) ((x z) y)))))
(define W (λ (x) (λ (y) ((x y) y))))

对应的 Y 组合子有好几种表示。

#lang lazy

(define Fact (λ (f) (λ (n) (if (zero? n) 1 (* n (f (- n 1)))))))

(define Y0 ((S (K ((S I) I))) ((S ((S (K S)) K)) (K ((S I) I)))))
(define Y1 ((W I) ((B (S I)) (W I))))
(define Y2 ((W S) ((B W) B)))

((Y0 Fact) 5)
((Y1 Fact) 5)
((((S I) Y2) Fact) 5)

最后一条，有 \({\bf{S}}{\bf{I}}{\bf{Y}} = {\bf{Y}}\)。证明略。