认识 Y-Combinator

写在开始

不得不说，当我开始学习函数式编程的时候，我并没有被匿名函数感到害怕，理解它的基本概念是极其容易的。但是当你试图去将你日常所书写的指令式的代码转换成函数式，特别是纯函数式的时候，你会感到这是不可能的。它和你之前的编程思想是完全脱离的。

所以当我第一次见到 Y-Combinator（Y 组合子）的时候，我的感觉是懵逼的，这是什么玩意。然而当我一步一步，了解这个东西是什么，它是怎么工作的之后，我对函数式编程的认识有了很大的进步。

即使是 C++ 这样的语言，也在 C++11 标准中引入了匿名函数，使得你有机会在 C++ 中使用函数式编程的特性。在编程中，如果能适当地使用函数式语法进行编程，将非常有助于你写出一些更好理解、更简单的代码。

而在了解一些基本概念之后，了解一下 Y-Combinator 是一个极好的选择，这个东西证明了函数式编程对递归的语义理解，证明了其在递归上和指令式编程的等价之处。你可以通过观察等价的这两者的不同的实现方式，来加深对这两者思想的认识。

与指令式编程的根本区别

大家看下面一段 C 代码

for (int i = 0; i < 100; i++){
  puts("Hello World");
}

显然这是一个非常常见的循环。然而这样的循环显然已经被抽象过了，我们也许可以用一个更原始的方法来实现。且让我引入一个 C 开发中应尽量避免的语句 goto 来解释。

int i = 0;
loop:
if (i >= 100) goto next;
puts("Hello World");
i++;
goto loop;
next:

这两段代码除了变量 i 的作用域有所区别以外几乎是等价的。相对的，第二段代码非常接近于编译到汇编时的指令，几乎是一一映射的。然而你可以发现，我们的循环都是依赖于跳转代码行数的，不得不说这种写法非常不函数式。

第一个函数

我们可以用一个递归来把这个循环实现地更像一个函数：

int loop(int n){
  if (n == 0) return 0;
  puts("Hello World");
  return loop(n - 1);
}
loop(100);

虽然这个函数是倒过来循环的，但我们大可忽略这些细节，毕竟要做修改也是相对容易的。我们通过一个函数递归的方式来实现了一个循环。需要特别注意的是，如果根据递归的定义，那么这个循环一旦大起来在今天我们的计算机的计算模型（而不是 Lisp Machine）上是会爆栈的，但好在由于是个尾递归，通常是会直接被编译器优化成一个循环的。这确保了即使你写的是函数式代码，也可以最终编译成适合 CPU 运算的形式而不太影响性能。

不过递归有一个问题，我们必须知道函数的名称才能这么做，在真正的 Lambda 运算模型上，函数是匿名的，也就是没有名字，这样你最后根本就无处调用你函数自己。因为你无法写出下面的代码（Ruby）：

lambda { |n|
  return if n == 0
  puts "Hello World"
  what_the_f**k_my_function_name_is(n-1)
}

魔法少女 Lambda 酱

下面我们演示一种黑魔法，来使得你没有办法得到自己函数名时实现递归。简单来说就是把「函数」当成一个「参数」传输。

loop = lambda {|f, n|
  return if n == 0
  puts "Hello World"
  f.call(n-1)
  }
loop.call(loop, 100);

我们把函数本身作为一个参数传了进去，达到了我们的想法。不过这里我们还不是一个完全的匿名函数，而是通过给匿名函数起了一个名字 loop，在外面调用了一下。不过事到如今，去掉这个 loop 已经很容易了。由于第一条的匿名函数定义中没有任何地方用到 loop 只在第二条指令中用到。我们只要将第二条指令中的所有 loop 都代换掉就行。我们就能得到下面的代码：

lambda {|f, n|
  return if n == 0
  puts "Hello World"
  f.call(n-1)
  }.call(lambda{|f, n|
    return if n == 0
    puts "Hello World"
    f.call(n-1)
    }, 100)

柯里化，最后一步

Amazing！我们通过一个匿名函数的调用成功实现了一个 100 的循环。我们现在距离 Haskell Brooks Curry 先生当年推出 Y 组合子只差一步，那就是将我们做的事情「Currying」（柯里化）。所谓 Currying 就是使用一个高阶函数，将一个函数的多个参数精简成一个。我们看到我们现在的匿名函数还有 f 和 n 两个参数，我们打算拿掉它。虽然其实并不是真正意义上的拿掉。柯里化，只不过把一个形如 f(x, y) 的函数写成了 f(x)(y)，也就是 f(x) 的返回是一个匿名函数，而这个匿名函数再以 y 为参数执行一次。这么搞一下，我们就得到了：

lambda {|p|
  return lambda { |f|
    return f.call(f);
    }.call(lambda {|f| 
      return p.call(lambda {|x| 
        return f.call(f).call(x)
        })
      })
  }.call(lambda {|f| 
    return lambda {|i| 
      return if i == 0; 
      f.call(i-1)
      }
    }).call(100)

由于柯里化后匿名函数和调用的参数都单一了，我们因此可以保证我们能将任意一个递归都表达成一个匿名函数的形式。按照 Lambda 演算的形式化表达 Y := λf.(λx.(f (x x)) λx.(f (x x))) 。你只要将自己要递归的函数替换掉里面 f 的位置，并最后执行一下这个匿名函数就成啦~

折腾半天干什么

你肯定想问，我们把一个循环写成这么复杂是为了什么。事实上我想展示的不是循环，而是递归。递归在图灵模型（我们通常 CPU 的计算模型）和丘奇模型（Lambda 演算）上都不是那么地原生的实现。

在图灵模型上地最终形式是每次递归，追加进内存中，并重新 goto 回函数开始，在退出时，再一步步内存推出来，并将递归的剩余部分执行完。

而在 Lambda 演算中，最终表达为一个�逻辑系统构成的严格的数学函数模型的执行。

这两者便是具体化和形式化的极限，充分表现了两种模型的特点。从根本加深了对两种模型差异的认知，从而让我们在两种模型上都能通过正确的编程思想来写代码，以把代码写得更好。

当然也是有一些实际意义的，比如在变量作用域严格的语言中，且又必须使用匿名函数的形式来书写你所需要的东西的时候，而你正好又需要递归才能达到你的要求，那么使用 Y-Combinator 是一个可选的方法。然而通常，出现这种情况大多是你写了错误的思想的代码所导致的，实际编程中几乎遇不到这种情况，毕竟将更抽象更容易理解的函数式编程写成这么一坨一眼看不懂的代码是很失败的。