Use MonadRef to implement MonadCont

Solution 1:

(This is not yet an answer, but only some clues came up in my mind. I hope this will lead to the real answer, by myself or by someone else.)

Call-by-Value is Dual to Call-by-Name -- Philip Wadler

In the above paper the author introduced the "Dual Calculus", a typed calculus that is corresponding to the classical logic. In the last section, there is a segment says

A strategy dual to call-by-need could avoid this inefficiency by overwriting a coterm with its covalue the first time it is evaluated.

As stated in Wadler's paper, call-by-name evaluating the continuations eagerly (it returns before all values being evaluated) whilst call-by-value evaluating the continuations lazily (it only returns after all values being evaluated).

Now, take a look at the callCC' above, I believe this is an example of the dual of call-by-need in the continuation side. The strategy of the evaluation, is that provide a fake "continuation" to the function given, but cache the state at this point to call the "true" continuation later on. This is somehow like making a cache of the continuation, and so once the computation finishes we restore that continuation. But cache the evaluated value is what it mean by call-by-need.

In general I suspect, state (computation up to the current point of time) is dual to continuation (the future computation). This will explain a few phenomenons. If this is true, it is not a surprise that MonadRef (correspond to a global and polymorphic state) is dual to MoncadCont (correspond to global and polymorphic continuations), and so they can be used to implement each other.