callCC는 엄격한 기능 언어로 어떻게 구현됩니까?

Question

하스켈에서 함수 quux의 예제와 연속 모나드의 정의 및 callCC을 고려해보십시오.

instance Monad (Cont r) where 
    return x = cont ($ x) 
    s >>= f = cont $ \c -> runCont s $ \x -> runCont (f x) c 

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a 
callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h 

quux :: Cont r Int 
quux = callCC $ \k -> do 
    let n = 5 
    k n 
    return 25 

이 예를 이해합니다. 할 일 블록은

로

k n >>= \_ -> return 25 == 
cont $ \c -> runCont (k n) $ \x -> runCont ((\_ -> return 25) x) c 

생각 될 수있다 그리고 우리는 위의 우리가 \x -> runCont ((\_ -> return 25) x) c가 밑줄로 무시 인수로 전달되는 것을 \a -> cont $ \_ -> h a입니다 k의 정의에서 볼 수 있습니다. 궁극적으로 return 25은 밑줄 인수가 사용되지 않으므로 지연 평가에서 결코 평가되지 않으므로 효과적으로 "무시"됩니다.

그래서이 구현은 callCC의 경우 기본적으로 느린 평가에 달려 있다고합니다. 이 callCC은 엄격한 (게으른) 기능적인 언어로 어떻게 작성 되었습니까?

Answer 1

아니요.이 구현은 callcc입니다. 이는 지연 평가에 의존하지 않습니다. 이를 증명하기 위해 엄격한 함수 언어로 구현하고 k n 이후의 모든 내용이 전혀 실행되지 않는다는 것을 보여줍니다.

엄격한 기능 언어는 JavaScript입니다. JavaScript가 정적으로 입력되지 않았기 때문에 newtype을 선언 할 필요가 없습니다. 따라서 return 및 >>= 기능을 자바 스크립트에서 Cont 모나드로 정의하는 것으로 시작합니다. 우리는 각각이 기능 unit 및 bind 전화 할게 :

function unit(a) { 
    return function (k) { 
     return k(a); 
    }; 
} 

function bind(m, k) { 
    return function (c) { 
     return m(function (a) { 
      return k(a)(c); 
     }); 
    }; 
} 

다음을 다음과 같이 우리가 callcc를 정의 다음과 같이

function callcc(f) { 
    return function (c) { 
     return f(function (a) { 
      return function() { 
       return c(a); 
      }; 
     })(c); 
    }; 
} 

이제 우리는 quux을 정의 할 수 있습니다

var quux = callcc(function (k) { 
    var n = 5; 

    return bind(k(n), function() { 
     alert("Hello World!"); 
     return unit(25); 
    }); 
}); 

참고하는 I 실행 여부를 테스트하기 위해 alert을 두 번째 인수에 bind에 추가했습니다. 이제 quux(alert)으로 전화하면 5이 표시되지만 "Hello World!"은 표시되지 않습니다. 이것은 bind에 대한 두 번째 인수가 절대로 실행되지 않았 음을 증명합니다. 직접 demo을 참조하십시오.

왜 이런 일이 발생합니까? quux(alert)에서 뒤로 시작합시다. bind의 베타 감소에 의해 다음

bind(function() { 
    alert(5); 
}, function() { 
    alert("Hello World!"); 
    return unit(25); 
})(alert); 

우리가 얻을 : 베타으로

(function (k) { 
    var n = 5; 

    return bind(k(n), function() { 
     alert("Hello World!"); 
     return unit(25); 
    }); 
})(function (a) { 
    return function() { 
     alert(a); 
    }; 
})(alert); 

그것이하게 다시 감소 : 베타 감소함으로써이 동등의

(function (c) { 
    return (function() { 
     alert(5); 
    })(function (a) { 
     return (function() { 
      alert("Hello World!"); 
      return unit(25); 
     })(a)(c); 
    }); 
})(alert); 

이제 우리는 볼 수 있습니다 why "Hello World!"가 표시되지 않았습니다. 베타 감소로 인해 우리는 function() { alert(5); }을 실행하고 있습니다. 인수를 호출하는 것은이 함수의 작업이지만 결코 수행되지 않습니다. 이 때문에 실행이 중지되고 "Hello World!"이 표시되지 않습니다.결론적으로 :

callcc 기능은 지연 평가에 의존하지 않습니다. k이 때문이 아니라 게으른 평가의하지만 첫 번째 인자이고, 따라서 즉시 반환 호출하지 않음으로써 k 휴식 체인을 호출하기 때문에 호출 된 후 callcc 만든

기능이 종료됩니다.

그리고 우리는 위의 우리가 \x -> runCont ((\_ -> return 25) x) c가 밑줄로 무시 인수로 전달되는 것을 \a -> cont $ \_ -> h a입니다 k의 정의에서 볼 수 있습니다

이 다시 질문에 저를 제공합니다. 궁극적으로 return 25은 밑줄 인수가 사용되지 않으므로 지연 평가에서 결코 평가되지 않으므로 효과적으로 "무시"됩니다.

실수입니다. 알 수 있듯이 k은 (\a -> cont $ \_ -> h a)이고 (\x -> runCont ((\_ -> return 25) x) c) 함수는 k에 의해 무시되는 인수로 전달됩니다. 그때까지 당신은 옳았습니다. 그러나 이것이 게으른 평가로 인해 return 25이 평가되지 않는다는 것을 의미하지는 않습니다. 함수 (\x -> runCont ((\_ -> return 25) x) c)이 호출되지 않기 때문에 단순히 평가되지 않습니다. 그 일이 끝났 으면 좋겠다.