如何减少 lambda 演算
How to reduce lambda calculus
我努力理解lambda演算，阅读精彩article。
在第8页，有一个表达式：
(λy.(x(λx.xy)))
如果我要用t、
替换最左边的(λy)
(λy.(x(λx.xy))) t
那么结果会是？
x(λx.xy)
我冒昧地将其重写为haskell语法
(\y -> x (\x-> x y))
(\y -> x (\x-> x y)) t
x (\x -> x t)
因为 y 已经绑定到输入 \y 所有 y 将被 t 代替。
编辑：如以下评论所述，如果要在何处包含自由 x，则将此范围内的绑定 x 重命名为 "fresh" 名称很重要。那是一个目前没有任何意义的名字。如果我们说
let t = \t -> x t
那么正确的替换看起来像
x (\z -> z (\t -> x t))
如 pigworker 所述，一些 z 被选择作为新鲜标识符来替换我们的绑定 x 以防止将自由 x 隐藏在 t 中。
我努力理解lambda演算，阅读精彩article。
在第8页，有一个表达式：
(λy.(x(λx.xy)))
如果我要用t、
(λy)
(λy.(x(λx.xy))) t
那么结果会是？
x(λx.xy)
我冒昧地将其重写为haskell语法
(\y -> x (\x-> x y))
(\y -> x (\x-> x y)) t
x (\x -> x t)
因为 y 已经绑定到输入 \y 所有 y 将被 t 代替。
编辑：如以下评论所述，如果要在何处包含自由 x，则将此范围内的绑定 x 重命名为 "fresh" 名称很重要。那是一个目前没有任何意义的名字。如果我们说
let t = \t -> x t
那么正确的替换看起来像
x (\z -> z (\t -> x t))
如 pigworker 所述，一些 z 被选择作为新鲜标识符来替换我们的绑定 x 以防止将自由 x 隐藏在 t 中。