!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ Runs the I/(O computation when the value is needed. E The effects may be duplicated when the value itself is duplicated Use a different  for different watcher types. OThe first indirection is the cache per return type, the second indirection the  values stored per key. CCatched stepwise computations are existential in the return value. Turn tracing on or off "Collects multiple error messages. The  version of a   report. N The main difference is that this variation is handle-based, which provides 4 a monadic way of accessing the progress reports.  KA cursor that keeps track of the latest report and the latest computation. SKeeps track of the handles in use by a current thread. If a thread access the same Q handle more than once, we ran in a loop, and fail the computation. This cycle F detection is only available to explicitly shared computations (via 2 or   memoizeSteps). In these situations, it'!s typically nasty to implement a T cycle-check, hence this is offered as a service. This has semantic consequences: S it is up to the programmer to prove that the computation would also have failed  without sharing. ?A progress report. Either the progress report denotes a single  step, or a finished//failed computation, or a suspended computation E in the form of a lookahead that waits for its future continuation  before it can proceed. PType index representing arbitrary failure. No information is provided about the B failure - only that it happened. We provide instances to treat  as 7 error messages, which makes them convenient to use. .Type index representing an arbitrary watcher. S Note: in such situations, you can choose an arbitrary type. This type, however, S explicitly states that there is no interest in the watcher type, which provides # a bit additional documentation. Type level version of  Type level version of  In the 2 mode, we may either evaluate lazily or stepwise.  In - mode, however, evaluation must be strict or  stepwise. BEvaluation-mode stack. The stack keeps in what evaluation context > (possibly lazy or required sequential) the computation is. DA transcoder is a function that transcodes a progress report of the  type i v to reports of the type i w . It gets a  as input  and produces a . as output. The intention is that transcoders C are pure functions: side effect is allowed, but it is up to the C programmer to ensure that the progress report are not affected.  If the input is ', the transcoder is notified that lazy A evaluation starts running the computation. The outcome of the @ transcoder is ignored. When this takes place is unspecified. Output of a transcoder. E Either it succeeds with zero or more transcoded progress reports, ! or it aborts the computation. Input to a transcoder.  . represents a single report to be transcoded.  9 indicates that the computation to where this transcoder  is applied, has succeeded.  is its counter-part.  5 indicates that a lazy evaluation has taken over the  computation. BOptional transcoding of info-messages. We expect not to transcode I often. Hence, we make explicit when no transcoding is done, such that 3 we can optimize the composition of transcoders. H Transcoding can in principle be by pattern matching on info-messages F and outputting them again. However, that would require a traversal I of the parent stack for each progress report. Instead, expecting that F there will only be a few transcoders, we compose these as a single ; transcoder that immediate encodes to the target domain. %Explicit closure for a pending bind. < represents the stack of pending binds of a computation, as E well as transcoders for progress reports. It specifies how we can  transform the value b to a, and transcode steps from i v to i w.  The stack is structured in F such a way that we do not need to inspect the entire structure for @ a single reduction step. For this purpose, we also store two J transcoders-values: a transcoder that only transcodes progress reports E to the format expected by its immediate parent, and automatically derived N from these a transcoder that transcodes directly to the format expected by  the root. <Represents a memory cell containing a stepwise computation. ? Essential here is that we keep track of a partially reduced : computation, and possibly seperately, the outcome of a O lazy evaluation on that computation. Lazy evalutation reduces a computation E differently, outside of our control. We cannot simply replace the  computation with a 'Final v'' value; only when strict evaluation of v O is non-bottom - something we do not know. The reason is that the outcome of  a ' lazyEval m'. is potentially less defined that the outcome 'stepwiseEval m'. ) However, we do want to share multiple  s on the same computation, = hence a separate cache for stepwise and lazy evaluations. <A handle to a Step-wise computation. If you use a handle to G request the next progress report, the effort to produce this report D is only performed once. If the handle is shared, it may not cost / any effort to get the next progress report. $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 8 e.g. values computing during the evaluation process. 6A stepwise computation may fail with an error of type e. B 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  function in the  class. A 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 . as type index, or it may be executed lazily,  then it has , as type index. Some operations on stepwise B computations may require evaluation to be sequential. There is 5 no way (neither need) to enforce lazy evaluation. A 2-value represents a partially evaluated step-wise  computation. # It is essentially a sequence of  progress reports, closed = by either failure, success, or the remaining computation. The  constructor % specifies the computation that is  'left-most' . Strict D evaluation starts with this computation first. It also specifies I the stack of binds that immediately follow the left-most computation. D Since the computation to evaluate first is always on top of this E structure, we do not have to inspect the stack for each reduction  step. The  constructor represents a A suspended computation that needs a continuation, such that it . can give the reports for the final result.  Note that the function of " takes a continuation that cannot E 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. /. D Furthermore, the function itself makes the assumption that it is F executed in a lazy context. This is a design choice: we could also J have demanded that it cannot make any assumptions on how it is called.  represents a progress report. The ( constructor represents an indirection. F Sharing an indirection has the effect that the effort of producing 3 the progress reports is only performed once. In  practice are % values produced by functions, hence D sharing is not provided by default. To have a sharing guarantee,  however, apply 2 to a  value. ?The additional indirection allows us to have explicit sharing, H such that we can update thunks, which opens up ways for parallelism. The = constructor serves three purposes. With it we can represent J entering a certain evaluation mode, leaving a certain evaluation mode, F and remembering the stack of evaluation modes we are currently in. 2Pushes a new evaluation mode on top of the stack. -Pushes the entire stack of evaluation modes. /Pops the latest evaluation mode off the stack. "Gets the current evaluation mode. In contrast to " does this function not require a " sequential evaluation context. 5Obtains a (recent) thunk associated with the handle. ?Writes a reference to a stepwise computation, and releases it.  Note: a  must follow exactly a . CTakes the stepwise computation from the reference and reserves it.  Note: a  must be followed exactly by a . /Creates a reference to a stepwise computation. 1 Should not be strict in its second parameter! F The first argument is intended an optional reference to an earlier $ version of the second parameter. ,Lazy evaluation of a step-wise computation. !2Sequential evaluation of a step-wise computation. 'Evaluation of a step-wise computation. 8 We cannot return the progress reports, as this would % linearize the entire computation. 9When using lazy evaluation, the left-hand side of a bind K is not guaranteed to be evaluated if the right-hand side is lazy in its 8 parameter. I.e. this behavior is similar as with the Identity monad. Invariant concerning the !: it is only passed topdown. For ,  we don'7t need to know when we leave a certain evaluation mode Applies the pending binds. "9One step strict evaluation. Reduction proceeds until one : progress report entry is produced, or the computation is ) suspended waiting for the continuation. ?Checks if a certain handle is in the stack of handles kept per " invocation. 9Keep track of the evaluation mode. The invariant is that " F always starts in DefaultMode. The Stepwise computation should thus 8 make sure to remember deviations in the computation. PInvariant: handles are always followed with a default operation environment, to S ensure that they can be reduced from different contexts. If the evaluation mode F differs from the default, the computation referred to should use a  & instruction to setup this context. 2 We enforce that handles can only be created to  computations, * such that a default context works out. % If the value that comes out is an $-value, we again turn the remaining P computation into an indirection, in order to allow sharing of this remaining  computation. kConditionally updates the handle with the new stepwise computation, if the old computation is not trivial. p If the handle the computation points to is by itself an indirection, we keep the indirection: only tripple or R more indirections can be short-circuited without loosing sharing in some cases. 9Reduces a pending computation until it can yield a step. B when the computation finished, it proceeds with the evaluation $ of the next parent on the stack. DThe evaluation stack we take as parameter applies only to the whole I pending compution. The evaluations performed for the active compution I may influence this stack. We need to make sure that upon resume, that / computation gets its new stack again (via a -node), and also  restore our stack again. YApplies the transcoder and builds a new computation, by prepending the transcoded steps, a and possibly replacing the initial computation with a failing one. This happens only when the  transcoder causes an abort. 4Remembers the evaluation mode for the continuation. Removes ; constructors. The removed data can be reconstructed again ( via inspection of the right argument KPushes the first stack on top of the latter stack, by appending the latter N as tail of the former, and reconstructing the global transcoders. The idea O is that afterward, progress reports can be passed on efficiently, bypassing P all pending parents. Also the idea is that the stack we push onto this stack M is rather small - typically not more than one operation - because we push < the pending-stack to the place where evaluation happens. BApplies the transcoder. It may drop progress reports by returning  7. It is not possible to apply changes to the remaining J computation. Transcoders are only applied during step-wise evaluation, > which would affect the outcome in case of lazy evaluation. E Todo: it may be interesting to yield additional progress reports. 2Empty transcoder: just passes along what it gets. !Pushes a transcoder on the parent' s stack. H Note: a pending-node specifies how to transcode the progress reports > resulting from the operation. The transcoder that we E push on the stack translates progress reports of the active . node into the domain of the parents. IComposes (efficiently) a global transcoder out of a local transcoder and 0 the global transcoder of the pending parent. IComposes two coders by applying the latter to the outcome of the former. "Pushes an operation on the stack. #$%4Evaluates step-wise (also ties the look-ahead knot) &'Applies a transcoder to a computation. 'CTranslates progress reports from one domain directly into another. (0Translates to zero or more reports, or failure. ) Assumes that 'i v' is structurally equal to 'i w'. *8Abort a computation. Note that in lazy evaluation mode, : abort is semantically equivalent to bottom, whereas in 2 stepwise evaluation, it provides backtracking. ; This means that if there is no backtracking-alternative 0 left, aborts are replaced by a bottom value. +4Turn a result into a (trivial) stepwise compuation. ,0Creates an always failing stepwise computation. -KCreates an always failing stepwise computation (without an error message). ."Creates a pending computation for m with f on the stack of parents. /5Allows the stepwise computation to run in lazy mode. 0;Forces the stepwise computation to run in sequential mode. 1GHelper function that demands that the type of the stepwise computation  is sequential. BRuns the given stepwise computation in a certain evaluation mode.  It uses the / constructor to indicate the transition to the / new evaluation mode. It also encodes with a  the transition D back. This, however, is only needed for stepwise evaluation: the  scope of the lazy/-sequential eval functions already determines % the scope of the evaluation mode. ?Coerces the evaluation context type to an arbitrary evaluation B context type. This is a phantom type, with the only purpose to . make sequential computations safer to use. 2JShares a stepwise computation. Work for such a shared computation is only  performed once. 37Converts a progress report back into a thunk that upon  "9-reduction immediately yields the progress report again. 4 Similar to 38, except that it takes the next task of a step instead. 5,Creates a handle to a stepwise computation. 61Access the latest progress report on the handle. 7LProgress the handle one step. Note that the handle maintains a reference to P the outcome of the previous computation. Hence, if this previous computation  was a 7, we need to continue with the computation as its rhs. 8SCloses the handle and returns the remaining computation. The remaining computation Q emits the last progress report first (if any), because this report may not be  acted upon yet. If you don'6t want this behavior, apply a transcoder that filters  out the first report. 98Closes the handle and embeds the remaining computation. :Wrapper for an effect. ;<BIntroduces a computation for merging child-progress reports while B taking also into account the effects that the merge has in the G evaluation of the parents. The remaining evaluation for the parents  is passed as continuation. =Creates an empty memo-env. >!Memoizes a stepwise computation. (Produces a unique key based on the type a 7Turn error messages in AnyFailure, effectively loosing  all details (if any). Trivial instance for . Instance for MonadIO.  The relative order of liftIO'+s, and non-duplication of effects, is only 9 guaranteed in a sequential context. Use with caution. Instance for MonadFix. " Note: the steps resulting from mfix f should not depend  on the actual outcome of mfix f": this would create a hard cycle. !Monad instance for Stepwise. See !Control.Monad.BreadthFirst.Proofs for  proofs of the monad laws. <  !"#$%&'()*+,-./0123456789:;<=>< !%:;"$#  <&(')*+.,-/023456798 1>=<    !"#$%&'()*+,-./0123456789:;<=>?PMerges two steps into a single step, thereby making use of the monoid instance. @kChooses locally: i.e. does not allow a lookahead beyond the current computation. A subcomputation does not  see beyond the current choice. AGlobal choice. i Takes the computation with the shortest sequence of reports that succeeds, or the longest that fails. P First parameter is a transcoder that translates reports to the final domain. Alternative instance. - Takes the shortest sequence that yields a % value, or the longest that fails. MonadError instance.  A  without a " is semantically equal to bottom.  > runs the computation stepwise, until it succeeds (then drops I the handler), or fails (then runs the handler instead). However, if the J evaluation requires a continuation, we drop the handler, since we do not 6 know what the future is when the handler is present. ?@A@?A?@ABBCRepmin with alternatives! H The tree may contain alternatives. The tree is returned such that it < (1) consists of the shortest (left-biassed) alternatives C (2) all leaves replaced with the minimal value occurring in the , tree (for the selected alternatives)  This tests the  feature. @Note: To show that online results are in general necessairy for F cyclic computations, we should actually make the selection process L dependent on the outcome of a previously but already resolved selection. K For example, by keeping a local minimum (from the left), and taking the 6 first alternative that goes under it. Perhaps a min/max game tree would  be a good example for that. HAlso, a lazy value depending on the outcome of two or more alternatives E can only be produced if there is one alternative left. If all the E alternatives would yield the same outermost constructor, still no I value can be produced. This is in general no problem; the reason that E you had alternatives there is likely because it returns different  results. DEFG+Container to keep the contained value lazy HIJKLMNOPQRSTUVWXYZ[\]^_Test 8: lookahead. Q Decisions taken in this example may depend on what happens in the continuation. O We takes as example path-finding in a labyrinth. Taking a step that brings us  back to a position where we'1ve been before is an immediate failure. However, 9 the possibilities that remain may hit a dead-end later. `%Test 7: collecting multiple results. lZ generates paths: the left subpath is of length n-1 the right subpath is a lot shorter (n  2)  (just for fun).  kX succeeds only for those paths that satisfy a funny criteria via xor. Those it returns.  When it succeeds, l0 emits a progress report collecting that value.  m_ tries out options in a breadth-first way, and concatenates the lists in the progress reports.  n- takes out the list of all succeeding paths. PWe collect these multiple results in a more informative form of progress report a`. The type of $ the watcher is important here. The k2 function does not make any assumptions about the  watcher, however l does. When k) succeeds, it collects that results in a b. abc@A type for the simplest form of progress report: just a message dc that L 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 A involving type of progress report that uses the watcher type. deKTest 1: verify that results are provided when available (online behavior).  With  = this means that the result should be delivered, independent G of the failure. Failure is just considered to be a bottom-value: if it's never R needed in the continuation, it is not triggered. This is different in comparison  to strict evaluation. -A short remark about the type signature: the  is the type of failures such T a computation may emit during stepwise evaluation (during lazy evaluation, this is  simply a bottom value). Both  and  are typical examples.  The dcQ type is the type of the progress reports. The watcher type is given seperately. 5 A computation may state how it is evaluated: either may use lazy evaluation (via the  type ) or use sequential evaluation (via the type  ). For most U computations this is not an issue: either keep it polymorphic (like in this example 5 via a universally quantified type variable), or use  (the preferred default  evaluation mode). I We also do not care about the watcher type for progress reports of type dc . Either 9 keep the type polymorphic, or simply choose a type like  (or '()'). V Finally, the last type of the value that evaluation of the computation results into.  The first three parameters to + typically stay the same, the latter three + may vary from one computation to another. fDTest 2: verify that the selection process causes strict evaluation.  Despite running   on f(, strict evaluation will be done on the O 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). g*Test 3: verify selection of alternatives. 7 The non-failure alternative is selected in this case.  The  annotation here we can use because we can. A -annotation is Q 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. hijkbWe may not make an assumption about the watcher here, hence we keep the watcher type polymorphic. lmn<Strips steps (thus evaluates sequentially), until it hits a b message, which is subsequently  delivers. opqrstuvExample labyrinth wxyz{|Test 8b: Explicit sharing. P 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 P form a DAG. However, certain paths on this DAG we may traverse more than once. B In this example, we ensure that we only traverse each path once. 9Note, however, that it memoizes the outcome (i.e. the Lab' value), produced in 4 a context potentially different from ours. The key loc in this case, however,  identifies a unique context. }ITest 8c: Ambiguity and online-ness improvement. If two parallel branches 8 converge on a single path, kill one of the branches. R A much more effective approach is to keep a shared trail via an IORef and kill R any branch that makes a move to a square already visited. However, the current N approach is more interesting: it takes a bit longer until common paths are  found. ~,Monoid instance for use in combination with . In practice, you'll not  use 9, but write more complicated merging strategies instead. KBCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Acdefghij`baklmn_^YZ[\]UVWXSTRPQOJNMLKopqrstuvwxGHIyz{|}~CFEDBABCFEDDEFGHIHIJNMLKKLMNOPQQRSTTUVWXVWXYZ[\]Z[\]^_`baabcddefghijklmnopqrstuvwxyz{|}~non-portable (GADTs) experimentalariem@cs.uu.nl?  !"#$%&'()*+,-./0123456789:;<=>?@A7We use slightly simpler stepwise computations for AGs. 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).  Unwraps a Closure E  !"#$%&'()*+,-./0123456789:;<=>?@A     !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOOPQRSTUVWWXYZ[\]^_`abcdeffghhijklmnopqrstuvwxyz{|}~stepwise-1.0.2Control.Monad.Stepwise.UnsafeControl.Monad.Stepwise.CoreControl.Monad.Stepwise.DerivedControl.Monad.Stepwise.ExamplesControl.Monad.Stepwise.AGControl.Monad.Stepwise.ProofsControl.Monad.Stepwisebase Unsafe.Coerce unsafeCoerceinlinePerformIO ghc7compat MemoEnvRefReportUnavailFutureFailureProgressFinished StepHandleFailed LookaheadFinStep AnyFailure AnyWatcher SequentialLazy TranscoderTransCodeOutTcFailed TcReportsCodeInTcFailTcDoneTcLazyTcReportStepwiselazyEvalseqEvalnext smallStep localStep stepwiseEval transcode translate translate'unsafeTranslateabortfinalfailureunspecifiedFailureresumelazily sequentiallyforceSequentialsharetasknextTaskhandlereportperformcloseproceedinfoemit lookahead newMemoEnv memoSteps mergeSteps localChoice globalChoiceRepMinBinTreeAltBinLeafBranch pickBranchDirWestSouthEastNorthPathInstrsPosLabStepsWalkedLabChnLCchnPoschnTrailLabInLIinLabinEndinMemoLab'LabJCollectItest1test2test3test4test5test6test7atest7bmergetest7csearchpos2keyfinishedmoveforward<<|>bestlab1 exp8Succsbranchembed' pathClosepathOnememoize convergeKillrunAheadrepminsemTreetest9 exp9SuccsCompSynInhChildinvokeMemoEnv MemoEntryEntry TraceLevelNoticeToplevelNoneErrors StepCursorCursorHandleHandles OneHandle NoHandlesForceSequential AllowLazyEvalModeEnvRefEnv ModeStack DefaultMode ExplicitMode Transcode TransCoder TransNone OperationCodeBindParentsRootContStepCellCellStepRefRefGHC.BasefailMonadInfoPendingAheadIndModeUnpureFailFinal pushEvalMode pushModeStack popEvalMode peekEvalModeunsafeIOtransformers-0.2.2.0Control.Monad.IO.ClassliftIO lookupRefputReftakeRef createRef extractVareval evalStackcontainsHandlenextRoot nextReportnext'remember nextHandle updateHandle nextPendingapplyTranscoder restoreModemodeElim pushStackrunCoder Data.MaybeNothing emptyCoder pushCoder composeCoders composeCoderpushOperwithMode coerceMode traceLeveltrace printTraceMsgmemoKey$fErrorAnyFailure$fMonoidAnyFailure$fMonadIOStepwise$fMonadFixStepwise$fMonadStepwise$fAlternativeStepwise$fMonadErroreStepwise mtl-2.0.1.0Control.Monad.Error.Class throwError catchErrorControl.Monad.FixMonadFixGHC.RealdivStringControl.Applicative<|> $fMonoidI exp1Succs exp1Fails exp1Fails2 exp2Fails exp3Succs exp4Succs exp5Succs exp5Fails exp6Succs test7Succs