无名称项
de Bruijn
使用自然数来表示项,而不是字母组成的名称;自然数 k
表示绑定于第 k
个 λ
层的被界定的变量(the variable bound by the k'th enclosing λ)
马世龙版《类型和程序设计语言》使用“囿”来形容这种被界定的关系
举例来说:
λx.x
表示为 λ . 0
λx.λy.x (y x)
表示为 λ.λ.1 (0 1)
λm.λn.λs.λz.m s (n z s)
表示为 λ.λ.λ.λ.3 1 (2 0 1)
(λx.(λx.x)) (λx.x)
表示为 (λ.(λ.0)) (λ.0)
无名称项也称为 de Bruijn
项;用来表示项的自然数称为 Bruijn
索引,“静态距离”也表示相同的概念
定义:设 T
是最小的集簇 {T0, T1, ...}
使得:
-
当
0 <= k < n
,k ∈ Tn
-
如果
t1 ∈ T
并且n > 0
则λ.t1 ∈ Tn-1
-
如果
t1 ∈ Tn
并且t2 ∈ Tn
则(t1 t2) ∈ Tn
Tn
的元素为至多含有 n
个自由变量的项