factorial function with just lambda expression

Question

What is the most transparent and elegant factorial function you can create, on your own, using only lambda expressions?

One of my students took a Scheme class at Berkeley and was given this extra credit problem of creating the factorial function with only lambda expressions (no define, let, or other power procedures). It took me awhile to solve, and was complicated and ugly.

I am teaching Scheme now, a couple of years later, and I realized I was going to set it as a challenge for myself, and thought others might appreciate it as well.

Answer 1

Here's one (curried) version:

((lambda (x) (x x))
 (lambda (fact-gen)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((fact-gen fact-gen) (sub1 n)))))))

Tail-recursive version:

(let ((fact-gen
       (lambda (fact-gen n acc)
         (if (zero? n)
             acc
             (fact-gen fact-gen (sub1 n) (* n acc))))))
  (lambda (n) (fact-gen fact-gen n 1)))

On Church numerals:

(let* ((one (lambda (s z) (s z)))
       (add1 (lambda (n) (lambda (s z) (s (n s z)))))
       (* (lambda (a b) (lambda (s z) (a (lambda (z2) (b s z2)) z))))
       (cons (lambda (a b) (lambda (f) (f a b)))))
  (lambda (n)
    ((n (lambda (p)
          (p (lambda (count acc)
               (cons (add1 count) (* count acc)))))
        (cons one one))
     (lambda (a b) b))))

Answer 2

Here's the simplest tail-recursive version I can think of:

(lambda (n)
  (((lambda (!) (! !))
    (lambda (!)
      (lambda (n acc)
        (if (zero? n)
            acc
            ((! !) (sub1 n) (* n acc))))))
   n 1))

It's hard to get recursion in less space. The self-application has to happen somewhere, and most standalone fixpoints in a call-by-value language like Scheme have to introduce extra lambdas to avoid runaway recursion at the self-application.

Instead, my solution and Jeremiah's hide the self-application in one branch of Scheme's short-circuit if, giving the necessary recursion with far fewer characters.