10 种编程语言实现 Y 组合子

Question

一 Y-Combinator

Y 组合子是 Lambda 演算的一部分，也是函数式编程的理论基础。它是一种方法/技巧，在没有赋值语句的前提下定义递归的匿名函数。即仅仅通过 Lambda 表达式这个最基本的 原子 实现循环/迭代，颇有道生一、一生二、二生三、三生万物的感觉。

1 从递归的阶乘函数开始

先不考虑效率等其他因素，写一个最简单的递归阶乘函数。此处采用 Scheme，你可以选择自己熟悉的编程语言跟着我一步一步实现 Y-Combinator 版的阶乘函数。

(define (factorial n)
  (if (zero? n)
    1
    (* n (factorial (- n 1)))))

Scheme 中 (define (fn-name)) 是 (define fn-name (lambda)) 的简写，就像 JS 中， function foo() {} 等价于 var foo = function() {} 。把上面的定义展开成 Lambda 的定义：

(define factorial
  (lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))

2 绑定函数名

想要递归地调用一个函数，就必须给这个函数取一个名字。匿名函数想要实现递归，就得取一个临时的名字。所谓临时，指这个名字只在此函数体内有效，函数执行完成后，这个名字就伴随函数一起消失。为解决这个问题，第一篇文章中[1]强制规定匿名函数有一个隐藏的名字 this 指向自己，这导致 this 这个变量名被强行占用，并不优雅，因此第二篇文章[2]借鉴 Clojure 的方法，允许自定义一个名字。

但在 Lambda 演算中，只有最普通的 Lambda，没有赋值语句，如何绑定一个名字呢？答案是使用 Lambda 的参数列表！

(lambda (factorial)
  (lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))

3 生成阶乘函数的函数

虽然通过参数列表，即使用闭包技术给匿名函数取了一个名字，但此函数并不是我们想要的阶乘函数，而是阶乘函数的元函数（meta-factorial），即生成阶乘函数的函数。因此需要执行这个元函数，获得想要的阶乘函数：

((lambda (factorial)
   (lambda (n)
     (if (zero? n)
       1
       (* n (factorial (- n 1))))))
 xxx)

此时又出现另一个问题：实参 xxx，即形参 factorial 该取什么值？从定义来看，factorial 就是函数自身，既然是“自身”，首先想到的就是复制一份一模一样的代码：

((lambda (factorial)
   (lambda (n)
     (if (zero? n)
       1
       (* n (factorial (- n 1))))))
 (lambda (factorial)
   (lambda (n)
     (if (zero? n)
       1
       (* n (factorial (- n 1)))))))

看起来已经把自己传递给了自己，但马上发现 (factorial (- n 1)) 会失败，因为此时的 factorial 不是一个阶乘函数，而是一个包含阶乘函数的函数，即要获取包含在内部的函数，因此调用方式要改成 ((meta-factorial meta-factorial) (- n 1)) ：

((lambda (meta-factorial)
   (lambda (n)
     (if (zero? n)
       1
       (* n ((meta-factorial meta-factorial) (- n 1))))))
 (lambda (meta-factorial)
   (lambda (n)
     (if (zero? n)
       1
       (* n ((meta-factorial meta-factorial) (- n 1)))))))

把名字改成 meta-factorial 就能清晰地看出它是阶乘的元函数，而不是阶乘函数本身。

4 去除重复

以上代码已经实现了 lambda 的自我调用，但其中包含重复的代码，meta-factorial 即做函数又做参数，即 (meta meta) ：

((lambda (meta)
   (meta meta))
 (lambda (meta-factorial)
   (lambda (n)
     (if (zero? n)
       1
       (* n ((meta-factorial meta-factorial) (- n 1)))))))

5 提取阶乘函数

因为我们想要的是阶乘函数，所以用 factorial 取代 (meta-factorial meta-factorial) ，方法同样是使用参数列表命名：

((lambda (meta)
   (meta meta))
 (lambda (meta-factorial)
   ((lambda (factorial)
      (lambda (n)
        (if (zero? n)
          1
          (* n (factorial (- n 1))))))
    (meta-factorial meta-factorial))))

这段代码还不能正常运行，因为 Scheme 以及其他主流的编程语言实现都采用“应用序”，即执行函数时先计算参数的值，因此 (meta-factorial meta-factorial) 原来是在求阶乘的过程中才被执行，现在提取出来后执行的时间被提前，于是陷入无限循环。解决方法是把它包装在 Lambda 中（你学到了 Lambda 的另一个用处：延迟执行）。

