Expressing Y in term of SKI-Combinators in JavaScript

Question

I was fiddling with Cominators in JavaScript and was being proud of (hopefully) getting S to work when I stumbled upon Wikipedia saying: "The Y combinator can be expressed in the SKI-calculus as: Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))", so I had to try that:

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

What am I doing wrong? Am I not translating that expression correctly? Is there something wrong with how I'm going about this? Does it even make sense? Most of what's to be read about stuff like this just makes my brain want to explode, so the point of this exercise for me was mainly to see if I understood the notation (and would thus be able to translate it to JavaScript).

Oh, and, by the way: what got me reading & fiddling again was that what prototype.js implements as Prototype.K is actually the I combinator. Has anyone noticed?

Answer 1

The problem here is that you are using a strictly evaluated programming language. The Y-combinator, pretty much like any other fixed point combinator, will only work properly when your functions are called by need, or 'lazily evaluated'.

I know of a way to work around this (one of my professors looked into it a while ago), but it will make your code completely unreadable.

Below I've shown what's going on exactly, hoping you can see why JavaScript can't handle a straightforward implementation of SKI-calculus.

---

This is what Y looks like after JavaScript evaluated your SKI-expression:

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

Now let's see what happens if you feed it your function function (fac) { ... }. Let's call that function f:

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

Since the first anonymous function is applied to an argument, it will be evaluated into this:

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

In a lazily evaluated language, the argument to f would now be left alone, and f itself would be evaluated. However, because JavaScript is a strictly evaluated language (or 'call-by-value'), it wants to know what argument it needs to pass to function f before actually running that function. So let's evaluate that argument, shall we?

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

I guess now you're starting to see now where things go wrong, and how the Y-combinator actually works. In any case, your JavaScript machine will run out of stack space, because it's trying to build an infinite stack of calls to f.