|Portability||Non-portable (rank-2 types, multi-parameter type classes, functional dependencies)|
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 sequence-of-frames 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
- 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
|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)|
Executes a CCT computation, yielding a value in the underlying monad
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
througha given prompt. For instance, only prompts of type 'Prompt r a' may be pushed onto a computation of type 'CC r a'.
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 sub-continuations that may be captured
Creates a new, unique prompt.
Delimits a computation with a given prompt.
Abortively capture the sub-continuation delimited by the given prompt, and call the given function with it. The prompt does not appear delimiting the sub-continuation, nor the resulting computation.
Pushes a sub-continuation, reinstating it as part of the continuation.
Assorted useful control operators
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.
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.
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
Abortively captures the current subcontinuation, delimiting it in a reified function. The resulting computation, however, is undelimited.
Abortively captures the current subcontinuation, delimiting neither it nor the resulting computation.
Aborts the current continuation up to the given prompt.
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,
newPrompt, which should be straight forward enough. Next comes
pushPrompt, which is the basic operation that delimits a computation.
In the absense of other control operators, it's simply a no-op, so
pushPrompt p (return v) == return v
pushPrompt p ((1:) `liftM` (2:) `liftM` withSubCont p (\k -> return ))
will yield a value of  on running, not [1, 2].
pushPrompt p ((1:) `liftM1 (2:) `liftM` withSubCont p (\k -> pushSubCont k (return )))
will yield the answer [1, 2]. However, Capturing a sub-continuation and immediately pusshing it is not a no-op, because the sub-continuation does not contain the delimiting prompt (and, of course, pushSubCont does not re-instate it, as it doesn't know what prompt was originally used). Thus, capturing and pushing a sub-continuation results in the net loss of one delimiter, and said delimiter will need to be re-pushed 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
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 sub-continuation. 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 sub-continuation 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:
shiftdelimits both e and every invocation of f. So, effectively, when using
shift, control effects can never escape a delimiter, and computations of the form:
reset (\p -> <computations with shift p>)
look pure from the outside.
controldelimits e, but not the sub-continuation in f. Thus, if the sub-continuation contains other
controlinvocations, the effects may escape an enclosing delimiter. So, for example:
reset (\p -> shift p (\f -> (1:) `liftM` f (return )) >= \y -> shift p (\_ -> return y))
shift0delimits f, but not e. So:
reset (\p -> (1:) `liftM` pushPrompt p (shift0 p (\_ -> shift0 p (\_ -> return ))))
yields , whereas using
shift would yield .
control0delimits neither e nor f, and is, in effect, the reified analogue to using withSubCont and pushSubCont directly.
For a more complete and in-depth discussion of these four control operators, see Shift to Control, by Chung-chieh 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]