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.

Resultant

a loop starting at N that multiplies N*--N until N is 1 ? – Histone

When you say "without use of recursion", do you mean "without a fixpoint combinator"? If so, that's impossible. – Pentachlorophenol

@GradyPlayer The lambda calculus consists only of functions. There are no loops. – Edaphic

Do you get series notation? – Histone

@GradyPlayer No, you get lambdas, applications and variables. Lambda Calculus – Pentachlorophenol

@Pentachlorophenol It would be possible, because of the definition of Church Numerals – Retaretable

Answer 1

If by "without the use of recursion" you mean without general recursion and hence without fixpoints (or self applications), we can simply observe that the factorial function is primitive recursive (that is, iterative, in essence), and there is a very general and simple encoding of primitive recursion by means of iteration (provided by church numerals) and pairs. I will discuss the general case that is quite instructive. Let < M,N > be some encoding of pairs, and let fst and snd be the associated projections. For instance, you can define

<M,N> = λz. z M N
fst = λp. p (λxy.x)
snd = λp. p (λxy.y)

Suppose to have a primitive recursive definition (without parameters, for the sake of simplicity)

f(0) = a
f(x+1) = h(x,f(x))

where a and h have been already defined.

The general idea is to use an auxiliary function f', where

                       f'(x) = <x,f(x)>

So, f'(0) = < 0, a>, and given the pair p = < x,f(x) > = f'(x), we build the next pair < x+1, f(x+1) > by computing the successor on the first component and applying h to the pair of arguments (that, taking advantage of our encoding of pairs, simply amounts to pass the continuation h as input to the pair p).

Summing up,

next = λp.< succ (fst p), p h>

Finally, to compute f(n) we need to iterate n times the function next starting from < 0, a>, and then take the second component:

 f = λn. snd (n next <0,a>)

Bartie

Using the church numeral to drive the iteration is a much better answer for doing this without the effect of recursion – great answer – Amuse

Thanks. This technique was explained to me by Gerard Huet more than 30 years ago, but I am not sure about who should be credited for it. Maybe someone out there knows the answer. – Bartie

A more direct way of using the iteration built into Church numerals is λn.λf.n(λf.λn.n(f(λf.λx.n f(f x))))(λx.f)(λx.x) (due to Bertram Felgenhauer), as shown on tromp.github.io/cl/diagrams.html, – Wondering

Answer 2

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

Amuse

U f = f f won't typecheck in Haskell. – Rahal

@AaditMShah thanks – I didn't make the time to test it in ghci; just never seen Y that way ^_^ – Amuse

I prefer the definition y f = f (y f) as you can see the recursion unfold naturally as well as witness laziness in action, preventing infinite loops. Also, Yoshihiko Futamura = Futamura (Yoshihiko Futamura). I'm so meta, even this acronym. =D – Rahal

well sure, but that definition requires an existing recursion capability; making it less interesting from a perspective of adding the capability where it doesn't already exist – thanks for sharing the link; never heard of him before – Amuse

True, however you can't define a fixed point combinator in a well-typed language without some fixed point primitive because recursion depends upon eating your own tail (i.e. U f = f f). However, such an expression wouldn't type check. At least not with isorecursive types. On an unrelated note, your expression U . (. U) wouldn't type check either. – Rahal