前言

我第一次听说Y combinator是在程序语言理论与设计原理这门课程, 同时也是第一次知道lambda演算和图灵机是完全等价的, 但是lambda演算的优雅程度图灵机是完全无法和lambda演算相提并论的。

看懂这篇文章的基础

  • 知道什么是高阶函数: 函数可以作为值传递, 也就是常说的lambda表达式
  • 知道$$Curry$$这样参数风格:$$\lambda .x \lambda.y.x+y$$
  • 知道$$\lambda$$的每一项都是一个约束条件, 约束了参数变量, 否则出现在函数中的变量就是自由的。
  • 知道 $$lambda$$演算有$$\beta$$规约和$$\alpha$$等价, 规约就是用$\lambda$项的参数替换掉表达式中相同的名称, $\alpha$等价是1相同的函数具有相同参数, 那么两个lambda项就是等价的($\alpha$等价是发生于没有自由变量的项中)

为什么需要Y combinator？

我们首先不管$\lambda$表达式的一些事情, 先看普通的编程语言中的一个递归实现:

1
2
3
4
5
6
7
function fact(n) {
	if (n == 0) {
		return 0;
	} else {
		return n + fact(n - 1);
	}
}

上面是一个在JavaScript中很简单的递归函数, 简单的模拟一下计算过程:

1
2
3
4
5
fact(0) = 0;
fact(1) = 1 + fact(0);
fact(2) = 2 + fact(1);
....
fact(n) = n + fact(n - 1)

那么上面的递归函数和在lambda表达式想表达的递归函数有什么不同吗?

我们是希望lambda表达式中出现的变量都是被约束的, 即不存在自由变量, 而上面的递归函数中是出现了自由变量的, 这个自由变量是fact, 显然它不是$\lambda$这个域(scope)中的, 所以我们是希望把这个自由变量给干掉的, 根据前面讲的每一个$\lambda$项都是一个约束项，所以我们只需要将fact这个变量给放到函数的参数上就可以了,这样做就不会出现自由变量了, 所以就得到下面这段代码:

1
2
//curry参数风格
let fact = f => n => n == 0 ? 0 : n + f(f)(n - 1);

那个这个函数fact如何实现递归呢? 答案就是使用一种叫做穷人的Y combinator也就是下面这种形式:

1
fact(fact)(3)

但是这种不通用, 我们是否可以使用lambda演算构造出那种无穷递归的函数, 就像下面这种: 

1
2
//所以你是可以无限进行递归下去的
Y g = g(Y g) = g(g(Y g))

既然这个东西对所有的函数都等价, 那肯定对fact也是等效的, 所以我们只需要规约出Yg定义

推导过程?

下面是完整的推导过程:

1
2
3
4
//先定义一个函数:
let ff = f => f(f);
//进行一个替换
ff(f => n => n == 0 ? 0 : n + f(f)(n - 1))(3)

然后就是改造第二项， 直接将f(f)提出来变成一个参数

1
(f => (g => n => n == 0 ? 0 : n + g(n-1))(v=>f(f)(v)))

看到没(g => n => n == 0 ? 0 : n + g(n-1)就是我们需要的递归定义了, 但是它在里面, 只有把它提到最外边才能得到最终的解

1
2
(fa => (f => fa(v=>f(f)(v))))
    (g => n => n == 0 ? 0 : n + g(n-1))

然后带回去:

1
2
ff( (fa => (f => fa(v => f(f)(v))))
     (g => n => n == 0 ? 0 : n + g(n-1)) ) (n)

然后再一次的将$\alpha$等价形式提出来:

1
2
(dd => ff( (fa => (f => fa(v => f(f)(v))))(dd)))
    (g => n => n == 0 ? 0 : n + g(n-1))(n)

然后将ff apply一下进去得到的结果:

1
2
(dd => (fa => (f => fa(v => f(f)(v))))(dd) 
    ((fa => (f => fa(v => f(f)(v))))(dd)));

然后把dd内联进去, 大工告成, 成功得到Y combinator

1
(dd => (f => dd(v=>f(f)(v)))(f => dd(v=>f(f)(v))))

然后我们可以根据这个Y combinator做非常有意思的事情， 写出任意的纯函数了哈哈

1
2
3
4
5
6
7
8
9
10
11
const Y = (dd => (f => dd(v=>f(f)(v)))(f => dd(v=>f(f)(v))))

let g = f => n => {
  if (n === 0) {
  	return 0;
  } else {
  	return n + f(n - 1);
  }
}

Y(g)(10)