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 の関数のセマンティクスが常にすべての引数を評価することです。

あなたの2番目の例では：

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

これは、条件が真の場合に 3 番目の引数を評価しないif特別な形式です。したがって、条件がであるため、3 番目の引数を評価せずに、すぐに を評価して返します。(= 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)これにより無限ループが発生します。