用JavaScript中的SKI-Combinators表示Y.

Question

我正在摆弄JavaScript中的Cominators,当我偶然发现维基百科说:"Y组合子可以在SKI演算中表达为:Y = S(K(SII))时,我很自豪(希望)让S上班." 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实际上是我的组合器.有人注意到了吗？

Answer 1

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

我知道一种解决这个问题的方法(我的一位教授不久前研究过它),但它会使你的代码完全不可读.

下面我已经展示了究竟发生了什么,希望你能看出为什么JavaScript无法处理SKI-calculus的直接实现.

这是Y在JavaScript评估您的SKI表达式之后的样子:

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-combinator实际上是如何工作的.在任何情况下,您的JavaScript机器都将耗尽堆栈空间,因为它正在尝试构建无限的调用堆栈f.