lambda - lambda 乘法如何工作？

Question

A Tutorial Introduction to the Lambda Calculus

本文介绍乘法函数

The multiplication of two numbers x and y can be computed using the following function:

(λxyz.x(yz))

The product of 2 by 2 is then:

(λxyz.x(yz))22

which reduces to

(λz.2(2z))

The reader can verify that by further reducing this expression, we can obtain the expected result 4.

我不知道如何将 (λz.2(2z)) 减少到 4。谁能告诉我这个过程？

lambda函数中的2是λsz.s(s(z))，4是λsz.s(s(s(s(z))))。

Answer 1

您可以通过应用替换来正式获得结果，就像在您引用的注释的前面示例中一样。

开始于:

2 ≡ λsz.s(s(z))

我们首先在 (λz.2(2z)) 中替换它的第二个实例(更改变量名称以避免捕获自由变量):

 (λz.2((λxy.x(x(y)))z))

等于(将 x 替换为 z):

(λz.2(λy.z(z(y))))

然后我们再次应用 2 的定义(对变量重新命名):

(λz.((λwu.w(w(u)))(λy.z(z(y))))))

等于(将 w 替换为 λy.z(z(y))):

(λz.(λu.(((λy.z(z(y)))((λy.z(z(y)))u)))))

现在我们可以在最严格的 lambda 中重复替换，将 y 替换为 u:

(λz.(λu.((λy.z(z(y)))(z(z(u))))))

最后我们可以应用最后的替换，将 y 替换为 z(z(u):

(λz.(λu.z(z(z(z(u))))))

这是 4。

作为最后的评论，请注意，考虑到数字 n 是一个具有两个参数的函数，该函数应用第一个参数 n 次到第二个。所以，(λz.2(2z)) 是应用两次函数 2z 的函数，它是应用两次 z 的函数，因此结果是对其参数应用四次 z 的函数。