方案中教堂数字的递归

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 如上所述，这应该 return n0，无需递归。但事实并非如此。为什么？

注意 1：这个递归循环可以完美地处理普通数字和普通函数：

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

这 returns 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) 和 returns 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)，而这个导致无限循环。

方案中教堂数字的递归

Recursion for church numerals in scheme

recursion

scheme

lambda-calculus

church-encoding