問題タブ [y-combinator]

私は Y Combinator を研究しており、それがどのように機能するかを紙の上で理解していますが、プログラミング言語でどのように実装できるかはまだわかりません。

このページによると: http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/

Y コンビネータの導出は次のようになります。

彼はどのように拡張できY(F)ますλ x.(Y(F))(x)か？そして、彼はどのように U Combinator を使用できるのでしょうか?

Javascript と Elixir での実装は次のとおりです。

これが式: の場合Y = \f.(\x.f(x x))(\x.f(x x))、ラムダ式の f, x と上記の実装の f, x, y の関係は何ですか? x は同じ x のように見え、f は同じ f のように見えます。それでは何yですか？具体的には、ラムダx xが使用する関数にラップされるのと同等なのはなぜyですか?

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

Racket の Y コンビネータは次のとおりです。

以下は、Scheme の Y コンビネータです。

私の質問は、Scheme がapply関数を必要とするのに、Racket が必要としないのはなぜですか?

この答えは言う

1. 以下は、ラムダ計算における基本的な y コンビネータです。

   Y f = (\x -> f (x x)) (\x -> f (x x))

つまり、Clojure では次のようなものです。

2. y-Combinator の別の式を次に示します (引数のステップ 2)。

3. チューリング完全言語をエンコードしました (y-Combinator を使用したため) (引数のステップ 3)

私の質問は、y-combinator がチューリング等価性を提供するのはなぜですか? それは議論の単なる仮定だったようです。

皆さんが元気であることを願っています。Harbor で固定小数点Y コンビネータを実装していますが、問題が発生しています。Y コンビネータは、ラムダ計算によって次のように定義できます。

Y = (λh.λF.F(λ x.((h(h))(F))(x))) (λh.λF.F(λ x.((h(h))(F))(x)))

パフォーマンスの質問で、Y-combinator を使用してメモ化を適用しようとしています。私の現在の実装は次のとおりです。

基本的に、ブロック内でステートメントを使用することはできませんが、式を使用することはでき、問題なく動作します。私は無限再帰と、0から無限までの制限を回避しています。

ここまでは問題なくコンパイルできますが、外側のブロックの変数にアクセスしようとすると、Harbor に顔を蹴られてしまいます。

Y コンビネーターの実装をテストするために、フィボナッチ数列の単純な実装を適用しようとしましたが、パラメーターを受け取るGブロックを返し、パラメーターを受け取るブロックを暗黙的に返すと、使用できなくなりN、Gコンパイラーは「外側のコードブロック変数に到達できません。」

これにより、ブロックをカリー化することもできます。私の質問は、ハーバーでブロック内の外部変数にアクセスするにはどうすればよいですか?

本The little schemerでは、長さが1以下のリストのみをサポートするこの関数を見つけました。

段階的に学習し、 2以下の長さのリストのみをサポートする同様の関数を作成したいと考えています。

次のようなコードを提供して、この質問に答えないでください。

この関数は任意の長さをサポートするためです。

そして、私はすでに次のような関数を書く方法を知っています:

私の目標を達成するために。しかし、このコードは最初のスニペットから一歩離れています。

たぶん、私は変更すべきではありません：