什么是 Lambda 演算

Lambda 演算（λ 演算）是一套从数学逻辑中发展，以变量绑定和替换的规则，来研究函数如何抽象化定义、函数如何被应用以及递归的 形式系统。
说人话就是 Lambda 演算是一个 定义了一套规则，并使用这套规则来 研究函数 的系统。

λ 演算的基本要素

λ 演算包含了三个基本要素：

1. 变量

跟其他编程语言类似，λ 演算系统有变量的概念，不过 λ 演算系统 不存在整数、字符串、对象等变量类型，整个系统的所有变量有且仅有一种类型 —— 函数类型。

因此 λ 演算非常简洁明了，你在计算和使用过程中不需要考虑类型之间的兼容和转换关系。

2. 函数

在 λ 演算中，函数是第一公民，所有的数据都是函数。

函数由两部分组成 —— 参数 和 函数体。

3. 应用

应用 —— 即将变量代入到函数中计算结果，这是 λ 演算的一种重要操作。

λ 演算的函数

我们之前提到了 λ 演算的函数由参数和函数体组成，具体来说，一个 λ 函数总是有着如下结构：

参数和函数体使用 一个点 隔开来，其中参数以 $\lambda$ 开头，之后跟随的是参数标识符，如：$\lambda x$、$\lambda y$ 甚至是 $\lambda 114514$。
因为 λ 演算中你不需要考虑类型转换，因此你的参数标识符可以是 任意字符串，当然前提是你能认得出来你写的是啥。

一个函数可以有多个参数，当你需要多个参数时，只需要粗暴地把参数按顺序堆叠在参数部分就行了：

你还可以在每个参数的尾部都使用一个点好隔开，这样也可以表示多个参数：

可以发现第二种表达法实际上是 把一个函数给拆分成了两个函数。
上面两种表达法有什么区别？到后面你就知道了。

λ 演算的应用

λ 演算的应用使用 类似于代数计算的乘法 表示：

以上分别表示使用 $a$ 作为参数应用于函数 $\lambda x.x$，以及使用 $\lambda y.a$ 作为参数应用于函数 $\lambda x.x$。

那么这个函数应用应该怎么计算呢？首先一个最简单的结论：λ 演算的应用实际上就是字符串替换。
所以有：

直接把函数体中对应参数的变量替换为参数即可，我们再来看一个相对复杂的例子：

可以看见，按照从左到右的顺序，依次应用参数，每一步都将函数体使用参数替换作为返回值。
需要注意的是，如果函数体中出现了可以进行计算的部分（如上面的红色部分），那么我们也应该先进行计算，然后再进行外部的应用。

为了严谨定义，对于字符串替换，我们又将其差分为 3 中小操作：

1. α 变换

α 变换是 λ 演算中的一个基础操作，简单来说就是你可以 修改函数中某一个参数的名字，然后对函数体中所有的该参数同样进行改名：

需要注意的是 α 变换是有边界的，它只能对函数自己的参数起作用，而不能对函数内部的其他函数起作用：

因为 α 变换最重要的一点是 保证算式变换前后的拓扑关系不变，而超出边界的变换 可能 会导致拓扑关系被破坏。

2. β 规约

β 规约实际上就是化简运算，将一长串 λ 算式不断使用函数应用，直至不能继续应用为止。

规约的顺序为 从左到右，先算括号：

当规约时可能发生语义冲突时，应该先使用 α 变换给有冲突的变量替换名字，然后再进行 β 规约：

如果强行进行规约，那么就会出现尴尬的事情了：

3. η 规约

当一个函数的函数体里 没有出现函数的参数 时，那么应用任意的参数到这个函数，函数只会把自己的函数体原原本本地返回：

这是一个非常显然的结论。

柯里化

之前我们将函数参数的时候说过，当有多个参数时，以下两种写法等价：

实际上就类似于这两种 JS 函数定义：

const func1 = (x, y) => x(y);
const func2 = (x) => (y) => x(y);

