最近玩游戏 《Functional》，发现完全使用 lambda 做各种抽象还蛮有趣的，这里做一些关于实践 lambda 的笔记，顺路把 Y 组合子也给咔嚓掉——已经很长一段时间想要去学习它但搁置了。这里使用 js 去实现，它使用箭头函数时的语法已经足够简洁；所有 lambda 符号都写作λ，且所有字面量的 abstraction 都会给予括号。

回顾

这里先把 lambda 回顾一遍，在 lambda 中，存在着三种表达式——variable，abstraction，application。variable 的语法为任何小写字母，如 x，y，abstraction 的语法如λx.x，application 的语法如A B，其中 A，B 均为表达式。

下面都是合法的 lambda：

对 lambda，我们能做的唯一一件事其实就是化简，具体来说，是把 Application 化简；比如对(λx.x x) y，对其进行化简就是把 x 替换成 y，得到它的函数体，即y y。

最后是 abstraction 和 application 的结合性问题，abstraction 是右结合的，application 是左结合的，这就是说：

从 js 的上下文来看，abstraction 就是函数定义，application 就是函数应用，下面均以此来称呼 abstraction 和 application。

Boolean

在一切开始之前，先预先定义一个 VOID 变量用于填充，它是一个 identity 函数：

布尔值是最简单的数据结构，它仅有两个值 True 和 False。

使用 Lambda 时，我们可以这样定义 Boolean：

对应的 js 为：

这里其实我并不明确这里的 a 和 b 为何需要是函数，可能是为延迟求值，也可能是为统一“模式匹配”的形式（见下面的部分总结），下面有些地方使用了这个形式，有些地方也没有。

它们的含义都很明确——TRUE 表示一个两参数的函数，返回第一个参数，FALSE 表示一个两参数的函数，返回第二个参数。可以认为，我们把 boolean 通过 lambda 去“编码”了。至于为何要这样编码，去问丘奇吧 hh。

这样抽象后，我们能够实现 if，if 是这样的结构——它接受三个参数，其中第一个参数是布尔值，若其为真，返回第二个参数，否则返回第三个参数，它的实现是显然的。

可以做一下演算，假设 1 和 2 是合法的 lambda 变量：

对其的使用类似这样：

在这里，由于 javascript 的弱类型，可以注意到，IF 其实就是 identity 函数x => x——IF(TRUE)(1)(2) = TRUE(1)(2) = 1，IF(TRUE) = TRUE。

实现 AND 和 OR 也是简单的，它们的参数均为布尔值，返回值也为布尔值：

Cons

Cons 的实现如下：

Cons 的这个定义a => b => onNil => onCons => onCons (a) (b)十分有趣，我们可以给它加点括号来更突出这有趣之处：

可以建立这样的心智模型，即 CONS 是这样一个函数，它接受两个参数，去返回一个数据结构，而我们通过去传递给它一个“Matcher”（模式匹配）去获取该数据结构中的值。同时也可以注意到，NIL 的结构和调用 CONS 返回的数据结构是一致的。

然后，显然需要实现一个检查 PAIR 是否是 NIL 的函数，这个函数的实现同样很 trick 但能找到模式：

为何这么实现？推导一下就行了：

这很像模式匹配——只不过我们必须通过函数参数的形式去绑定所有值就是了，比如这个 IS_NIL 函数可以看成这样（使用 Scala 的模式匹配语法）：

Maybe

照葫芦画瓢，我们可以尝试去抽象 Maybe：

map 的操作如 map，flatMap，orElse 也可以定义出来：

使用类似这样：

部分总结

在 haskell 中，Bool，Cons，Maybe，Either，Tree（二叉树）的类型定义分别如下：

使用 lambda 对其的抽象如下：

可以发现，对任何 ADT，它似乎都能通过 lambda 去抽象，其中，每一个值构造器对应一个函数，其接受值构造器的参数，去构造相应数据结构；然后，我们传递给这个数据结构一个 Matcher，对其进行“模式匹配”并获得值。

丘奇数

通过上面的观念，我们尝试操作一下自然数，皮亚诺自然数的 Haskell 定义是这样的：

定义相应 lambda，并去推演 ONE，TWO，THREE……

但这样的自然数定义实在有点难以形容，这时候就来了丘奇数，它修改了 SUCC，把“Matcher”提前应用给了它的“值”：

可以发现，自然数的值就是 f 应用的次数，f 应用 n 次，则对应的自然数的值就是 n；其 js 表述如下：

根据丘奇数的形式，可以很容易地将丘奇数转换为 js 的数字：

这种形式非常有趣，它像某种 reduce，其中 x 为初始值，f 为 step 函数，我们可以把 f 换成不同的函数（只要它的签名满足A => A），把 x 换成不同的值（即这里的类型A），比如我们可以去构造一个同这个自然数大小相同长度的列表：

这个性质对定义四则运算非常重要，比如考虑加法，对任意自然数 n，我们将其加 a，就是将其应用 a 次 SUCC，形式化地来说，就是：

那么，如何在 n 上应用 a 次 SUCC 呢？答案很明白了：

测试一下：

乘法也很简单——自然数 n 乘以自然数 a，就是0 + n + n + ... + n，其中 n 的个数为 a，我们只需要让 f 的值变为λx. PLUS x n即可，一个简单的闭包罢了：

要定义减法，我们需要先定义 PRED 即前驱，减一操作，即从λx.λf. f (f x) 到λx.λf.f x。这个操作对皮亚诺自然数来说是非常容易的，但对丘奇数（，对我）来说完全不 trival，这里参考 如何理解丘奇计数的减法？ - Thomas Lin 的回答 - 知乎。

