recursion - 方案中教堂数字的递归

Question

根据维基百科的定义，我在教堂数字上定义了教堂数字零和其他一些标准功能，如下所示：

(define n0 (λ (f x) x))

(define newtrue
  (λ(m n) m))

(define newfalse
  (λ(m n) n))

(define iszero
  (λ(m) (m (λ(x) newfalse) newtrue)))

(define ifthenelse
  (λ(a b c) (a b c)))

使用这些，我将递归循环编写为：

(((λ(r) (λ(n) (ifthenelse (iszero n) n ((r r) n))))
   (λ(r) (λ(n) (ifthenelse (iszero n) n ((r r) n))))) n0)

现在对于n0上述参数，这应该返回n0，而不进入递归。但事实并非如此。为什么？

注 1：此递归循环与普通数字和普通函数完美配合：

(((λ(r) (λ(n) (if (= 0 n) n ((r r) n))))
   (λ(r) (λ(n) (if (= 0 n) n ((r r) n))))) 0)

这0将按原样返回。

注意 2：函数ifthenelse, iszero, newtrue,newfalse也可以自己正常工作。

Answer 1

循环的原因是 Scheme 中函数的语义是总是评估它的所有参数。

在您的第二个示例中：

(((λ(r) (λ(n) (if (= 0 n) n ((r r) n))))
   (λ(r) (λ(n) (if (= 0 n) n ((r r) n))))) 0)

您正在使用if，这是一种特殊形式，如果条件为真，则不计算第三个参数。因此，它(= 0 n)立即计算并返回0，因为条件是#true，而不计算第三个参数((r r) n)。

相反，在第一个示例中：

(((λ(r) (λ(n) (ifthenelse (iszero n) n ((r r) n))))
   (λ(r) (λ(n) (ifthenelse (iszero n) n ((r r) n))))) n0)

ifthenelse是一个函数，因此，根据 Scheme 的求值规则，它的所有参数都被求值，包括((r r) n)，这会导致无限循环。