Copyright | (c) R. Kent Dybvig, Simon L. Peyton Jones and Amr Sabry |
---|---|

License | MIT |

Maintainer | Dan Doel |

Stability | Experimental |

Portability | Non-portable (rank-2 types, multi-parameter type classes, functional dependencies) |

Safe Haskell | None |

Language | Haskell98 |

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
- 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) Source | |

MonadState s m => MonadState s (CCT ans m) Source | |

MonadTrans (CCT ans) Source | |

Monad m => MonadDelimitedCont (Prompt ans) (SubCont ans m) (CCT ans m) Source | |

Monad m => Monad (CCT ans m) Source | |

Monad m => Functor (CCT ans m) Source | |

Monad m => Applicative (CCT ans m) Source | |

MonadIO m => MonadIO (CCT ans m) Source |

runCCT :: Monad m => (forall ans. CCT ans m a) -> m a Source

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
`through`

a given prompt. For instance, only prompts of type 'Prompt r a' may be pushed onto a computation of type 'CC r a'.

class Monad m => MonadDelimitedCont p s m | m -> p s where Source

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.

pushPrompt :: p a -> m a -> m a Source

Delimits a computation with a given prompt.

withSubCont :: p b -> (s a b -> m b) -> m a Source

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.

pushSubCont :: s a b -> m a -> m b Source

Pushes a sub-continuation, reinstating it as part of the continuation.

# Assorted useful control operators

reset :: MonadDelimitedCont p s m => (p a -> m a) -> m a Source

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 a Source

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 a Source

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 a Source

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 a Source

Abortively captures the current subcontinuation, delimiting neither it nor the resulting computation.

abort :: MonadDelimitedCont p s m => p b -> m b -> m a Source

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 no-op, so

pushPrompt p (return v) == return v

`withSubCont`

is the primitive that allows the capture of sub-continuations.
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 sub-continuations 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 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
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 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:

`shift`

delimits 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.

`control`

delimits*e*, but not the sub-continuation in*f*. Thus, if the sub-continuation contains other`control`

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 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]