How does the Y-combinator programmatically program a fixed point?

Question

I believe that mathematically I understand the idea of ​​Y-combinator: it returns a fixed point of a given functional F , thus f = Y(F) , where F satisfies f == F(f) .

But I do not understand how the actual calculation program does it?

Let's take a look at the javascript example provided here (the comment also adds a version of CoffeeScript that is easier to read):

 var Y = function (F) { return (function(x) { return F(function(y) { return x(x)(y); }); })(function(x) { return F(function(y) { return x(x)(y); }); }); }; var Factorial = function (factorial) { return function (n) { if (n === 0) { return 1; } else { return n * factorial(n - 1); } } }; /* Equivalent CoffeeScript: Y = (F) -> ( (x) -> F((y) -> x(x)(y)) )( (x) -> F((y) -> x(x)(y)) ) Factorial = (factorial) -> if n == 0 then 1 else n * factorial(n-1) */ Y(Factorial)(6) == 720 // => true computed_factorial = Y(Factorial) 

The part I don’t understand is how the computed_factorial (fixed point) function is actually calculated? By tracing the definition of Y, you will find that it works with infinitely recursion in the x(x) , I do not see any final case implied there. However, this is strangely coming back. Can someone explain?

Answer 1

I am going to use the syntax of the ES6 arrow function. Since you seem to know CoffeeScript, it is easy for you to read it.

Here is your Y combinator

 var Y = F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y))) 

I am going to use an improved version of your factorial tho function. Instead, a drive is used instead, which will prevent the evaluation from turning into a large pyramid. The process of this function will be linear iterative, while yours will be recursive. When ES6 finally gets the tail call eliminated, it makes an even bigger difference.

The difference in syntax is nominal. It doesn't really matter, since you just want to see how Y is evaluated.

 var factorial = Y (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1) ) (1); 

Well, that will make the computer start to do some work. So give an assessment of this before we go any further ...

I hope you have a really good marker in your text editor ...

 var factorial = Y (f=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1) // sub Y = (F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y)))) (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1) // apply F=> to fact=> = (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (1) // apply x=> to x=> = (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1) // apply fact=> to y=> = (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (1) // apply acc=> to 1 = n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1) // return value = [Function] (n=> ...) 

So you can see here after we call:

 var factorial = Y(fact=> acc=> n=> ...) (1); //=> [Function] (n=> ...) 

We get a function back that waits for one input, n . Let the factorial run now

Before continuing, you can check (and you should) that each line is correct by copying / pasting it into javascript repl. Each line will return 24 (this is the correct answer for factorial(4) . Sorry if I messed it up for you). This is similar to when you simplify fractions, solve algebraic equations, or balance chemical formulas; every step should be the right answer.

Be sure to scroll all the way to the right for my comments. I will tell you what operation I performed on each line. The result of the completed operation is on the next line.

And make sure you use this highlighter marker again ...

 factorial (4) // sub factorial = (n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1)) (4) // apply n=> to 4 = 4 < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // 4 < 2 = false ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // ?: = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // 1*4 = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (4-1) // 4-1 = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3) // apply y=> to 4 = (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (4) (3) // apply x=> to x=> = (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3) // apply fact=> to y=> = (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (4) (3) // apply acc=> to 4 = (n=> n < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*n) (n-1)) (3) // apply n=> to 3 = 3 < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // 3 < 2 = false ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // ?: = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // 4*2 = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (3-1) // 3-1 = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2) // apply y=> to 12 = (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (12) (2) // apply x=> to y=> = (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2) // apply fact=> to y=> = (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (12) (2) // apply acc=> 12 = (n=> n < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*n) (n-1)) (2) // apply n=> 2 = 2 < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // 2 < 2 = false ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // ?: = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // 12*2 = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (2-1) // 2-1 = (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1) // apply y=> to 24 = (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (24) (1) // apply x=> to x=> = (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1) // apply fact=> to y=> = (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (24) (1) // apply acc=> to 24 = (n=> n < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*n) (n-1)) (1) // apply n=> to 1 = 1 < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1) // 1 < 2 = true ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1) // ?: = 24 

---

I saw other implementations of Y Here is a simple process to create another (for use in javascript) from scratch.

 // text book var Y = f=> f (Y (f)) // prevent immediate recursion (javascript is applicative order) var Y = f=> f (x=> Y (f) (x)) // remove recursion using U combinator var Y = U (h=> f=> f (x=> h (h) (f) (x))) // given: U = f=> f (f) var Y = (h=> f=> f (x=> h (h) (f) (x))) (h=> f=> f (x=> h (h) (f) (x))) 

