教堂数字：如何在 lambda 演算中编码零？

Question

我正在学习 lambda 演算，但我似乎无法理解数字 0 的编码。

“接受一个函数和第二个值并对参数应用该函数零次的函数”怎么会为零？还有其他方法可以对零进行编码吗？这里有人能帮我编码0吗？

Answer 1

“接受一个函数和第二个值并对参数应用该函数零次的函数”当然不是零。它的“编码”为零。当您处理普通 lambda 演算时，您必须以某种方式对数字（以及其他基本类型）进行编码，并且每种类型都规定了一些要求。例如，自然数的一个要求是能够将给定数字加 1，另一个要求是能够区分零和更大的数字（如果您想了解更多信息，请查找“皮亚诺算术”）。 Dario 引用的流行编码为您提供了这两件事，并且它还通过执行某件事（编码为

f 参数）N 次的函数来表示整数 N - 这是使用自然数的一种自然方式.

还有其他可能的编码——例如，一旦您可以表示列表，您就可以将 N 表示为包含 N 个项目的列表。这些编码各有优缺点，但上面的编码是迄今为止最流行的一种。

参见

Answer 2

：

0 ≡ λf.λx. x
1 ≡ λf.λx. f x
2 ≡ λf.λx. f (f x)
3 ≡ λf.λx. f (f (f x))
...
n ≡ λf.λx. fn x

如果您学习 Lambda 演算，您可能已经知道 λxy.y

Answer 3

*arg2* 将减少为

arg2，因为 x 没有被替换，余数 (λy.y) 是恒等函数。 您可以用许多其他方式写零（即提出不同的约定），但使用 λxy.y 有充分的理由。例如，您希望零成为第一个自然数，因此如果您对其应用后继函数，您将得到 1、2、3 等。使用函数 λabc.b(abc)，您将得到 λxy.x(y ), λxy.x(x(y)), λxy.x(x(x(y))) 等，换句话说，你得到了一个完整的数字系统。

此外，您希望零成为加法的中性元素。通过后继函数 S := λabc.b(abc)，我们可以将

n

+*m* 定义为

n S m，即 n 乘以后继函数对 m 的应用。我们的零 λxy.y 满足这一点，0 S m 和 m S 0 都减少到 m。

在通常的命令式编程语言表示中，我们有类似的 for 循环表示法

Answer 4

for(state = <start_state>; state!=<end_state>; state = inc(state)){
   f(state);
}

我们在当前状态上应用函数 f，应用该函数后，我们将当前状态修改（通常是递增或其他）到下一个状态。在 lambda 演算中，没有赋值运算符，因此您可以将数字视为具有给定初始状态

z

和滚动状态函数

s

 的 for 循环，这是应用于前一个状态的东西，因此表示数字的 lambda 会将这些作为参数 

(λsz.s z)

，用于在初始状态上应用一个 for 循环，因此表示数字 1。使用此逻辑，我们可以为 0 构造 λsz.z，因为我们知道该函数在初始状态上应用了零次，因此该数字代表 0。