bf-cata-1.1

Description

Some combinators to express breadth-first evaluation of catamorphisms, which allows you to stepwise evaluate the results of children. If, during the evaluation of an alternative, a choice needs to be made between taking the results of its children, with these combinators, you can stepwise evaluate the children in parallel, until a choice can be made. Until a choice is made, evaluation proceeds strictly; after a choice is made, evaluation proceeds lazily. What constitutes to be a step is determined by the callee.

Synopsis

# Documentation

newtype Child i n Source

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

Constructors

 Child (Inh n -> Comp i n)

data family Inh n :: *Source

data family Syn n :: *Source

data Comp i n Source

Computation of synthesized attributes of nonterminal of type `n`. It is a trace of `Info`-effects, that keeps track of the intermediate states of the tree (using `Pending`), ending ultimately in the synthesized values (using `Final`). Operationally, we lift `Info`-values over `Pending`-values, thereby gradually rewriting the latter, until it results in a `Final`.

invoke :: Child i n -> Inh n -> Comp i nSource

Unwraps a `Child`

final :: Syn n -> Comp i nSource

Wrapper for final result.

info :: i -> Comp i n -> Comp i nSource

Wrapper for an effect.

resume :: Comp i n' -> (Syn n' -> Comp i n) -> Comp i nSource

Create a |Pending| computation that waits for the given computation.

data Inject Source

Injection of steps as conventional call

lazyEval :: Comp i n -> Syn nSource

Lazy evaluation of a computation. Note: we cannot inspect the effect-trace, as it would sequentialize the evaluation of children.

oneStep :: Comp i n -> Outcome i nSource

One step strict evaluation. Reduction proceeds until the computation is either finished or yields an `Info`-effect.

data Outcome i n Source

Result of one step evaluation: either the final result or an updated computation. What constitutes to a step depends on the application: evaluation proceeds until an outcome can be given.

Constructors

 Fin !(Syn n) Step !i (Comp i n)