JavaScriptでSKIコンビネータの観点からYを表現する

Question

私はJavaScriptでコミネータをいじっていて、ウィキペディアに出くわしたときに（うまくいけば）Sが機能することを誇りに思っていました。「YコンビネータはSKI計算で次のように表すことができます：Y= S（K（SII））（S（S（KS）K）（K（SII））） "なので、試してみる必要がありました： ジェネラコディセタグプレ

何が間違っているのですか？その表現を正しく翻訳していませんか？私がこれについてどうやっているのか何か問題がありますか？それも意味がありますか？このようなものについて読むべきことのほとんどは、私の脳を爆発させたくなるだけなので、この演習のポイントは、主に、表記法を理解したかどうかを確認することでした（したがって、JavaScriptに翻訳できるようになります）。

ああ、ちなみに、私がもう一度読んでいじくり回したのは、prototype.jsがPrototype.Kとして実装しているのは実際にはIコンビネーターであるということでした。誰か気づきましたか？

Answer 1

ここでの問題は、厳密に評価されたプログラミング言語を使用していることです。 Yコンビネータは、他の固定小数点コンビネータとほとんど同じように、関数が必要に応じて呼び出された場合、または「遅延評価」された場合にのみ正しく機能します。

これを回避する方法を知っています（私の教授の1人が調べました少し前）ですが、コードが完全に読めなくなります。

以下に、JavaScriptがSKI-calculusの単純な実装を処理できない理由を理解できることを願って、正確に何が起こっているかを示しました。

---

JavaScriptがSKI式を評価した後のYは次のようになります： ジェネラコディセタグプレ

次に、関数function (fac) { ... }をフィードするとどうなるか見てみましょう。その関数をfと呼びましょう： ジェネラコディセタグプレ

最初の無名関数が引数に適用されるため、次のように評価されます。 ジェネラコディセタグプレ

遅延評価された言語では、fへの引数はそのままになり、f自体が評価されます。ただし、JavaScriptは厳密に評価された言語（または「値による呼び出し」）であるため、関数を実際に実行する前に、関数fに渡す必要のある引数を知りたいと考えています。では、その議論を評価しましょう。 ジェネラコディセタグプレ

今、あなたは物事がどこでうまくいかないのか、そしてY-combinatorが実際にどのように機能するのかを見始めていると思います。いずれにせよ、JavaScriptマシンは、fへの呼び出しの無限のスタックを構築しようとしているため、スタックスペースが不足します。