Monad transformer for multi-prompt delimited control
This library implements the superset of the interface described in
A Monadic Framework for Delimited Continuations R. Kent Dybvig, Simon Peyton Jones, and Amr Sabry JFP, v17, N6, pp. 687--730, 2007. http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR615
This code is the straightforward implementation of the
definitional machine described in the above paper. To be precise,
we implement an equivalent machine, where captured continuations are
always sandwiched between two prompts. This equivalence as
well as the trick to make it all well-typed are described in
the FLOPS 2010 paper. Therefore, to the great extent
this code is the straightforward translation of delimcc from OCaml.
The parallel stack of delimcc is the
real stack now (containing
parts of the real continuation, that is).
This code implements, in CPS, what amounts to a segmented stack (the technique of implementing call/cc efficiently, first described in Hieb, Dybvig and Bruggeman's PLDI 1990 paper).
- data CC m a
- data SubCont m a b
- data Prompt m a
- newPrompt :: (Monad m, Mutation m) => CC m (Prompt m a)
- pushPrompt :: (Monad m, Mutation m) => Prompt m w -> CC m w -> CC m w
- takeSubCont :: (Monad m, Mutation m) => Prompt m b -> (SubCont m a b -> CC m b) -> CC m a
- pushSubCont :: (Monad m, Mutation m) => SubCont m a b -> CC m a -> CC m b
- runCC :: (Monad m, Mutation m) => CC m a -> m a
- abortP :: (Monad m, Mutation m) => Prompt m w -> CC m w -> CC m any
- pushDelimSubCont :: (Monad m, Mutation m) => SubCont m a b -> CC m a -> CC m b
- shiftP :: (Monad m, Mutation m) => Prompt m w -> ((a -> CC m w) -> CC m w) -> CC m a
- shift0P :: (Monad m, Mutation m) => Prompt m w -> ((a -> CC m w) -> CC m w) -> CC m a
- controlP :: (Monad m, Mutation m) => Prompt m w -> ((a -> CC m w) -> CC m w) -> CC m a
- isPromptSet :: (Monad m, Mutation m) => Prompt m w -> CC m Bool
- module Control.Mutation
Delimited-continuation monad transformer The (CC m) monad is the Cont monad with the answer-type (), combined with the persistent-state monad. The state PTop is the `parallel stack' of delimcc, which is the real stack now. The base monad m must support reference cells, that is, be a member of the type class Mutation. Since we need reference cells anyway, we represent the persistent state as a reference cell PTop, which is passed as the environment.
The context between two exception frames: The captured sub-continuation
It is a fragment of the parallel stack: a list of PFrames in inverse order.
Since we are in the Cont monad, there is no
the type Ekfragment is ()
We manipulate portions of the stack between two exception frames. The type of the exception DelimCCE is ()
The type of prompts is just like that in OCaml's delimcc
Basic Operations of the delimited control interface All control operators in the end jump to the exception frame
(in delimcc, that was `raise DelimCCE'; here it is `pfr_ek h')
An efficient variation of take_subcont, which does not capture any continuation. This code makes it clear that abort is essentially raise.
An optimization: pushing the _delimited_ continuation. This is the optimization of the pattern
pushPrompt (subcont_pb sk) (pushSubcont sk m)
corresponding to pushing the continuation captured by shift/shift0. The latter continuation always has the delimiter at the end. Indeed shift can be implemented more efficiently as a primitive rather than via push_prompt/control combination...
Useful derived operations
Check to see if a prompt is set