liboleg-2010.1.9.0: Control/CCExc.hs

{-# LANGUAGE PatternGuards, KindSignatures #-}
{-# LANGUAGE ExistentialQuantification, Rank2Types, ImpredicativeTypes #-}

-- | Monad transformer for multi-prompt delimited control
-- It implements the superset of the interface described in
--
-- <http://okmij.org/ftp/continuations/implementations.html#CC-monads>
--
-- > 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
--
-- The first main difference is the use of generalized prompts, which
-- do not have to be created with new_prompt and therefore can be defined
-- at top level. That removes one of the main practical drawbacks of
-- Dybvig et al implementations: the necessity to carry around the prompts
-- throughout all the code.
--
-- The delimited continuation monad is parameterized by the flavor
-- of generalized prompts. The end of this code defines several flavors;
-- the library users may define their own. User-defined flavors are 
-- especially useful when user's code uses a small closed set of answer-types. 
-- Flavors PP and PD below are more general, assuming the set of possible
-- answer-types is open and Typeable. If the user wishes to create several
-- distinct prompts with the same answer-types, the user should use
-- the flavor of prompts accepting an integral prompt identifier, such as PD.
-- Prompts of the flavor PD correspond to the prompts in Dybvig, Peyton Jones,
-- Sabry framework. If the user wishes to generate unique prompts, the user
-- should arrange himself for the generation of unique integers
-- (using a state monad, for example). On the other hand, the user
-- can differentiate answer-types using `newtype.' The latter can
-- only produce the set of distinct prompts that is fixed at run-time.
-- Sometimes that is sufficient. There is not need to create a gensym
-- monad then.
--
-- The second feature of our implementation is the use of the 
-- bubble-up semantics:
-- See page 57 of <http://okmij.org/ftp/gengo/CAG-talk.pdf>
-- This present code implements, for the first time, the delimited 
-- continuation monad CC *without* the use of the continuation monad. 
-- This code implements CC in direct-style, so to speak.
-- Instead of continuations, we rely on exceptions. Our code has a lot
-- in common with the Error monad. In fact, our code implements
-- an Error monad for resumable exceptions.

module Control.CCExc (
	      CC,			-- Types
	      SubCont,
	      CCT,
	      Prompt,

	      -- Basic delimited control operations
	      pushPrompt,
              takeSubCont,
              pushSubCont,
              runCC,

              -- Useful derived operations
	      abortP,
              shiftP,
              shift0P,
              controlP,

              -- Pre-defined prompt flavors
	      PS, ps,
              P2, p2L, p2R,
              PP, pp,
              PM, pm,
              PD, newPrompt,
              as_prompt_type
	      ) where

import Control.Monad.Trans
import Data.Typeable			-- for prompts of the flavor PP, PD

-- | Delimited-continuation monad transformer
-- It is parameterized by the prompt flavor p
newtype CC p m a = CC{unCC:: m (CCV p m a)}

-- | The captured sub-continuation
type SubCont p m a b = CC p m a -> CC p m b

-- | Produced result: a value or a resumable exception
data CCV p m a = Iru a
	       | forall x. Deru (SubCont p m x a) (p m x) -- The bubble

-- | The type of control operator's body
type CCT p m a w = SubCont p m a w -> CC p m w

-- | Generalized prompts for the answer-type w: an injection-projection pair
type Prompt p m w = 
    (forall x. CCT p m x w -> p m x,
     forall x. p m x -> Maybe (CCT p m x w))


--
-- |CC monad: general monadic operations
--
instance Monad m => Monad (CC p m) where
    return = CC . return . Iru

    m >>= f = CC $ unCC m >>= check
	where check (Iru a)         = unCC $ f a
	      check (Deru ctx body) = return $ Deru (\x -> ctx x >>= f) body


instance MonadTrans (CC p) where
    lift m = CC (m >>= return . Iru)

instance MonadIO m => MonadIO (CC p m) where
    liftIO = lift . liftIO

--
-- | Basic Operations of the delimited control interface
--
pushPrompt :: Monad m =>
	      Prompt p m w -> CC p m w -> CC p m w
pushPrompt p@(_,proj) body = CC $ unCC body >>= check
 where
 check e@Iru{} = return e
 check (Deru ctx body) | Just b <- proj body  = unCC $ b ctx
 check (Deru ctx body) = return $ Deru (\x -> pushPrompt p (ctx x)) body


-- | Create the initial bubble
takeSubCont :: Monad m =>
	       Prompt p m w -> CCT p m x w -> CC p m x
takeSubCont p@(inj,_) body = CC . return $ Deru id (inj body)

-- Apply the captured continuation
pushSubCont :: Monad m => SubCont p m a b -> CC p m a -> CC p m b
pushSubCont = ($)

runCC :: Monad m => CC (p :: (* -> *) -> * -> *) m a -> m a
runCC m = unCC m >>= check
 where
 check (Iru x) = return x
 check _       = error "Escaping bubble: you have forgotten pushPrompt"


-- --------------------------------------------------------------------
-- | Useful derived operations
--
abortP :: Monad m => 
	  Prompt p m w -> CC p m w -> CC p m any
abortP p e = takeSubCont p (\_ -> e)

shiftP :: Monad m => 
	  Prompt p m w -> ((a -> CC p m w) -> CC p m w) -> CC p m a
shiftP p f = takeSubCont p $ \sk -> 
	       pushPrompt p (f (\c -> 
		  pushPrompt p (pushSubCont sk (return c))))

shift0P :: Monad m => 
	  Prompt p m w -> ((a -> CC p m w) -> CC p m w) -> CC p m a
shift0P p f = takeSubCont p $ \sk -> 
	       f (\c -> 
		  pushPrompt p (pushSubCont sk (return c)))

controlP :: Monad m => 
	  Prompt p m w -> ((a -> CC p m w) -> CC p m w) -> CC p m a
controlP p f = takeSubCont p $ \sk -> 
	       pushPrompt p (f (\c -> 
		  pushSubCont sk (return c)))

-- --------------------------------------------------------------------
-- Prompt flavors

-- | The extreme case: prompts for the single answer-type w.
-- The monad (CC PS) then is the monad for regular (single-prompt) 
-- delimited continuations
newtype PS w m x = PS (CCT (PS  w) m x w)

-- | There is only one generalized prompt of the flavor PS for a
-- given answer-type w. It is defined below
ps :: Prompt (PS w) m w
ps = (inj, prj)
 where
 inj = PS
 prj (PS x) = Just x

-- | Prompts for the closed set of answer-types
-- The following prompt flavor P2, for two answer-types w1 and w2,
-- is given as an example. Typically, a programmer would define their
-- own variant data type with variants for the answer-types that occur
-- in their program.
--
newtype P2 w1 w2 m x = 
  P2 (Either (CCT (P2 w1 w2) m x w1) (CCT (P2 w1 w2) m x w2))


-- | There are two generalized prompts of the flavor P2:
p2L :: Prompt (P2 w1 w2) m w1
p2L = (inj, prj)
 where
 inj = P2 . Left
 prj (P2 (Left x)) = Just x
 prj _ = Nothing

p2R :: Prompt (P2 w1 w2) m w2
p2R = (inj, prj)
 where
 inj = P2 . Right
 prj (P2 (Right x)) = Just x
 prj _ = Nothing


-- | Prompts for the open set of answer-types
--
data PP m x = forall w. Typeable w => PP (CCT PP m x w)

-- | We need to wrap the type alias CCT into a newtype. Otherwise, gcast
-- doesn't work. We can't treat (CCT p m a w) as a an application of
-- the `type constructor' (CCT p m a) to the type w: type aliases can't 
-- be partially applied. But we can treat the type (NCCT p m a w) that way.
newtype NCCT p m a w = NCCT{unNCCT :: CCT p m a w}

pp :: Typeable w => Prompt PP m w
pp = (inj, prj)
 where
 inj = PP
 prj (PP c) = maybe Nothing (Just . unNCCT) (gcast (NCCT c))

-- | The same as PP but with the phantom parameter c
-- The parameter is useful to statically enforce various constrains
-- (statically pass some information between shift and reset)
-- The prompt PP is too `dynamic': all errors are detected dynamically
-- See Generator2.hs for an example
data PM c m x = forall w. Typeable w => PM (CCT (PM c) m x w)

pm :: Typeable w => Prompt (PM c) m w
pm = (inj, prj)
 where
 inj = PM
 prj (PM c) = maybe Nothing (Just . unNCCT) (gcast (NCCT c))

-- | Open set of answer types, with an additional distinction (given by
-- integer identifiers)
-- This prompt flavor corresponds to the prompts in the Dybvig, Peyton-Jones,
-- Sabry framework (modulo the Typeable constraint).
--
data PD m x = forall w. Typeable w => PD Int (CCT PD m x w)

newPrompt :: Typeable w => Int -> Prompt PD m w
newPrompt mark = (inj, prj)
 where
 inj = PD mark
 prj (PD mark' c) | mark' == mark, 
		    Just (NCCT x) <- gcast (NCCT c) = Just x
 prj _ = Nothing

-- | It is often helpful, for clarity of error messages, to specify the 
-- answer-type associated with the prompt explicitly (rather than relying 
-- on the type inference to figure that out). The following function
-- is useful for that purpose.
as_prompt_type :: Prompt p m w -> w -> Prompt p m w
as_prompt_type = const