11–20 of 22 posts
Is there a really clear explanation anywhere of the idea behind all this? Or is it the kind of thing where this is simple as it gets, and I just need to put in more work to get it?
Earlier quoted context omitted.
That is by far the clearest implementation of the Y-combinator I've ever seen. And I'm not even a JavaScript programmer.
Really? What about function Y(f) { var g = f(function(arg) { return g(arg); }); return g; } The inner() function from Mozilla's implementation is actually unnecessary in languages that support lexical closures.
If you just want a clear definition of a fixed-point combinator, you might as well use a non-strict language like Haskell, which doesn't require you to eta-expand g. Here's one recursive definition of fix in Haskell:
fix f = f (fix f)
Here's another one, which closer to what you gave in JavaScript (this is what you'll actually find in the Haskell standard libraries):
fix f = let x = f x in x
I don't see how it's clear there is no recursion. Perhaps my definition of recursion is overly broad? I will now proceed to demonstrate my deep ignorance. :-) [edit ... I'm not being sarcastic here ... I suspect I may be wrong on some definition or other.]
Drop the example in a debugger and you can step in until there are 7 instances of the callsite "return ((n == 0) ? 1 : (n*fact(n-1))) ;" on every other frame of the callstack.
I would describe this as the anonymous function in the Ycombinator calls the generator corecursively making a callstack proportional to the number of times you must call the generator before it finds the fixed point.
"Clearly there is no recursion, iteration, or mutation." I don't see how it's clear there is no recursion. Perhaps my definition of recursion is overly broad? I will now proceed to demonstrate my deep ignorance. :-) [edit ... I'm not being sarcastic here ... I suspect I may be wrong on some definition or other.] Drop the example in a debugger and you can step in until there are 7 instances of the callsite "return ((n…
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);});
}) ;
} ;
[...]
The Y combinator is a closed expression--it makes no
explicit reference to an outside variable or to itself.
Clearly, there is no recursion, iteration or mutation.
"Clearly there is no recursion, iteration, or mutation." I don't see how it's clear there is no recursion. Perhaps my definition of recursion is overly broad? I will now proceed to demonstrate my deep ignorance. :-) [edit ... I'm not being sarcastic here ... I suspect I may be wrong on some definition or other.] Drop the example in a debugger and you can step in until there are 7 instances of the callsite "return ((n…
Your definition of recursion is overly broad. 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);}); }) ; } ; [...] The Y combinator is a closed expression--it makes no explicit reference to an outside variable or to itself. Clearly, there is no recursion, iteration or mutation. Look at the definition of Y—there are no…
Y(F) is not recursive. (Y(F))(X) is recursive. Is that accurate?
This is absolutely fascinating, but I'm having trouble really grokking the principle behind this. I understand fixed points of mathematical functions with numbers, but my mind seems to explode in the transition to functions of functions. Is there a really clear explanation anywhere of the idea behind all this? Or is it the kind of thing where this is simple as it gets, and I just need to put in more work to get it?
This is absolutely fascinating, but I'm having trouble really grokking the principle behind this. I understand fixed points of mathematical functions with numbers, but my mind seems to explode in the transition to functions of functions. Is there a really clear explanation anywhere of the idea behind all this? Or is it the kind of thing where this is simple as it gets, and I just need to put in more work to get it?
First of all, the Y-combinator is a function of a function of a function (of a number), so we're three levels deep, which is part of what causes the head-spinning, I think. So ignore the Y-combinator for the moment.
Simply consider the function of a function (of a number) F:
F = function (f) {
return function(n) {
return (n == 0) ? 1 : (n*f(n - 1)); };
};
We can pass whatever functions from numbers to numbers we want to F to make new functions from numbers to numbers.
E.g., we could pass in
exf1 = function(n) { return n };
F(exf1) = function(n) { return (n == 0) ? 1 : (n*(n - 1)) };
exf2 = function(n) { return 1; }
F(exf2) = function(n) { (n == 0) 1 : n - 1 };
fact: number -> number
fact(n) = n*(n - 1)*...*1
F(fact) = function(n) { return n == 0 ? 1 : n*fact(n - 1) }
Now consider the Y combinator. We know the Y combinator gives us a fixed point of a functional, i.e.,
F(Y(F)) = Y(F)
Y: functional -> function
Y: (function -> function) -> function
Y: ((number -> number) -> (number -> number)) -> (number -> number))
The article makes the claim that there is only one fixed point of F, which means Y(f) must actually be fact, but to be honest, I'm not sure why we know there can't be other fixed points of F which Y(F) might give us (though maybe this is obvious and I'm being stupid :).
But anyway we can tell by tracing through the definition of Y that it we really do get Y(F) = fact.
This is absolutely fascinating, but I'm having trouble really grokking the principle behind this. I understand fixed points of mathematical functions with numbers, but my mind seems to explode in the transition to functions of functions. Is there a really clear explanation anywhere of the idea behind all this? Or is it the kind of thing where this is simple as it gets, and I just need to put in more work to get it?
I don't know if these ramblings will help, but here are some thoughts :) First of all, the Y-combinator is a function of a function of a function (of a number), so we're three levels deep, which is part of what causes the head-spinning, I think. So ignore the Y-combinator for the moment. Simply consider the function of a function (of a number) F: F = function (f) { return function(n) { return (n == 0) ? 1 : (n*f(n -…
This is absolutely fascinating, but I'm having trouble really grokking the principle behind this. I understand fixed points of mathematical functions with numbers, but my mind seems to explode in the transition to functions of functions. Is there a really clear explanation anywhere of the idea behind all this? Or is it the kind of thing where this is simple as it gets, and I just need to put in more work to get it?
I don't know if these ramblings will help, but here are some thoughts :) First of all, the Y-combinator is a function of a function of a function (of a number), so we're three levels deep, which is part of what causes the head-spinning, I think. So ignore the Y-combinator for the moment. Simply consider the function of a function (of a number) F: F = function (f) { return function(n) { return (n == 0) ? 1 : (n*f(n -…