Mogensen 二进制编码的继任者和前任问题
Trouble with successor & predecessor in Mogensen's binary encoding
我想将二进制数添加到我的非类型化 lambda 演算库中，但我受困于 succ 和 pred 函数。我正在使用 paper by T. Mogensen 中概述的表示，虽然那里定义的大多数函数都有效，但 succ 和 pred 返回错误结果。
我很确定我的表述是正确的：
dec bin De Bruijn classic
0 0 λλλ3 λa.λb.λc.a
1 1 λλλ13 λa.λb.λc.c a
2 10 λλλ2(13) λa.λb.λc.b (c a)
3 11 λλλ1(13) λa.λb.λc.c (c a)
4 100 λλλ2(2(13)) λa.λb.λc.b (b (c a))
5 101 λλλ1(2(13)) λa.λb.λc.c (b (c a))
6 110 λλλ2(1(13)) λa.λb.λc.b (c (c a))
7 111 λλλ1(1(13)) λa.λb.λc.c (c (c a))
8 1000 λλλ2(2(2(13))) λa.λb.λc.b (b (b (c a)))
元组和投影看起来也不错：
tuple De Bruijn classic
[T, F] λ1(λλ2)(λλ1) λa.a (λb.λc.b) (λb.λc.c)
[T, F, F] λ1(λλ2)(λλ1)(λλ1) λa.a (λb.λc.b) (λb.λc.c) (λb.λc.c)
[T, F, F, T] λ1(λλ2)(λλ1)(λλ1)(λλ2) λa.a (λb.λc.b) (λb.λc.c) (λb.λc.c) (λb.λc.b)
πkn De Bruijn classic
π12 λ1(λλ2) λa.a (λb.λc.b)
π22 λ1(λλ1) λa.a (λb.λc.c)
上移 0 位 (shl0) 和 1 位 (shl1) 在测试中效果很好：
SHL0 ≡ λnbzo.z (n b z o) = λ λ λ λ 2 (4 3 2 1)
SHL1 ≡ λnbzo.o (n b z o) = λ λ λ λ 1 (4 3 2 1)
但是 succ 和 pred 取决于上面列出的条款：
SUCC ≡ λn.π22 (n Z A B) ≡ λ π22 (1 Z A B) where
Z ≡ [ZERO, ONE] // encoded like in the first piece of code
A ≡ λp.p (λnm.[SHL0 n, SHL1 n]) ≡ λ 1 (λ λ [SHL0 2, SHL1 2])
B ≡ λp.p (λnm.[SHL1 n, SHL0 m]) ≡ λ 1 (λ λ [SHL1 2, SHL0 1])
PRED ≡ λn.π22 (n Z A B) ≡ λ π22 (1 Z A B) where
Z ≡ [ZERO, ZERO] // encoded like in the first piece of code
A ≡ λp.p (λnm.[SHL0 n, SHL1 m]) ≡ λ 1 (λ λ [SHL0 2, SHL1 1])
B ≡ λp.p (λnm.[SHL1 n, SHL0 n]) ≡ λ 1 (λ λ [SHL1 2, SHL0 2])
示例结果：
succ 0 = λa.λb.λc.c a / λλλ13 ok
succ 1 = λa.λb.λc.b (b c) / λλλ2(21) wrong, expected λλλ2(13)
succ 2 = λa.λb.λc.c (b (c (λd.λe.λf.e (b d e f)) (λd.λe.λf.f (b d e f)))) / λλλ1(2(1(λλλ2(5321))(λλλ1(5321)))) wrong, expected λλλ1(13)
succ 3 = λa.λb.λc.b (b c) / λλλ2(21) wrong, expected λλλ2(2(13))
pred 1 = λa.λb.λc.b a / λλλ23 wrong-ish, expected λλλ3; it's just a leading zero, but it's stated that those should only be caused by inputs that are powers of 2
pred 2 = λa.λb.λc.c (b c) / λλλ1(21) wrong, expected λλλ13
pred 3 = λa.λb.λc.b (b a) / λλλ2(23) wrong, expected λλλ2(13)
pred 4 = λa.λb.λc.c (b c) / λλλ1(21) wrong, expected λλλ1(13)
我的术语评估器针对数百个术语进行了测试，所以我对此非常有信心；我怀疑是我误读了什么东西还是印刷错误了。我错过了什么吗？
所以，正如 ljedrz 提到的，我们设法让 Morgensen 数字在单独的聊天中工作。在这个答案中，我将简要描述它的一般工作原理。
问题是：« 我怀疑是我误读了什么东西还是印刷错误。我错过了什么吗？ »
tl;dr：原来是一些与评估顺序相关的棘手问题导致了问题。问题 中出现的 Morgensen 数字做 工作。
更长的答案：succ 是如何工作的？
N.B.: 在下面的 b_n 总是假定为 1，如在原始论文中。
Morgensen 数字背后的想法是将数字 n = b_n ... b_2 b_1 编码为 \z.\x_0.\x_1. x_{b_1} ( x_{b_2} (... ( x_{b_n} z ) ...) )。这很难读，但如果这样说就更清楚了：
A number n is a term which expects 3 arguments, and when applied, returns x_{b_1} ( x_{b_2} (... ( x_{b_n} z ) ...) )
嗯，这还不清楚。如果我们看得更深一些，我们会看到数字 n 从项 z 开始递归应用 x_0 或 x_1。请注意，递归调用是 "from left to right"，即，如果我有一个数字 b_n b_{n-1} ... b_2 b_1，则递归调用按以下顺序计算：
- 先
b_n z，就当i_{n-1}
- 然后
b_{n-1} i_{n-1}，让它成为i_{n-2}
- ...
- 最后是i_1b_1
（嗯，评估策略决定了准确的评估顺序，我认为很容易认为它是这样评估的）
与列表中 fold 函数的关系
实际上，当我意识到这一点时，它只是让我想到了位列表的 fold_left 功能：假设你有一个位列表 l = [b_n; ... ; b_2; b_1]，那么你可以执行以下操作：
fold_left (fun prev_acc -> fun b -> if b = 0 then x_0 prev_acc else x_1 prev_acc) z l
设f为
fun prev_acc -> fun b -> if b = 0 then x_0 prev_acc else x_1 prev_acc
which returns (根据 Ocaml doc)
f (f (... (f z b_n) ...) b_2) b_1
计算结果为：
f z b_n 的计算结果为 x_{b_n} z，即上面的 i_{n-1}。- ...
f i_{1} b_1，同上
结论，您完全可以将 Morgensen 数字视为列表中的 fold_left（或 fold_right，具体取决于您如何想象列表）。
获取数字的succ
得到一个数字的succ就是得到n+1。二进制增量作为一个很好的 属性:
if m = bn ... bi bj bk ... b1 with bj being the first 0 (i.e. bk = ... = b1 = 1), then m + 1 = bn ... bi 1 0 ... 0
这可以说明：
bn ... bi 0 1 1 1 1 1
如果我添加 1，那么我得到（通过详细说明所有步骤）：
bn ... bi 0 1 1 1 1 1
+1
--------------------------
bn ... bi 0 1 1 1 1 0
+1 < I have a carry here, which gets propagated
...
--------------------------
bn ... bi 0 0 0 0 0 0
+1 < The carry ends up here
--------------------------
bn ... bi 1 0 0 0 0 0 < This is our result of doing a +1.
注意 (bn ... bi 0 1 ... 1) + 1 是 (bn ... bi 0) + 1 附加到 0 ... 0，更一般地说，它也适用于任何 bj：(bn ... bi bj 1 ... 1) + 1 是 (bn ... bi bj) + 1 附加到 0 ... 0。
这看起来不错，只有一个问题，进位是从右向左传播（LSB 到 MSB），而 Morgensen 数字是从 MSB 到 LSB。
为了解决最后一个问题，我们可以进行推测：假设我有一个数字 b_n ... bi bj bk ... b1，并且我想拥有它的后继者。我将不得不递归地计算它，但只能从 MSB 到 LSB。
也就是说，如果我在 "step bj"，我只能使用子序列 bn ... bi 和 bj 本身。
例如，这允许我们计算 bn ... bi 的 succ。现在是推测部分：
- 我知道，如果在
bj之后，只有1，那么在前面的备注之后，那么后继者就是((bn ... bi bj) + 1)::(0 ... 0)
- 但是，如果
bk ... b1中有一个0，则位(bn ... bi bj)保持不变
所以我们的想法是 return 在元组中的每一位都有两种可能性。非正式地，传递给 fold_left 的函数看起来像这样：
fun tuple_msb -> fun bj ->
(original_msb, incr_msb)
其中 (1) tuple_msb 是一个包含 (bn ... bi, (bn ... bi) + 1) 的元组；其中 (2) original_msb 和 incr_msb 是根据 bj 计算的。确实：
- 如果
bj是0，那么(bn ... bi bj) + 1 = (bn ... bi 0) + 1 = (bn ... bi 1)
- 如果
bj 是 1，则 (bn ... bi bj) + 1 = (bn ... bi 1) + 1 = ((bn ... bi) + 1)::0。
也就是说，传递给 fold_left 的完整函数如下：
(* We keep the original sequence on the left of the tuple, the incremented `bn ... bi bj` on the right *)
fun tuple_msb -> fun bj ->
if bj = 0 then
(tuple_msb._1 :: 0, tuple_msb._1 :: 1)
else
(tuple_msb._1 :: 1, tuple_msb._2 :: 0)
和基本情况（即起始元素是元组(0, 1)）
从这里开始，很容易回到 Morgensen 不可读的术语（这里有一个关于参数顺序的隐藏的小捷径，但这并不重要）：
根据x_0 和 x_1，基本情况（即开头的 z 是 (0, 1)）。
为了获得最终的后继者，我们必须获得 returned 元组的正确部分，因此是最终的
let succ n =
let ret_tuple = n z x_0 x_1 in
ret_tuple._2
或 lambda 术语：
succ' = λn. π22 (n z x_0 x_1)
所有 π22、z、x_0 和 x_1 均已相应定义。
我们的 succ' 与提议的 succ 有点不同，即 x_0 不完全是 A 而 x_1 不完全是 B，但这最后一步很简单，留给感兴趣的 reader ;-)
当 Bromind 告诉我他们对 succ 的定义略有不同时，我将其移植到 Ocaml+utop 中并用我的库进行了测试。不过，它也失败了，所以我开始分析所有涉及的术语，结果发现一切看起来都与我的实现几乎相同。确信我的评估者是可靠的并且这些定义是有效的，我一直在寻找直到找到真正的原因。
不过，为了不破坏乐趣，我要补充一点，我实际上联系了教授。 Mogensen 关于这个，他非常友好地为我提供了表达式 succ 1:
的高级评估步骤
succ 1
= (λn.π² (n Z A B)) |1|
= (λn.π² (n Z A B)) (λz01.1 z)
= π² ((λz01.1 z) Z A B)
= π² (B Z)
= π² ((λp.p (λnm.[↑1 n, ↑0 m])) [|0|, |1|])
= π² ([|0|, |1|] (λnm.[↑1 n, ↑0 m]))
= π² ((λx.x |0| |1|) (λnm.[↑1 n, ↑0 m]))
= π² ((λnm.[↑1 n, ↑0 m]) |0| |1|)
= π² [↑1 |0|, ↑0 |1|]
= ↑0 |1|
= (λn.λz01.0 (n z 0 1)) |1|
= λz01.0 (|1| z 0 1)
= λz01.0 ((λz01.1 z) z 0 1)
= λz01.0 (1 z)
= |2|
这个解决方案 100% 有效，但与我的实现相比它太高级了，所以我决定用 "low-level" β-reductions 来检测定义失败的确切点。
下面是 De Bruijn 索引表示法中的初始表达式 (succ 1)：
(λ(λ1(λλ1))(1(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))))(λλλ13)
及其缩减步骤（正常顺序；其他也不起作用）：
(λ(λ1(λλ1))(1(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))))(λλλ13)
^ ^ ^^^^^^^
↳ becomes λλλ13
(λ1(λλ1))((λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))))
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))
(λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^ ^ ^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ3)(λλλ13)
(λλ1(λ1(λλλ3)(λλλ13)))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - is dropped
(λ1(λ1(λλλ3)(λλλ13)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))
(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))(λ1(λλλ3)(λλλ13))(λλ1)
^^ ^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ3)(λλλ13)
(λ1(λλλ3)(λλλ13))(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))(λλ1)
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)
(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ3)(λλλ13)(λλ1)
^ ^^^^^^ - is dropped
(λλ1((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ13)(λλ1)
^ ^ ^^^^^^^
↳ becomes λλλ13
(λ1((λλλλ1(4321))(λλλ13))((λλλλ2(4321))1))(λλ1)
^^ ^
↳ becomes (λλ1) ↳ becomes (λλ1)
(λλ1)((λλλλ1(4321))(λλλ13))((λλλλ2(4321))(λλ1))
^ ^^^^^^^^^^^^^^^^^^^^^^ - is dropped
(λ1)((λλλλ2(4321))(λλ1))
^^ ^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλλ2(4321))(λλ1)
(λλλλ2(4321))(λλ1)
^ ^ ^^^^^
↳ becomes λλ1
λλλ2((λλ1)321)
^ ^ - is dropped
λλλ2((λ1)21)
^^ ^
↳ becomes 2
λλλ2(21) // fail
这是一个微妙的问题：A 和 B 都需要将它们的元组设为 unnormalized/destructured 形式，以便 succ 和 pred与纯 β 归约评估器一起工作的定义。我注意到这一点是因为我的实现使用了规范化元组，而 Bromind 没有。
让我们看看正确的定义：
(λ(λ1(λλ1))(1(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))))(λλλ13)
及其归约步骤（又是正常顺序）：
(λ(λ1(λλ1))(1(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))))(λλλ13)
^ ^ ^^^^^^^
↳ becomes λλλ13
(λ1(λλ1))((λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))))
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))
(λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^ ^ ^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ3)(λλλ13)
(λλ1(λ1(λλλ3)(λλλ13)))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - is dropped
(λ1(λ1(λλλ3)(λλλ13)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))
(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))(λ1(λλλ3)(λλλ13))(λλ1)
^^ ^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ3)(λλλ13)
(λ1(λλλ3)(λλλ13))(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))(λλ1)
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)
(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ3)(λλλ13)(λλ1)
^ ^ ^^^^^^
↳ becomes λλλ3
(λ(λλλ132)((λλλλ1(4321))(λλλ3))((λλλλ2(4321))1))(λλλ13)(λλ1)
^ ^ ^^^^^^^
↳ becomes λλλ13
(λλλ132)((λλλλ1(4321))(λλλ3))((λλλλ2(4321))(λλλ13))(λλ1)
^ ^ ^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλλ1(4321))(λλλ3)
(λλ1((λλλλ1(4321))(λλλ3))2)((λλλλ2(4321))(λλλ13))(λλ1)
^ ^ ^^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλλ2(4321))(λλλ13)
(λ1((λλλλ1(4321))(λλλ3))((λλλλ2(4321))(λλλ13)))(λλ1)
^^ ^^^^^
↳ becomes λλ1
(λλ1)((λλλλ1(4321))(λλλ3))((λλλλ2(4321))(λλλ13))
^ ^^^^^^^^^^^^^^^^^^^^^ - is dropped
(λ1)((λλλλ2(4321))(λλλ13))
^^ ^^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλλ2(4321))(λλλ13)
(λλλλ2(4321))(λλλ13)
^ ^ ^^^^^^^
↳ becomes λλλ13
λλλ2((λλλ13)321)
^ ^ ^
↳ becomes the right-hand side 3 and gets an index upgrade due to extra abstractions
λλλ2((λλ15)21)
^ ^
↳ gets its index downgraded
λλλ2((λ14)1)
^^ ^
↳ becomes the right-hand side 1; 4 gets an index downgrade
λλλ2(13) // aww yiss
关键区别如下：
(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ3)(λλλ13)(λλ1) // normalized tuple
^ ^^^^^^ - is dropped
(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ3)(λλλ13)(λλ1) // unnormalized tuple
^ ^ ^^^^^^
↳ becomes λλλ3
如果 A 或 B 包含归一化元组，Z 元组中的零将被丢弃并退出游戏，因此关键步骤 π² ((λnm.[↑1 n, ↑0 m]) |0| |1|) => π² [↑1 |0|, ↑0 |1|] 可以'完全发生。
下面是 succ 的错误定义（对于纯 β 归约评估器）和正确的完整定义（包括 Z、A、B）之间的区别:
λ PI22 (1 [ZERO, ONE] (λ 1 (λ λ [SHL0 2, SHL1 2])) (λ 1 (λ λ [SHL1 2, SHL0 1]))) // wrong
λ PI22 (1 [ZERO, ONE] (λ 1 (λ λ TUPLE2 (SHL0 2) (SHL1 2))) (λ 1 (λ λ TUPLE2 (SHL1 2) (SHL0 1)))) // right
where TUPLE2 ≡ λ λ λ 1 3 2
我想将二进制数添加到我的非类型化 lambda 演算库中，但我受困于 succ 和 pred 函数。我正在使用 paper by T. Mogensen 中概述的表示，虽然那里定义的大多数函数都有效，但 succ 和 pred 返回错误结果。
我很确定我的表述是正确的：
dec bin De Bruijn classic
0 0 λλλ3 λa.λb.λc.a
1 1 λλλ13 λa.λb.λc.c a
2 10 λλλ2(13) λa.λb.λc.b (c a)
3 11 λλλ1(13) λa.λb.λc.c (c a)
4 100 λλλ2(2(13)) λa.λb.λc.b (b (c a))
5 101 λλλ1(2(13)) λa.λb.λc.c (b (c a))
6 110 λλλ2(1(13)) λa.λb.λc.b (c (c a))
7 111 λλλ1(1(13)) λa.λb.λc.c (c (c a))
8 1000 λλλ2(2(2(13))) λa.λb.λc.b (b (b (c a)))
元组和投影看起来也不错：
tuple De Bruijn classic
[T, F] λ1(λλ2)(λλ1) λa.a (λb.λc.b) (λb.λc.c)
[T, F, F] λ1(λλ2)(λλ1)(λλ1) λa.a (λb.λc.b) (λb.λc.c) (λb.λc.c)
[T, F, F, T] λ1(λλ2)(λλ1)(λλ1)(λλ2) λa.a (λb.λc.b) (λb.λc.c) (λb.λc.c) (λb.λc.b)
πkn De Bruijn classic
π12 λ1(λλ2) λa.a (λb.λc.b)
π22 λ1(λλ1) λa.a (λb.λc.c)
上移 0 位 (shl0) 和 1 位 (shl1) 在测试中效果很好：
SHL0 ≡ λnbzo.z (n b z o) = λ λ λ λ 2 (4 3 2 1)
SHL1 ≡ λnbzo.o (n b z o) = λ λ λ λ 1 (4 3 2 1)
但是 succ 和 pred 取决于上面列出的条款：
SUCC ≡ λn.π22 (n Z A B) ≡ λ π22 (1 Z A B) where
Z ≡ [ZERO, ONE] // encoded like in the first piece of code
A ≡ λp.p (λnm.[SHL0 n, SHL1 n]) ≡ λ 1 (λ λ [SHL0 2, SHL1 2])
B ≡ λp.p (λnm.[SHL1 n, SHL0 m]) ≡ λ 1 (λ λ [SHL1 2, SHL0 1])
PRED ≡ λn.π22 (n Z A B) ≡ λ π22 (1 Z A B) where
Z ≡ [ZERO, ZERO] // encoded like in the first piece of code
A ≡ λp.p (λnm.[SHL0 n, SHL1 m]) ≡ λ 1 (λ λ [SHL0 2, SHL1 1])
B ≡ λp.p (λnm.[SHL1 n, SHL0 n]) ≡ λ 1 (λ λ [SHL1 2, SHL0 2])
示例结果：
succ 0 = λa.λb.λc.c a / λλλ13 ok
succ 1 = λa.λb.λc.b (b c) / λλλ2(21) wrong, expected λλλ2(13)
succ 2 = λa.λb.λc.c (b (c (λd.λe.λf.e (b d e f)) (λd.λe.λf.f (b d e f)))) / λλλ1(2(1(λλλ2(5321))(λλλ1(5321)))) wrong, expected λλλ1(13)
succ 3 = λa.λb.λc.b (b c) / λλλ2(21) wrong, expected λλλ2(2(13))
pred 1 = λa.λb.λc.b a / λλλ23 wrong-ish, expected λλλ3; it's just a leading zero, but it's stated that those should only be caused by inputs that are powers of 2
pred 2 = λa.λb.λc.c (b c) / λλλ1(21) wrong, expected λλλ13
pred 3 = λa.λb.λc.b (b a) / λλλ2(23) wrong, expected λλλ2(13)
pred 4 = λa.λb.λc.c (b c) / λλλ1(21) wrong, expected λλλ1(13)
我的术语评估器针对数百个术语进行了测试，所以我对此非常有信心；我怀疑是我误读了什么东西还是印刷错误了。我错过了什么吗？
所以，正如 ljedrz 提到的，我们设法让 Morgensen 数字在单独的聊天中工作。在这个答案中，我将简要描述它的一般工作原理。
问题是：« 我怀疑是我误读了什么东西还是印刷错误。我错过了什么吗？ »
tl;dr：原来是一些与评估顺序相关的棘手问题导致了问题。问题 中出现的 Morgensen 数字做 工作。
更长的答案：succ 是如何工作的？
N.B.: 在下面的 b_n 总是假定为 1，如在原始论文中。
Morgensen 数字背后的想法是将数字 n = b_n ... b_2 b_1 编码为 \z.\x_0.\x_1. x_{b_1} ( x_{b_2} (... ( x_{b_n} z ) ...) )。这很难读，但如果这样说就更清楚了：
A number
nis a term which expects 3 arguments, and when applied, returnsx_{b_1} ( x_{b_2} (... ( x_{b_n} z ) ...) )
嗯，这还不清楚。如果我们看得更深一些，我们会看到数字 n 从项 z 开始递归应用 x_0 或 x_1。请注意，递归调用是 "from left to right"，即，如果我有一个数字 b_n b_{n-1} ... b_2 b_1，则递归调用按以下顺序计算：
- 先
b_n z，就当i_{n-1} - 然后
b_{n-1} i_{n-1}，让它成为i_{n-2} - ...
- 最后是i_1b_1
（嗯，评估策略决定了准确的评估顺序，我认为很容易认为它是这样评估的）
与列表中 fold 函数的关系
实际上，当我意识到这一点时，它只是让我想到了位列表的 fold_left 功能：假设你有一个位列表 l = [b_n; ... ; b_2; b_1]，那么你可以执行以下操作：
fold_left (fun prev_acc -> fun b -> if b = 0 then x_0 prev_acc else x_1 prev_acc) z l
设f为
fun prev_acc -> fun b -> if b = 0 then x_0 prev_acc else x_1 prev_acc
which returns (根据 Ocaml doc)
f (f (... (f z b_n) ...) b_2) b_1
计算结果为：
f z b_n的计算结果为x_{b_n} z，即上面的i_{n-1}。- ...
f i_{1} b_1，同上
结论，您完全可以将 Morgensen 数字视为列表中的 fold_left（或 fold_right，具体取决于您如何想象列表）。
获取数字的succ
得到一个数字的succ就是得到n+1。二进制增量作为一个很好的 属性:
if
m = bn ... bi bj bk ... b1withbjbeing the first0(i.e.bk = ... = b1 = 1), thenm + 1 = bn ... bi 1 0 ... 0
这可以说明：
bn ... bi 0 1 1 1 1 1
如果我添加 1，那么我得到（通过详细说明所有步骤）：
bn ... bi 0 1 1 1 1 1
+1
--------------------------
bn ... bi 0 1 1 1 1 0
+1 < I have a carry here, which gets propagated
...
--------------------------
bn ... bi 0 0 0 0 0 0
+1 < The carry ends up here
--------------------------
bn ... bi 1 0 0 0 0 0 < This is our result of doing a +1.
注意 (bn ... bi 0 1 ... 1) + 1 是 (bn ... bi 0) + 1 附加到 0 ... 0，更一般地说，它也适用于任何 bj：(bn ... bi bj 1 ... 1) + 1 是 (bn ... bi bj) + 1 附加到 0 ... 0。
这看起来不错，只有一个问题，进位是从右向左传播（LSB 到 MSB），而 Morgensen 数字是从 MSB 到 LSB。
为了解决最后一个问题，我们可以进行推测：假设我有一个数字 b_n ... bi bj bk ... b1，并且我想拥有它的后继者。我将不得不递归地计算它，但只能从 MSB 到 LSB。
也就是说，如果我在 "step bj"，我只能使用子序列 bn ... bi 和 bj 本身。
例如，这允许我们计算 bn ... bi 的 succ。现在是推测部分：
- 我知道，如果在
bj之后，只有1，那么在前面的备注之后，那么后继者就是((bn ... bi bj) + 1)::(0 ... 0) - 但是，如果
bk ... b1中有一个0，则位(bn ... bi bj)保持不变
所以我们的想法是 return 在元组中的每一位都有两种可能性。非正式地，传递给 fold_left 的函数看起来像这样：
fun tuple_msb -> fun bj ->
(original_msb, incr_msb)
其中 (1) tuple_msb 是一个包含 (bn ... bi, (bn ... bi) + 1) 的元组；其中 (2) original_msb 和 incr_msb 是根据 bj 计算的。确实：
- 如果
bj是0，那么(bn ... bi bj) + 1 = (bn ... bi 0) + 1 = (bn ... bi 1) - 如果
bj是1，则(bn ... bi bj) + 1 = (bn ... bi 1) + 1 = ((bn ... bi) + 1)::0。
也就是说，传递给 fold_left 的完整函数如下：
(* We keep the original sequence on the left of the tuple, the incremented `bn ... bi bj` on the right *)
fun tuple_msb -> fun bj ->
if bj = 0 then
(tuple_msb._1 :: 0, tuple_msb._1 :: 1)
else
(tuple_msb._1 :: 1, tuple_msb._2 :: 0)
和基本情况（即起始元素是元组(0, 1)）
从这里开始，很容易回到 Morgensen 不可读的术语（这里有一个关于参数顺序的隐藏的小捷径，但这并不重要）：
根据x_0 和 x_1，基本情况（即开头的 z 是 (0, 1)）。
为了获得最终的后继者，我们必须获得 returned 元组的正确部分，因此是最终的
let succ n =
let ret_tuple = n z x_0 x_1 in
ret_tuple._2
或 lambda 术语：
succ' = λn. π22 (n z x_0 x_1)
所有 π22、z、x_0 和 x_1 均已相应定义。
我们的 succ' 与提议的 succ 有点不同，即 x_0 不完全是 A 而 x_1 不完全是 B，但这最后一步很简单，留给感兴趣的 reader ;-)
当 Bromind 告诉我他们对 succ 的定义略有不同时，我将其移植到 Ocaml+utop 中并用我的库进行了测试。不过，它也失败了，所以我开始分析所有涉及的术语，结果发现一切看起来都与我的实现几乎相同。确信我的评估者是可靠的并且这些定义是有效的，我一直在寻找直到找到真正的原因。
不过，为了不破坏乐趣，我要补充一点，我实际上联系了教授。 Mogensen 关于这个，他非常友好地为我提供了表达式 succ 1:
succ 1
= (λn.π² (n Z A B)) |1|
= (λn.π² (n Z A B)) (λz01.1 z)
= π² ((λz01.1 z) Z A B)
= π² (B Z)
= π² ((λp.p (λnm.[↑1 n, ↑0 m])) [|0|, |1|])
= π² ([|0|, |1|] (λnm.[↑1 n, ↑0 m]))
= π² ((λx.x |0| |1|) (λnm.[↑1 n, ↑0 m]))
= π² ((λnm.[↑1 n, ↑0 m]) |0| |1|)
= π² [↑1 |0|, ↑0 |1|]
= ↑0 |1|
= (λn.λz01.0 (n z 0 1)) |1|
= λz01.0 (|1| z 0 1)
= λz01.0 ((λz01.1 z) z 0 1)
= λz01.0 (1 z)
= |2|
这个解决方案 100% 有效，但与我的实现相比它太高级了，所以我决定用 "low-level" β-reductions 来检测定义失败的确切点。
下面是 De Bruijn 索引表示法中的初始表达式 (succ 1)：
(λ(λ1(λλ1))(1(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))))(λλλ13)
及其缩减步骤（正常顺序；其他也不起作用）：
(λ(λ1(λλ1))(1(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))))(λλλ13)
^ ^ ^^^^^^^
↳ becomes λλλ13
(λ1(λλ1))((λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))))
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))
(λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^ ^ ^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ3)(λλλ13)
(λλ1(λ1(λλλ3)(λλλ13)))(λ1(λλλ1((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - is dropped
(λ1(λ1(λλλ3)(λλλ13)))(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))
(λ1(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)))(λ1(λλλ3)(λλλ13))(λλ1)
^^ ^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ3)(λλλ13)
(λ1(λλλ3)(λλλ13))(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))(λλ1)
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1)
(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ3)(λλλ13)(λλ1)
^ ^^^^^^ - is dropped
(λλ1((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ13)(λλ1)
^ ^ ^^^^^^^
↳ becomes λλλ13
(λ1((λλλλ1(4321))(λλλ13))((λλλλ2(4321))1))(λλ1)
^^ ^
↳ becomes (λλ1) ↳ becomes (λλ1)
(λλ1)((λλλλ1(4321))(λλλ13))((λλλλ2(4321))(λλ1))
^ ^^^^^^^^^^^^^^^^^^^^^^ - is dropped
(λ1)((λλλλ2(4321))(λλ1))
^^ ^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλλ2(4321))(λλ1)
(λλλλ2(4321))(λλ1)
^ ^ ^^^^^
↳ becomes λλ1
λλλ2((λλ1)321)
^ ^ - is dropped
λλλ2((λ1)21)
^^ ^
↳ becomes 2
λλλ2(21) // fail
这是一个微妙的问题：A 和 B 都需要将它们的元组设为 unnormalized/destructured 形式，以便 succ 和 pred与纯 β 归约评估器一起工作的定义。我注意到这一点是因为我的实现使用了规范化元组，而 Bromind 没有。
让我们看看正确的定义：
(λ(λ1(λλ1))(1(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))))(λλλ13)
及其归约步骤（又是正常顺序）：
(λ(λ1(λλ1))(1(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))))(λλλ13)
^ ^ ^^^^^^^
↳ becomes λλλ13
(λ1(λλ1))((λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))))
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))
(λλλ13)(λ1(λλλ3)(λλλ13))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^ ^ ^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ3)(λλλ13)
(λλ1(λ1(λλλ3)(λλλ13)))(λ1(λλ(λλλ132)((λλλλ2(4321))2)((λλλλ1(4321))2)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - is dropped
(λ1(λ1(λλλ3)(λλλ13)))(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))(λλ1)
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))
(λ1(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)))(λ1(λλλ3)(λλλ13))(λλ1)
^^ ^^^^^^^^^^^^^^^^^
↳ becomes λ1(λλλ3)(λλλ13)
(λ1(λλλ3)(λλλ13))(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))(λλ1)
^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
↳ becomes λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1)
(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ3)(λλλ13)(λλ1)
^ ^ ^^^^^^
↳ becomes λλλ3
(λ(λλλ132)((λλλλ1(4321))(λλλ3))((λλλλ2(4321))1))(λλλ13)(λλ1)
^ ^ ^^^^^^^
↳ becomes λλλ13
(λλλ132)((λλλλ1(4321))(λλλ3))((λλλλ2(4321))(λλλ13))(λλ1)
^ ^ ^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλλ1(4321))(λλλ3)
(λλ1((λλλλ1(4321))(λλλ3))2)((λλλλ2(4321))(λλλ13))(λλ1)
^ ^ ^^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλλ2(4321))(λλλ13)
(λ1((λλλλ1(4321))(λλλ3))((λλλλ2(4321))(λλλ13)))(λλ1)
^^ ^^^^^
↳ becomes λλ1
(λλ1)((λλλλ1(4321))(λλλ3))((λλλλ2(4321))(λλλ13))
^ ^^^^^^^^^^^^^^^^^^^^^ - is dropped
(λ1)((λλλλ2(4321))(λλλ13))
^^ ^^^^^^^^^^^^^^^^^^^^^^
↳ becomes (λλλλ2(4321))(λλλ13)
(λλλλ2(4321))(λλλ13)
^ ^ ^^^^^^^
↳ becomes λλλ13
λλλ2((λλλ13)321)
^ ^ ^
↳ becomes the right-hand side 3 and gets an index upgrade due to extra abstractions
λλλ2((λλ15)21)
^ ^
↳ gets its index downgraded
λλλ2((λ14)1)
^^ ^
↳ becomes the right-hand side 1; 4 gets an index downgrade
λλλ2(13) // aww yiss
关键区别如下：
(λλλ1((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ3)(λλλ13)(λλ1) // normalized tuple
^ ^^^^^^ - is dropped
(λλ(λλλ132)((λλλλ1(4321))2)((λλλλ2(4321))1))(λλλ3)(λλλ13)(λλ1) // unnormalized tuple
^ ^ ^^^^^^
↳ becomes λλλ3
如果 A 或 B 包含归一化元组，Z 元组中的零将被丢弃并退出游戏，因此关键步骤 π² ((λnm.[↑1 n, ↑0 m]) |0| |1|) => π² [↑1 |0|, ↑0 |1|] 可以'完全发生。
下面是 succ 的错误定义（对于纯 β 归约评估器）和正确的完整定义（包括 Z、A、B）之间的区别:
λ PI22 (1 [ZERO, ONE] (λ 1 (λ λ [SHL0 2, SHL1 2])) (λ 1 (λ λ [SHL1 2, SHL0 1]))) // wrong
λ PI22 (1 [ZERO, ONE] (λ 1 (λ λ TUPLE2 (SHL0 2) (SHL1 2))) (λ 1 (λ λ TUPLE2 (SHL1 2) (SHL0 1)))) // right
where TUPLE2 ≡ λ λ λ 1 3 2