рекурсия для церковных числительных в схеме

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

Причина в том, что семантика функций в Схеме всегда оценивает все ее аргументы.

В вашем втором примере:

(((λ(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), и это вызывает бесконечное петля.