Factorial function for church numbers

Question

I am trying to implement a factorial lambda expression as described in the book Lambda calculus, Combinators and functional programming

The method described here:

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

Where

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

and is-zero , one , multiply and predecessor defined for standard church numbers. Actual definitions are here .

I translated it to the next

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

and

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

The commented versions are equivalent fac and Y functions from the Rosetta code .

Question 1:

I understand that by reading elsewhere, Y-rosetta β-reduces to Y-mine . In this case, why is it preferable to use this function over another?

Question 2:

Even if I use Y-rosetta . I get a StackOverflowError when I try

 ((Y-rosetta fac-mine) two) 

a

 ((Y-rosetta fac-rosetta) 2) 

works great.

Where does unguarded recursion take place?

I suspect this is due to the way the if form works in clojure, which is not completely equivalent to my is-zero implementation. But I myself could not find the error.

Thanks.

Update:

Given @amalloy's answer, I changed fac-mine bit to accept lazy arguments. I am not very familiar with clojure, so this is probably not the case. But basically, I made is-zero use the anonymous functions of the null argument and appreciated everything that it returns.

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

Now I get the error message:

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

Which seems really strange, given that lazy-next-term always called with n and f

Answer 1

The fac-mine body does not look right: it calls (is-zero n one) for side effects, and then unconditionally calls (multiply n (f (predecessor n))) . Presumably you need a conditional choice here (although I don't understand why this does not throw an arity exception, given your definition of is-zero ).