在 λ 演算中，我们允许只提供部分参数，函数只进行部分演算，然后返回一个新的函数来接收其他参数，直到所有的参数都接受完成。
这就是 柯里化 的概念。

当然在如上的 JS 代码中 func1 并不满足这个条件，它必须同时接收两个参数，因此实际上 λ 演算中的函数都是以 func2 形式进行执行的。

λ 演算中所有的函数都是柯里化执行的，因此你可以在任何时候代入部分参数进行部分演算，以获得新的函数作为结果。

λ 演算的图灵完备性

λ 演算是图灵完备的，也就是说我们可以使用 λ 演算构建出任何使用其他编程语言所编写的程序，并能够实现任何图灵机可以实现的功能。

在现实生活中，如果我们能够成功用 λ 演算表达出 真、假值 以及 与或非 操作，那么通过组合这些基本元素，我们就能知道 λ 演算是图灵完备的，因为现实中的计算机就是由这些基础元素搭建出来的。

真假值与条件函数

定义如下：

条件函数有三个参数，分别是 条件、真分支 和 假分支，通过分别带入真值和假值，我们能够很容易地验证条件函数的正确性：

由于这里所说的分支实际上还是一个函数，其实条件函数更像是一个 三目运算符。

与或非

当有了真假值和三目运算符，与或非操作当然也就非常好定义了：

我们将对应的函数代入化简一下：

简单代入几个值进行计算：

更多的逻辑运算

在实现了如上基础逻辑系统之后，我们已经可以组合出任意的逻辑运算了，如异或和同或：

他们如果要展开的话式子就太复杂了，此处不进行展示，有兴趣的话可以亲自去试一试（
不过既然能组合出任意逻辑，那么实际上就表示了 λ 演算的图灵完备。

用 λ 演算存储数据

你可能会摸不着头脑，但是 λ 演算的确可以表示出一个能存储数据的结构，而它实际上只是一个简单的条件函数！

考虑链表的建立方式，对于每个存储单元我们需要两个字段，一个是 字段，另一个是 Next 指针。
指针对于 λ 演算来说太复杂了，那么我们可以考虑一种套娃的形式 —— 在 Next 指针存储另一个完整的链表，最终变成这样：

这样一来，我们就能构建一系列的操作了：

这个链表看起来更像一个栈结构了，你可以通过应用函数来验证其正确性：

以上函数组合出了一个如下的链表：

我想要取出数据：

当然这样做还是比较抽象的，因为我们还没有定义整数，所以如果需要提取深层数据，只能不停的重复调用。

λ 演算的自然数定义与演算

想要用 λ 演算这种抽象算式来数数，最好的方法就是用 皮亚诺公理 了，我们来复习一下公理内容：

1. $0$ 是自然数
2. 每一个确定的自然数 $a$，都具有确定的后继数 $a^{\prime }$ ，$a^{\prime }$ 也是自然数
3. $0$ 不是任何自然数的后继数
4. 不同的自然数有不同的后继数，如果自然数 $b$、$c$ 的后继数都是自然数 $a$，那么 $b=c$
5. 设 $S\subseteq \mathbb{N}$，且满足2个条件（i）$0\in S$；（ii）如果 $\forall n\in S$，那么 $n^{\prime }\in S$。则 $S$ 是包含全体自然数的集合，即 $S=\mathbb{N}$。

用皮亚诺公理数数

要利用皮亚诺公理，我们需要定义两个东西 —— 0 和 后继数。
有了他们我们就可以从 0 开始一直数数下去了。

在 λ 演算中，他们被定义为：

我们如果想要数 1，那么就将后继操作应用于 0：

数 2 也是同理：

发现了一个规律，数多少个自然数，实际上就是在 λ 算式里 套娃 多少个 s：

后继函数利用 λ 演算本质上就是字符串替换的特性巧妙地实现了这一点。

这一种对自然数的特殊编码方式被称为 丘奇编码。

加法

在知道了自然数与 s 的关系之后，加法操作就很简单了，只需要将两个数字的 s 部分拼接在一起就行：