Answer 2

In a lazy evaluation language, Y-combinator can be defined as:

 Y = (f => (x => f( x(x) )) (x => f( x(x) ))) 

But since Javascript is an impatient evaluation language, defining Y in this way will cause the x (x) part to execute recursively while you try to apply Y to the function.

To work around this problem, you can enter an anonymous shell to delay x execution. This wrapper function will behave the same as x (x) when called, but will return immediately, as this is just a function definition.

Knowing that x (x) will be bound to a recursive function, in the case of an example:

 Factorial = f => n => n==0 ? 1 : n*f(n-1) 

We can say in advance that only one argument will be passed to him. This allows us to use the following template to create an anonymous function that behaves the same as any given function f (x):

 f => x => f(x) 

When we apply this pattern to the x (x) member, Y will no longer return indefinitely and becomes:

 Y = (f => (x => f( y => x(x)(y) )) (x => f( y => x(x)(y) ))) 

Answer 3

Y combinator is one of the most interesting phenomena in lambda calculus. I doubt that once you see it, you can come up with an interpretation of its functionality.

 Y = f => (g => g(g))(g => n => f(g(g))(n)); 

Try to understand step by step. I will use the arrow functions, so if you are not familiar with them, follow this link . They are very simple. x => x means function(x){return x;} . The JS this has different meanings within the arrows, but it does not correspond to the topic according to this subject.

So, as always, we will go with the factorial function, but the Y combinator that we deduce will be valid for all recursive functions.

The factorial function can simply be expressed as follows:

 var fa = n => n === 0 ? 1 : n*fa(n-1); fact(5) // <- 120 

But let’s say that we don’t want to refer to the fa function recursively; instead, we would like to get a working factorial function from a hypothetical version of a factorial function. What is a hypothetical factor function? A hypothetical factorial function takes the correct factorial function and returns us the actual factorial function. As below

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

So, if I pass fa function fh as an argument, it will work. How;

 fh(fa)(5); // <- 120 

But we do not want to refer to another factorial function, such as fa , since we have already defined the factorial logic in the fh function. Then we think. fh stores the argument f in closure and returns me the actual factorial function ( n => n === 0 ? 1 : n*f(n-1) ) if I pass it the corresponding factorial function, for example fa . So if I go to him; Quick try fh(fh)(5) // <- NaN meh ..!

So, we begin to play with the internal function. Normally I would go through this step, but it would be useful to see the transformations ... so let's continue. I can define a fb function to return to me a function that takes two arguments, itself and a factor counter n

 fb = (f,n) => n === 0 ? 1 : n* f(f,n-1), // fb(fb,5) <- 120 

So far so good, but the two argument functions have not been close to what I'm looking for. I can separate them by adding another functional step.

 fc = f => n => n === 0 ? 1 : n* f(f)(n-1), // fc(fc)(5) <- 120 

Now this is very close to our hypothetical function fh . But the internal manifestations of f(f)(n-1) We must correct this to show f (n-1). Well, maybe we can use JS beauty IIFE to help us ...

 fd => f => n => ((g,n) => n === 0 ? 1 : n * (g,n-1))(f(f),n) // fd(fd)(5) <- 120 

Do you see IIFE ..? ((g,n) => n === 0 ? 1 : n * g(n-1))(f(f),n) However, while this seems OK, I have to get rid of the double argument (g,n) IIFE to achieve the desired result. This will take another level of functionality.

 fe => f => n => (g => n => n === 0 ? 1 : n * g(n-1))(f(f))(n) // fe(fe)(5) <- 120 

Now we have inside g => n => n === 0 ? 1 : n * g(n-1) g => n => n === 0 ? 1 : n * g(n-1) , which is the body of our hypothetical function fh . This means that I can replace (I like this part ... just like substitution based on calculus, actually it is ...) fh in the above function, for example:

 fe => f => n => fh(f(f))(n) // fe(fe)(5) <- 120 

Time to complete it. What did I want first of all ..? I want to pass fh function (Y-combinator) and get its fixed point. Here I know that fe(fe) uses fh and returns me a valid factorial function. So, let's define a function to take our hyperactive recursive function as an argument and give us something working (fixed). IIFE to help again.

 Y = f => (g => g(g))(g => n => f(g(g))(n)); 

So this should work for anything. Let's try our Y combinator with a hypothetical Fibonacci function.

 var Y = f => (g => g(g))(g => n => f(g(g))(n)), fibH = f => n => n === 0 ? 0 : n === 1 ? 1 : f(n-2) + f(n-1), fibo = Y(fibH); console.log(fibo(10)); 

I hope everything is clear ...