Lambda 微积分：捕获避免替换的递归定义

Question

我花了几周时间编写了无类型 lambda 演算的实现。

我相信在这样做的过程中，我可能已经制定了一个递归定义来避免捕获替换（即它使用替换作为一种 alpha 转换形式），它非常适合维基百科上给出的替换定义。

如果有人能为我验证它的正确性，我将不胜感激，如果它是正确的，请解释为什么这个定义很少被使用，因为我发现它非常清晰和简单。

维基百科的定义：

x[x := N] ≡ N  
y[x := N] ≡ y, if x ≠ y  
(M1 M2)[x := N] ≡ (M1[x := N]) (M2[x := N])  
(λx.M)[x := N] ≡ λx.M  
(λy.M)[x := N] ≡ λy.(M[x := N]), if x ≠ y, provided y ∉ FV(N)

我的额外定义来强制避免捕获：

(λy.M)[x := N] ≡ λy'.(M'[x := N]), if x ≠ y and y ∈ FV(N)

其中

y' ∉ (FV(N) ∪ FV(M))  
M' ≡ M[y:=y']

Answer 1

你的规则是正确的。

它不经常使用，因为它需要跟踪自由变量。这确实违反直觉，因为我们都同意名称无关紧要，而在此实现中，名称起着核心作用。

您还没有展示您的操作语义。如果这样做，您会看到应用程序规则需要知道 x 是否被 N 捕获，如 (λx.M) N 中那样。如果是这样，需要触发 alpha 重命名。

这里的问题是基本的一个表达式有太多（无限）表示。解决这个问题的一种典型方法是通过 de Bruijin 索引，或者称为本地无名的混合方法。

https://en.wikipedia.org/wiki/De_Bruijn_index

https://www.chargueraud.org/research/2009/ln/main.pdf

主要思想是相同的：两者都取绑定表达式的商，这样一个表达式恰好具有一种规范形式。

Lambda 微积分：捕获避免替换的递归定义

Lambda Calculus: Recursive definition of capture avoiding substitution

lambda-calculus