我们可以去尝试构造这样一个 PAIR 的序列，其中对每一个元素，它的第一个元素是第二个元素的后继，且对序列中后一个元素，它的第一个元素为前一个元素的第一个元素的后继，第二个元素为前一个元素的第二个元素；定义PRED ZERO = ZERO，依此定义这个序列的起始值为(ZERO, ZERO)；

根据示意图能发现，对任意自然数 n，只要找到这个序列中第 n 个值，它的第二个元素就是它的前驱。

因此，能够定义起始元素以及步进函数：

根据上面的把自然数转换成 js 数字，列表的操作，我们同样可以把自然数直接转换成这个序列中的元素，只消 x，f 的值确定即可，其中 x 为 START（类型为(Nat, Nat)），f 为 STEP（类型为(Nat, Nat) => (Nat, Nat)），因此，要获取自然数的前驱，我们得到这样的代码：

老实说，它的纯 lambda 形式我实在化简不下去了，这里直接开摆，把上面的 PRED 用 js 实现：

有了 PRED，我们能够定义减法了，自然数 n 减去自然数 a，就是 n 减去 a 次 1，即执行 n 次 PRED

Y 组合子

这一节参考了https://stackoverflow.com/a/6713431和https://stackoverflow.com/a/6714066。

递归，也就是自己引用自己，比如下面的阶乘函数 fact，在其函数体中引用了自己：

但在 lambda 演算中我们无法这样做，因为在 lambda 演算中不存在所谓的“名字”，因此无法直接去编写递归的函数；而通过 Y 组合子，我们便能在不引用自身的情况下编写递归函数，放到 js 的语境下，就是说我们能编写匿名的递归函数。

但在研究 Y 组合子之前，先来思考一下，怎样的情况下我们能让一个函数去不通过名字来引用自己？显然，这时候要拿到自己只可能通过两种方式——去捕获上层变量，或者去从函数参数中拿；其中后者的实现还是比较容易想到的——调用函数的时候，把自身传递过去就好了！比如这里编写一个 fib 函数：

虽然乍一眼看起来有点作弊，但这是 lambda 可以实现出来的。我们考虑再来一个阶乘函数：

容易注意到，这玩意调用的时候是有特定的模式的——F(F)(...args)，我们将这个模式抽象一波：

可以看到，这玩意已经部分能满足需求了，但蛋疼的一点是，在编写该递归函数的时候，每次调用自己都得写f(f)(...)，这比较麻烦，这种思考方式不可行。

现在回到递归函数，第一步，来写一个递归的 fact 函数：

第二步，我们可以把这个函数变成“Supplier”，这种形式和上面的显然是等价的，其中参数_显然被直接扔掉了：

第三步：直到上一步，事情还是 trival 的，函数仍旧引用了自己，为了解决这个问题，再抽象一层，我们可以把函数体里的fact(_)通过参数去传入，这要求_ = fact(_)，这里令_ = recur，得到recur = fact(recur)，将参数_替换为recur，将函数体中的fact(_)替换为fact(recur)，替换为recur，得到：

而 recur 的定义其实就是这个：recur = fact(recur)，这里引用了自己，所以必须要使用递归函数去定义；而且这不是 haskell，所以不能用 point-free 风格，这里必须要知道 recur 的类型，而这是容易看出来的：number => number，下面便是结果：

好的，现在 fact 不是递归函数了，但我们又引入了一个新的递归函数 recur（欣慰的是，所有递归函数最后都能抽象成无显式递归的“body”和这样一个 recur 函数。

我们对 recur 采用和第一步到第二步同样的手段，即给它包一层 Supplier：

然后，问题就在于如何处理_和recur(_)了，我实在弄不明白，把答案直接列出来：

现在，所有的显式递归都已经移除，把最终的代码都列出来：

容易发现，这里只有 fact 是“变”量，换成其它的递归函数，只有 fact 会改变，因此，我们将这个模式抽象出来，就得到了 Y 组合子：

它很容易使用 lambda 去表述：

这形式比想象中简单多了 hhh，可惜它的发现过程怕是值几篇博士论文吧？

Lazy List

有了 Y 组合子，现在可以自由地耍花活了，该操作操作列表了，但在此之前先和皮亚诺自然数过两招，不然列表存啥元素呢？这里首先给出皮亚诺自然数的定义，以及其到 javascript 数字类型的转换函数：

皮亚诺自然数的加法也是简单的——对两个自然数a，b相加，检查a是否是ZERO，若是，则返回b，若不是，则令a为(SUCC c)，对c，(SUCC b)相加；乘法同样简单，对两个自然数a，b相乘，检查a是否是ZERO，若是，则返回ZERO，若不是，则令a为(SUCC c)，求c，b的乘积和b的和：

这就足够了，下面实现列表相关操作，这里要求列表是惰性的，即 b 为返回 CDR 的函数，下面实现一下 map-filter-reduce，并实现 take 和 iterate，最终去实现一个自然数列表，取前 10 项奇数（本想取前 100 项，然而发现这爆栈了）的和；其中因为布尔值和自然数都未使用上面那种非严格求值的形式，这里定义了一个LAZY_IF来保证 if 为“短路”操作：

就这样了，之后预备看《The Little Schemer》，多去了解一下递归，以及深入了解 Y 组合子。

参考资料

• https://www.zhihu.com/question/64274105

• https://zhuanlan.zhihu.com/p/298996358

• https://zhuanlan.zhihu.com/p/312895562

• https://matt.might.net/articles/js-church/

• https://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/