将 Lambda 项减少为范式
Reduce Lambda Term to Normal Form
我刚刚学习了 lambda 演算，我在尝试减少时遇到了问题
(λx. (λy. y x) (λz. x z)) (λy. y y)
恢复正常形式。我到达 (λy. y (λy. y y) (λz. (λy. y y) z) 然后有点迷路了。我不知道从这里去哪里，或者它是否正确。
(λx. (λy. y x) (λz. x z)) (λy. y y)
正如@ymonad 指出的那样，y 参数之一需要重命名以避免捕获（合并只是巧合地共享相同名称的不同变量）。在这里我重命名后一个实例（使用 α-equivalence）：
(λx. (λy. y x) (λz. x z)) (λm. m m)
下一步是β-reduce。在这个表达式中，我们可以在两个地方之一这样做：我们可以减少最外层的应用程序 (λx) 或内部应用程序 (λy)。我打算做后者，主要是随心所欲/因为我想得有点超前，认为它会导致更短的中间表达式：
(λx. (λz. x z) x) (λm. m m)
还有更多β-还原要做。我将再次选择内部表达式，因为我可以看到它的发展方向，但在这种情况下实际上并不重要，无论如何我都会得到相同的最终答案：
(λx. x x) (λm. m m)
旁注：这两个 lambda 表达式（也称为 "Mockingbird"（根据 Raymond Smullyan））实际上是 α 等价的，并且整个表达式是（不）著名的 Ω 组合器。然而，如果我们忽略所有这些，并应用另一个 β-reduction:
(λm. m m) (λm. m m)
啊，这仍然是 β-可还原的。或者是吗？这个表达式α——等价于前面的。天哪，我们似乎发现自己陷入了无限循环，这在图灵完备（或者我们应该说 Lambda 完备？）语言中总是可能发生的。人们可能会将其表示为我们的原始表达式等于 "bottom"（用 Haskell 的说法），表示为 ⊥:
(λx. (λy. y x) (λz. x z)) (λy. y y) = ⊥
这是一个错误吗？嗯，一些好的 LC 理论是：
- 如果一个表达式有一个β范式，那么它将是相同的β-正常形式，无论使用什么减少顺序来达到它，并且
- 如果一个表达式有一个β-范式，那么正常顺序评估是保证能找到。
那么什么是正常顺序？简而言之，就是β——每一步都减少最外层的表达式。让我们把这个表达式再旋转一下！
(λx. (λy. y x) (λz. x z)) (λm. m m)
(λy. y (λm. m m)) (λz. (λm. m m) z)
(λz. (λm. m m) z) (λm. m m)
(λm. m m) (λm. m m)
该死。看起来这个表达式没有正常形式——它 diverges（不终止）。
我刚刚学习了 lambda 演算，我在尝试减少时遇到了问题
(λx. (λy. y x) (λz. x z)) (λy. y y)
恢复正常形式。我到达 (λy. y (λy. y y) (λz. (λy. y y) z) 然后有点迷路了。我不知道从这里去哪里，或者它是否正确。
(λx. (λy. y x) (λz. x z)) (λy. y y)
正如@ymonad 指出的那样，y 参数之一需要重命名以避免捕获（合并只是巧合地共享相同名称的不同变量）。在这里我重命名后一个实例（使用 α-equivalence）：
(λx. (λy. y x) (λz. x z)) (λm. m m)
下一步是β-reduce。在这个表达式中，我们可以在两个地方之一这样做：我们可以减少最外层的应用程序 (λx) 或内部应用程序 (λy)。我打算做后者，主要是随心所欲/因为我想得有点超前，认为它会导致更短的中间表达式：
(λx. (λz. x z) x) (λm. m m)
还有更多β-还原要做。我将再次选择内部表达式，因为我可以看到它的发展方向，但在这种情况下实际上并不重要，无论如何我都会得到相同的最终答案：
(λx. x x) (λm. m m)
旁注：这两个 lambda 表达式（也称为 "Mockingbird"（根据 Raymond Smullyan））实际上是 α 等价的，并且整个表达式是（不）著名的 Ω 组合器。然而，如果我们忽略所有这些，并应用另一个 β-reduction:
(λm. m m) (λm. m m)
啊，这仍然是 β-可还原的。或者是吗？这个表达式α——等价于前面的。天哪，我们似乎发现自己陷入了无限循环，这在图灵完备（或者我们应该说 Lambda 完备？）语言中总是可能发生的。人们可能会将其表示为我们的原始表达式等于 "bottom"（用 Haskell 的说法），表示为 ⊥:
(λx. (λy. y x) (λz. x z)) (λy. y y) = ⊥
这是一个错误吗？嗯，一些好的 LC 理论是：
- 如果一个表达式有一个β范式，那么它将是相同的β-正常形式，无论使用什么减少顺序来达到它，并且
- 如果一个表达式有一个β-范式，那么正常顺序评估是保证能找到。
那么什么是正常顺序？简而言之，就是β——每一步都减少最外层的表达式。让我们把这个表达式再旋转一下！
(λx. (λy. y x) (λz. x z)) (λm. m m)
(λy. y (λm. m m)) (λz. (λm. m m) z)
(λz. (λm. m m) z) (λm. m m)
(λm. m m) (λm. m m)
该死。看起来这个表达式没有正常形式——它 diverges（不终止）。