Lambda还原

Question

我很难理解如何将lambda术语简化为正常形式。有人能帮助我理解如何减少这个lambda的表达吗？我不知道该从哪里开始。

(λx. (λa. (λx x a)) x) 20 (λx. x+3)

提前谢谢你

Answer 1

我只关注你的表情。要获得更深层次的解释，您可以阅读this question的答案。

首先，让我们考虑如何在这些表达式上解释方括号。请考虑以下表达式：

(λx. x*x) 5 => 5*5 => 25

因此，对这个表达式的计算是用方括号外的值5替换x。

现在，让我们在表达式中从左到右放置一些括号：

(((λx. ( λa. (λx. x a)) x) 20) (λx. x+3))

让我们调用(λa. (λX.xa))变量z作为简化。所以，我们会有：

(((λx. z x) 20) (λx. x+3))

这个表达式现在类似于我们的第一个例子。用值20代替x，我们将有：

((z 20) (λx. x+3))

这与以下相同：

(((λa. (λx. x a)) 20) (λx. x+3))

再一次，我们可以用20来代替

((λx. x 20) (λx. x+3))

之后，我们可以将左边的x替换为右侧的整个表达式(λx.λ)。

((λx. x+3) 20)

最后，我们可以用20代替x

((λx. x+3) 20) => 20+3 = 23