Lambda 演算 beta 归约具体步骤及原因

Question

来自我最近读的一本书：

第一个：

.(..)()((.)) 此时，最外层的 lambda 绑定是不可约的，因为它没有可应用的参数。剩下的就是一次一层地进入术语，直到我们找到可以简化的东西。

下一个：

.(.)((.)) 我们可以将 lambda 绑定应用于 argument 。我们一直在寻找可以申请的条款。接下来我们可以应用的是 lambda 绑定到 lambda 项 ((.)).

我不明白。在第一节中，它说 </code> 没有适用的参数，我大概可以理解，但是在下一节中我认为 <code>z 可以绑定到 ((.)) 因为如你所见，.(.)，</code> 的主体显然有一个可以绑定的 <code>z 参数。但是书中只是忽略了头部</code>，直接将<code>n绑定到((.))。我的意思是 . 没有 n 参数，为什么要绑定它？

有人可以向我解释一下吗？

Answer 1

Lambda 表示法解析起来有点奇怪。 IMO Haskell 语法更清晰：

\z -> (\m -> \n -> m) z ((\p -> p) z)

或者，更明确

\z -> (
        (
           ( \m -> (\n -> m) )
           z
        )
        ( (\p -> p) z )
      )

第一个缩减步骤是

\z -> (
        (
           (\n -> z)
        )
        ( (\p -> p) z )
      )

或

\z -> (
        (\n -> z)
        ( (\p -> p) z )
      )

那么您确实可以绑定 ((\p -> p) z) – 不是绑定到 z，而是绑定到 n！（虽然实际上根本没有使用。）

\z -> (
        (z)
      )

或简单地 \z -> z。所以，我们仍然有那个 z lambda，正如书中所说，它是不可修正的。我们就是没有别的了！

...我不确定这是否真的是您的问题。如果是：为什么我们不首先看看我们是否可以减少 ((\p -> p) z)，那么答案是，我认为，lambda 演算本身根本没有定义它（它只是定义了您可以应用什么转换，而不是您应该应用的顺序。^{实际上我不确定关于这一点，如果我错了请纠正我})。在像 Scheme 这样的严格语言中，你确实会首先减少 ((\p -> p) z); Haskell 不会那样做，因为没有必要。无论哪种方式，这都无关紧要，因为无论如何结果都会被丢弃。

   ( \z -> (\n -> z) ((\p -> p) z) )
≡  ( \z -> (\n -> z) z )
≡  ( \z -> (\n -> z) foo )
≡  ( \z -> z )

Answer 2

关键是n从来没有在抽象中使用过。 n 仍然绑定到 ((λp.p)z)，但立即被丢弃。

λz.(λm.λn.m)(z)((λp.p)z) = λz.(λn.z)((λp.p)z)  Replacing m with z
                         = λz.z                Replacing n with ((λp.p)z)

Answer 3

使用正常的顺序评估，你可以在两个 beta 减少中得到答案

// beta reduction 1
λz.(<b>λm.</b>λn.<b>m</b>)(<b>z</b>)((λp.p)z) →β (λn.m) [m := z]
λz.(<del>λm.</del>λn.<b>z</b>)<del>(z)</del>((λp.p)z)

// beta reduction 2
λz.(<b>λn.</b>z)(<b>(λp.p)z</b>)       →β z      [n := ((λp.p)z)]
λz.<del>(λn.</del>z<del>)((λp.p)z)</del>

// result
λz.z

第二次归约可能看起来很棘手，因为 n 绑定到 ((λp.p)z) 但表达式只是 z，所以 n 被丢弃了。

使用applicative order evaluation，多了一步

// beta reduction 1
λz.(λm.λn.m)(z)((<b>λp.p</b>)<b>z</b>) →β p      [p := z]
λz.(λm.λn.m)(z)(<del>(λp.</del><b>z</b><del>)z</del>)

// beta reduction 2
λz.(<b>λm.</b>λn.<b>m</b>)(<b>z</b>)(z)       →β (λn.m) [m := z]
λz.(<del>λm.</del>λn.<b>z</b>)<del>(z)</del>(z)

// beta reduction 3
λz.(<b>λn.</b>z)(<b>z</b>)             →β z      [n := z]
λz.<del>(λn.</del>z<del>)(z)</del>

// result
λz.z

在这种情况下，无论我们使用普通顺序评估还是应用顺序评估，结果都是一样的。不同的评估策略有时会评估出不同的结果。

重要说明，在应用 λz 之前，我们在上面完成的减少步骤不会发生 （取决于实施）。在您提供的示例代码中，从未应用 λz，因此简化 λz 的术语只是为了练习，在这种情况下。

我们所做的只是证明 lambda 等效性（在两种不同的评估策略下）

λz.(λm.λn.m)(z)((λp.p)z) <=> λz.z

Lambda 演算 beta 归约具体步骤及原因

Lambda calculus beta reduction specific steps and why

haskell

lambda

functional-programming

lambda-calculus