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

 

一 Y-Combinator

 

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

1 从递归的阶乘函数开始

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

1. (define (factorial n) 
2.   (if (zero? n) 
3.     1 
4.     (* n (factorial (- n 1))))) 

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

1. (define factorial 
2.   (lambda (n) 
3.     (if (zero? n) 
4.       1 
5.       (* n (factorial (- n 1)))))) 

2 绑定函数名

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

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

1. (lambda (factorial) 
2.   (lambda (n) 
3.     (if (zero? n) 
4.       1 
5.       (* n (factorial (- n 1)))))) 

3 生成阶乘函数的函数

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

1. ((lambda (factorial) 
2.    (lambda (n) 
3.      (if (zero? n) 
4.        1 
5.        (* n (factorial (- n 1)))))) 
6.  xxx) 

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

1. ((lambda (factorial) 
2.    (lambda (n) 
3.      (if (zero? n) 
4.        1 
5.        (* n (factorial (- n 1)))))) 
6.  (lambda (factorial) 
7.    (lambda (n) 
8.      (if (zero? n) 
9.        1 
10.        (* n (factorial (- n 1))))))) 

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

1. ((lambda (meta-factorial) 
2.    (lambda (n) 
3.      (if (zero? n) 
4.        1 
5.        (* n ((meta-factorial meta-factorial) (- n 1)))))) 
6.  (lambda (meta-factorial) 
7.    (lambda (n) 
8.      (if (zero? n) 
9.        1 
10.        (* n ((meta-factorial meta-factorial) (- n 1))))))) 

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

4 去除重复

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

1. ((lambda (meta) 
2.    (meta meta)) 
3.  (lambda (meta-factorial) 
4.    (lambda (n) 
5.      (if (zero? n) 
6.        1 
7.        (* n ((meta-factorial meta-factorial) (- n 1))))))) 

5 提取阶乘函数

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

1. ((lambda (meta) 
2.    (meta meta)) 
3.  (lambda (meta-factorial) 
4.    ((lambda (factorial) 
5.       (lambda (n) 
6.         (if (zero? n) 
7.           1 
8.           (* n (factorial (- n 1)))))) 
9.     (meta-factorial meta-factorial)))) 

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

1. ((lambda (meta) 
2.    (meta meta)) 
3.  (lambda (meta-factorial) 
4.    ((lambda (factorial) 
5.       (lambda (n) 
6.         (if (zero? n) 
7.           1 
8.           (* n (factorial (- n 1)))))) 
9.     (lambda args 
10.       (apply (meta-factorial meta-factorial) args))))) 

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

6 形成模式

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

1. ((lambda (fn) 
2.    ((lambda (meta) 
3.       (meta meta)) 
4.     (lambda (meta-fn) 
5.       (fn 
6.         (lambda args 
7.           (apply (meta-fn meta-fn) args)))))) 
8.  (lambda (factorial) 
9.    (lambda (n) 
10.      (if (zero? n) 
11.        1 
12.        (* n (factorial (- n 1))))))) 

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

1. (define (y-combinator fn) 
2.   ((lambda (meta) 
3.      (meta meta)) 
4.    (lambda (meta-fn) 
5.      (fn 
6.        (lambda args 
7.          (apply (meta-fn meta-fn) args)))))) 

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

1. (y-combinator 
2.   (lambda (fib) 
3.     (lambda (n) 
4.       (if (< n 3) 
5.         1 
6.       (+ (fib (- n 1)) 
7.          (fib (- n 2))))))) 

二 10种实现

 

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

如何定义匿名函数;

如何就地调用一个匿名函数;

如何将函数作为参数传递给其他函数;

如何定义参数数目不定的函数;

如何把函数作为值返回;

如何将数组里的元素平坦开来传递给函数;

三元表达式的使用方法。

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

1 Scheme

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

1. (define (y-combinator f) 
2.   ((lambda (u) 
3.      (u u)) 
4.    (lambda (x) 
5.      (f (lambda args 
6.           (apply (x x) args)))))) 
7.  
8. ((y-combinator 
9.   (lambda (factorial) 
10.     (lambda (n) 
11.       (if (zero? n) 
12.           1 
13.           (* n (factorial (- n 1))))))) 
14.  10) ; => 3628800 

2 Clojure

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

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

