Lambda微积分变量的变化及应用题
Lambda Calculus change of variable and application question
我正在学习 Haskell 我正在学习什么是抽象、替换（beta 等价）、应用、自由和绑定变量（alpha 等价），但我对解决这些练习有一些疑问，我不知道不知道我的解决方案是否正确。
进行以下替换
1. (λ x → y x x) [x:= f z]
Sol. (\x -> y x x) =>α (\w -> y w w) =>α (\w -> x w w) =>β (\w -> f z w w)
2. ((λ x → y x x) x) [y:= x]
Sol. ((\x -> y x x)x) =>α (\w -> y w w)[y:= x] = (\w -> x w w)
3. ((λ x → y x) (λ y → y x) y) [x:= f y]
Sol. aproximation, i don't know how to do it: ((\x -> y x)(\y -> y x) y) =>β
(\x -> y x)y x)[x:= f y] =>β y x [x:= f y] = y f y
4. ((λ x → λ y → y x x) y) [y:= f z]
Sol aproximation, ((\x -> (\y -> (y x x))) y) =>β ((\y -> (y x x)) y) =>α ((\y -> (y x x)) f z)
我的另一个疑问是我是否可以在 this website 上 运行 这些表达式？这是一个 Lambda 微积分计算器，但我不知道如何 运行 这些测试。
1. (λ x → y x x) [x:= f z]
Sol. (\x -> y x x) =>α (\w -> y w w) =>α (\w -> x w w) =>β (\w -> f z w w)
不，您不能重命名 y，它在 (λ x → y x x) 中是免费的。只有 bound 变量可以（一致地）进行 α 重命名。但是只有 free 变量可以被替换，并且在那个 lambda 项中没有 free x。
2. ((λ x → y x x) x) [y:= x]
Sol. ((\x -> y x x)x) =>α (\w -> y w w)[y:= x] = (\w -> x w w)
是的，将 x 替换为 y 将允许它被 λ x 捕获，因此您确实必须在 [=14] 中对 x 进行 α 重命名=] 像您一样首先使用一些新的唯一名称，但出于某种原因您已将应用程序丢弃到免费 x。你不能只省略一个术语的一部分，所以它是 ((\w -> y w w) x)[y:= x]。现在执行替换。请注意，系统不会要求您执行结果项的 β 归约，而只是替换。
我会留下另外两个。只要仔细遵守规则。如果您首先将所有绑定名称重命名为唯一名称，这很容易，即使重命名不是严格要求的，例如
((λ x → y x) (λ y → y x) y) [x:= f y] -->
((λ w → y w) (λ z → z x) y) [x:= f y]
“唯一”部分还包括替换项中使用的自由变量，这些变量可能会在以其他方式替换后被捕获（即，在替换它们的项中，没有首先执行重命名）。这就是为什么我们必须在上面的项中重命名绑定 y，因为 y 在替换项中出现自由。我们不必重命名绑定 x，但这样做更容易。
我正在学习 Haskell 我正在学习什么是抽象、替换（beta 等价）、应用、自由和绑定变量（alpha 等价），但我对解决这些练习有一些疑问，我不知道不知道我的解决方案是否正确。
进行以下替换
1. (λ x → y x x) [x:= f z]
Sol. (\x -> y x x) =>α (\w -> y w w) =>α (\w -> x w w) =>β (\w -> f z w w)
2. ((λ x → y x x) x) [y:= x]
Sol. ((\x -> y x x)x) =>α (\w -> y w w)[y:= x] = (\w -> x w w)
3. ((λ x → y x) (λ y → y x) y) [x:= f y]
Sol. aproximation, i don't know how to do it: ((\x -> y x)(\y -> y x) y) =>β
(\x -> y x)y x)[x:= f y] =>β y x [x:= f y] = y f y
4. ((λ x → λ y → y x x) y) [y:= f z]
Sol aproximation, ((\x -> (\y -> (y x x))) y) =>β ((\y -> (y x x)) y) =>α ((\y -> (y x x)) f z)
我的另一个疑问是我是否可以在 this website 上 运行 这些表达式？这是一个 Lambda 微积分计算器，但我不知道如何 运行 这些测试。
1. (λ x → y x x) [x:= f z]
Sol.(\x -> y x x) =>α (\w -> y w w) =>α (\w -> x w w) =>β (\w -> f z w w)
不，您不能重命名 y，它在 (λ x → y x x) 中是免费的。只有 bound 变量可以（一致地）进行 α 重命名。但是只有 free 变量可以被替换，并且在那个 lambda 项中没有 free x。
2. ((λ x → y x x) x) [y:= x]
Sol.((\x -> y x x)x) =>α (\w -> y w w)[y:= x] = (\w -> x w w)
是的，将 x 替换为 y 将允许它被 λ x 捕获，因此您确实必须在 [=14] 中对 x 进行 α 重命名=] 像您一样首先使用一些新的唯一名称，但出于某种原因您已将应用程序丢弃到免费 x。你不能只省略一个术语的一部分，所以它是 ((\w -> y w w) x)[y:= x]。现在执行替换。请注意，系统不会要求您执行结果项的 β 归约，而只是替换。
我会留下另外两个。只要仔细遵守规则。如果您首先将所有绑定名称重命名为唯一名称，这很容易，即使重命名不是严格要求的，例如
((λ x → y x) (λ y → y x) y) [x:= f y] -->
((λ w → y w) (λ z → z x) y) [x:= f y]
“唯一”部分还包括替换项中使用的自由变量，这些变量可能会在以其他方式替换后被捕获（即，在替换它们的项中，没有首先执行重命名）。这就是为什么我们必须在上面的项中重命名绑定 y，因为 y 在替换项中出现自由。我们不必重命名绑定 x，但这样做更容易。