在 JavaScript 中用 SKI 组合器表达 Y

Question

我正在摆弄 JavaScript 中的组合器，并为（希望）让 S 工作而感到自豪，当时我偶然发现维基百科说：“Y 组合器可以在 SKI 演算中表示为：Y = S (K (SII)) ( S (S (KS) K) (K (SII)))"，所以我不得不尝试：

var I = function (x) {
            return x;
        };
    
var K = function (x) {
        return function(){
            return x;}
        };

var S = function (x) {
           return function (y) {
               return function (z) {
                   return x(z)(y(z));
               }
           }
       };

var Y = S (K(S(I)(I))) (S(S(K(S))(K)) (K(S(I)(I))));

Y;    //evals to:
//function (z) {return x(z)(y(z));}

//And this (lifted from Crockford's Site):
var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});    //fails:
//RangeError: Maximum call stack size exceeded

我做错了什么？我这个表达翻译得不正确吗？我处理这件事的方式有问题吗？这还有道理吗？大多数关于这样的东西的阅读内容只会让我的大脑想要爆炸，所以这个练习对我来说主要是看看我是否理解这个符号（从而能够将其翻译成 JavaScript）。

哦，顺便说一句：是什么让我阅读和阅读的？再次摆弄的是，prototype.js 作为 Prototype.K 实现的实际上是 I 组合器。有人注意到了吗？

Answer 1

这里的问题是您使用的是严格评估的编程语言。 Y 组合器与任何其他定点组合器非常相似，只有在根据需要调用函数或“延迟求值”时才能正常工作。

我知道解决这个问题的方法（我的一位教授研究了一段时间之前），但这会让你的代码完全不可读。

下面我展示了到底发生了什么，希望您能明白为什么 JavaScript 无法处理 SKI 演算的直接实现。

---

这就是 JavaScript 计算 SKI 表达式后 Y 的样子：

var Y = function (q) {
    return (function(p){return q(p(p))})(function(p){return q(p(p))});
};

现在让我们看看如果向它提供函数 function (fac) { ... } 会发生什么。让我们调用该函数 f：

var factorial = (function(p){return f(p(p))})(function(p){return f(p(p))});

由于第一个匿名函数应用于参数，因此它将被计算为：

var factorial = f(
    (function(p){return f(p(p))})(function(p){return f(p(p))})
);

在惰性计算语言中，f 的参数现在将不加理会，f 本身就会被求值。然而，由于 JavaScript 是一种严格评估的语言（或“按值调用”），因此它想知道在实际运行该函数之前需要将什么参数传递给函数 f。那么让我们评估一下这个论点，好吗？

var factorial = f(f(
        (function(p){return f(p(p))})(function(p){return f(p(p))})
    )
);

我想现在你已经开始明白哪里出了问题，以及 Y 组合器实际上是如何工作的。无论如何，您的 JavaScript 机器都会耗尽堆栈空间，因为它正在尝试构建对 f 的无限调用堆栈。