Is there a real-world applicability for the continuation monad outside of academic use?

Question

(later visitors: two answers to this question both give excellent insight, if you are interested you should probably read them both, I could only except one as a limitation of SO)

From all discussions I find online on the continuation monad they either mention how it could be used with some trivial examples, or they explain that it is a fundamental building block, as in this article on the Mother of all monads is the continuation monad.

I wonder if there is applicability outside of this range. I mean, does it make sense to wrap a recursive function, or mutual recursion in a continuation monad? Does it aid in readability?

Here's an F# version of the continuation mode taken from this SO post:

type ContinuationMonad() =
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    member this.Return x = fun k -> k x

let cont = ContinuationMonad()

Is it merely of academic interest, for instance to help understand monads, or computation builders? Or is there some real-world applicability, added type-safety, or does it circumvent typical programming problems that are hard to solve otherwise?

I.e., the continuation monad with call/cc from Ryan Riley shows that it is complex to handle exceptions, but it doesn't explain what problem it is trying to solve and the examples don't show why it needs specifically this monad. Admittedly, I just don't understand what it does, but it may be a treasure trove!

(Note: I am not interested in understanding how the continuation monad works, I think I have a fair grasp of it, I just don't see what programming problem it solves.)

Chantey

I can't think of a good example but I think there are some cases where it simplifies CPS code used in order to use tailcalls. – Thinner

@Gustavo, if an avid F# programmer like yourselves doesn't use it in everyday code, then that may be enough proof that you can live without bothering about it. – Chantey

Well, probably like most monads, in the sense that they offer simplicity at the cost of the complexity of the initial learning curve, which is huge. However I can imagine a situation where you need to use a library which is coded in CPS style in which it would be helpful. I'm planning to move out of Either/Option error handling and migrate to double barrelled exceptions in one of my libraries, maybe I will end up using it if I have lot of chaining on these CPS functions. Why don't you add the Haskell tag? I'm sure you will get interesting answers if you do that. – Thinner

Here's an example of it, applied to FsCheck's Gen type. – Lobby

In Haskell, the Continuation monad is sometimes used to implement fast backtracking search. Also, a restricted variant of the Continuation monad called the Codensity monad is used to re-associate operations that would be inefficient if evaluated in the "default" order (a generalization of difference lists). – Cham

Yoneda is another CPS variant that can be useful in certain circumstances (namely, to collect multiple fmap operations into one, or to "upgrade" an arbitrary type to a Functor). I don't personally know how Cont and ContT are used in the wild, but that reflects the limits of my knowledge and not limits of their use. – Rerun

Answer 1

The "mother of all monads" stuff is not purely academic. Dan Piponi references Andrzej Filinski's Representing Monads, a rather good paper. The upshot of it is if your language has delimited continuations (or can mimic them with call/cc and a single piece of mutable state) then you can transparently add any monadic effect to any code. In other words, if you have delimited continuations and no other side effects, you can implement (global) mutable state or exceptions or backtracking non-determinism or cooperative concurrency. You can do each of these just by defining a few simply functions. No global transformation or anything needed. Also, you only pay for the side-effects when you use them. It turns out the Schemers were completely right about call/cc being highly expressive.

If your language doesn't have delimited continuations, you can get them via the continuation monad (or better the double-barrelled continuation monad). Of course, if you're going to write in monadic-style anyway – which is a global transformation – why not just use the desired monad from the get-go? For Haskellers, this is typically what we do, however, there are still benefits from using the continuation monad in many cases (albeit hidden away). A good example is the Maybe/Option monad which is like having exceptions except there's only one type of exception. Basically, this monad captures the pattern of returning an "error code" and checking it after each function call. And that's exactly what the typical definition does, except by "function call" I meant every (monadic) step of the computation. Suffice to say, this is pretty inefficient, especially when the vast majority of the time there is no error. If you reflect Maybe into the continuation monad though, while you have to pay the cost of the CPSed code (which GHC Haskell handles suprisingly well), you only pay to check the "error code" in places where it matters, i.e. catch statements. In Haskell, the Codensity monad than danidiaz mentioned is a better choice because the last thing Haskellers want is to make it so that arbitrary effects can be transparently interleaved in their code.

As danidiaz also mentioned, many monads are more easily or more efficiently implemented using essentially a continuation monad or some variant. Backtracking search is one example. While not the newest thing on the backtracking, one of my favorite papers that used it was Typed Logical Variables in Haskell. The techniques used in it was also used in the Wired Hardware Description Language. Also from Koen Claesson is A Poor Man's Concurrency Monad. More modern uses of the ideas in this example include: the monad for deterministic parallelism in Haskell A Monad for Deterministic Parallelism and scalable I/O managers Combining Events And Threads For Scalable Network Services. I'm sure I can find similar techniques used in Scala. If it wasn't provided, you could use a continuation monad to implement asynchronous workflows in F#. In fact, Don Syme references exactly the same papers I just referenced. If you can serialize functions but don't have continuations, you can use a continuation monad to get them and do the serialized continuation type of web programming made popular by systems like Seaside. Even without serializable continuations, you can use the pattern (essentially the same as async) to at least avoid callbacks while storing the continuations locally and only sending a key.

Ultimately, relatively few people outside of Haskellers are using monads in any capacity, and as I alluded to earlier, Haskellers tend to want to use more contcrollable monads than the continuation monad, though they do use them internally quite a bit. Nevertheless, continuation monads or continuation monad like things, particularly for asynchronous programming, are becoming less uncommon. As C#, F#, Scala, Swift, and even Java start incorporating support monadic or at least monadic-style programming, these ideas will become more broadly used. If the Node developers were more conversant with this, maybe they would have realized you could have your cake and eat it too with regards to event-driven programming.

Incomer

Thanks, Derek, for this extensive answer. I have to admit that I don't follow everything of it. While well written, I have trouble understanding what delimited continuations are, let alone double barrelled continuation monads. I may ask a follow-up question for that, though. I wonder why you say "few people outside Haskellers use monads", as monads are omnipresent, however differently named, in F# (Maybe, Either, State) and perhaps other functional languages (Scheme, Scala, Erlang?). It will take some time to digest this all, thanks though! – Chantey

Technically, call/cc by itself is not expressive. It's either delimited continuation or call/cc + set! that is expressivd. – Huxley

Answer 2

To provide a more direct F#-specific answer (even though Derek already covered that too), the continuation monad pretty much captures the core of how asynchronous workflows work.

A continuation monad is a function that, when given a continuation, eventually calls the continuation with the result (it may never call it or it may call it repeatedly too):

type Cont<'T> = ('T -> unit) -> unit

