Consider the following example in Haskell of a function quux
along with the definitions of the continuation monad and 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
As I understand this example. The do block can be thought of as
k n >>= \_ -> return 25 ==
cont $ \c -> runCont (k n) $ \x -> runCont ((\_ -> return 25) x) c
And we can see from the definition of k
which is \a -> cont $ \_ -> h a
that in the above we have \x -> runCont ((\_ -> return 25) x) c
being passed into the argument that is ignored with underscore. Ultimately the return 25
is effectively "ignored" because the underscore argument is never used so from lazy evaluation its never evaluated.
So as far as I can tell this implementation of callCC
strongly fundamentally depends on lazy evaluation. How would this callCC
be done in a strict (non-lazy) functional language?
No. This implementation of callcc
doesn't depend upon lazy evaluation. To prove this I'll implement it in a strict functional language and show that anything after k n
is not executed at all.
The strict functional language I'll be using is JavaScript. Since JavaScript is not statically typed you don't need to declare a newtype
. Hence we start by defining the return
and >>=
functions of the Cont
monad in JavaScript. We'll 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 an alert
inside the second argument to bind
to test whether or not it's executed. Now if you call quux(alert)
it will display 5
but it won't display "Hello World!"
. This proves that the second argument to bind
was never executed. See the demo for yourself.
Why does this happen? Let's start backwards from quux(alert)
. By beta reduction it's 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);
By beta reducing it again it becomes:
bind(function () {
alert(5);
}, function () {
alert("Hello World!");
return unit(25);
})(alert);
Next by the 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!"
was never displayed. By beta reduction we're executing function () { alert(5); }
. It's the job of this function to call its argument, but it never does. Because of this execution stops and "Hello World!"
is never displayed. In conclusion:
The callcc
function doesn't depend upon lazy evaluation.
The function created by callcc
terminates after k
is called not because of lazy evaluation but because calling k
breaks the chain by not calling it's first argument and hence returns immediately.
This brings me back to your question:
And we can see from the definition of
k
which is\a -> cont $ \_ -> h a
that in the above we have\x -> runCont ((\_ -> return 25) x) c
being passed into the argument that is ignored with underscore. Ultimately thereturn 25
is effectively "ignored" because the underscore argument is never used so from lazy evaluation its never evaluated.
You're mistaken. As you can see k
is (\a -> cont $ \_ -> h a)
and the function (\x -> runCont ((\_ -> return 25) x) c)
is passed into the the argument that's ignored by k
. You were correct until then. However this doesn't mean that return 25
is not evaluated because of lazy evaluation. It's simply not evaluated because the function (\x -> runCont ((\_ -> return 25) x) c)
is never called. I hope that cleared things up.