BLC如何编码括号?例如,这个怎么样:
λa.λb.λc.(a ((b c) d))
需要在BLC中进行编码吗?
注:维基百科的文章并不是很有帮助,因为它使用了一个不熟悉的符号,并且只提供了一个简单的例子,其中没有括号,以及一个非常复杂的例子,很难分析。这篇论文在这方面也是类似的。
λa.λb.λc.(a ((b c) d))
需要在BLC中进行编码吗?
注:维基百科的文章并不是很有帮助,因为它使用了一个不熟悉的符号,并且只提供了一个简单的例子,其中没有括号,以及一个非常复杂的例子,很难分析。这篇论文在这方面也是类似的。
如果你指的是维基百科上讨论的基于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
,而在此编码中不需要闭括号。