4

我正在尝试实现Lambda-calculus, Combinators and Functional Programming一书中描述的阶乘 lambda 表达式

它的描述方式是：

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是为标准教会数字定义的。实际定义在这里。

我将其翻译为以下内容

(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 代码中的等效 fac 和 Y 函数。

问题一：

我从其他地方的阅读中了解到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总是用nand调用这似乎真的很奇怪f

4

1 回答 1

1

的主体fac-mine看起来不对：它调用(is-zero n one)副作用，然后无条件调用(multiply n (f (predecessor n))). 大概你想要一个有条件的选择（虽然我不明白为什么这不会抛出一个异常，给定你的定义is-zero）。

于 2012-12-17T00:41:26.433 回答