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

A Church numeral is already embodying the recursive counting down to the base case of 0. No conditionals nor arithmetic comparisons are needed to encode this loop. The Church number n is already a loop performing n steps of an iteration:

n f x = f (f (f (... (f x) ...)))
;;      ---- n steps ----

Factorial for Church numerals, as a lambda term, is

λnf.n(λra.a(r(λgx.g(agx))))(λa.f)(λh.h)

All the lambdas are curried, i.e. functions of strictly one argument, and all applications are binary, associating to the left: λab.abc is λa.(λb.abc) and fxy is ((fx)y). This lambda expression is an optimized version of the one which encodes

FACT n f x = n G ZERO ONE f x
  WHERE
  G r a f = MULT a (r (SUCC a)) f
          = a (r (SUCC a) f)
  SUCC a   f x = f (a f x)
  MULT a b f x = a (b f) x
  ZERO     f x = x
  ONE      f x = f x

where the standard Church numerals definitions for MULT, SUCC, etc. are shown.

A Church numeral is already embodying the recursive counting down to the base case of 0. Hence the r variable name.

Passing it the additional argument lets it treat it as an accumulating variable, – hence the a variable name, – counting up while unraveling the n levels-deep applications structure created by the Church numeral itself, thus counting up from 1 to n while passing it inward:

G r a = MULT a (r (SUCC a))

FACT n f x 
 = n G ZERO ONE f x
 = G (G (G ... (G ZERO) ... )) ONE f x
 ; ---- G, n times ----
 = MULT ONE
     (MULT TWO
        (MULT THREE ...
               (MULT {n} 
                  (ZERO {n+1})) ... )) f x
 = MULT ONE
     (MULT TWO
        (MULT THREE ...
               (MULT {n} ONE) ... )) f x
 = ONE
     (MULT TWO
        (MULT THREE ...
               (MULT {n} ONE) ... ) f)  x
 = ONE
     (TWO
        (THREE ...
               ({n} (ONE f)) ... ))  x
 = ONE
     (TWO
        (THREE ...
               ({n}  f) ... ))  x
 =
   f (f (f ... (f x) ... ))

for any f and x.

The passing of f inward by MULT a b f = a (b f) moves the same f into the deepest level eventually. Thus it translates into the following, of which the original lambda expression is an optimized version, directly emplacing f at its right place:

λn.n(λraf.a(r(λgx.g(agx))f))(λaf.f)(λh.h)
;; optimized:
λnf.n(λra.a(r(λgx.g(agx))))(λa.f)(λh.h)

The optimized version works in fewer steps, like this:

G' r a = a (r (SUCC a))

