Portability  Nonportable (rank2 types, multiparameter type classes, functional dependencies) 

Stability  Experimental 
Maintainer  Dan Doel 
A monadic treatment of delimited continuations.
Adapted from the paper A Monadic Framework for Delimited Continuations, by R. Kent Dybvig, Simon Peyton Jones and Amr Sabry (http://www.cs.indiana.edu/~sabry/papers/monadicDC.pdf)
This module implements the delimited continuation monad and transformer, using the sequenceofframes implementation from the original paper.
 data CC ans a
 runCC :: (forall ans. CC ans a) > a
 data CCT ans m a
 runCCT :: Monad m => (forall ans. CCT ans m a) > m a
 data SubCont ans m a b
 data Prompt ans a
 class Monad m => MonadDelimitedCont p s m  m > p s where
 newPrompt :: m (p a)
 pushPrompt :: p a > m a > m a
 withSubCont :: p b > (s a b > m b) > m a
 pushSubCont :: s a b > m a > m b
 reset :: MonadDelimitedCont p s m => (p a > m a) > m a
 shift :: MonadDelimitedCont p s m => p b > ((m a > m b) > m b) > m a
 control :: MonadDelimitedCont p s m => p b > ((m a > m b) > m b) > m a
 shift0 :: MonadDelimitedCont p s m => p b > ((m a > m b) > m b) > m a
 control0 :: MonadDelimitedCont p s m => p b > ((m a > m b) > m b) > m a
 abort :: MonadDelimitedCont p s m => p b > m b > m a
The CC monad
The CC monad may be used to execute computations with delimited control.
The CCT monad transformer
The CCT monad transformer allows you to layer delimited control effects over an arbitrary monad.
The CCT transformer is parameterized by the following types
 ans : A region parameter, so that prompts and subcontinuations may only be used in the same region they are created.
 m : the underlying monad
 a : The contained value. A value of type CCT ans m a can be though
of as a computation that calls its continuation with a value of
type
a
MonadReader r m => MonadReader r (CCT ans m)  
MonadState s m => MonadState s (CCT ans m)  
MonadTrans (CCT ans)  
Monad m => MonadDelimitedCont (Prompt ans) (SubCont ans m) (CCT ans m)  
Monad m => Monad (CCT ans m)  
Monad m => Functor (CCT ans m)  
Monad m => Applicative (CCT ans m)  
MonadIO m => MonadIO (CCT ans m) 
runCCT :: Monad m => (forall ans. CCT ans m a) > m aSource
Executes a CCT computation, yielding a value in the underlying monad
MonadDelimitedCont (Prompt ans) (SubCont ans Identity) (CC ans)  
Monad m => MonadDelimitedCont (Prompt ans) (SubCont ans m) (CCT ans m) 
The prompt type, parameterized by two types: * ans : The region identifier, used to ensure that prompts are only used within the same context in which they are created.
 a : The type of values that may be returned
through
a given prompt. For instance, only prompts of type 'Prompt r a' may be pushed onto a computation of type 'CC r a'.
MonadDelimitedCont (Prompt ans) (SubCont ans Identity) (CC ans)  
Monad m => MonadDelimitedCont (Prompt ans) (SubCont ans m) (CCT ans m) 
class Monad m => MonadDelimitedCont p s m  m > p s whereSource
A typeclass for monads that support delimited control operators. The type varibles represent the following:
m : The monad itself
p : The associated type of prompts that may delimit computations in the monad
s : The associated type of subcontinuations that may be captured
Creates a new, unique prompt.
pushPrompt :: p a > m a > m aSource
Delimits a computation with a given prompt.
withSubCont :: p b > (s a b > m b) > m aSource
Abortively capture the subcontinuation delimited by the given prompt, and call the given function with it. The prompt does not appear delimiting the subcontinuation, nor the resulting computation.
pushSubCont :: s a b > m a > m bSource
Pushes a subcontinuation, reinstating it as part of the continuation.
MonadDelimitedCont (Prompt ans) (SubCont ans Identity) (CC ans)  
Monad m => MonadDelimitedCont (Prompt ans) (SubCont ans m) (CCT ans m) 
Assorted useful control operators
reset :: MonadDelimitedCont p s m => (p a > m a) > m aSource
An approximation of the traditional reset operator. Creates a new prompt, calls the given function with it, and delimits the resulting computation with said prompt.
shift :: MonadDelimitedCont p s m => p b > ((m a > m b) > m b) > m aSource
The traditional shift counterpart to the above reset
. Reifies the
subcontinuation into a function, keeping both the subcontinuation, and
the resulting computation delimited by the given prompt.
control :: MonadDelimitedCont p s m => p b > ((m a > m b) > m b) > m aSource
The control operator, traditionally the counterpart of prompt. It does
not delimit the reified subcontinuation, so control effects therein can
escape. The corresponding prompt is performed equally well by reset
above.
shift0 :: MonadDelimitedCont p s m => p b > ((m a > m b) > m b) > m aSource
Abortively captures the current subcontinuation, delimiting it in a reified function. The resulting computation, however, is undelimited.
control0 :: MonadDelimitedCont p s m => p b > ((m a > m b) > m b) > m aSource
Abortively captures the current subcontinuation, delimiting neither it nor the resulting computation.
abort :: MonadDelimitedCont p s m => p b > m b > m aSource
Aborts the current continuation up to the given prompt.
Examples
This module provides many different control operators, so hopefully the
examples herein can help in selecting the right ones. The most raw are the
four contained in the MonadDelimitedCont
type class. The first, of course,
is newPrompt
, which should be straight forward enough. Next comes
pushPromp
t, which is the basic operation that delimits a computation.
In the absense of other control operators, it's simply a noop, so
pushPrompt p (return v) == return v
withSubCont
is the primitive that allows the capture of subcontinuations.
Unlike callCC, withSubCont
aborts the delimited continuation it captures,
so:
pushPrompt p ((1:) `liftM` (2:) `liftM` withSubCont p (\k > return []))
will yield a value of [] on running, not [1, 2].
The final primitive control operator is pushSubCont
, which allows the use
of the subcontinuations captured using withSubCont
. So:
pushPrompt p ((1:) `liftM1 (2:) `liftM` withSubCont p (\k > pushSubCont k (return [])))
will yield the answer [1, 2]. However, Capturing a subcontinuation and immediately pusshing it is not a noop, because the subcontinuation does not contain the delimiting prompt (and, of course, pushSubCont does not reinstate it, as it doesn't know what prompt was originally used). Thus, capturing and pushing a subcontinuation results in the net loss of one delimiter, and said delimiter will need to be repushed to negate that effect, if desired.
Out of these four primitive operators have been built various functional
abstractions that incorporate one or more operations. On the delimiting
side is reset
, which combines both prompt creation and delimiting. In
some papers on the subject (such as Shift to Control), each capture
operator would be paired with a corresponding delimiter operator (and
indeed, a separate CPS transform). However, since prompts are explicitly
passed in this implementation, a single delimiter suffices for supporting
all capture operators (although pushPrompt
will need to be used if one
wishes to explicitly push a prompt more than once).
The simplest control flow operator is abort
, which, as its name suggests,
simply aborts a given subcontinuation. For instance, the second example
above can be written:
pushPrompt p ((1:) `liftM` (2:) `liftM` abort p (return []))
The rest of the functions reify the subcontinuation into a function, so that it can be used. The shift/control operators all have similar effects in this regard, but differ as to where they delimit various parts of the resulting computation. Some names may help a bit for the following explanation, so consider:
shift p (\f > e)
p is, obviously, the prompt; f is the reified continuation, and e is the computation that will be run in the aborted context. With these names in mind, the control operators work as follows:

shift
delimits both e and every invocation of f. So, effectively, when usingshift
, control effects can never escape a delimiter, and computations of the form:
reset (\p > <computations with shift p>)
look pure from the outside.

control
delimits e, but not the subcontinuation in f. Thus, if the subcontinuation contains othercontrol
invocations, the effects may escape an enclosing delimiter. So, for example:
reset (\p > shift p (\f > (1:) `liftM` f (return [])) >= \y > shift p (\_ > return y))
yields a value of [1], while replacing the shift
s with control
yields a value of [].

shift0
delimits f, but not e. So:
reset (\p > (1:) `liftM` pushPrompt p (shift0 p (\_ > shift0 p (\_ > return []))))
yields [], whereas using shift
would yield [1].

control0
delimits neither e nor f, and is, in effect, the reified analogue to using withSubCont and pushSubCont directly.
For a more complete and indepth discussion of these four control operators, see Shift to Control, by Chungchieh Shan.
A small example program follows. It uses delimited continuations to reify a monadic loop into an iterator object. Saving references to old iterators allows one to effecively store references to various points in the traversal. Effectively, this is a simple, restricted case of a generalized zipper.
data Iterator r a = I a (CC r (Iterator r a))  Done current :: Iterator r a > Maybe a current (I a _) = Just a current Done = Nothing next :: Iterator r a > CC r (Iterator r a) next (I _ m) = m next Done = return Done iterator :: ((a > CC r ()) > CC r ()) > CC r (Iterator r a) iterator loop = reset $ \p > loop (\a > shift p $ \k > return $ I a (k $ return ())) >> return Done test = do i < iterator $ forM_ [1..5] go [] i where go l Done = return l go l i = do let (Just a) = current i l' = replicate a a ++ l i' < next i go l' i'
The results are what one might expect from such an iterator object:
*Test> runCC test [5,5,5,5,5,4,4,4,4,3,3,3,2,2,1]