-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Stepwise monad: stepwise computations, providing resolution of
-- non-deterministic choice, breadth-first search strategies and online
-- results.
@package stepwise
@version 1.0.2
module Control.Monad.Stepwise.Unsafe
-- | Runs the I/O computation when the value is needed. The effects may be
-- duplicated when the value itself is duplicated
inlinePerformIO :: IO a -> a
unsafeCoerce :: a -> b
ghc7compat :: a -> b
module Control.Monad.Stepwise.Proofs
module Control.Monad.Stepwise.Core
-- | A step-wise computation with errors e, progress reports
-- i, parametrized by watcher w, and evaluating to a
-- value of type a.
--
-- Progress reports i are indexed by the watcher type
-- w. To compose step-wise computations, they must agree on the
-- same type i. However, specific caller/callee combinations can
-- agree on a type w to report progress reports that contain
-- e.g. values computing during the evaluation process.
--
-- A stepwise computation may fail with an error of type e.
-- Failure is conceptually just another form of progress reports:
-- however, after a failure, there will not be any subsequent progress
-- reports. This distinction allows us to capture the behavior of the
-- fail function in the Monad class. For non-critical
-- failures, use conventional progress reports. If the information about
-- the failure is not an issue, use either AnyFailure or
-- String as the type for e.
--
-- A stepwise computation specifies its operational context via the type
-- index o. There are two operational modes: either the
-- computation requires to be executed sequentially, then it has
-- Sequential as type index, or it may be executed lazily, then it
-- has Lazy as type index. Some operations on stepwise
-- computations may require evaluation to be sequential. There is no way
-- (neither need) to enforce lazy evaluation.
--
-- A Stepwise-value represents a partially evaluated step-wise
-- computation. It is essentially a sequence of Info progress
-- reports, closed by either failure, success, or the remaining
-- computation.
--
-- The Pending constructor specifies the computation that is
-- 'left-most'. Strict evaluation starts with this computation first. It
-- also specifies the stack of binds that immediately follow the
-- left-most computation. Since the computation to evaluate first is
-- always on top of this structure, we do not have to inspect the stack
-- for each reduction step.
--
-- The Ahead constructor represents a suspended computation that
-- needs a continuation, such that it can give the reports for the final
-- result. Note that the function of Ahead takes a continuation
-- that cannot make any assumption about how it is executed (hence the
-- universal o'). If it needs to make an assumption, it should
-- do so via e.g. lazily. Furthermore, the function itself makes
-- the assumption that it is executed in a lazy context. This is a design
-- choice: we could also have demanded that it cannot make any
-- assumptions on how it is called.
--
-- Info represents a progress report.
--
-- The Ind constructor represents an indirection. Sharing an
-- indirection has the effect that the effort of producing the progress
-- reports is only performed once. In practice are Stepwise values
-- produced by functions, hence sharing is not provided by default. To
-- have a sharing guarantee, however, apply share to a
-- Stepwise value.
--
-- The additional indirection allows us to have explicit sharing, such
-- that we can update thunks, which opens up ways for parallelism.
--
-- The Mode constructor serves three purposes. With it we can
-- represent entering a certain evaluation mode, leaving a certain
-- evaluation mode, and remembering the stack of evaluation modes we are
-- currently in.
data Stepwise e i o w a
data StepHandle e i o w a
-- | Lazy evaluation of a step-wise computation.
lazyEval :: Stepwise e i Lazy w a -> a
-- | Sequential evaluation of a step-wise computation.
seqEval :: Stepwise e i Sequential w a -> a
-- | Evaluates step-wise (also ties the look-ahead knot)
stepwiseEval :: Stepwise e i o w a -> a
-- | Wrapper for an effect.
info :: i w -> Stepwise e i o w a -> Stepwise e i o w a
emit :: i w -> Stepwise e i o w ()
-- | One step strict evaluation. Reduction proceeds until one progress
-- report entry is produced, or the computation is suspended waiting for
-- the continuation.
next :: Stepwise e i o w a -> IO (Progress e i o w a)
localStep :: Stepwise e i o w a -> Progress e i o w a
smallStep :: Stepwise e i o w a -> Progress e i o w a
-- | A progress report. Either the progress report denotes a single step,
-- or a finished/failed computation, or a suspended computation in the
-- form of a lookahead that waits for its future continuation before it
-- can proceed.
data Progress e i o w a
Step :: !i w -> Stepwise e i o w a -> Progress e i o w a
Fin :: !a -> Progress e i o w a
Lookahead :: !forall b v. (forall o'. a -> Stepwise e i o' v b) -> Stepwise e i Lazy v b -> Progress e i o w a
Failed :: !Maybe e -> Progress e i o w a
-- | Introduces a computation for merging child-progress reports while
-- taking also into account the effects that the merge has in the
-- evaluation of the parents. The remaining evaluation for the parents is
-- passed as continuation.
lookahead :: (forall b v. (forall o'. a -> Stepwise e i o' v b) -> Stepwise e i Lazy v b) -> Stepwise e i o w a
-- | Applies a transcoder to a computation.
transcode :: Transcoder e i v w -> Stepwise e i o v a -> Stepwise e i o w a
-- | A transcoder is a function that transcodes a progress report of the
-- type i v to reports of the type i w. It gets a
-- CodeIn as input and produces a CodeOut as output. The
-- intention is that transcoders are pure functions: side effect is
-- allowed, but it is up to the programmer to ensure that the progress
-- report are not affected. If the input is TcLazy, the transcoder
-- is notified that lazy evaluation starts running the computation. The
-- outcome of the transcoder is ignored. When this takes place is
-- unspecified.
newtype Transcoder e i v w
Trans :: ((CodeIn e i v) -> IO (CodeOut e i w)) -> Transcoder e i v w
-- | Input to a transcoder. TcReport represents a single report to
-- be transcoded. TcDone indicates that the computation to where
-- this transcoder is applied, has succeeded. TcFail is its
-- counter-part. TcLazy indicates that a lazy evaluation has taken
-- over the computation.
data CodeIn e i w
TcReport :: !i w -> CodeIn e i w
TcLazy :: CodeIn e i w
TcDone :: CodeIn e i w
TcFail :: !Maybe e -> CodeIn e i w
-- | Output of a transcoder. Either it succeeds with zero or more
-- transcoded progress reports, or it aborts the computation.
data CodeOut e i w
TcReports :: [i w] -> CodeOut e i w
TcFailed :: !Maybe e -> CodeOut e i w
-- | Translates to zero or more reports, or failure.
translate' :: (i v -> IO (Either (Maybe e) [i w])) -> Stepwise e i o v a -> Stepwise e i o w a
-- | Translates progress reports from one domain directly into another.
translate :: (i v -> i w) -> Stepwise e i o v a -> Stepwise e i o w a
-- | Assumes that 'i v' is structurally equal to 'i w'.
unsafeTranslate :: Stepwise e i o v a -> Stepwise e i o w a
-- | Abort a computation. Note that in lazy evaluation mode, abort is
-- semantically equivalent to bottom, whereas in stepwise evaluation, it
-- provides backtracking. This means that if there is no
-- backtracking-alternative left, aborts are replaced by a bottom value.
abort :: e -> Stepwise e i o w a
-- | Turn a result into a (trivial) stepwise compuation.
final :: a -> Stepwise e i o w a
-- | Creates a pending computation for m with f on the
-- stack of parents.
resume :: Stepwise e i o w b -> (b -> Stepwise e i o w a) -> Stepwise e i o w a
-- | Creates an always failing stepwise computation.
failure :: Maybe e -> Stepwise e i o w a
-- | Creates an always failing stepwise computation (without an error
-- message).
unspecifiedFailure :: Stepwise e i o w a
-- | Allows the stepwise computation to run in lazy mode.
lazily :: Stepwise e i Lazy w a -> Stepwise e i o w a
-- | Forces the stepwise computation to run in sequential mode.
sequentially :: Stepwise e i Sequential w a -> Stepwise e i o w a
-- | Shares a stepwise computation. Work for such a shared computation is
-- only performed once.
share :: Stepwise e i o v a -> Stepwise e i Sequential w (Stepwise e i o v a)
-- | Converts a progress report back into a thunk that upon
-- next-reduction immediately yields the progress report again.
task :: Progress e i o w a -> Stepwise e i o w a
-- | Similar to task, except that it takes the next task of a step
-- instead.
nextTask :: Progress e i o w a -> Stepwise e i o w a
-- | Creates a handle to a stepwise computation.
handle :: Stepwise e i o v a -> Stepwise e i Sequential w (StepHandle e i o v a)
-- | Access the latest progress report on the handle.
report :: StepHandle e i o v a -> Stepwise e i Sequential w (Report e i o v a)
-- | Progress the handle one step. Note that the handle maintains a
-- reference to the outcome of the previous computation. Hence, if this
-- previous computation was a Info, we need to continue with the
-- computation as its rhs.
perform :: StepHandle e i o v a -> Stepwise e i Sequential w ()
-- | Closes the handle and embeds the remaining computation.
proceed :: StepHandle e i Lazy w a -> Stepwise e i Sequential w a
-- | Closes the handle and returns the remaining computation. The remaining
-- computation emits the last progress report first (if any), because
-- this report may not be acted upon yet. If you don't want this
-- behavior, apply a transcoder that filters out the first report.
close :: StepHandle e i Lazy v a -> Stepwise e i Sequential w (Stepwise e i Lazy v a)
-- | The Report version of a Progress report. The main
-- difference is that this variation is handle-based, which provides a
-- monadic way of accessing the progress reports.
data Report e i o w a
Finished :: !a -> Report e i o w a
Progress :: !i w -> Report e i o w a
Failure :: !Maybe e -> Report e i o w a
Future :: !forall b v. (forall o'. a -> Stepwise e i o' v b) -> Stepwise e i Lazy v b -> Report e i o w a
Unavail :: Report e i o w a
-- | Type level version of ForceSequential
data Sequential
-- | Type level version of AllowLazy
data Lazy
-- | Type index representing an arbitrary watcher. Note: in such
-- situations, you can choose an arbitrary type. This type, however,
-- explicitly states that there is no interest in the watcher type, which
-- provides a bit additional documentation.
data AnyWatcher
-- | Type index representing arbitrary failure. No information is provided
-- about the failure - only that it happened. We provide instances to
-- treat AnyFailure as error messages, which makes them convenient
-- to use.
data AnyFailure
AnyFailure :: AnyFailure
-- | Helper function that demands that the type of the stepwise computation
-- is sequential.
forceSequential :: Stepwise e i Sequential w a -> Stepwise e i Sequential w a
-- | Memoizes a stepwise computation.
memoSteps :: Typeable a => MemoEnvRef e i o w -> Int -> Stepwise e i o w a -> Stepwise e i o w a
-- | Creates an empty memo-env.
newMemoEnv :: IO (MemoEnvRef e i o w)
-- | Use a different MemoEnv for different watcher types.
type MemoEnvRef e i o w = IORef (MemoEnv e i o w)
instance Typeable AnyWatcher
instance Error (Errors e)
instance Monoid (Errors e)
instance Error AnyFailure
instance Monoid AnyFailure
instance Error e => MonadIO (Stepwise e i Sequential w)
instance Error e => MonadFix (Stepwise e i Lazy w)
instance Error e => Functor (Stepwise e i o w)
instance Error e => Monad (Stepwise e i o w)
-- | This module contains some utility functions that build on the core
-- interface of Stepwise computations.
--
-- Todo: nicer abstractions for specific merge-patterns.
module Control.Monad.Stepwise.Derived
-- | Chooses locally: i.e. does not allow a lookahead beyond the current
-- computation. A subcomputation does not see beyond the current choice.
localChoice :: (i w -> Stepwise e i o w a -> i w -> Stepwise e i o w a -> Stepwise e i o w a) -> (e -> e -> Stepwise e i o w a) -> Stepwise e i o w a -> Stepwise e i o w a -> Stepwise e i o w a
-- | Merges two steps into a single step, thereby making use of the monoid
-- instance.
mergeSteps :: (Monoid (i w), Monoid e, Error e) => i w -> Stepwise e i o w a -> i w -> Stepwise e i o w a -> Stepwise e i o w a
-- | Global choice. Takes the computation with the shortest sequence of
-- reports that succeeds, or the longest that fails. First parameter is a
-- transcoder that translates reports to the final domain.
globalChoice :: Error e => (forall v. Stepwise e i Lazy v a) -> (forall v. Stepwise e i Lazy v a) -> Stepwise e i o w a
instance (Monoid (i w), Monoid e, Error e) => Alternative (Stepwise e i o w)
instance Error e => Applicative (Stepwise e i o w)
instance Error e => MonadError e (Stepwise e i o w)
-- | This module shows some example stepwise-computations, and focus on
-- individual features provided by the library. We start with testing out
-- some basic functionality, then switch to more interesting examples. In
-- practice, you'll combine several of the features presented here.
module Control.Monad.Stepwise.Examples
-- | A type for the simplest form of progress report: just a message
-- I that indicates that a bit of work has been done. It is
-- indexed by the watcher type t, which in this case doesn't
-- matter. Later examples show a more involving type of progress report
-- that uses the watcher type.
data I t
I :: I t
-- | Test 1: verify that results are provided when available (online
-- behavior). With lazyEval this means that the result should be
-- delivered, independent of the failure. Failure is just considered to
-- be a bottom-value: if it's never needed in the continuation, it is not
-- triggered. This is different in comparison to strict evaluation.
--
-- A short remark about the type signature: the AnyFailure is the
-- type of failures such a computation may emit during stepwise
-- evaluation (during lazy evaluation, this is simply a bottom value).
-- Both String and AnyFailure are typical examples. The
-- I type is the type of the progress reports. The watcher type is
-- given seperately. A computation may state how it is evaluated: either
-- may use lazy evaluation (via the type Lazy) or use
-- sequential evaluation (via the type Sequential). For most
-- computations this is not an issue: either keep it polymorphic (like in
-- this example via a universally quantified type variable), or use
-- Lazy (the preferred default evaluation mode). We also do not
-- care about the watcher type for progress reports of type I.
-- Either keep the type polymorphic, or simply choose a type like
-- AnyWatcher (or '()'). Finally, the last type of the value that
-- evaluation of the computation results into. The first three parameters
-- to Stepwise typically stay the same, the latter three may vary
-- from one computation to another.
test1 :: Stepwise AnyFailure I any AnyWatcher Int
-- | Test 2: verify that the selection process causes strict evaluation.
-- Despite running lazyEval on test2, strict evaluation
-- will be done on the alternatives until a choice is made. In this case,
-- both alternatives fail, so the entire result fails. Note that the
-- <|>-implementation takes the first child that succeeds,
-- or the last child that fails (left-biased).
test2 :: Stepwise AnyFailure I any AnyWatcher Int
-- | Test 3: verify selection of alternatives. The non-failure alternative
-- is selected in this case. The Lazy annotation here we can use
-- because we can. A Lazy-annotation is in principle never
-- required (you can in such cases keep it polymorphic), but if possible,
-- it's a good idea to do so, to make clear which computations should
-- preferably be evaluated lazily.
test3 :: Stepwise AnyFailure I Lazy AnyWatcher Int
test4 :: Stepwise AnyFailure I any AnyWatcher Int
test5 :: Stepwise AnyFailure I any AnyWatcher [Int]
test6 :: Stepwise AnyFailure I Lazy AnyWatcher Int
-- | Test 7: collecting multiple results.
--
-- test7b generates paths: the left subpath is of length n-1 the
-- right subpath is a lot shorter (n div 2) (just for fun).
-- test7a succeeds only for those paths that satisfy a funny
-- criteria via xor. Those it returns. When it succeeds, test7b
-- emits a progress report collecting that value. merge tries out
-- options in a breadth-first way, and concatenates the lists in the
-- progress reports. test7c takes out the list of all succeeding
-- paths.
--
-- We collect these multiple results in a more informative form of
-- progress report J. The type of the watcher is important here.
-- The test7a function does not make any assumptions about the
-- watcher, however test7b does. When test7a succeeds, it
-- collects that results in a Collect.
data J t
Collect :: [t] -> J t
J :: J t
-- | We may not make an assumption about the watcher here, hence we keep
-- the watcher type polymorphic.
test7a :: [Bool] -> Stepwise AnyFailure J Lazy somewatcher [Bool]
test7b :: Int -> [Bool] -> Stepwise AnyFailure J Lazy [Bool] ()
merge :: Stepwise AnyFailure J Lazy [Bool] () -> Stepwise AnyFailure J Lazy [Bool] () -> Stepwise AnyFailure J Lazy [Bool] ()
-- | Strips steps (thus evaluates sequentially), until it hits a
-- Collect message, which is subsequently delivers.
test7c :: Stepwise AnyFailure J Lazy a [[Bool]]
-- | Test 8: lookahead. Decisions taken in this example may depend on what
-- happens in the continuation. We takes as example path-finding in a
-- labyrinth. Taking a step that brings us back to a position where we've
-- been before is an immediate failure. However, the possibilities that
-- remain may hit a dead-end later.
type Lab a = RWST LabIn Instrs LabChn (Stepwise AnyFailure LabSteps Lazy AnyWatcher) a
type Lab' a = Stepwise AnyFailure LabSteps Lazy AnyWatcher (a, LabChn, Instrs)
data LabIn
LI :: !Set Pos -> {-# UNPACK #-} !Pos -> {-# UNPACK #-} !MemoEnvRef AnyFailure LabSteps Lazy AnyWatcher -> LabIn
inLab :: LabIn -> !Set Pos
inEnd :: LabIn -> {-# UNPACK #-} !Pos
inMemo :: LabIn -> {-# UNPACK #-} !MemoEnvRef AnyFailure LabSteps Lazy AnyWatcher
data LabChn
LC :: !Pos -> !Set Pos -> LabChn
chnPos :: LabChn -> !Pos
chnTrail :: LabChn -> !Set Pos
data LabSteps t
Walked :: !Set Pos -> LabSteps t
type Pos = (Int, Int)
newtype Instrs
Instrs :: (Path -> Path) -> Instrs
type Path = [Dir]
data Dir
North :: Dir
East :: Dir
South :: Dir
West :: Dir
search :: Lab ()
pos2key :: Pos -> Int
finished :: Lab ()
move :: Dir -> Lab ()
forward :: Dir -> Pos -> Pos
(<<|>) :: Lab a -> Lab a -> Lab a
best :: Lab' a -> Lab' a -> Lab' a
-- | Example labyrinth
lab1 :: [Pos]
exp8Succs :: Path
branch :: Lab a -> Lab (Branch a)
-- | Container to keep the contained value lazy
data Branch a
Branch :: Lab' a -> Branch a
pickBranch :: Branch a -> Lab' a
embed' :: Lab' a -> Lab a
pathClose :: Instrs -> Path
pathOne :: Dir -> Instrs
-- | Test 8b: Explicit sharing. This example builds on the previous one.
-- Since we immediately fail when a step would take us back at a position
-- that we've been before, the paths we traverse form a DAG. However,
-- certain paths on this DAG we may traverse more than once. In this
-- example, we ensure that we only traverse each path once.
--
-- Note, however, that it memoizes the outcome (i.e. the Lab' value),
-- produced in a context potentially different from ours. The key
-- loc in this case, however, identifies a unique context.
memoize :: MemoEnvRef AnyFailure LabSteps Lazy AnyWatcher -> Int -> Lab () -> Lab ()
-- | Test 8c: Ambiguity and online-ness improvement. If two parallel
-- branches converge on a single path, kill one of the branches. A much
-- more effective approach is to keep a shared trail via an IORef and
-- kill any branch that makes a move to a square already visited.
-- However, the current approach is more interesting: it takes a bit
-- longer until common paths are found.
convergeKill :: Lab' a -> Lab' a -> Lab (Lab' a, Lab' a)
runAhead :: Int -> Lab' a -> Lab (Lab' a)
-- | Repmin with alternatives! The tree may contain alternatives. The tree
-- is returned such that it (1) consists of the shortest (left-biassed)
-- alternatives (2) all leaves replaced with the minimal value occurring
-- in the tree (for the selected alternatives) This tests the
-- MonadFix feature.
--
-- Note: To show that online results are in general necessairy for cyclic
-- computations, we should actually make the selection process dependent
-- on the outcome of a previously but already resolved selection. For
-- example, by keeping a local minimum (from the left), and taking the
-- first alternative that goes under it. Perhaps a min/max game tree
-- would be a good example for that.
--
-- Also, a lazy value depending on the outcome of two or more
-- alternatives can only be produced if there is one alternative left. If
-- all the alternatives would yield the same outermost constructor, still
-- no value can be produced. This is in general no problem; the reason
-- that you had alternatives there is likely because it returns different
-- results.
data BinTree
Leaf :: Int -> BinTree
Bin :: BinTree -> BinTree -> BinTree
Alt :: BinTree -> BinTree -> BinTree
type RepMin a = Stepwise AnyFailure I Lazy AnyWatcher a
repmin :: BinTree -> RepMin BinTree
semTree :: BinTree -> Int -> RepMin (Int, BinTree)
test9 :: RepMin BinTree
exp9Succs :: BinTree
instance Typeable Instrs
instance Typeable LabChn
instance Show BinTree
instance Enum Dir
instance Show Dir
instance Monoid Instrs
instance Monoid (I t)
-- | Note: Some documentation may not be visible in the Haddock
-- documentation; also check the comments directly in the source code.
--
-- A module for the step-wise evaluation of pure computations, in
-- particular suitable to resolve non-deterministic choices in
-- computations.
--
-- This module provides a monadic interface for a special form of pure
-- coroutines that, upon disgression of the caller, yield lazily
-- the result of the coroutine, or evaluates strictly until it can yield
-- next callee-determined progress report. Due to the monadic interface,
-- such a coroutine is an ordinary composable monadic haskell function,
-- with the exception that it may be decorated with statements that yield
-- progress reports. Both the result and progress reports are purely
-- functional: given an expression written with this interface, the
-- evaluated value as well as all the progress reports are uniquely
-- determined by the values for the free variables of the expression.
--
-- Given such a coroutine m, we can both refer to its progress
-- reports and its value from another coroutine. Given a coroutine
-- m, the conventional way to access its value is via a
-- coroutine m >>= f, where f is itself a
-- coroutine that takes m's value as parameter. The progress
-- reports of m are incorporated as part of the progress reports
-- of m >>= f, ordered such that the progress reports of
-- m are emitted before those of f. Alternatively, we
-- can ask m to yield the next progress report via smallStep
-- m. This returns a progress report, and an updated coroutine to be
-- used as continuation. In this case, m evaluated one step,
-- hence 'step-wise'.
--
-- Stepwise evaluation provides a means to encode non-deterministic
-- choices in a deterministic way via advanced search strategies. For
-- example, with this module, we can define a coroutine that determines
-- its result by making a choice between the results of two other
-- coroutines. For that, we step through the evaluation of both
-- coroutines until we saw sufficient progress reports to make a choice.
-- Meanwhile, we already yield progress reports. Finally, we make a
-- choice by integrating the coroutine in the conventional way.
-- Consequently, the choice is optimized away, and the coroutine that is
-- not selected becomes garbage.
--
-- With this approach, we encode a breadth-first evaluation by letting
-- each couroutine emitting steps regularly, and alternate the coroutine
-- to take steps from. We get depth-first behavior by fully stepping
-- through one of the choices first before considering the other choice.
-- Custom strategies are possible by emitting progress reports. For
-- example, a coroutine can emit statistics about the work done so far
-- and predictions of the work still to do to produce the result, which
-- can subsequently be used to direct the evaluation process.
--
-- A coroutine has the type BF e i w a, where a is the
-- final result computed by the coroutine. Such a computation may fail,
-- with reasons indicated by the type e. Progress reports are of
-- the type i w, i.e. parameterized in the type of a
-- watcher w. A watcher is a type index that allows the
-- progress reports to be different depending on the caller of a
-- coroutine: both the callee and its caller (and the caller's caller,
-- etc.) coroutines must share the same type i for progress
-- reports. Specific callee/caller combinations may decide on a common
-- type w to communicate special-typed progress information. To
-- emit such a progress report to a caller with a different watcher-type,
-- it has to be transcoded first via e.g. transcode.
--
-- In some situations, the choice between a coroutine a and
-- b may depend on what happends when we pick i.e. a
-- and our caller continues its evaluation. For example, suppose that the
-- continued evaluation is represented by some unknown coroutine
-- r, and we we define a coroutine c = choice a b. This
-- means that the actual evaluation is choice a b >>= r.
-- We may want to lift this choice over r, to choice' (a
-- >>= r) (b >>= r). Since r is unknown,
-- choice' cannot base its choice on the value computed by a
-- >>= r or b >>= r. Both the type of the
-- result and the watcher type are existential. However, we can inspect
-- if one of the alternatives fails, and inspect progress reports that
-- are independent of the watcher type. We provide this choice-lifting
-- via a special operation call lookahead. It provides us with our
-- continuation r, and we must define the coroutine denoting
-- c' >>= r, where c' denotes our choice. This
-- lifting comes with a price: requesting a step from a coroutine may
-- require us to provide it a continuation that represents what we are
-- going to do afterwards with it. For example, if we pass return,
-- there is no lookahead beyond the evaluation of the coroutine. However,
-- if we pass the continuation obtained through lookahead, we
-- potentially look ahead through a possible future. The difference
-- between progress report type and watcher type is important here. We
-- cannot make assumptions about the wachter of the continuation: but we
-- do know that we get progress reports of type i with
-- unspecified watcher type.
--
-- When we request a step from e = m >>= f, we gradually
-- reduce it until it emits the next progress report. It first gradually
-- reduces m. When it is entirely finished with m, it
-- continues with f, after parametrizing it with the value
-- computed for m. However, given such a partially reduced
-- e' = m' >>= f', when we ask for the lazyEval
-- e, we immediately get the result lazyEval (f' (lazyEval
-- m')). lazyEval discards any progress reports and
-- immediately produces a lazy result. When f is not strict in
-- its first argument, this means that a value can already be produced,
-- possibly without even evaluating the remainder of m'. For
-- example, lazyEval (choice a b) strictly evaluates a
-- and b as long as it is asking for steps. Once choice
-- selects one alternative, lazy evaluation takes over. This allows us to
-- produce online results when choices have been resolved.
--
-- Benchmark results show that a Stepwise bind is approximately 10
-- times slower compared to a bind of the identity monad (independent of
-- the amount of binds). Stepwise evaluation of a bind via
-- stepwiseEval is only marginally (e.g. approx 10%) slower
-- compared to lazyEval of a bind.
--
-- A downside of the monadic interface is that it requires code to be
-- written in a sequential way (it enforces monadic style upon the
-- program). For tree traversals, we eliminate this downside with
-- Attribute Grammars. For the class of Ordered Attribute Grammars
-- (non-cyclic tree-traversals fall in this class), the UUAG system has
-- an option to automatically derive code for this library.
--
-- This library is a generalization of the Steps-technique presented in
-- `Polish parsers, Step by Step` by R. J. M. Hughes and S. D. Swierstra,
-- and the later work in `Combinator Parsing: A Short Tutorial' by S. D.
-- Swierstra. The key difference is that we do not construct a single
-- function f :: a -> b in Apply f (as mentioned in
-- the latter paper) that represents a continuation of what still needs
-- to be computed. Instead, we explicitly build a stack of all pending
-- right-hand sides g1..gn that follow the currently active
-- computation m in m >>= g1 >>= ... gn.
-- The functions g on the stack thus have the monadic type g
-- :: a -> BF e i w b. When we request a new progress report and
-- m is fully reduced, we reduce the pending-stack: pop off
-- g1, parametrize it with the result of m, then start
-- reducing that value. Consequently, we have no difficulties dealing
-- with the monadic bind in this approach. This representation, however,
-- does not impair laziness. We still manage to map this representation
-- back to a function f :: a -> b. This transformation is
-- performed by lazyEval. A smaller difference is that our
-- interface to deal with progress reports does not expose the above
-- mentioned stack, which reduces complexity for the programmer.
module Control.Monad.Stepwise
-- | Module for use in combination with UUAG's --breadtfirst option.
module Control.Monad.Stepwise.AG
-- | Semantics of a child of type n as a function from inherited
-- attributes (Inh n) to a computation Comp i n of
-- synthesized attributes (Syn n).
newtype Child i n
Child :: (Inh n -> Comp i n) -> Child i n
-- | We use slightly simpler stepwise computations for AGs.
type Comp i n = Stepwise AnyFailure i Lazy AnyWatcher (Syn n)
-- | Unwraps a Closure
invoke :: Child i n -> Inh n -> Comp i n