FACT' n f x 
 = n G' (Kf) ONE x
 = G' (G' (G' ... (G' (Kf)) ... )) ONE x
 ; ------ G', n times ----
 = ONE (G' (......) TWO) x
 = ONE
     (TWO
        (THREE ...
               (G' (Kf) {n}) ... ))  x
 = ONE
     (TWO
        (THREE ...
               ({n} (Kf {n+1})) ... ))  x
 = ONE
     (TWO
        (THREE ...
               ({n}   f) ... ))  x
 =
   f (f (f ... (f x) ... ))

All combinators are currying lambda expressions, allowing for the pervasive omnipresent partial evaluation, e.g.

(define K (lambda (a) (lambda (b) a)))
(define MULT (lambda (a) (lambda (b)
                (lambda (f) (a (b f))))))
;; etc.

We can run it in Scheme as

(define FACT
  (lambda (n)
    (lambda (f)
      (((n (lambda (r)
             (lambda (a)
               (a (r (lambda (g)
                       (lambda (x)
                         (g ((a g) x)))))))))
        (lambda (a) f))
       (lambda (h) h)))))

(((FACT (lambda(g) (lambda (z) (g(g(g(g z)))))))
  (lambda (x) (+ x 1)))
 0)

;; => 24

Scheme is a non-currying language, hence all the parens. This is arguably much easier to follow in the curried syntax like Lambda Calculus or Combinators-based "calculators" like KRC, perhaps.

The same trick of "accumulating and passing it inward" is used in the implementation of the predecessor (i.e. decrement-by-1) function for Church numerals:

PRED n f x = n (X f) (K x) I

X f r i = i (r f)

Here the "accumulation" is not counting, but rather switching I for f once, on the very first step only, thus turning

SUCC n f x = f (f (f ... (f x) ... ))

into

PRED (SUCC n) f x =
           = I (f (f ... (f x) ... ))
           =    f (f ... (f x) ... )
           = n  f x

Same approach is used when implementing the TAIL function for the Church-encoded lists. This is not coincidental, as Church lists are right folds, and Church numerals are in effect right folds over unary encodings of arithmetic numbers, i.e. lists of unimportant, indistinguishable elements where the list's length represents the number:

churchList [a,b,c] g z 
                = g a (g b (g c z))

churchNum 3 f x = f   (f   (f   x))
  =
    churchList [(),(),()] (K f) x

As a curiosity, eliminating all variable references, the (longer) factorial lambda expression can be coded with standard combinators as

;; FACT n = n G 0 1 
FACT = CCI(CC(KI)(CCG(I)))    ;; 1, 0, G, _
     = C(C(CIG)(KI))I         ;; (((_ G) 0) 1)
     = C(C(CI(SSCB(SB)))(KI))I
;; where
   G ka = MULT a (k (SUCC a)) = Ba(k(SBa)) =
          = SB(Bk(SB))a = ... = SSCB(SB)ka 
;; where
Sabc = ac(bc)
Babc = a (bc) = S(Ka)bc
Cabc = acb    = Sa(Kb)c
Wfx  = fxx    = SfIx = CSIfx
U x  =  xx    = WIx
Kab  = a
Ia   = a
0 fx = x = SKfx = KIfx
1 fx = fx = Ifx
SUCC mfx =  f(mfx) = Bf(mf)x = SBmfx
ADD nmfx = nf(mfx) = B(nf)(mf)x = n SUCC m f x
MULT nmfx = n(mf)x = Bnmfx      = n (ADD m) 0 f x
POW bnfx = nbfx = CIbnfx        = n (MULT b) 1 f x
PRED nfx = n(Xf)(Kx)I   WHERE  X fri = i(rf)

The shorter lambda expression leads to a longer and more convoluted combinators encoding.

The combinators notation can be easier to use than the lambda notation. Consider the presentation

                                  = g(Uz) = BgUz = CBUgz
H       g  z    = g (z    z   )   = Bgzz = W(Bg)z = BWBgz
Y g = H g (H g) = g (H g (H g))   = U(Hg) = BUHg = BU(CBU)g
                                  = SHHg = WSHg = WS(BWB)g

which actually lets one see what's going on here.

Answer 2

Here's one that I did a while back

 (define fibs
  (lambda (idx)
    ((((lambda (f)
            ((lambda (x) (x x))
             (lambda (y) (f (lambda (a)
                              (lambda (b) (((y y) a) b)))))))
       (lambda (f) (lambda (s)
                     (lambda (idx)
                       (if (= idx 0)
                           ((lambda (p)
                              (p (lambda (h) (lambda (t) h)))) s)
                           ((f (((lambda (p)
                                   (p (lambda (h) (lambda (t) t)))) s)))
                            (- idx 1)))))))
      ((((lambda (f)
            ((lambda (x) (x x))
             (lambda (y) (f (lambda (a)
                              (lambda (b) (((y y) a) b)))))))
         (lambda (f) 
           (lambda (a)
             (lambda (b)
               (((lambda (h)
                   (lambda (t) (lambda (a) ((a h) t)))) a)
                (lambda () ((f b) (+ a b)))))))) 0) 1))
     idx)))  

It defines all of the fibonacci numbers (via a infinite list of church pairs, of course)

I did go even further, getting rid of if, 0, 1, +, and -, but in the end those were needed to convert back and forth from church numerals anyway. And it was getting ridiculous at that point.

Answer 3

I first wrote the solution in the untyped lambda calculus, using top-level definitions for things like zero?, true, false, etc, defined using Church encodings. This implementation assumes that multi-argument functions are curried and that functions are partially applied (like Haskell).

Church encoding natural numbers looks like:

(define 0  λf x. x)
(define 1  λf x. f x)
(define 2  λf x. f (f x))
(define 3  λf x. f (f (f x)))

Church booleans true and false are defined below

(define const  λx y. x)
(define U      λf. f f)
(define true   λt f. t)
(define false  λt f. f)
(define succ   λn f x. f (n f x))
(define 0      λf x. x)
(define *      λm n f x. m (n f) x)
(define zero?  λn. n (const false) true)
(define pred   λn f x. n (λg h. h (g f)) (const x) id)

With those pre-requisites defined, now we define the factorial function using self-application for recursion. This definition is tail-recursive.

(define !
  U (lambda loop acc n.
      zero? n -- branches wrapped in lambdas
              -- to accomodate call-by-value
       (lambda _. acc)
       (lambda _. (loop loop (* n acc) (pred n))))
       n) -- dummy argument to evaluate selected branch
    1)

From here, I cheated and performed normal order evaluation on !; this is essentially partial evaluation. For this to work, I had to remove the definition of U to prevent divergence, then add it back in after.

Here's the resulting term. It is fairly cryptic (though I would've had difficulty writing anything this short by hand, without an interpreter) so I've added comments identifying the parts I can still recognize.

(λx. x x)             -- self application
(λloop acc n.
  n (λy t f. f)       -- const false
    (λt f. t)         -- true
    (λ_. acc)         -- zero? branch
    (λ_. loop loop    -- other branch
      (λf. n (acc f))
      (λf x. n (λg h. h (g f)) (λy. x) (λx. x)))  -- pred
    n)  -- dummy argument
(λf. f) -- 1

The multiplication might be hard to spot, but it's there. Now, to test it I evaluated the term applied to 3, or (λf x. f (f (f x))). Hybrid applicative and hybrid normal evaluation both reduce to a normal term without diverging, yielding λf x. f (f (f (f (f (f x))))), or 6. Other reduction strategies either diverge (due to the self application) or don't reduce to normal form.

Answer 4

Here's mine that I coded up before when wrapping my head around the Y-Combinator.

[λ (n) 
    ;; Y combinator (specialized to two arguments)
    (([λ (rec-func)
        ([λ (procedure)
           (rec-func [λ (arg1 arg2) ((procedure procedure) arg1 arg2)])]
         [λ (procedure)
           (rec-func [λ (arg1 arg2) ((procedure procedure) arg1 arg2)])])]
    ;; The factorial function (tail recursive)
     [λ (func-arg)
           [λ (n tot)
             (if (zero? n)
                 tot
                 (func-arg (- n 1) (* n tot)))]]) 
     n 1)]

Answer 5

The one I did a couple of years ago had twice as many lines and was much harder to follow.

(lambda (n)
  ((lambda (fact) (fact fact 1 n))
   (lambda (f P n) (if (<= n 1) P (f f (* n P) (- n 1))))))

Answer 6

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 7

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.