How is callCC implemented in strict functional languages?

Question

Consider the following Haskell example quux function, as well as the definition of the continuation of monad and callCC .

 instance Monad (Cont r) where return x = cont ($ x) s >>= f = cont $ \c -> runCont s $ \x -> runCont (fx) c callCC :: ((a -> Cont rb) -> Cont ra) -> Cont ra callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> ha)) h quux :: Cont r Int quux = callCC $ \k -> do let n = 5 kn return 25 

As I understand this example. The do block can be thought of as

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

And from the definition of k , which is \a -> cont $ \_ -> ha , we can see that in the above case, \x -> runCont ((\_ -> return 25) x) c is passed to the argument, which ignored with underscore. Ultimately, return 25 effectively "ignored" because the underscore argument is never used, so it is never evaluated from a lazy evaluation.

So, as far as I can tell about this callCC implementation, it fundamentally depends on a lazy assessment. How to do callCC in a strict (not lazy) functional language?

Answer 1

Not. This callcc implementation is independent of lazy evaluation. To prove this, I implement it in a strictly functional language and show that something after kn does not work at all.

The strict functional language I will use is JavaScript. Since JavaScript is not statically typed, you do not need to declare newtype . Therefore, we start by defining the return and >>= functions of the Cont monad in JavaScript. We will call these functions unit and bind respectively:

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

Next, we define callcc as follows:

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

Now we can define quux as follows:

 var quux = callcc(function (k) { var n = 5; return bind(k(n), function () { alert("Hello World!"); return unit(25); }); }); 

Note that I added alert to the second bind argument to check if it is running. Now, if you call quux(alert) , it will display 5 , but it will not display "Hello World!" . This proves that the second argument to bind never executed. Check out the demo for yourself.

Why is this happening? Go back from quux(alert) . Using beta reduction, it is equivalent to:

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

Beta, decreasing it again, becomes:

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

Further on beta reduction of bind we get:

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

Now we can see why "Hello World!" never displayed. In beta, we execute function () { alert(5); } function () { alert(5); } . It is the task of this function to call its argument, but it never happens. Because of this, execution stops and "Hello World!" never displayed. Finally:

The callcc function is independent of lazy evaluation.

The function created by callcc terminates after k is called not because of a lazy evaluation, but because the call to k breaks the chain without calling its first argument and therefore returns immediately.

This brings me back to your question:

And from the definition of k , which is \a -> cont $ \_ -> ha , we can see that in the above case, \x -> runCont ((\_ -> return 25) x) c is passed to the argument, which ignored with underscore. Ultimately, return 25 effectively "ignored" because the underscore argument is never used, so it was never evaluated from a lazy rating.

You are wrong. As you can see, k is (\a -> cont $ \_ -> ha) , and the function (\x -> runCont ((\_ -> return 25) x) c) is passed to the argument that k ignored. You were right until then. However, this does not mean that return 25 not evaluated due to lazy evaluation. It is simply not evaluated because the function (\x -> runCont ((\_ -> return 25) x) c) never called. I hope this cleared up.