遞歸在方案Church數

Question

我已經定義教堂數字0，根據維基百科的定義，在教會數字的一些其他的標準功能如下：

(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是一個函數，那麼，根據計劃的評估規則，所有它的參數進行評估，包括((r r) n)，這將導致環形循環。