Lambda 微积分函数约简步骤

Question

我正在学习Lambda 微积分。有人可以帮忙减少吗？

(λa.((aλb.λc.c)λd.λe.d))(λf.λg.f)

实际结果为λb.λc.c。但我需要解决它的步骤

我已经完成了这些步骤，但我卡住了：

(λa.((aλb.λc.c)λd.λe.d))(λf.λg.f)
(λa.(aλb.λd.λe.d))(λf.λg.f)
(λf.λg.f)(λb.λd.λe.d)
(λg.λb.λd.λe.d)

我是不是步骤错了？有什么规则我不知道吗？

Answer 1

视觉评价

仅使用文本构建步骤的可视化模型可能具有挑战性。正如另一个答案所指出的，您的 () 以一种奇怪的方式使用。我希望这个答案有帮助 -

fix parens:
<del>(λa.((a λb.λc.c) λd.λe.d)) (λf.λg.f)</del>

eval:
(λa.a (λb.λc.c) (λd.λe.d)) (λf.λg.f)
                           =========
    __________________________/
   /
(λa.a (λb.λc.c) (λd.λe.d))
    =    \         \
    |     \         \ 
    |      \         \
(λf.λg.f) (λb.λc.c) (λd.λe.d)
          =========    /
    _________/  ______/
   /           /
(λf.λg.f) (λd.λe.d)
       =     \__
       |        \
(λg.(λb.λc.c)) (λd.λe.d)
               =========
   _______________/
  /
(λg.λb.λc.c)
    =======
     /
    /
λb.λc.c

更高的直觉

顺便说一下，λb.λc.c 等同于 Church's FALSE、λa.λb.b。回到你原来的程序，给定 Church 的布尔值 -

true := λa.λb.a
false := λa.λb.b

取原表达式-

(λa.a (λb.λc.c) (λd.λe.d)) (λf.λg.f)

使用 true 和 false 重写 -

(λa.a false true) true

计算为 -

true false true

计算为 -

false

我们了解到 (λa.a false true) 为我们提供了布尔值的倒数。我们可以将其命名为 not -

true := λa.λb.a
false := λa.λb.b
not := λp.p false true

它是这样工作的-

not true //=> false
not false //=> true

Lambda 微积分函数约简步骤

Lambda Calculus Function Reduction steps

lambda-calculus