non recursive lambda calculus factorial function

Question

How to write a factorial function without use of recursion using lambda calculus? Meaning just the math notation not implementation in any particular programming language.

When you say "without use of recursion", do you mean "without a fixpoint combinator"? If so, that's impossible. — sepp2k
@GradyPlayer The lambda calculus consists only of functions. There are no loops. — molbdnilo
@GradyPlayer No, you get lambdas, applications and variables. Lambda Calculus — sepp2k

Mulan Mulan · Accepted Answer · 2017-10-19T00:04:47

i didn't say anything i didn't mean

By "without the use of recursion" you must mean "without a function calling itself by name"

Anyway, let's write factorial

fact := λn. zero? n one (mult n (fact (dec n)))

Now, we don't particularly care about zero?, mult, dec, or even one in this example; you can implement those on your own – we just want to remove the bolded, by-name recursion,

... fact (dec n)

The easiest way to do this is to apply a lambda to itself – meet the U combinator

U := λf. f f

Now, we can wrap our original expression in a lambda, and apply U

fact := U (λf. λn. zero? n one (mult n (??? (dec n))))

But what do we put in place of fact ??? – Recall that f is a reference to the outer lambda itself, so in order for that to be the same case in the next "iteration", we must apply f to itself, just as U did – in fact, you can think of U as a sort of mirror, and your function can reflect back into that mirror in order to recur; only this time, without using a name ^_^

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

Yes, yes, but the even more astute will notice that you can utilize the mirror (U) directly inside the lambda, too

fact := U (λf. λn. zero? n one (mult n (U f (dec n))))

expanded without U

We know how to expand the inner – we wrote it that way the first time

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

Now expand the outer U

fact := (λf. λn. zero? n one (mult n (f f (dec n)))) (λf. λn. zero? n one (mult n (f f (dec n))))

does it work?

all church numerals represented as #N

fact := U λf. λn. zero? n #1 (mult n (U f (dec n)))

fact #4

U (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λf. f f) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λf. λn. zero? n #1 (mult n (U f (dec n))) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λn. zero? n #1 (mult n (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec n))) #4

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// (zero? #4); false; returns second argument
(mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// which is #4 * ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4))

// which is ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) #3)

// which is equivalent to...
fact #3

// so ...
(mult #4 (fact #3))

// repeating this pattern ...
(mult #4 (mult #3 (fact #2))
(mult #4 (mult #3 (mult #2 (fact #1)))
(mult #4 (mult #3 (mult #2 (mult #1 (fact #0))))
(mult #4 (mult #3 (mult #2 (mult #1 #1))))
(mult #4 (mult #3 (mult #2 #1)))
(mult #4 (mult #3 #2))
(mult #4 #6)
#24

demonstration in javascript

Go ahead and view the U combinator's power with your very own eyeballs !

const U =
  f => f (f)
  
const fact =
  U (f => n =>
    n === 0 ? 1 : n * U (f) (n - 1))
    
console.log (fact (4)) // 24

And again as a pure lambda expression

console.log (
  (f => n => n === 0 ? 1 : n * f (f) (n - 1))
    (f => n => n === 0 ? 1 : n * f (f) (n - 1))
      (4)
) // 24

mutual recursion

The above snippet demonstrates a very important property of this recursive process: it's mutually recursive. As you can see, there are actually two (albeit the same) functions driving the recursion; A calls B, B calls A – However in the case of the U combinator, there is only one function that gets applied to itself, so it does in fact enable direct recursion – the lambda does call itself using its parameter, not its name (lambdas don't have a name to call)

Y ?

Because I said so

the U combinator is a little cumbersome because it expects the user to "reflect" the function in order to recur – what if we could provide the outer lambda with a function that is the mirror itself?

U := λf. f f
Y := λg. U (λf. g (U f))

I'm gonna show you the same definition again, but on two lines just so you can see the "mirrors" and their positions

          / g, user's function
         /
        /  / outer reflection
       /  /
Y := λg. U (λf.   ...   )
                g (U f)
                 \
                  \ call g with inner reflection

So now, whenever you apply Y to any lambda (g), its parameter becomes the function to compute the lambda itself – changing fact to

fact := Y (λf. λn. zero? n one (mult n (f (dec n))))

expanding Y

Y := λg. U (λf. g (U f))             // expand inner U
Y := λg. U (λf. g (f f))             // expand outer U
Y := λg. (λf. g (f f)) (λf. g (f f))

which is the definition you see there in wikipedia; just alpha-renamed

i just had a profound discovery

Deriving Y from U above, I saw something I've never seen before - a hidden B

Y := λg. U (λf. g (U f))

B := λf. λg. λx. f (g x)

Y' := λg. U (B g U)

One of the most beautiful things I've ever seen – and it works too; not that we should have any reason to think it wouldn't...

#lang lazy

(define B (λ (f)
            (λ (g)
              (λ (x)
                (f (g x))))))

(define U (λ (f)
            (f f)))

(define Y (λ (g)
            (U ((B g) U))))

(define fact (Y (λ (f)
                  (λ (n)
                    (if (= n 0)
                        1
                        (* n (f (sub1 n))))))))

(fact 4) ;; 24

Haskellers

Have you ever seen Y expressed as?

Y = U . (. U)
  where U f = f f

non recursive lambda calculus factorial function

2 Answers