*施工中*
包括 Wikipedia 在内的很多地方都写得比较晦涩难懂，这里试图用尽可能平滑的学习曲线来帮助大家理解。(来自5个小时后的自己：我摆烂了x)
λ 演算从入门到入门
仅就这篇文章来说并不需要对 λ 演算有非常深入的理解，可以认为 λ 演算就是一种重写， 或者....字符串替换*, 又或者...任意你所熟悉的语言里的匿名函数 **。
(λx. x) 42
JavaScript:
(x => x)(42)(λf. f 114514) (λx. x)
JavaScript:
(f => f(114514))(x => x)Omega
那么假设我们的语言里面没有 while 没有 for 没有常见的控制循环的控制流结构，
也没有赋值的概念，仅仅只有匿名函数和函数调用
是否有可能仅用 λ 演算写出可以一直运行下去不停机的东西呢？
r e C A P T C H A:
呐，现在我有一个 term
(λx. x x) (λx. x x)
JavaScript:
(x => x(x))(x => x(x))可以请你帮我在脑子里面运行一下这个嘛
✅I'm not a robot!
Y
现在我们有了一个会一直运行下去的 omega(ω)，我们接下来的目标是在运行的同时进行一些有意义的运算。
现在我又有另一个 term ****
λf.(λx. x x) (λx.f (x x))
JavaScript:
f => (x => x(x))(x => f(x(x)))咦，这个是不是就是往上面的 ω 里面塞进了一个函数 f (?
既然 ω 会一直 reduce 下去，从直觉上来说如果我们能在每一次 reduction 里塞进一个 f 的话这不正是我们想要做的吗。
f
从上面 Y 的定义可以看到，我们需要将一个 f 作为参数传递给 Y (或者说将 Y 应用于 f)，那么 f 又是什么呢？
f 是 Y f 每一次 reduce 会被调用一次的函数
(λx.f (x x)) (λx.f (x x))
f ((λx.f (x x)) (λx.f (x x)))
f (f ((λx.f (x x)) (λx.f (x x))))f 的参数是不是很眼熟呢,
如果在 f 的函数体里面使用传进去的这个参数会发生什么呢？
(λr. λn. r (do_something n)) (λx.f (x x))(λx.f (x x)) n_0
((λx.f (x x)) (λx.f (x x))) (do_something n_0)
...
f ((λx.f (x x)) (λx.f (x x))) (do_something n_0)
((λx.f (x x)) (λx.f (x x))) (do_something (do_something n_0))
...求值策略与 Z 组合子
如上文所述，我们的语言里面只有匿名函数和函数调用，可即使是如此简单的语言仍然可以存在一些设计上的不同选择，比如说可以选择不同的求值策略。
在传参的时候我们(语言设计者)需要选择 及早求值(eager evaluation)/call-by-value 或是 惰性求值(lazy evaluation)/call-by-name。一般来说这种设计上的选择对于语言的使用者来说是透明的(当然也有部分语言允许使用者来选)，但这个问题对于我们现在正在进行的讨论很重要。
考虑下面的例子：
(λx. 0) ωω 指的是一开始提到的不停机的 omega term。
试想如果语言采用了及早求值的策略，那么运行这个例子会爆栈，因为需要先求值 ω。
可如果语言使用的是惰性求值的策略，那么这里会得到常数 0，因为 ω 实际上并没有被使用。
回到 Y 组合子的话题，如果我们在常见的及早求值的程序语言里使用标准的 Y 组合子会发生什么呢？
f ((λx.f (x x)) (λx.f (x x)))
显然如果我们先求值参数的话会像前面的例子一样爆栈。
那么在无法改变语言选择的求值策略的前提下，我们是否有办法魔改 Y 组合子来避免这个问题呢..?
当然可以！
(λf. (λx. (x x)) (λx.f (x x))) f
...
f ((λx.f (x x)) (λx.f (x x))) -- 这个参数就是上面的 (x x)上面是我们的 Y 组合子，在某一步需要把 (x x) 传给 f，但是就像刚刚讨论的那样，因为及早求值的语言需要先对 f 的参数 (x x) 求值会爆栈。我们可以用一个 trick 去推迟 (x x) 的求值，比如说把 (x x) 封装进一个 lambda 里面而不改变原本的语义。
直觉上这只是把未来可能的参数显式地表达了出来而不改变本来的意思, 这个又叫做 η-conversion。
(x x)
λz. (x x) z所以我们的 Y 现在变成了这样：
λf. (λx. (x x)) (λx. f (λz. (x x) z))这个魔改版的 Y 又叫做 Z 组合子。
不动点
前面是从操作语义的角度理解 Y, 即每一步是如何运行的，那么从数学的角度看的话 Y 又是什么呢？
Y 组合子属于不动点组合子的一种，什么是不动点呢？
对于函数 f, 如果 x_0 是 f 的不动点，那么
的不动点是 0，1
或 (λx. x) 的不动点是任意的 x
什么又是组合子呢？
组合子是从逻辑来的一个数学概念，
在这里可以理解为是一个没有 free variable (所有变量均来自于绑定的参数) 的高阶函数。*****
而 Y 就是一个高阶函数(组合子)，其参数是一个函数 f，而将 Y 应用于 f 即得到 f 的不动点，
所以现在我们有 Y f = f (Y f) = f (f (Y f)) = f (f (f (Y f))) = ...
！
recursive types(µ types)
先挖一个坑，之后可能会单独写一篇文章x
Θ 组合子
除了 Y 组合子还有其他的不动点组合子，比如说 theta(Θ)
(λx. (x x))(λx.λy y (x x y))出于和引入 Z 组合子一样的原因，我们也可以对 theta 应用 η-conversion
(λx. (x x))(λx.λy y (λz. (x x y) z))Θ 同样满足不动点组合子的特性 Θ f = f (Θ f) = f (f (Θ f)) = ...
Yet Another (boring) factorial example in JavaScript
fac = r => n => n == 0 ? 1 : n * r(n-1)y = f => (x => x(x))(x => f(z => x(x)(z)))
y(fac)(5) // 120
fac(y(fac))(5) //120 again
fac(fac(y(fac)))(5) //still 120
theta = (x => x(x))(x => y => y(z => x(x)(y)(z)))
theta(fac)(5)
fac(theta(fac))(5)
{- TODOs :
非标准的不动点组合子？
-}
这个可以吃吗
不能，但是可以让你在一些奇怪的地方写递归
比如说在 Rust 的闭包里写递归 (
除此之外可能没有太大的实际意义，因为在大多数情况下我们可以给要递归的东西一个名字然后通过名字来引用它。
但无论如何这是一个会让很多人初见 🤯 的东西
而且很优雅！
脚注
*：这么理解正确与否取决于具体的求值策略，这篇文章里如无特别说明默认的假定是 call-by-name***
**：大部分常见的语言默认的求值策略应该是 call-by-value, Haskell 除外，关于不同求值策略带来的影响请见 Z 组合子一章.
***：更准确地说 call-by-name 也不能理解成字符串替换，不过就这篇文章的目的来说就当成是也无妨.
****：
比起
(λx. (x x))(λx.f (x x))
更常见到的可能是另一种形式
(λx. f (x x))(λx.f (x x))其实下面的形式相当于多应用了一次 f，但这二者仍然是等价的，至于为什么是这样这个问题就留给读者好啦(
*****：如果对这个话题感兴趣的话 https://writings.stephenwolfram.com/2020/12/combinators-and-the-story-of-computation/