liboleg-2010.1.9.0: An evolving collection of Oleg Kiselyov's Haskell modules



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.

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 Source

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.


MonadTrans CC 
Monad m => Monad (CC m)

CC monad: general monadic operations

MonadIO m => MonadIO (CC m) 

data SubCont m a b Source

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 real stack: the type Ekfragment is ()

data Prompt m a Source

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

newPrompt :: (Monad m, Mutation m) => CC m (Prompt m a)Source

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

pushPrompt :: (Monad m, Mutation m) => Prompt m w -> CC m w -> CC m wSource

takeSubCont :: (Monad m, Mutation m) => Prompt m b -> (SubCont m a b -> CC m b) -> CC m aSource

pushSubCont :: (Monad m, Mutation m) => SubCont m a b -> CC m a -> CC m bSource

runCC :: (Monad m, Mutation m) => CC m a -> m aSource

abortP :: (Monad m, Mutation m) => Prompt m w -> CC m w -> CC m anySource

An efficient variation of take_subcont, which does not capture any continuation. This code makes it clear that abort is essentially raise.

pushDelimSubCont :: (Monad m, Mutation m) => SubCont m a b -> CC m a -> CC m bSource

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

shiftP :: (Monad m, Mutation m) => Prompt m w -> ((a -> CC m w) -> CC m w) -> CC m aSource

Useful derived operations

shift0P :: (Monad m, Mutation m) => Prompt m w -> ((a -> CC m w) -> CC m w) -> CC m aSource

controlP :: (Monad m, Mutation m) => Prompt m w -> ((a -> CC m w) -> CC m w) -> CC m aSource

isPromptSet :: (Monad m, Mutation m) => Prompt m w -> CC m BoolSource

Check to see if a prompt is set