clojure - 教堂数字的阶乘函数

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)))))))

注释掉的版本是 Rosetta code 中的等效 fac 和 Y 函数。 .

问题 1:

我从其他地方阅读到Y-rosetta β-还原为Y-mine。在这种情况下，为什么最好使用其中一种而不是另一种？

问题2:

即使我使用Y-rosetta。当我尝试时出现 StackOverflowError

((Y-rosetta fac-mine) two)

同时

((Y-rosetta fac-rosetta) 2)

工作正常。

无保护递归发生在哪里？

我怀疑这与 clojure 中 if 形式的工作方式有关，它并不完全等同于我的 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(前任 n)))。想必您想要在这里有一个条件选择(尽管考虑到您对 is-zero 的定义，我不明白为什么这不会引发 arity 异常)。