Выражение Y в терминах SKI-комбинаторов в JavaScript - PullRequest
Новая
       87

Выражение Y в терминах SKI-комбинаторов в JavaScript

6 голосов
/ 10 сентября 2011

Я возился с Коминаторами в 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.Кто-нибудь заметил?

1 Ответ

6 голосов
/ 10 сентября 2011

Проблема в том, что вы используете строго оцененный язык программирования. Y-комбинатор, как и любой другой комбинатор с фиксированной точкой, будет работать правильно только тогда, когда ваши функции вызываются по необходимости или «лениво оцениваются».

Я знаю способ обойти это ( один из моих профессоров некоторое время назад изучил это ), но это сделает ваш код полностью нечитаемым.

Ниже я точно показал, что происходит, надеясь, что вы поймете, почему JavaScript не может выполнить простую реализацию SKI-исчисления.

Вот как 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-комбинатор. В любом случае, вашему компьютеру JavaScript не хватит места в стеке, потому что он пытается создать бесконечный стек вызовов для f.

...