爲Church數

Question

我試圖在書中描述來實現的階乘lambda表達式階乘功能Lambda-calculus, Combinators and Functional Programming

它描述的方法有：

fact = (Y)λf.λn.(((is-zero)n)one)((multiply)n)(f)(predecessor)n 
Y = λy.(λx.(y)(x)x)λx.(y)(x)x 

其中

(x)y is equivalent to (x y) and 
(x)(y)z is equivalent to (x (y x)) and 
λx.x is equivalent to (fn [x] x) 

和is-zero，one，multiply和predecessor被定義爲標準教堂數字。實際定義here。

我翻譯的是以下

(defn Y-mine [y]  ; (defn Y-rosetta [y]    
    ((fn [x] (y (x x))) ; ((fn [f] (f f))     
    (fn [x]    ;  (fn [f]      
     (y    ;  (y (fn [& args]    
     (x x)))))  ;   (apply (f f) args)))))) 

和

(def fac-mine        ; (def fac-rosetta 
    (fn [f]         ;  (fn [f] 
    (fn [n]         ;  (fn [n] 
     (is-zero n        ;   (if (zero? n) 
     one         ;   1 
     (multiply n (f (predecessor n))))))) ;   (* n (f (dec n))))))) 

註釋掉版本相當於FAC和Y功能從Rosetta code。

問題1：

我在外地讀了該Y-rosettaβ-減少了Y-mine理解。在這種情況下，爲什麼最好使用那一個呢？

問題2：

即使我使用Y-rosetta。我得到的StackOverflowError當我嘗試

((Y-rosetta fac-mine) two) 

而

((Y-rosetta fac-rosetta) 2) 

工作正常。

無保留遞歸在哪裏發生？

我懷疑這與if窗體在clojure中的工作方式有關，它與我的is-zero實現不完全等價。但我一直無法自己找到錯誤。

謝謝。

更新：

考慮到@ amalloy的回答，我改變fac-mine稍微採取懶惰的參數。我不是很熟悉clojure，所以這可能不是正確的做法。但是，基本上，我讓is-zero採用匿名零參數函數並評估返回值。

(def lazy-one (fn [] one)) 
(defn lazy-next-term [n f] 
    (fn [] 
    (multiply n (f (predecessor n))))) 

(def fac-mine      
    (fn [f]       
    (fn [n]       
     ((is-zero n     
     lazy-one      
     (lazy-next-term n f)))))) 

現在我得到一個錯誤說：

=> ((Y-rosetta fac-mine) two) 
ArityException Wrong number of args (1) passed to: core$lazy-next-term$fn clojure.lang.AFn.throwArity (AFn.java:437) 

這似乎很奇怪的考慮lazy-next-term總是調用n和f

Answer 1

的fac-mine的身體看上去錯誤：它調用(is-zero n one)爲副作用，然後無條件地撥打(multiply n (f (predecessor n)))。大概你想在這裏有條件的選擇（雖然我不明白爲什麼這不會拋出一個秩序異常，因爲你的定義爲is-zero）。