Deriving the Fix point combinator Y in Javascript

Try it in JsFiddle Source

Y combinator is one of the most remarkable concepts in computer science.The Y combinator, discovered by Haskell B. Curry, in order to represent recursion in lambda calculus.

Fixed-point combinator is about creating recursion without self-reference . like below at a positive Quine type sentence

If you write the following quote twice, the second time inside quotes, the resulting sentence is true: “If you write the following quote twice, the second time inside quotes, the resulting sentence is true:”

No self-reference, we have instructions about how to construct a sentence and then do something with it. And the sentence that gets constructed is equal to the instructions. if we analyze this we have GG where G x is the instructions to construct xx and do something to it.

Gx=f(xx) So G is λx.f(xx) and we have

GG=(λx.f(xx))(λx.f(xx))

This is for a fixed f we can abstract f with λf and we get

Y=λf.(MM)=λf.((λx.f(xx))(λx.f(xx))

lets do that in Javascript now. Lets start with the recursive definition of factorial :

var fact = n => n == 0 ? 1 : n * fact(n — 1);

As usual we can remove the recursion by allow the function at the left part to be different from the definition on the right part.

var factF = f => n => n == 0 ? 1 : n * f(n — 1);       (!)

We will try to refactor this definition in order to separate the recursion aspect by finding a Y combinator that we can apply to factF and the following will hold :

Y(factF)=factF (Y(factF)).

this means that Y(factF) will be the fix point of the factF. Which means that if we call Y(factF)= fact then the following will hold :

fact= factF(fact)=n=>n==0?1 : n *fact (n-1)

think about this for some time. So we actually get the initial recursive definition of the factorial.

Y(f => n => n == 0 ? 1 : n * f(n — 1))  //= fact

Here we have added a new parameter f and we got a higher order Functional definition. In this definition we could for example get different functions if we plug in different f Let’s try the simplest one let’s say var f = (x) =>1

If we replace this in factF definition, we get this function

var factF1 = n => n == 0? 1: n;

we can replace f with the identity var f = (x) => x then we will get this definition :

var factF1 = n => n == 0? 1: n * (n-1);

we imagine that there must be a special function ffix that when we give it as a parameter to our factF, and this will get us the correct result of the factorial. The way to find this function ffix is thought the magic Y combinator.

First we replace g(g) inside the functional. Now the type is different and now we can actually give as a function the Factorial itself !!! we have a sense that this might give us the correct result. And it does.

var factF2 = g => n => n == 0 ? 1 : n * g(g)(n — 1);
 factF2(factF2)(7) ;

then we can abstract the g(g) by writing it like this:

(f =>______(f) ____)( n=>g(g)n ) thats a lambda abstraction is like putting a placeholder at a position

var factF = g => (f=> n => n == 0 ? 1 : n * f(n — 1))(n => g(g)(n));

Now we also want to remove the double call factF(factF)(7)

we can write this instead

var h = f=>(f(f)); 
(h(factF )(7))

Lets inline in the last equation (h(factF )(7)) the factF from above

(f=>(f(f)))( g => (f=> n => n == 0 ? 1 : n * f(n — 1))(n => g(g)(n)));

Now we must extract abstract the f=> n => n == 0? 1: n * f (n — 1) from this last one

var Y = (u =>(f => (f(f)))(g => (u)(n => g(g)(n)))) 

so now we can apply the Y on the functional and get the factorial

Y(f => n => n == 0 ? 1 : n * f(n — 1))(7)

That was the extraction of the Y combinator step by step. It seems like a complex concept but if you do it once then it becomes a bit clearer.
Hopefully this fix point combinator resembles the lambda calculus Y combinator. Y =λ.f(λ.x(f(x x))λ.x(f(x x)))