Lambda 微积分如何添加数字？
How would the Lambda Calculus add numbers?
我一直在阅读 lambda 演算，喜欢它提出的想法，但有些事情我无法解释；
lambda 演算如何计算加法数？
我明白了
(\x . + x x) 3
和3 + 3一样，也就是6，但是加法函数本来是怎么实现的呢？
它是 compilers/languages 必须内置的东西，还是只能由 lambda 演算定义？
假设您使用的是 Church numerals，而不是一些原始数字类型，加法是组合：
\x \y . (\z . x(y(z)))
如果您在 lambda 演算中添加了某种原始数值类型，则加法要么必须是原始数值类型，要么必须按照类似后继运算的方式进行定义。
是的，您可以在 lambda 演算中定义数字（实际上是任意数据类型）。这是想法。
首先，让我们选择要定义的数字。最简单的数字是 自然数 ：0、1、2、3 等等。我们如何定义这些？通常的方法是使用 Peano axioms:
- 0是自然数。
- 若n为自然数，则Sn为自然数
这里，S表示n或n+1的后继者。因此，前几个 Peano 自然数是 0、S0、SS0、SSS0 等等——这是一元表示。
现在，在lambda演算中，我们可以表示函数应用，所以我们可以表示Sn，但我们不知道如何表示0和S本身。但幸运的是，lambda 演算为我们提供了一种推迟选择的方法：我们可以将它们作为参数，让其他人来决定！让我们为给定的 0 写 z，为给定的 S 写 s。那么我们可以如下表示前几个数，写⟦n⟧ for "the lambda calculus representation of the natural number n":
- ⟦0⟧ = λ z s . z
- ⟦1⟧ = λ z s . s z
- ⟦2⟧ = λ z s . s (s z)
- ⟦3⟧ = λ z s . s (s (s z))
正如自然数n是n对S的应用0一样，[=94的lambda-calculus表示=]n 是 n 副本 any 后继函数 s 的应用任意零z。我们也可以定义继任者：
- ⟦0⟧ = λ z s . z
- ⟦S⟧ = λ n . λ z s . s (n z s)
在这里，我们看到后继者在确保n之后，将s的一个额外副本应用到n 使用相同的 z 和 s。我们可以看到这给了我们相同的表示，使用 ⇝ for "evaluates to":
- ⟦0⟧ = λ z s . z
- ⟦1⟧ = ⟦S0⟧
= (λ n . λ z s . s (n z s))(λ z′ s′ . z′)
⇝ λ z s . s ((λ z′ s′ . z′) z s)
⇝ λ z s . s z
- ⟦2⟧ = ⟦SS0⟧
= (λ n . λ z s . s (n z s))((λ n′ . λ z′ s′ . s′ (n′ z′ s′))(λ z″ s″ . z″))
⇝ (λ n . λ z s . s (n z s))(λ z′ s′ . s′ ((λ z″ s″ . z″) z′ s′))
⇝ (λ n . λ z s . s (n z s))(λ z′ s′ . s′ z′)
⇝ λ z s . s ((λ z′ s′ . s′ z′) z s)
⇝ λ z s . s (s z)
- ⟦3⟧ = ⟦SSS0⟧
= (λ n . λ z s . s (n z s))((λ n′ . λ z′ s′ . s′ (n′ z′ s′))((λ n″ . λ z″ s″ . s″ (n″ z″ s″))(λ z‴ s‴ . z‴)))
⇝ (λ n . λ z s . s (n z s))((λ n′ . λ z′ s′ . s′ (n′ z′ s′))(λ z″ s″ . s″ ((λ z‴ s‴ . z‴) z″ s″)))
⇝ (λ n . λ z s . s (n z s))((λ n′ . λ z′ s′ . s′ (n′ z′ s′))(λ z″ s″ . s″ z″))
⇝ (λ n . λ z s . s (n z s))(λ z′ s′ . s′ ((λ z″ s″ . s″ z″) z′ s′))
⇝ (λ n . λ z s . s (n z s))(λ z′ s′ . s′ (s′ z′))
⇝ λ z s . s ((λ z′ s′ . s′ (s′ z′)) z s)
⇝ λ z s . s (s (s z))
（是的，它变得密集且难以快速阅读。如果您觉得自己需要更多练习，那么完成它是一个很好的练习 – 它导致我在我最初写的内容中发现了一个错误！）
现在，我们已经定义了 0 和 S，这是一个好的开始，但我们还需要一个归纳原理。毕竟，这就是使自然数成为现实的原因！那么，这将如何运作？好吧，事实证明我们基本上已经准备好了。当以编程方式考虑我们的归纳原理时，我们需要一个函数，它将一个基本案例和一个归纳案例作为输入，并产生一个从自然数到某种输出的函数。我将调用输出 "a proof for n"。那么我们的输入应该是：
- 一个基本案例，这是我们对 0 的证明。
- 一个归纳案例，它是一个函数，它将 n 的证明作为输入并产生 Sn 的证明。
换句话说，我们需要某种零值和某种后继函数。但这些只是我们的 z 和 s 参数！所以结果 我们将自然数表示为它们的归纳原理，我认为这很酷。
这意味着我们可以定义基本操作。我在这里只定义加法，剩下的留作练习。在我们的归纳公式中，我们可以定义加法如下：
- m + 0 = m
- m + Sn = S(m + n )
这是在第二个参数上归纳定义的。那么我们如何翻译呢？变成：
- ⟦+⟧ = λ m n . λ z s . n (m z s) s
这是从哪里来的？好吧，我们将我们的归纳原理应用到 n。在基本情况下，我们 return m（使用环境 z 和 s） , 同上。在归纳的情况下，我们将后继者（环境 s）应用于我们得到的结果。所以这一定是对的！
另一种看待这个问题的方式是，因为 n z s 适用 n 份 s 到 z，我们有 n (m z s) s 适用 n 份 s 到 m z s ，共 n + m 份 s 到 z。同样，这是正确答案！
（如果您仍然不相信，我鼓励您设计一个像 ⟦1+2⟧ 这样的小例子；它应该小到易于处理但又大到至少有点有趣。）
现在我们了解了如何在纯无类型 lambda 演算中定义自然数的加法。如果您愿意，这里有一些额外的想法供您进一步阅读；这些更简洁，解释更少。
这种表示技术更普遍适用；它不仅适用于自然数。它被称为Church encoding, and can be adapted to represent arbitrary algebraic data types。正如我们用归纳原理表示自然数一样，我们用结构递归原理（它们的折叠）表示所有数据类型：数据类型的表示是一个函数，它为每个构造函数接受一个参数，然后应用 "constructor" 到所有必要的参数。所以：
- 布尔值：
- ⟦False⟧ = λ f t . f
- ⟦True⟧ = λ f t . t
- 元组：
- ⟦(x,y)⟧ = λ p . p x y
- 求和类型（
data Either a b = Left a | Right b）：
- ⟦左 x⟧ = λ l r 。 l x
- ⟦右 y⟧ = λ l r 。 r y
- 列表（
data List a = Nil | Cons a (List a)）：
- ⟦Nil⟧ = λ n c 。 n
- ⟦Cons x l⟧ = λ n c 。 c x l
请注意，在最后一种情况下，l 本身就是一个编码列表。
此技术也适用于类型设置，我们可以在其中讨论数据类型的折叠（或 变形）。 （我主要提到这个是因为我个人认为它真的很酷。）然后 data Nat = Z | S Nat 与 forall a. a -> (a -> a) -> a 同构，e 的列表与 forall a. e -> (e -> a -> a) -> a 同构，这只是common foldr :: (e -> a -> a) -> a -> [e] -> a 类型签名的一部分。全称量化的a表示自然数或列表本身的类型；它们需要被普遍量化，因此传递这些需要 higher-rank types。 foldr Cons Nil 是恒等函数这一事实证明了同构；对于编码为 n 的自然数，我们同样有 n Z S 恢复我们的原始列表。
如果您对我们只使用自然数这一事实感到困扰，我们可以定义整数的表示；例如，常见的 unary-style 表示是
data Int = NonNeg Nat | NegSucc Nat
这里，NonNeg n代表n，NegSucc n代表-(n+1)；否定情况下的额外 +1 确保存在唯一的 0。如果您愿意，可以直接说服自己，您可以使用具有真实数据类型的编程语言在 Int 上实现各种算术函数；然后可以通过 Church 编码将这些函数编码到无类型的 lambda 演算中，这样我们就设置好了。分数也可以成对表示，尽管我不知道确保所有分数都可以唯一表示的表示。表示实数变得棘手，但 IEEE 754 浮点数可以表示为 32、64 或 128 元组的布尔值，这是非常低效和庞大的，但可编码。
自然数（和整数等）的更有效表示也可用；例如，
data Pos = One
| Twice Pos
| TwiceSucc Pos
编码正二进制数（Twice n是2*n，或者在末尾加一个0；TwiceSucc是2*n + 1，或者在末尾加一个1 到最后；基本情况是 One，单个 1)。对自然数进行编码就像
一样简单
data Nat = Zero | PosNat Pos
但随后我们的函数（例如加法）变得更复杂（但速度更快）。
我一直在阅读 lambda 演算，喜欢它提出的想法，但有些事情我无法解释；
lambda 演算如何计算加法数？
我明白了
(\x . + x x) 3
和3 + 3一样，也就是6，但是加法函数本来是怎么实现的呢？
它是 compilers/languages 必须内置的东西，还是只能由 lambda 演算定义？
假设您使用的是 Church numerals，而不是一些原始数字类型，加法是组合：
\x \y . (\z . x(y(z)))
如果您在 lambda 演算中添加了某种原始数值类型，则加法要么必须是原始数值类型，要么必须按照类似后继运算的方式进行定义。
是的，您可以在 lambda 演算中定义数字（实际上是任意数据类型）。这是想法。
首先，让我们选择要定义的数字。最简单的数字是 自然数 ：0、1、2、3 等等。我们如何定义这些？通常的方法是使用 Peano axioms:
- 0是自然数。
- 若n为自然数，则Sn为自然数
这里，S表示n或n+1的后继者。因此，前几个 Peano 自然数是 0、S0、SS0、SSS0 等等——这是一元表示。
现在，在lambda演算中，我们可以表示函数应用，所以我们可以表示Sn，但我们不知道如何表示0和S本身。但幸运的是，lambda 演算为我们提供了一种推迟选择的方法：我们可以将它们作为参数，让其他人来决定！让我们为给定的 0 写 z，为给定的 S 写 s。那么我们可以如下表示前几个数，写⟦n⟧ for "the lambda calculus representation of the natural number n":
- ⟦0⟧ = λ z s . z
- ⟦1⟧ = λ z s . s z
- ⟦2⟧ = λ z s . s (s z)
- ⟦3⟧ = λ z s . s (s (s z))
正如自然数n是n对S的应用0一样，[=94的lambda-calculus表示=]n 是 n 副本 any 后继函数 s 的应用任意零z。我们也可以定义继任者：
- ⟦0⟧ = λ z s . z
- ⟦S⟧ = λ n . λ z s . s (n z s)
在这里，我们看到后继者在确保n之后，将s的一个额外副本应用到n 使用相同的 z 和 s。我们可以看到这给了我们相同的表示，使用 ⇝ for "evaluates to":
- ⟦0⟧ = λ z s . z
- ⟦1⟧ = ⟦S0⟧
= (λ n . λ z s . s (n z s))(λ z′ s′ . z′)
⇝ λ z s . s ((λ z′ s′ . z′) z s)
⇝ λ z s . s z- ⟦2⟧ = ⟦SS0⟧
= (λ n . λ z s . s (n z s))((λ n′ . λ z′ s′ . s′ (n′ z′ s′))(λ z″ s″ . z″))
⇝ (λ n . λ z s . s (n z s))(λ z′ s′ . s′ ((λ z″ s″ . z″) z′ s′))
⇝ (λ n . λ z s . s (n z s))(λ z′ s′ . s′ z′)
⇝ λ z s . s ((λ z′ s′ . s′ z′) z s)
⇝ λ z s . s (s z)- ⟦3⟧ = ⟦SSS0⟧
= (λ n . λ z s . s (n z s))((λ n′ . λ z′ s′ . s′ (n′ z′ s′))((λ n″ . λ z″ s″ . s″ (n″ z″ s″))(λ z‴ s‴ . z‴)))
⇝ (λ n . λ z s . s (n z s))((λ n′ . λ z′ s′ . s′ (n′ z′ s′))(λ z″ s″ . s″ ((λ z‴ s‴ . z‴) z″ s″)))
⇝ (λ n . λ z s . s (n z s))((λ n′ . λ z′ s′ . s′ (n′ z′ s′))(λ z″ s″ . s″ z″))
⇝ (λ n . λ z s . s (n z s))(λ z′ s′ . s′ ((λ z″ s″ . s″ z″) z′ s′))
⇝ (λ n . λ z s . s (n z s))(λ z′ s′ . s′ (s′ z′))
⇝ λ z s . s ((λ z′ s′ . s′ (s′ z′)) z s)
⇝ λ z s . s (s (s z))
（是的，它变得密集且难以快速阅读。如果您觉得自己需要更多练习，那么完成它是一个很好的练习 – 它导致我在我最初写的内容中发现了一个错误！）
现在，我们已经定义了 0 和 S，这是一个好的开始，但我们还需要一个归纳原理。毕竟，这就是使自然数成为现实的原因！那么，这将如何运作？好吧，事实证明我们基本上已经准备好了。当以编程方式考虑我们的归纳原理时，我们需要一个函数，它将一个基本案例和一个归纳案例作为输入，并产生一个从自然数到某种输出的函数。我将调用输出 "a proof for n"。那么我们的输入应该是：
- 一个基本案例，这是我们对 0 的证明。
- 一个归纳案例，它是一个函数，它将 n 的证明作为输入并产生 Sn 的证明。
换句话说，我们需要某种零值和某种后继函数。但这些只是我们的 z 和 s 参数！所以结果 我们将自然数表示为它们的归纳原理，我认为这很酷。
这意味着我们可以定义基本操作。我在这里只定义加法，剩下的留作练习。在我们的归纳公式中，我们可以定义加法如下：
- m + 0 = m
- m + Sn = S(m + n )
这是在第二个参数上归纳定义的。那么我们如何翻译呢？变成：
- ⟦+⟧ = λ m n . λ z s . n (m z s) s
这是从哪里来的？好吧，我们将我们的归纳原理应用到 n。在基本情况下，我们 return m（使用环境 z 和 s） , 同上。在归纳的情况下，我们将后继者（环境 s）应用于我们得到的结果。所以这一定是对的！
另一种看待这个问题的方式是，因为 n z s 适用 n 份 s 到 z，我们有 n (m z s) s 适用 n 份 s 到 m z s ，共 n + m 份 s 到 z。同样，这是正确答案！
（如果您仍然不相信，我鼓励您设计一个像 ⟦1+2⟧ 这样的小例子；它应该小到易于处理但又大到至少有点有趣。）
现在我们了解了如何在纯无类型 lambda 演算中定义自然数的加法。如果您愿意，这里有一些额外的想法供您进一步阅读；这些更简洁，解释更少。
这种表示技术更普遍适用；它不仅适用于自然数。它被称为Church encoding, and can be adapted to represent arbitrary algebraic data types。正如我们用归纳原理表示自然数一样，我们用结构递归原理（它们的折叠）表示所有数据类型：数据类型的表示是一个函数，它为每个构造函数接受一个参数，然后应用 "constructor" 到所有必要的参数。所以：
- 布尔值：
- ⟦False⟧ = λ f t . f
- ⟦True⟧ = λ f t . t
- 元组：
- ⟦(x,y)⟧ = λ p . p x y
- 求和类型（
data Either a b = Left a | Right b）：- ⟦左 x⟧ = λ l r 。 l x
- ⟦右 y⟧ = λ l r 。 r y
- 列表（
data List a = Nil | Cons a (List a)）：- ⟦Nil⟧ = λ n c 。 n
- ⟦Cons x l⟧ = λ n c 。 c x l
请注意，在最后一种情况下，l 本身就是一个编码列表。
- 布尔值：
此技术也适用于类型设置，我们可以在其中讨论数据类型的折叠（或 变形）。 （我主要提到这个是因为我个人认为它真的很酷。）然后
data Nat = Z | S Nat与forall a. a -> (a -> a) -> a同构，e的列表与forall a. e -> (e -> a -> a) -> a同构，这只是commonfoldr :: (e -> a -> a) -> a -> [e] -> a类型签名的一部分。全称量化的a表示自然数或列表本身的类型；它们需要被普遍量化，因此传递这些需要 higher-rank types。foldr Cons Nil是恒等函数这一事实证明了同构；对于编码为n的自然数，我们同样有n Z S恢复我们的原始列表。如果您对我们只使用自然数这一事实感到困扰，我们可以定义整数的表示；例如，常见的 unary-style 表示是
data Int = NonNeg Nat | NegSucc Nat这里，
NonNeg n代表n，NegSucc n代表-(n+1)；否定情况下的额外+1确保存在唯一的0。如果您愿意，可以直接说服自己，您可以使用具有真实数据类型的编程语言在Int上实现各种算术函数；然后可以通过 Church 编码将这些函数编码到无类型的 lambda 演算中，这样我们就设置好了。分数也可以成对表示，尽管我不知道确保所有分数都可以唯一表示的表示。表示实数变得棘手，但 IEEE 754 浮点数可以表示为 32、64 或 128 元组的布尔值，这是非常低效和庞大的，但可编码。自然数（和整数等）的更有效表示也可用；例如，
data Pos = One | Twice Pos | TwiceSucc Pos编码正二进制数（
一样简单Twice n是2*n，或者在末尾加一个0；TwiceSucc是2*n + 1，或者在末尾加一个1到最后；基本情况是One，单个1)。对自然数进行编码就像data Nat = Zero | PosNat Pos但随后我们的函数（例如加法）变得更复杂（但速度更快）。