1. (defn y-combinator [f] 
2.   (#(% %) (fn [x] (f #(apply (x x) %&))))) 
3.  
4. ((y-combinator 
5.   (fn [factorial] 
6.     #(if (zero? %) 1 (* % (factorial (dec %)))))) 
7.  10) 

3 Common Lisp

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

1. (defun y-combinator (f) 
2.   ((lambda (u) 
3.      (funcall u u)) 
4.    (lambda (x) 
5.      (funcall f (lambda (&rest args) 
6.                   (apply (funcall x x) args)))))) 
7.  
8. (funcall (y-combinator 
9.           (lambda (factorial) 
10.             (lambda (n) 
11.               (if (zerop n) 
12.                 1 
13.                 (* n (funcall factorial (1- n))))))) 
14.          10) 

4 Ruby

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

1. def y_combinator(&f) 
2.   lambda {|&u| u[&u]}.call do |&x| 
3.     f[&lambda {|*a| x[&x][*a]}] 
4.   end 
5. end 
6.  
7. y_combinator do |&factorial| 
8.   lambda {|n| n.zero? ? 1: n*factorial[n-1]} 
9. end[10] 

5 Python

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

1. def y_combinator(f): 
2.     return (lambda u: u(u))(lambda x: f(lambda *args: x(x)(*args))) 
3.  
4. y_combinator(lambda factorial: lambda n: 1 if n < 2 else n * factorial(n-1))(10) 

6 Perl

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

1. sub y_combinator { 
2.     my $f = shift; 
3.     sub { $_[0]->($_[0]); }->(sub { 
4.         my $x = shift; 
5.         $f->(sub { $x->($x)->(@_); }); 
6.     }); 
7. } 
8.  
9. print y_combinator(sub { 
10.     my $factorial = shift; 
11.     sub { $_[0] < 2? 1: $_[0] * $factorial->($_[0] - 1); }; 
12. })->(10); 

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

1. sub y_combinator($f) { 
2.   sub($u) { $u->($u); }->(sub($x) { 
3.     $f->(sub { $x->($x)->(@_); }); 
4.   }); 
5. } 
6.  
7. print y_combinator(sub($factorial) { 
8.   sub($n) { $n < 2? 1: $n * $factorial->($n - 1); }; 
9. })->(10); 

7 JavaScript

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

1. var y_combinator = function(fn) { 
2.     return (function(u) { 
3.         return u(u); 
4.     })(function(x) { 
5.         return fn(function() { 
6.             return x(x).apply(null, arguments); 
7.         }); 
8.     }); 
9. }; 
10.  
11. y_combinator(function(factorial) { 
12.     return function(n) { 
13.         return n <= 1? 1: n * factorial(n - 1); 
14.     }; 
15. })(10); 

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

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

8 Lua

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

1. function y_combinator(f) 
2.     return (function(u) 
3.         return u(u) 
4.     end)(function(x) 
5.         return f(function(...) 
6.             return x(x)(...) 
7.         end) 
8.     end) 
9. end 
10.  
11. print(y_combinator(function(factorial) 
12.     return function(n) 
13.         return n < 2 and 1 or n * factorial(n-1) 
14.     end 
15. end)(10)) 

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

9 PHP

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

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

1. <?php 
2. function y_combinator($f) { 
3.     return call_user_func(function($u) { 
4.         return $u($u); 
5.     }, function($x) use ($f) { 
6.         return $f(function() use ($x) { 
7.             return call_user_func_array($x($x), func_get_args()); 
8.         }); 
9.     }); 
10. } 
11.  
12. echo call_user_func(y_combinator(function($factorial) { 
13.     return function($n) use ($factorial) { 
14.         return ($n < 2)? 1: ($n * $factorial($n-1)); 
15.     }; 
16. }), 10); 

10 Java

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

1. package me.zzp.fn; 
2.  
3. public class YCombinator { 
4.     public interface Lambda<E> { 
5.         E call(Object... args); 
6.     } 
7.  
8.     public static Lambda<Lambda> yCombinator(final Lambda<Lambda> f) { 
9.         return new Lambda<Lambda>() { 
10.             @Override 
11.             public Lambda call(Object... args) { 
12.                 final Lambda<Lambda> u = (Lambda<Lambda>) args[0]; 
13.                 return u.call(u); 
14.             } 
15.         }.call(new Lambda<Lambda>() { 
16.             @Override 
17.             public Lambda call(Object... args) { 
18.                 final Lambda<Lambda> x = (Lambda<Lambda>) args[0]; 
19.                 return f.call(new Lambda<Object>() { 
20.                     @Override 
21.                     public Object call(Object... args) { 
22.                         return x.call(x).call(args); 
23.                     } 
24.                 }); 
25.             } 
26.         }); 
27.     } 
28.  
29.     public static void main(String[] args) { 
30.         Lambda<Lambda> y = yCombinator(new Lambda<Lambda>() { 
31.             @Override 
32.             public Lambda call(Object... args) { 
33.                 final Lambda<Integer> factorial = (Lambda<Integer>) args[0]; 
34.                 return new Lambda<Integer>() { 
35.                     @Override 
36.                     public Integer call(Object... args) { 
37.                         Integer n = Integer.parseInt(args[0].toString()); 
38.                         if (n < 2) { 
39.                             return Integer.valueOf(1); 
40.                         } else { 
41.                             return n * factorial.call(n - 1); 
42.                         } 
43.                     } 
44.                 }; 
45.             } 
46.         }); 
47.         System.out.println(y.call(10)); 
48.     } 
49. } 

相关链接

[1]http://zzp.me/2011-08-05/recursive-lambda/

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

原文地址：https://zhuanlan.51cto.com/art/202104/656928.htm