7

当我偶然发现 Wikipedia 说：“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组合子。有没有人注意到？

4

1 回答 1

6

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

我知道一种解决此问题的方法（我的一位教授不久前研究过它），但它会使您的代码完全不可读。

下面我展示了到底发生了什么，希望你能明白为什么 JavaScript 不能处理 SKI 演算的简单实现。

这是YJavaScript 评估您的 SKI 表达式后的样子：

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

现在让我们看看如果你给它你的 function 会发生什么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))})
);

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

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

我想现在你开始看到哪里出了问题，以及 Y 组合器实际上是如何工作的。在任何情况下，您的 JavaScript 机器都会耗尽堆栈空间，因为它正在尝试构建对f.

于 2011-09-10T00:57:56.557 回答