non recursive lambda calculus factorial function

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.

回答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>)

回答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?