为什么 λ 演算最优评估器能够在没有公式的情况下计算大的模幂？
Why are λ-calculus optimal evaluators able to compute big modular exponentiations without formulas?
教会数字是自然数作为函数的编码。
(\ f x → (f x)) -- church number 1
(\ f x → (f (f (f x)))) -- church number 3
(\ f x → (f (f (f (f x))))) -- church number 4
巧妙地，您只需应用 2 个教堂数字即可取幂。也就是说，如果你将 4 应用到 2，你会得到教堂编号 16，或 2^4。显然，这是完全不切实际的。教堂数字需要线性数量的内存，而且速度非常非常慢。计算像 10^10 这样的东西——GHCI 可以快速正确地回答——会花费很长时间，而且无论如何都无法容纳你计算机上的内存。
我最近一直在试验最优 λ 评估器。在我的测试中，我不小心在我的最佳 λ 计算器上输入了以下内容：
10 ^ 10 % 13
应该是乘法，而不是求幂。在我绝望地动动手指放弃 forever-运行 程序之前，它回答了我的请求：
3
{ iterations: 11523, applications: 5748, used_memory: 27729 }
real 0m0.104s
user 0m0.086s
sys 0m0.019s
随着我的"bug alert"闪烁，我去Google验证了一下，确实10^10%13 == 3。 但是 λ 计算器不应该找到那个结果，它几乎不能存储 10^10。 为了科学，我开始强调它。它立即回答了我20^20%13 == 3、50^50%13 == 4、60^60%3 == 0。我不得不使用 external tools 来验证这些结果，因为 Haskell 本身无法计算它（由于整数溢出）（如果你使用当然是整数而不是整数！）。将其推向极限，这就是 200^200%31:
的答案
5
{ iterations: 10351327, applications: 5175644, used_memory: 23754870 }
real 0m4.025s
user 0m3.686s
sys 0m0.341s
如果我们为宇宙中的每个原子创建一个宇宙副本，并且我们为总共拥有的每个原子配备一台计算机，我们将无法存储教堂编号 200^200。这促使我质疑我的 mac 是否真的那么强大。也许最佳评估者能够跳过不必要的分支并以与延迟评估相同的方式 Haskell 直接得出答案。为了测试这一点，我将 λ 程序编译为 Haskell:
data Term = F !(Term -> Term) | N !Double
instance Show Term where {
show (N x) = "(N "++(if fromIntegral (floor x) == x then show (floor x) else show x)++")";
show (F _) = "(λ...)"}
infixl 0 #
(F f) # x = f x
churchNum = F(\(N n)->F(\f->F(\x->if n<=0 then x else (f#(churchNum#(N(n-1))#f#x)))))
expMod = (F(\v0->(F(\v1->(F(\v2->((((((churchNum # v2) # (F(\v3->(F(\v4->(v3 # (F(\v5->((v4 # (F(\v6->(F(\v7->(v6 # ((v5 # v6) # v7))))))) # v5))))))))) # (F(\v3->(v3 # (F(\v4->(F(\v5->v5)))))))) # (F(\v3->((((churchNum # v1) # (churchNum # v0)) # ((((churchNum # v2) # (F(\v4->(F(\v5->(F(\v6->(v4 # (F(\v7->((v5 # v7) # v6))))))))))) # (F(\v4->v4))) # (F(\v4->(F(\v5->(v5 # v4))))))) # ((((churchNum # v2) # (F(\v4->(F(\v5->v4))))) # (F(\v4->v4))) # (F(\v4->v4))))))) # (F(\v3->(((F(\(N x)->F(\(N y)->N(x+y)))) # v3) # (N 1))))) # (N 0))))))))
main = print $ (expMod # N 5 # N 5 # N 4)
这会正确输出 1 (5 ^ 5 % 4) - 但抛出任何高于 10^10 的东西都会卡住，从而消除了假设。
optimal evaluator I used 是一个 160 行长的未优化 JavaScript 程序，不包含任何类型的指数模数数学 - 我使用的 lambda 演算模数函数同样简单：
(λab.(b(λcd.(c(λe.(d(λfg.(f(efg)))e))))(λc.(c(λde.e)))(λc.(a(b(λdef.(d(λg.(egf))))(λd.d)(λde.(ed)))(b(λde.d)(λd.d)(λd.d))))))
我没有使用特定的模运算算法或公式。 那么，最佳评估者是如何得出正确答案的呢？
这不是答案，而是建议您可以从哪里开始寻找。
有一种简单的方法可以在 space 中计算模幂，特别是通过重写
(a * x ^ y) % z
作为
(((a * x) % z) * x ^ (y - 1)) % z
如果一个求值者这样求值并且保持累加参数a的正常形式那么你将避免使用太多space。如果您的评估器确实 是 最优的，那么大概它不能做比这个更多的工作，所以特别是不能使用比这个评估所花费的时间更多的 space .
我不太确定最佳评估者到底是什么，所以恐怕我不能使这个更严格。
这种现象来自于共享 beta 减少步骤的数量，这在 Haskell 风格的惰性求值（或通常的按值调用，在这方面相差不大) 和 Vuillemin-Lévy-Lamping-Kathail-Asperti-Guerrini-(et al…) "optimal" 评估。这是一个通用功能，完全独立于您可以在此特定示例中使用的算术公式。
共享意味着拥有您的 lambda 项的表示，其中一个 "node" 可以描述您所表示的实际 lambda 项的几个相似部分。例如，您可以表示
\x. x ((\y.y)a) ((\y.y)a)
使用一个（有向无环）图，其中只出现一次表示 (\y.y)a 的子图，并且有两条边指向该子图。在 Haskell 术语中，你有一个 thunk，你只计算一次，还有两个指向这个 thunk 的指针。
Haskell-style memoization 实现了完整子项的共享。这种共享级别可以用有向无环图来表示。最优共享没有这个限制：它也可以共享 "partial" 个子项，这可能意味着图形表示中的循环。
要了解这两个共享级别之间的区别，请考虑术语
\x. (\z.z) ((\z.z) x)
如果您的共享仅限于完整的子项，就像 Haskell 中的情况一样，您可能只会出现一次 \z.z，但这里的两个 beta-redexes 将是不同的：一个一个是(\z.z) x，另一个是(\z.z) ((\z.z) x)，因为它们不是等价的，所以不能共享。
如果允许共享部分子项，那么就可以共享部分项(\z.z) []（这不仅仅是函数\z.z，而是"the function \z.z applied to something), which evaluates in one step to just something, whatever this argument is. Hence you can have a graph in which only one node represents the two applications of \z.z to two distinct arguments, and in which these two applications can be reduced in just one step. Remark that there is a cycle on this node, since the argument of the "第一次出现”正是"second occurrence"。
最后，通过最佳共享，您可以从（表示的图表）\x. (\z.z) ((\z.z) x)) 到（表示的图表）结果 \x.x 只需一个 beta 缩减步骤（加上一些簿记）。这基本上就是您的最佳评估器中发生的情况（图形表示也是防止 space 爆炸的原因）。
对于稍微扩展的解释，您可以查看论文Weak Optimality, and the Meaning of Sharing（您感兴趣的是介绍和第 4.1 节，以及末尾的一些参考书目指针）。
回到你的例子，在 Church 整数上工作的算术函数的编码是 "well-known" 最佳评估器可以比主流语言表现更好的例子之一（在这句话中，实际上众所周知意味着少数专家知道这些例子）。
有关更多此类示例，请查看 Asperti 和 Chroboczek 的论文 Safe Operators: Brackets Closed Forever（顺便说一下，您会在这里找到有趣的 lambda 项，这些 lambda 项不是 EAL 类型的；所以我鼓励您采取查看预言机，从这篇 Asperti/Chroboczek 论文开始。
正如您自己所说，这种编码完全不切实际，但它们仍然是一种理解正在发生的事情的好方法。让我以进一步调查的挑战作为结束：你能否找到一个例子，在这些例子中，对这些所谓的不良编码的最佳评估实际上与对合理数据表示的传统评估相当？ （据我所知，这是一个真正的开放性问题）。
教会数字是自然数作为函数的编码。
(\ f x → (f x)) -- church number 1
(\ f x → (f (f (f x)))) -- church number 3
(\ f x → (f (f (f (f x))))) -- church number 4
巧妙地，您只需应用 2 个教堂数字即可取幂。也就是说，如果你将 4 应用到 2，你会得到教堂编号 16，或 2^4。显然，这是完全不切实际的。教堂数字需要线性数量的内存，而且速度非常非常慢。计算像 10^10 这样的东西——GHCI 可以快速正确地回答——会花费很长时间，而且无论如何都无法容纳你计算机上的内存。
我最近一直在试验最优 λ 评估器。在我的测试中，我不小心在我的最佳 λ 计算器上输入了以下内容：
10 ^ 10 % 13
应该是乘法，而不是求幂。在我绝望地动动手指放弃 forever-运行 程序之前，它回答了我的请求：
3
{ iterations: 11523, applications: 5748, used_memory: 27729 }
real 0m0.104s
user 0m0.086s
sys 0m0.019s
随着我的"bug alert"闪烁，我去Google验证了一下，确实10^10%13 == 3。 但是 λ 计算器不应该找到那个结果，它几乎不能存储 10^10。 为了科学，我开始强调它。它立即回答了我20^20%13 == 3、50^50%13 == 4、60^60%3 == 0。我不得不使用 external tools 来验证这些结果，因为 Haskell 本身无法计算它（由于整数溢出）（如果你使用当然是整数而不是整数！）。将其推向极限，这就是 200^200%31:
5
{ iterations: 10351327, applications: 5175644, used_memory: 23754870 }
real 0m4.025s
user 0m3.686s
sys 0m0.341s
如果我们为宇宙中的每个原子创建一个宇宙副本，并且我们为总共拥有的每个原子配备一台计算机，我们将无法存储教堂编号 200^200。这促使我质疑我的 mac 是否真的那么强大。也许最佳评估者能够跳过不必要的分支并以与延迟评估相同的方式 Haskell 直接得出答案。为了测试这一点，我将 λ 程序编译为 Haskell:
data Term = F !(Term -> Term) | N !Double
instance Show Term where {
show (N x) = "(N "++(if fromIntegral (floor x) == x then show (floor x) else show x)++")";
show (F _) = "(λ...)"}
infixl 0 #
(F f) # x = f x
churchNum = F(\(N n)->F(\f->F(\x->if n<=0 then x else (f#(churchNum#(N(n-1))#f#x)))))
expMod = (F(\v0->(F(\v1->(F(\v2->((((((churchNum # v2) # (F(\v3->(F(\v4->(v3 # (F(\v5->((v4 # (F(\v6->(F(\v7->(v6 # ((v5 # v6) # v7))))))) # v5))))))))) # (F(\v3->(v3 # (F(\v4->(F(\v5->v5)))))))) # (F(\v3->((((churchNum # v1) # (churchNum # v0)) # ((((churchNum # v2) # (F(\v4->(F(\v5->(F(\v6->(v4 # (F(\v7->((v5 # v7) # v6))))))))))) # (F(\v4->v4))) # (F(\v4->(F(\v5->(v5 # v4))))))) # ((((churchNum # v2) # (F(\v4->(F(\v5->v4))))) # (F(\v4->v4))) # (F(\v4->v4))))))) # (F(\v3->(((F(\(N x)->F(\(N y)->N(x+y)))) # v3) # (N 1))))) # (N 0))))))))
main = print $ (expMod # N 5 # N 5 # N 4)
这会正确输出 1 (5 ^ 5 % 4) - 但抛出任何高于 10^10 的东西都会卡住，从而消除了假设。
optimal evaluator I used 是一个 160 行长的未优化 JavaScript 程序，不包含任何类型的指数模数数学 - 我使用的 lambda 演算模数函数同样简单：
(λab.(b(λcd.(c(λe.(d(λfg.(f(efg)))e))))(λc.(c(λde.e)))(λc.(a(b(λdef.(d(λg.(egf))))(λd.d)(λde.(ed)))(b(λde.d)(λd.d)(λd.d))))))
我没有使用特定的模运算算法或公式。 那么，最佳评估者是如何得出正确答案的呢？
这不是答案，而是建议您可以从哪里开始寻找。
有一种简单的方法可以在 space 中计算模幂，特别是通过重写
(a * x ^ y) % z
作为
(((a * x) % z) * x ^ (y - 1)) % z
如果一个求值者这样求值并且保持累加参数a的正常形式那么你将避免使用太多space。如果您的评估器确实 是 最优的，那么大概它不能做比这个更多的工作，所以特别是不能使用比这个评估所花费的时间更多的 space .
我不太确定最佳评估者到底是什么，所以恐怕我不能使这个更严格。
这种现象来自于共享 beta 减少步骤的数量，这在 Haskell 风格的惰性求值（或通常的按值调用，在这方面相差不大) 和 Vuillemin-Lévy-Lamping-Kathail-Asperti-Guerrini-(et al…) "optimal" 评估。这是一个通用功能，完全独立于您可以在此特定示例中使用的算术公式。
共享意味着拥有您的 lambda 项的表示，其中一个 "node" 可以描述您所表示的实际 lambda 项的几个相似部分。例如，您可以表示
\x. x ((\y.y)a) ((\y.y)a)
使用一个（有向无环）图，其中只出现一次表示 (\y.y)a 的子图，并且有两条边指向该子图。在 Haskell 术语中，你有一个 thunk，你只计算一次，还有两个指向这个 thunk 的指针。
Haskell-style memoization 实现了完整子项的共享。这种共享级别可以用有向无环图来表示。最优共享没有这个限制：它也可以共享 "partial" 个子项，这可能意味着图形表示中的循环。
要了解这两个共享级别之间的区别，请考虑术语
\x. (\z.z) ((\z.z) x)
如果您的共享仅限于完整的子项，就像 Haskell 中的情况一样，您可能只会出现一次 \z.z，但这里的两个 beta-redexes 将是不同的：一个一个是(\z.z) x，另一个是(\z.z) ((\z.z) x)，因为它们不是等价的，所以不能共享。
如果允许共享部分子项，那么就可以共享部分项(\z.z) []（这不仅仅是函数\z.z，而是"the function \z.z applied to something), which evaluates in one step to just something, whatever this argument is. Hence you can have a graph in which only one node represents the two applications of \z.z to two distinct arguments, and in which these two applications can be reduced in just one step. Remark that there is a cycle on this node, since the argument of the "第一次出现”正是"second occurrence"。
最后，通过最佳共享，您可以从（表示的图表）\x. (\z.z) ((\z.z) x)) 到（表示的图表）结果 \x.x 只需一个 beta 缩减步骤（加上一些簿记）。这基本上就是您的最佳评估器中发生的情况（图形表示也是防止 space 爆炸的原因）。
对于稍微扩展的解释，您可以查看论文Weak Optimality, and the Meaning of Sharing（您感兴趣的是介绍和第 4.1 节，以及末尾的一些参考书目指针）。
回到你的例子，在 Church 整数上工作的算术函数的编码是 "well-known" 最佳评估器可以比主流语言表现更好的例子之一（在这句话中，实际上众所周知意味着少数专家知道这些例子）。 有关更多此类示例，请查看 Asperti 和 Chroboczek 的论文 Safe Operators: Brackets Closed Forever（顺便说一下，您会在这里找到有趣的 lambda 项，这些 lambda 项不是 EAL 类型的；所以我鼓励您采取查看预言机，从这篇 Asperti/Chroboczek 论文开始。
正如您自己所说，这种编码完全不切实际，但它们仍然是一种理解正在发生的事情的好方法。让我以进一步调查的挑战作为结束：你能否找到一个例子，在这些例子中，对这些所谓的不良编码的最佳评估实际上与对合理数据表示的传统评估相当？ （据我所知，这是一个真正的开放性问题）。