JavaScript에서 SKI-Combinators의 용어로 Y 표현하기

Question

JavaScript로 코미네이터를 만났을 때 Wikipedia를 우연히 만났을 때 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

여기서 문제는 엄격하게 평가 된 프로그래밍 언어를 사용하고 있다는 것입니다. J-combinator는 다른 고정 소수점 결합 자와 거의 비슷하게 함수가 필요에 따라 호출되거나 '느슨하게 평가 된'경우에만 올바르게 작동합니다.

이 문제를 해결할 방법을 알고 있지만 (one of my professors looked into it a while ago) 코드를 완전히 읽을 수 없게 만듭니다.

다음은 JavaScript가 SKI 미적분의 간단한 구현을 처리 할 수없는 이유를 알기 바란다.

---

이 자바 스크립트가 SKI-식을 평가 한 후 같은 Y는 모습입니다 :

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

지금의 당신이 그것을 함수 function (fac) { ... } 공급하면 어떻게되는지 보자. 의 그 기능 f 부르 자 : 지금 f에 게으르게 평가 언어에서

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

, 인수 것 : 첫 번째 익명 함수가 인수에 적용되기 때문에

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

을, 그것은이로 평가됩니다 혼자 남겨져 f 자체가 평가됩니다. 그러나 JavaScript는 엄격하게 평가 된 언어 (또는 'call-by-value')이므로 실제로 함수를 실행하기 전에 함수 f에 전달해야하는 인수를 알아야합니다. 그 논점을 평가합시다.

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

이제는 문제가있는 곳과 Y 결합 자의 실제 작동 방식을 확인하게 될 것입니다. 어쨌든, JavaScript 기계는 스택 공간이 부족합니다. f에 무한 스택을 호출하려고하기 때문입니다.