二进制λ演算如何编码括号？

Question

BLC如何编码括号？例如，这个怎么样：

λa.λb.λc.(a ((b c) d))

需要在BLC中进行编码吗？

注：维基百科的文章并不是很有帮助，因为它使用了一个不熟悉的符号，并且只提供了一个简单的例子，其中没有括号，以及一个非常复杂的例子，很难分析。这篇论文在这方面也是类似的。

- MaiaVictor

Answer 1

如果你指的是维基百科上讨论的基于De Bruijn指数的二进制编码，那实际上很简单。首先需要进行De Bruijn编码，这意味着用自然数替换变量，表示变量和其λ绑定器之间的λ绑定器数量。在这种符号表示法中，

λa.λb.λc.(a ((b c) d))

变成

λλλ 3 ((2 1) d)

其中d是某个自然数，大于等于4。由于表达式中没有上限，我们无法确定它应该是哪个数字。

然后是编码本身，递归定义为：

enc(λM) = 00 + enc(M)
enc(MN) = 01 + enc(M) + enc(N)
enc(i) = 1*i + 0

其中+表示字符串连接，*表示重复。系统地应用这个规则，我们得到：

  enc(λλλ 3 ((2 1) d))
= 00 + enc(λλ 3 ((2 1) d))
= 00 + 00 + enc(λ 3 ((2 1) d))
= 00 + 00 + 00 + enc(3 ((2 1) d))
= 00 + 00 + 00 + 01 + enc(3) + enc((2 1) d)
= 00 + 00 + 00 + 01 + enc(3) + 01 + enc(2 1) + enc(d)
= 00 + 00 + 00 + 01 + enc(3) + 01 + 01 + enc(2) + enc(1) + enc(d)
= 000000011110010111010 + enc(d)

正如您所看到的，开括号被编码为01，而在此编码中不需要闭括号。

- Fred Foo

---

非常棒的答案，谢谢。所以括号不是必要的，因为01已经表示二进制应用程序。只是一个问题，这样编码数字是否最优？因为这种方式似乎很浪费。 - MaiaVictor

@Viclib：你说得对，这里使用的是一元数表示法（记数符号），对于复杂公式来说，二进制编码可能更好。不过定义会更难，我现在不打算尝试了——你需要确保它不会与表示λ和应用的比特串发生冲突。 - Fred Foo