((lambda (meta)
   (meta meta))
 (lambda (meta-factorial)
   ((lambda (factorial)
      (lambda (n)
        (if (zero? n)
          1
          (* n (factorial (- n 1))))))
    (lambda args
      (apply (meta-factorial meta-factorial) args)))))

此时，代码中第 4 行到第 8 行正是最初定义的匿名递归阶乘函数，我们终于得到了阶乘函数本身！

6 形成模式

如果把其中的阶乘函数作为一个整体提取出来，那就是得到一种“模式”，即能生成任意匿名递归函数的模式：

((lambda (fn)
   ((lambda (meta)
      (meta meta))
    (lambda (meta-fn)
      (fn
        (lambda args
          (apply (meta-fn meta-fn) args))))))
 (lambda (factorial)
   (lambda (n)
     (if (zero? n)
       1
       (* n (factorial (- n 1)))))))

Lambda 演算中称这个模式为 Y 组合子（Y-Combinator），即：

(define (y-combinator fn)
  ((lambda (meta)
     (meta meta))
   (lambda (meta-fn)
     (fn
       (lambda args
         (apply (meta-fn meta-fn) args))))))

有了 Y 组合子，我们就能定义任意的匿名递归函数。前文中定义的是递归求阶乘，再定义一个递归求斐波那契数：

(y-combinator
  (lambda (fib)
    (lambda (n)
      (if (< n 3)
        1
      (+ (fib (- n 1))
         (fib (- n 2)))))))

二 10 种实现

下面用 10 种不同的编程语言实现 Y 组合子，以及 Y 版的递归阶乘函数。实际开发中可能不会用上这样的技巧，但这些代码分别展示了这 10 种语言的诸多语法特性，能帮助你了解如何在这些语言中实现以下功能：

1. 如何定义匿名函数；
2. 如何就地调用一个匿名函数；
3. 如何将函数作为参数传递给其他函数；
4. 如何定义参数数目不定的函数；
5. 如何把函数作为值返回；
6. 如何将数组里的元素平坦开来传递给函数；
7. 三元表达式的使用方法。

这 10 种编程语言，有 Python、PHP、Perl、Ruby 等大家耳熟能详的脚本语言，估计最让大家惊讶的应该是其中有 Java！

1 Scheme

我始终觉得 Scheme 版是这么多种实现中最优雅的！它没有“刻意”的简洁，读起来很自然。

(define (y-combinator f)
  ((lambda (u)
     (u u))
   (lambda (x)
     (f (lambda args
          (apply (x x) args))))))

((y-combinator
  (lambda (factorial)
    (lambda (n)
      (if (zero? n)
          1
          (* n (factorial (- n 1)))))))
 10) ; => 3628800

2 Clojure

其实 Clojure 不需要借助 Y-Combinator 就能实现匿名递归函数，它的 lambda——fn——支持传递一个函数名，为这个临时函数命名。也许 Clojure 的 fn 不应该叫匿名函数，应该叫临时函数更贴切。

同样是 Lisp，Clojure 版本比 Scheme 版本更简短，却让我感觉是一种刻意的简洁。我喜欢用 fn 取代 lambda，但用稀奇古怪的符号来缩减代码量会让代码的可读性变差（我最近好像变得不太喜欢用符号，哈哈）。

