Lambda 演算归约步骤
Lambda Calculus Reduction steps
我正在学习 Lambda 微积分,我一直在研究归约....任何人都可以用这个例子解释归约的类型,尤其是以最简单的方式解释 beta 归约。也不介意简单易懂的教程。
(λxyz .xyz )(λx .xx )(λx .x )x
Lambda 演算
Lambda 演算有一种螺旋式上升到很多步骤的方法,使解决问题变得乏味,而且看起来很难,但实际上并没有那么糟糕。在 lambda 演算中,只有 lambda,你能用它们做的就是替换。 Lambda 就像函数或方法 - 如果您熟悉编程,它们就是将函数作为输入并 return 新函数作为输出的函数。
lambda演算基本上有两个半过程:
1) Alpha 转换 - 如果您在内部应用两个具有相同变量名的 lambda 表达式,则将其中一个更改为新的变量名。例如 (λx.xx)(λx.x) 变成类似 (λx.xx)(λy.y) 或 (λx.xx)(λx'。 x') 还原后。结果与您开始时的结果相同,只是变量名称不同。
2) Beta 减少 - 基本上只是替换。这就是用输入调用 lambda 表达式,并得到输出的过程。 lambda 表达式就像一个函数,您可以通过在整个表达式中替换输入来调用该函数。取 (λx.xy)z,(λx.xy) 的后半部分,句点之后的所有内容,都是输出,你保留输出,但是用变量(在句点之前命名)替换提供的输入。 z
是输入,x
是参数名,xy
是输出。在输出中找到所有出现的参数,并用输入替换它们,这就是它减少的结果,所以 (λx.xy)z
=> xy
用 z
代替 x
, 即 zy
.
2.5) Eta Conversion/Eta 缩减 - 这是特殊情况缩减,我只称之为一半过程,因为它有点 Beta 缩减,有点像 技术上它不是.您可能会在维基百科或教科书中看到它被写为 "Eta-conversion converts between λx.(f x) and f whenever x does not appear free in f",这听起来确实令人困惑。如果 f 不使用 x,则真正的意思是 λx.(f x) = f。如果它实际上是完全有道理的,但最好通过一个例子来展示。考虑 (λx.(λy.yy)x),这通过 eta 减少等效于 (λy.yy),因为 f = (λy.yy),它没有一个 x ,你可以通过减少它来证明这一点,因为它会解决到 (λx.xx),这显然是同一件事。你说要专注于减少 beta,所以我不打算详细讨论 eta 转换,但很多人都在努力 on the cs theory stack exchange
关于 Beta 缩减的符号:
我将使用以下符号将提供的输入替换为输出:
(λ param . output)input
=> output [param := input]
=> result
这意味着我们在输出中替换出现的参数,这就是它减少到
示例:
(λx.xy)z
= (xy)[x:=z]
= (zy)
= zy
足够的理论,让我们来解决这个问题。 Lambda 微积分很好玩。
您提出的问题只需通过 Alpha Conversion 和 Beta Reduction 即可解决,不要被下面的过程那么长所吓倒。毫无疑问,它很长,但解决它的任何一步都非常困难。
(λxyz.xyz)(λx.xx)(λx.x)x
= (((λxyz.xyz)(λx.xx))(λx.x))x - 让我们在 "Normal Order" 中添加括号,左结合性, abc 简化为 ((ab)c),其中 b 应用于 a,c 应用于
的结果
= (((λxyz.xyz)(λx.xx))(λx.x))x - Select 嵌套最深的应用程序并首先减少它。
粗体部分缩减为:
(λxyz.xyz)(λx.xx)
= (λx.λyz.xyz)(λx.xx) - 意思相同,但我们取出第一个参数,因为我们要减少它,所以我想要它要清楚
= (λx.λyz.xyz)(λx'.x'x') - Alpha 转换,有些人坚持使用新字母,但我喜欢在末尾附加数字或 `s,无论哪种方式很好。因为两个表达式都使用参数 x 我们必须在一侧重命名它们,因为两个 X 是局部变量,所以不必表示相同的东西。
= (λyz.xyz)[x := λx'.x'x'] - 减少 beta 的符号,我们删除第一个参数,并将它在输出中的出现替换为正在出现的applied [a := b] 表示将a替换为b.
= (λyz.(λx'.x'x')yz) - 实际减少,我们用提供的 lambda 表达式替换 x 的出现。
= (λyz. ((λx'.x'x')y) z) - 又是括号的正常顺序,看,这次是另一个要减少的应用程序y 应用于 (λx'.x'x'),所以让我们现在减少它
= (λyz. ((x'x')[x' := y]) z) - 将其放入符号中以减少 beta。
= (λyz. (yy) z) - 我们将两次出现的 x'x' 换成 Ys,现在完全减少了。
将此添加回原始表达式:
(((λxyz.xyz)(λx.xx))(λx.x))x
= ((λyz.(yy)z)(λx.x))x - 这不是新的,只是把我们之前发现的放回去。
= ((λyz.(yy)z)(λx.x))x - 抓取最深的嵌套应用,它是 (λx.x) 应用于 (λyz.(yy)z)
我们再单独解决:
(λyz.(yy)z)(λx.x)
= (λy.λz.(yy)z)(λx.x) - 为了清楚起见,再次带出第一个参数。
= (λz.(yy)z)[y := (λx.x)] - 放入 beta 缩减符号,我们弹出第一个参数,并注意 Ys 将切换为 ( λx.x)
= (λz.((λx.x)(λx.x))z) - 实际的 reduction/substitution,粗体现在可以减少部分
= (λz.((x)[x := λx.x])z) - 希望你现在明白了,我们开始beta reduce (λx.x)(λx.x) 通过将其放入形式 (x)[x := λx.x]
= (λz.((λx.x))z) - 还有替换
= (λz.(λx.x)z) - 清除了过多的括号,我们发现了什么,但是另一个应用程序要处理
= (λz.(x)[x:=z]) - 弹出 x 参数,记为
= (λz.(z)) - 执行替换
= (λz.z) - 清除多余的括号
把它放回主表达式中:
((λyz.(yy)z)(λx.x))x
= ((λz.z))x - 填写我们上面证明的内容
= (λz.z)x - 清除过多的括号,现在减少到最后一个应用,x 应用于(λz.z)
= (z)[z:=x] - beta 缩减,记为符号
= (x) - 进行替换
= x - 清除多余的括号
所以,是的。答案是x
,减少了groovy.
只需将事物替换为对应的事物即可:
(λ<b>x</b>yz . <b>x</b> y z )(λx . xx )(λx . x )x
= _________________________ ~~~~~~~~~~
(λ<b>y</b>z . (λx . x x )<b>y</b> z ) (λx . x )x
= _________ ~~~~~~~~~
(λ<b>z</b> . (λx . x x )(λx . x )<b>z</b> ) x
= ___ ~~~
(λ<b>x</b> . <b>x x</b> )(λx . x )x
= ________ ________ ~~~~~~~~~
(λ<b>x</b> . <b>x</b> )(λx . x ) x
= ____ ~~~~~~~~~
(λ<b>x</b>.<b>x</b>) x
= ___ ~~~
x
但实际上,我们这里所拥有的不过是
IUIx = UIx = IIx = Ix = x
其中 Ux === xx
和 Ix === x
根据定义(因此,Ixy === xy
和 Ixyz === xyz
)。
看到了吗?这是 notation 的事情。
术语:
- reduction = Reduction 是一种计算模型,由一组确定术语向前推进的规则组成。
- alpha-equivalence = 当两个项以绑定变量的名称为模时相等,例如λx。 x === 拉姆达 x。 y 但 body 单独 x !== y 因为这些明确表示它们是不同的符号 objects...除非你作弊并做 x=y (好的似乎不存在 alpha 缩减术语)
- beta-reduction = 通过函数应用减少,即 (λx.e1) e2 = e1[ x := e2 ].
参考文献:
- beta-red 维基百科:https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B2-reduction
- 不错的测试版网站:https://prl.ccs.neu.edu/blog/2016/11/02/beta-reduction-part-1/
什么是 β 还原?
更一般地说,什么是减少? Reduction 是一种计算模型,由一组确定术语如何向前推进的规则组成。 β-reduction 是函数应用的减少。当你进行 β-reduce 时,你从函数中删除了 λ,并在其 body 中用参数替换函数的参数。更正式地说,我们可以定义 β-reduction 如下:
(λx.e1) e2 = e1[ x := e2 ]
β-还原
β-归约规则表明,形式为 {\displaystyle (\lambda x.t)s}(\lambda x.t)s 的应用归约为 {\displaystyle t[x:=s] }t[x:=s]。使用符号 {\displaystyle (\lambda x.t)s\to t[x:=s]}(\lambda x.t)s\to t[x:=s]表示 {\displaystyle (\lambda x.t)s}(\lambda x.t)s β-化简为 {\displaystyle t[x:=s]}t[x:=s]。例如,对于每个 {\displaystyle s}s,{\displaystyle (\lambda x.x)s\to x[x:=s]=s}(\lambda x.x)s\tox[x:=s]=s。这表明 {\displaystyle \lambda x.x}\lambda x.x 确实是恒等式。类似地,{\displaystyle (\lambda x.y)s\to y[x:=s]=y}(\lambda x.y)s\to y[x:=s] =y,这表明 {\displaystyle \lambda x.y}\lambda x.y 是一个常数函数。
lambda 演算可被视为函数式编程语言的理想化版本,如 Haskell 或标准 ML。在这种观点下,β-reduction 对应于一个计算步骤。可以通过额外的 β 减少重复此步骤,直到没有更多的应用程序需要减少。在此处介绍的无类型 lambda 演算中,此归约过程可能不会终止。例如,考虑术语 {\displaystyle \Omega =(\lambda x.xx)(\lambda x.xx)}\Omega =(\lambda x.xx)(\lambda x.xx)。这里 {\displaystyle (\lambda x.xx)(\lambda x.xx)\to (xx)[x:=\lambda x.xx]=(x[x:=\ lambda x.xx])(x[x:=\lambda x.xx])=(\lambda x.xx)(\lambda x.xx)}(\lambda x.xx)(\lambda x.xx)\to (xx)[x:=\lambda x.xx]=(x[x:=\lambda x.xx ])(x[x:=\lambdax.xx])=(\lambdax.xx)(\lambdax.xx)。也就是说,项在单个 β 归约中归约为自身,因此归约过程永远不会终止。
无类型 lambda 演算的另一个方面是它不区分不同类型的数据。例如,可能需要编写一个只对数字进行操作的函数。但是,在无类型 lambda 演算中,没有办法阻止函数应用于真值、字符串或其他 non-number objects.
我正在学习 Lambda 微积分,我一直在研究归约....任何人都可以用这个例子解释归约的类型,尤其是以最简单的方式解释 beta 归约。也不介意简单易懂的教程。
(λxyz .xyz )(λx .xx )(λx .x )x
Lambda 演算
Lambda 演算有一种螺旋式上升到很多步骤的方法,使解决问题变得乏味,而且看起来很难,但实际上并没有那么糟糕。在 lambda 演算中,只有 lambda,你能用它们做的就是替换。 Lambda 就像函数或方法 - 如果您熟悉编程,它们就是将函数作为输入并 return 新函数作为输出的函数。
lambda演算基本上有两个半过程:
1) Alpha 转换 - 如果您在内部应用两个具有相同变量名的 lambda 表达式,则将其中一个更改为新的变量名。例如 (λx.xx)(λx.x) 变成类似 (λx.xx)(λy.y) 或 (λx.xx)(λx'。 x') 还原后。结果与您开始时的结果相同,只是变量名称不同。
2) Beta 减少 - 基本上只是替换。这就是用输入调用 lambda 表达式,并得到输出的过程。 lambda 表达式就像一个函数,您可以通过在整个表达式中替换输入来调用该函数。取 (λx.xy)z,(λx.xy) 的后半部分,句点之后的所有内容,都是输出,你保留输出,但是用变量(在句点之前命名)替换提供的输入。 z
是输入,x
是参数名,xy
是输出。在输出中找到所有出现的参数,并用输入替换它们,这就是它减少的结果,所以 (λx.xy)z
=> xy
用 z
代替 x
, 即 zy
.
2.5) Eta Conversion/Eta 缩减 - 这是特殊情况缩减,我只称之为一半过程,因为它有点 Beta 缩减,有点像 技术上它不是.您可能会在维基百科或教科书中看到它被写为 "Eta-conversion converts between λx.(f x) and f whenever x does not appear free in f",这听起来确实令人困惑。如果 f 不使用 x,则真正的意思是 λx.(f x) = f。如果它实际上是完全有道理的,但最好通过一个例子来展示。考虑 (λx.(λy.yy)x),这通过 eta 减少等效于 (λy.yy),因为 f = (λy.yy),它没有一个 x ,你可以通过减少它来证明这一点,因为它会解决到 (λx.xx),这显然是同一件事。你说要专注于减少 beta,所以我不打算详细讨论 eta 转换,但很多人都在努力 on the cs theory stack exchange
关于 Beta 缩减的符号:
我将使用以下符号将提供的输入替换为输出:
(λ param . output)input
=> output [param := input]
=> result
这意味着我们在输出中替换出现的参数,这就是它减少到
示例:
(λx.xy)z
= (xy)[x:=z]
= (zy)
= zy
足够的理论,让我们来解决这个问题。 Lambda 微积分很好玩。
您提出的问题只需通过 Alpha Conversion 和 Beta Reduction 即可解决,不要被下面的过程那么长所吓倒。毫无疑问,它很长,但解决它的任何一步都非常困难。
(λxyz.xyz)(λx.xx)(λx.x)x
= (((λxyz.xyz)(λx.xx))(λx.x))x - 让我们在 "Normal Order" 中添加括号,左结合性, abc 简化为 ((ab)c),其中 b 应用于 a,c 应用于
的结果= (((λxyz.xyz)(λx.xx))(λx.x))x - Select 嵌套最深的应用程序并首先减少它。
粗体部分缩减为:
(λxyz.xyz)(λx.xx)
= (λx.λyz.xyz)(λx.xx) - 意思相同,但我们取出第一个参数,因为我们要减少它,所以我想要它要清楚
= (λx.λyz.xyz)(λx'.x'x') - Alpha 转换,有些人坚持使用新字母,但我喜欢在末尾附加数字或 `s,无论哪种方式很好。因为两个表达式都使用参数 x 我们必须在一侧重命名它们,因为两个 X 是局部变量,所以不必表示相同的东西。
= (λyz.xyz)[x := λx'.x'x'] - 减少 beta 的符号,我们删除第一个参数,并将它在输出中的出现替换为正在出现的applied [a := b] 表示将a替换为b.
= (λyz.(λx'.x'x')yz) - 实际减少,我们用提供的 lambda 表达式替换 x 的出现。
= (λyz. ((λx'.x'x')y) z) - 又是括号的正常顺序,看,这次是另一个要减少的应用程序y 应用于 (λx'.x'x'),所以让我们现在减少它
= (λyz. ((x'x')[x' := y]) z) - 将其放入符号中以减少 beta。
= (λyz. (yy) z) - 我们将两次出现的 x'x' 换成 Ys,现在完全减少了。
将此添加回原始表达式:
(((λxyz.xyz)(λx.xx))(λx.x))x
= ((λyz.(yy)z)(λx.x))x - 这不是新的,只是把我们之前发现的放回去。
= ((λyz.(yy)z)(λx.x))x - 抓取最深的嵌套应用,它是 (λx.x) 应用于 (λyz.(yy)z)
我们再单独解决:
(λyz.(yy)z)(λx.x)
= (λy.λz.(yy)z)(λx.x) - 为了清楚起见,再次带出第一个参数。
= (λz.(yy)z)[y := (λx.x)] - 放入 beta 缩减符号,我们弹出第一个参数,并注意 Ys 将切换为 ( λx.x)
= (λz.((λx.x)(λx.x))z) - 实际的 reduction/substitution,粗体现在可以减少部分
= (λz.((x)[x := λx.x])z) - 希望你现在明白了,我们开始beta reduce (λx.x)(λx.x) 通过将其放入形式 (x)[x := λx.x]
= (λz.((λx.x))z) - 还有替换
= (λz.(λx.x)z) - 清除了过多的括号,我们发现了什么,但是另一个应用程序要处理
= (λz.(x)[x:=z]) - 弹出 x 参数,记为
= (λz.(z)) - 执行替换
= (λz.z) - 清除多余的括号
把它放回主表达式中:
((λyz.(yy)z)(λx.x))x
= ((λz.z))x - 填写我们上面证明的内容
= (λz.z)x - 清除过多的括号,现在减少到最后一个应用,x 应用于(λz.z)
= (z)[z:=x] - beta 缩减,记为符号
= (x) - 进行替换
= x - 清除多余的括号
所以,是的。答案是x
,减少了groovy.
只需将事物替换为对应的事物即可:
(λ<b>x</b>yz . <b>x</b> y z )(λx . xx )(λx . x )x
= _________________________ ~~~~~~~~~~
(λ<b>y</b>z . (λx . x x )<b>y</b> z ) (λx . x )x
= _________ ~~~~~~~~~
(λ<b>z</b> . (λx . x x )(λx . x )<b>z</b> ) x
= ___ ~~~
(λ<b>x</b> . <b>x x</b> )(λx . x )x
= ________ ________ ~~~~~~~~~
(λ<b>x</b> . <b>x</b> )(λx . x ) x
= ____ ~~~~~~~~~
(λ<b>x</b>.<b>x</b>) x
= ___ ~~~
x
但实际上,我们这里所拥有的不过是
IUIx = UIx = IIx = Ix = x
其中 Ux === xx
和 Ix === x
根据定义(因此,Ixy === xy
和 Ixyz === xyz
)。
看到了吗?这是 notation 的事情。
术语:
- reduction = Reduction 是一种计算模型,由一组确定术语向前推进的规则组成。
- alpha-equivalence = 当两个项以绑定变量的名称为模时相等,例如λx。 x === 拉姆达 x。 y 但 body 单独 x !== y 因为这些明确表示它们是不同的符号 objects...除非你作弊并做 x=y (好的似乎不存在 alpha 缩减术语)
- beta-reduction = 通过函数应用减少,即 (λx.e1) e2 = e1[ x := e2 ].
参考文献:
- beta-red 维基百科:https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B2-reduction
- 不错的测试版网站:https://prl.ccs.neu.edu/blog/2016/11/02/beta-reduction-part-1/
什么是 β 还原? 更一般地说,什么是减少? Reduction 是一种计算模型,由一组确定术语如何向前推进的规则组成。 β-reduction 是函数应用的减少。当你进行 β-reduce 时,你从函数中删除了 λ,并在其 body 中用参数替换函数的参数。更正式地说,我们可以定义 β-reduction 如下:
(λx.e1) e2 = e1[ x := e2 ]
β-还原 β-归约规则表明,形式为 {\displaystyle (\lambda x.t)s}(\lambda x.t)s 的应用归约为 {\displaystyle t[x:=s] }t[x:=s]。使用符号 {\displaystyle (\lambda x.t)s\to t[x:=s]}(\lambda x.t)s\to t[x:=s]表示 {\displaystyle (\lambda x.t)s}(\lambda x.t)s β-化简为 {\displaystyle t[x:=s]}t[x:=s]。例如,对于每个 {\displaystyle s}s,{\displaystyle (\lambda x.x)s\to x[x:=s]=s}(\lambda x.x)s\tox[x:=s]=s。这表明 {\displaystyle \lambda x.x}\lambda x.x 确实是恒等式。类似地,{\displaystyle (\lambda x.y)s\to y[x:=s]=y}(\lambda x.y)s\to y[x:=s] =y,这表明 {\displaystyle \lambda x.y}\lambda x.y 是一个常数函数。
lambda 演算可被视为函数式编程语言的理想化版本,如 Haskell 或标准 ML。在这种观点下,β-reduction 对应于一个计算步骤。可以通过额外的 β 减少重复此步骤,直到没有更多的应用程序需要减少。在此处介绍的无类型 lambda 演算中,此归约过程可能不会终止。例如,考虑术语 {\displaystyle \Omega =(\lambda x.xx)(\lambda x.xx)}\Omega =(\lambda x.xx)(\lambda x.xx)。这里 {\displaystyle (\lambda x.xx)(\lambda x.xx)\to (xx)[x:=\lambda x.xx]=(x[x:=\ lambda x.xx])(x[x:=\lambda x.xx])=(\lambda x.xx)(\lambda x.xx)}(\lambda x.xx)(\lambda x.xx)\to (xx)[x:=\lambda x.xx]=(x[x:=\lambda x.xx ])(x[x:=\lambdax.xx])=(\lambdax.xx)(\lambdax.xx)。也就是说,项在单个 β 归约中归约为自身,因此归约过程永远不会终止。
无类型 lambda 演算的另一个方面是它不区分不同类型的数据。例如,可能需要编写一个只对数字进行操作的函数。但是,在无类型 lambda 演算中,没有办法阻止函数应用于真值、字符串或其他 non-number objects.