Реализация Y-комбинатора в javascript и elixir

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))Какая связь между f, x в лямбда-выражении и f, x, y в приведенной выше реализации? X выглядит так, как будто это тот же самый X, f выглядит так же, как F. Тогда что y? В частности, почему лямбда-эквивалент x x быть завернутым в функцию, которая использует y?

Является y вроде как аргументы к функции!?

Answer 1

Это что-то вроде аргументов функции!?

Да, точно. Лямбда-исчисление неявно каррируется. Вместо x x Вы могли бы также написать \y.x x y,