2

私は 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関数への引数のようなものです! ?

4

1 に答える 1

2

y は関数の引数のようなものですか!?

はい、正確に。ラムダ計算は暗黙的にカリー化されています。あなたの代わりにx x書くこともできます\y.x x y。

于 2014-09-12T09:25:56.853 に答える