(defn y-combinator [f]
  (#(% %) (fn [x] (f #(apply (x x) %&)))))

((y-combinator
  (fn [factorial]
    #(if (zero? %) 1 (* % (factorial (dec %))))))
 10)

3 Common Lisp

Common Lisp 版和 Scheme 版其实差不多，只不过 Common Lisp 属于 Lisp-2，即函数命名空间与变量命名空间不同，因此调用匿名函数时需要额外的 funcall。我个人不喜欢这个额外的调用，觉得它是冗余信息，位置信息已经包含了角色信息，就像命令行的第一个参数永远是命令。

(defun y-combinator (f)
  ((lambda (u)
     (funcall u u))
   (lambda (x)
     (funcall f (lambda (&rest args)
                  (apply (funcall x x) args))))))

(funcall (y-combinator
          (lambda (factorial)
            (lambda (n)
              (if (zerop n)
                1
                (* n (funcall factorial (1- n)))))))
         10)

4 Ruby

Ruby 从 Lisp 那儿借鉴了许多，包括它的缺点。和 Common Lisp 一样，Ruby 中执行一个匿名函数也需要额外的“.call”，或者使用中括号“[]”而不是和普通函数一样的小括号“()”，总之在 Ruby 中匿名函数与普通函数不一样！还有繁杂的符号也影响我在 Ruby 中使用匿名函数的心情，因此我会把 Ruby 看作语法更灵活、更简洁的 Java，而不会考虑写函数式风格的代码。

def y_combinator(&f)
  lambda {|&u| u[&u]}.call do |&x|
    f[&lambda {|*a| x[&x][*a]}]
  end
end

y_combinator do |&factorial|
  lambda {|n| n.zero? ? 1: n*factorial[n-1]}
end[10]

5 Python

Python 中匿名函数的使用方式与普通函数一样，就这段代码而言，Python 之于 Ruby 就像 Scheme 之于 Common Lisp。但 Python 对 Lambda 的支持简直弱爆了，函数体只允许有一条语句！我决定我的工具箱中用 Python 取代 C 语言，虽然 Python 对匿名函数的支持只比 C 语言好一点点。

def y_combinator(f):
    return (lambda u: u(u))(lambda x: f(lambda *args: x(x)(*args)))

y_combinator(lambda factorial: lambda n: 1 if n < 2 else n * factorial(n-1))(10)

6 Perl

我个人对 Perl 函数不能声明参数的抱怨更甚于繁杂的符号！

sub y_combinator {
    my $f = shift;
    sub { $_[0]->($_[0]); }->(sub {
        my $x = shift;
        $f->(sub { $x->($x)->(@_); });
    });
}

print y_combinator(sub {
    my $factorial = shift;
    sub { $_[0] < 2? 1: $_[0] * $factorial->($_[0] - 1); };
})->(10);

假设 Perl 能像其他语言一样声明参数列表，代码会更简洁直观：

sub y_combinator($f) {
  sub($u) { $u->($u); }->(sub($x) {
    $f->(sub { $x->($x)->(@_); });
  });
}

print y_combinator(sub($factorial) {
  sub($n) { $n < 2? 1: $n * $factorial->($n - 1); };
})->(10);

7 JavaScript

JavaScript 无疑是脚本语言中最流行的！但冗长的 function、return 等关键字总是刺痛我的神经：

var y_combinator = function(fn) {
    return (function(u) {
        return u(u);
    })(function(x) {
        return fn(function() {
            return x(x).apply(null, arguments);
        });
    });
};

y_combinator(function(factorial) {
    return function(n) {
        return n <= 1? 1: n * factorial(n - 1);
    };
})(10);

ES6 提供了 => 语法，可以更加简洁：

const y_combinator = fn => (u => u(u))(x => fn((...args) => x(x)(...args)));
y_combinator(factorial => n => n <= 1? 1: n * factorial(n - 1))(10);

8 Lua

Lua 和 JavaScript 有相同的毛病，最让我意外的是它没有三元运算符！不过没有使用花括号让代码看起来清爽不少~

function y_combinator(f)
    return (function(u)
        return u(u)
    end)(function(x)
        return f(function(...)
            return x(x)(...)
        end)
    end)
end

print(y_combinator(function(factorial)
    return function(n)
        return n < 2 and 1 or n * factorial(n-1)
    end
end)(10))

注意：Lua 版本为 5.2。5.1 的语法不同，需将 x(x)(...) 换成 x(x)(unpack(arg)) 。

9 PHP

PHP 也是 JavaScript 的难兄难弟，function、return……

此外，PHP 版本是脚本语言中符号（$、_、()、{}）用的最多的！是的，比 Perl 还多。

function y_combinator($f) {
    return call_user_func(function($u) {
        return $u($u);
    }, function($x) use ($f) {
        return $f(function() use ($x) {
            return call_user_func_array($x($x), func_get_args());
        });
    });
}

echo call_user_func(y_combinator(function($factorial) {
    return function($n) use ($factorial) {
        return ($n < 2)? 1: ($n * $factorial($n-1));
    };
}), 10);

10 Java

最后，Java 登场。我说的不是 Java 8，即不是用 Lambda 表达式，而是匿名类！匿名函数的意义是把代码块作为参数传递，这正是匿名类所做得事情。

相关链接

[1] http://zzp.me/2011-08-05/recursive-lambda/
[2] http://zzp.me/2012-08-04/clojure-style-lambda-in-common-lisp/