F# asynchronous computations are a bit more complex - they take continuation (in case of success), exception and cancellation continuations and also include the cancellation token. Using a slightly simplified definition, F# core library uses (see the full definition here):

type AsyncParams =
    { token : CancellationToken
      econt : exn -> unit
      ccont : exn -> unit } 

type Async<'T> = ('T -> unit) * AsyncParams -> unit

As you can see, if you ignore AsyncParams, it is pretty much the continuation monad. In F#, I think the "classical" monads are more useful as an inspiration than as a direct implementation mechanism. Here, the continuation monad provides a useful model of how to handle certain kinds of computations - and with many additional async-specific aspects, the core idea can be used to implement asynchronous computations.

I think this is quite different to how monads are used in classic academic works or in Haskell, where they tend to be used "as is" and perhaps composed in various ways to construct more complex monads that capture more complex behaviour.

This may be just my personal opinion, but I'd say that the continuation monad is not practically useful in itself, but it is a basis for some very practical ideas. (Just like lambda calculus is not really practically useful in itself, but it can be seen as an inspiration for nice practical languages!)

Wahhabi

Thanks, Tomas, this is an excellent addition to Derek's. It helps that you explain that it is a basis for more advanced implementations (where async is very close). With these signatures, I realize now that I used this in practice several times, most recently in an adaptation of the FsCheck framework into a useful unit-testing mini-framework. Understanding I wrote this makes it easier to expand on it, generalize it, embrace it, knowing the paradigms. – Chantey

Answer 3

I certainly find it easier to read a recursive function implemented using the continuation monad compared to one implemented using explicit recursion. For example, given this tree type:

type 'a Tree = 
| Node of 'a * 'a Tree * 'a Tree
| Empty

here's one way to write a bottom-up fold over a tree:

let rec fold e f t = cont {
    match t with
    | Node(a,t1,t2) ->
        let! r1 = fold e f t1
        let! r2 = fold e f t2
        return f a r1 r2
    | Empty -> return e
}

This is clearly analogous to a naïve fold:

let rec fold e f t =
    match t with
    | Node(a,t1,t2) ->
        let r1 = fold e f t1
        let r2 = fold e f t2
        f a r1 r2
    | Empty -> return e

except that the naïve fold will blow the stack when called on a deep tree because it's not tail recursive, while the fold written using the continuation monad won't. You can of course write the same thing using explicit continuations, but to my eye the amount of clutter that they add distracts from the structure of the algorithm (and putting them in place is not completely fool-proof):

let rec fold e f t k = 
    match t with
    | Node(a,t1,t2) -> 
        fold e f t1 (fun r1 ->
        fold e f t2 (fun r2 ->
        k (f r1 r2)))
    | Empty -> k e

Note that in order for this to work, you'll need to modify your definition of ContinuationMonad to include

member this.Delay f v = f () v

Geosphere

Brilliant, concise and clear. So that means that my assumption that "continuation monads magically turn recursion into tail-recursion" was wrong. They do turn it into tail-recursion. This is very helpful and means it can be quite applicable in "modern day F# programming". – Chantey