I've been studying the Y Combinator, and I get how it works on paper, but I don't know yet understand how it can be implemented in a programming language.
According to this page: http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/
The derivation of Y combinator goes:
Y(F) = F(Y(F))
# Of course, if we tried to use it, it would never work because the function Y immediately calls itself, leading to infinite recursion.
# Using a little λ-calculus, however, we can wrap the call to Y in a λ-term:
Y(F) = F(λ x.(Y(F))(x))
# Using another construct called the U combinator, we can eliminate the recursive call inside the Y combinator, which, with a couple more transformations gets us to:
Y = (λh.λF.F(λ x.((h(h))(F))(x))) (λh.λF.F(λ x.((h(h))(F))(x)))
How can he expand Y(F) to be λ x.(Y(F))(x)? And how can he use the U Combinator?
Here is the implementation in Javascript and Elixir:
# javascript
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);});
});
};
# elixir
defmodule Combinator do
def fix(f) do
(fn x ->
f.(fn y -> (x.(x)).(y) end)
end).(fn x ->
f.(fn y -> (x.(x)).(y) end)
end)
end
end
If this is the formula: Y = \f.(\x.f(x x))(\x.f(x x)), what is the relationship between f, x in the lambda expression, and the f, x, y in the implementation above? The x looks like it's the same x, the f looks like the same f. Then what is y? Specifically why is the lambda equivalent of x x being wrapped in a function that uses y?
Is y kind of like the arguments to the function!?
Is y kind of like the arguments to the function!?
Yes, exactly. Lambda calculus is implicitly curried. Instead of x x you might as well write \y.x x y.