Search code examples
haskellcontinuations

Correct terminology for continuations

I've been poking around continuations recently, and I got confused about the correct terminology. Here Gabriel Gonzalez says:

A Haskell continuation has the following type: 

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

i.e. the whole (a -> r) -> r thing is the continuation (sans the wrapping)

The wikipedia article seems to support this idea by saying

a continuation is an abstract representation of the control state of a computer program.

However, here the authors say that

Continuations are functions that represent "the remaining computation to do."

but that would only be the (a->r) part of the Cont type. And this is in line to what Eugene Ching says here:

a computation (a function) that requires a continuation function in order to fully evaluate.

We’re going to be seeing this kind of function a lot, hence, we’ll give it a more intuitive name. Let’s call them waiting functions.

I've seen another tutorial (Brian Beckman and Erik Meijer) where they call the whole thing (the waiting function) the observable and the function which is required for it to complete the observer.

  • What is the the continuation, the (a->r)->r thingy or just the (a->r) thing (sans the wrapping)?
  • Is the wording observable/observer about correct?
  • Are the citations above really contradictory, is there a common truth?
Solution

  • Fueled by reading about continuations via Andrzej Filinski's Declarative Continuations and Categorical Duality I adopt the following terminology and understanding.

    A continuation on values of a is a "black hole which accepts values of a". You can see it as a black box with one operation—you feed it a value a and then the world ends. Locally at least.

    Now let's assume we're in Haskell and I demand that you construct for me a function forall r . (a -> r) -> r. Let's say, for now, that a ~ Int and it'll look like

    f :: forall r . (Int -> r) -> r
f cont = _

    where the type hole has a context like

    r    :: Type
cont :: Int -> r
-----------------
_    :: r

    Clearly, the only way we can comply with these demands is to pass an Int into the cont function and return it after which no further computation can happen. This models the idea of "feed an Int to the continuation and then the world ends".

    So, I would call the function (a -> r) the continuation so long as it's in a context with a fixed-but-unknown r and a demand to return that r. For instance, the following is not so much of a continuation

    forall r . (a -> r) -> (r, a)

    as we're clearly allowed to pass back out more information from our failing universe than the continuation alone allows.

    On "Observable"

    I'm personally not a fan of the "observer"/"observable" terminology. In that terminology we might write

    newtype Observable a = O { observe :: forall r . (a -> r) -> r }

    so that we have observe :: Observable a -> (a -> r) -> r which ensures that exactly one a will be passed to an "observer" a -> r "observing" it. This gives a very operational view to the type above while Cont or even the scarily named Yoneda Identity explains much more declaratively what the type actually is.

    I think the point is to somehow hide the complexity of Cont behind metaphor to make it less scary for "the average programmer", but that just adds an extra layer of metaphor for behavior to leak out of. Cont and Yoneda Identity explain exactly what the type is without dressing it up.