javascript - javascript 和 Elixir 中的 Y 组合器实现

Question

我一直在研究 Y Combinator，我在纸上了解了它的工作原理，但我还不知道如何用编程语言实现它。

根据此页面:http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/

Y组合器的推导如下:

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

他如何将Y(F)展开为λ x.(Y(F))(x)？他如何使用U Combinator？

这是 Javascript 和 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

如果公式是:Y =\f.(\x.f(x x))(\x.f(x x))，那么 lambda 表达式中的 f、x 之间的关系是什么？上面实现中的 f、x、y？ x 看起来像是同一个 x，f 看起来像是同一个 f。那么y是什么？具体来说，为什么 x x 的 lambda 等价物被包装在使用 y 的函数中？

y 有点像函数的参数!？

Answer 1

Is y kind of like the arguments to the function!?

是的，完全正确。 Lambda 演算隐式 curried 。您也可以编写 \y.x x y，而不是 x x。