这里的 $bsx$ 实则是将 $b$ 的函数体完整返回，而 $as(bsx)$ 则是保留 $a$ 的 $s$ 字符串，将最末尾的 $x$ 给替换成 $b$，这样一来实际上就是把两数的 s 进行了拼接。

所以有：

乘法

小学数学学过，乘法实际上就是多次加法，但是在 λ 演算的世界里，乘法要简单的多，只需要 将一个数中所有的 s 替换成另一个数 就行了，因此有：

这里的 $a(bs)$ 实际上就是将 $a$ 中的 $s$ 全部替换成 $bs$，这就隐含了将 $b$ 中的 $s$ 重复 $a$ 次这个乘法语义。

所以有：

幂次

如果将乘法执行多次，那么得到的就是幂次，按照替换方法，在 λ 演算中实现也非常简单：

这里计算 $a^b$ 只需要将 $b$ 中的 $s$ 全部替换成 $a$，就隐含了将 $a$ 中的 $s$ 重复 $b$ 次的语义。

跟乘法不同，幂次没有引入 $s$ 变量，因为我们实际上是以 递归 的形式计算幂次，需要将每一步计算得到的新结果再进行 s 替换，而不像乘法一样进行一次替换就行。

所以有：

前驱

光有加法乘法和幂次可不够，我们还希望有减法，在这之前，我们需要获取一个自然数的前驱值。

在丘奇编码中，前驱值就比较复杂了：

光看可分析不出啥，我们来演算一下：

为了把一个 s 给去掉，我们要花费这么多步……
其实观察计算步骤，我们还是能看出来演算做了什么的，无非重新从 0 开始数数，直到 n-1 的时候停止返回。

那么如果我们想要求 0 的前驱？

当然是算不出来的了，因为自然数中没有负数。

减法

有了前驱之后，减法定义就相对容易了：

当 $a\ge b$ 时计算得到 $a-b$ 否则计算得 0。

如：

可以看出减法实际上就是将减数的 s 替换成了前驱操作，通过对 $a$ 做 $b$ 次前驱操作实现的。

比较运算

在有了如上的基本代数工具之后，是时候将数字和真假值联系起来了，这时候我们就需要一系列比较运算了，一切的基础都要从与 0 比较开始：

这个函数可太直观了，记得一些自然数的丘奇编码如下：

如果将 0 应用于这个函数，则很明显会返回一个真值，又由于 s 被传入一个永远返回假值的函数，所以只要数字的丘奇编码中出现了 s，那么它永远返回假。

那么接下来要比较两个数是否小于等于关系，就可以简单表示如下：

只要 $a-b\le 0$ 那么这个函数就将返回真。

有了这个基本比较，其他的比较函数也容易得到了：

Y 组合子

考虑计算阶乘，用 λ 演算可以这样表示：

如计算 $3!$，有：

我们使用递归操作，让函数不断地调用自己实现了阶乘计算，但是如果我们的函数没有名字呢？
当涉及到匿名函数递归时，我们就需要一个工具来帮助我们调用函数自己，而它就是 Y 组合子。

Y 组合子的定义如下：

Y 组合子接收一个函数作为参数，且对于任意函数 $f$，显然有：

我们得到了一个可以无限自展开的新函数！

那么这样一来，我们就可以定义新的阶乘函数了：

计算展开过程过于复杂，这里就不展示了，不过要使用 Y 组合子进行递归展开需要满足一个条件，那就是最终函数应该展开至一个 不动点，即：

此时就算无穷展开下去函数值也不会发生改变，那么就可以停止展开，开始回溯计算值。
如果函数无法满足这个条件，也就意味着无穷展开没有边界了，自然运算永远也不会停下。

小结

λ 演算大道至简，没有什么乱七八糟的概念，虽然是计算机世界中的一块基石，但是更多的反而是面向数学而非计算机。

想要给 λ 演算写一个编译器/解释器很容易，但是想拿它来写程序那就大可不必了。

函数式编程就大量借鉴了 λ 演算的思路与想法，到时候再写文章讨论吧。