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.
- newtype Child i n = Child (Inh n -> Comp i n)
- data family Inh n :: *
- data family Syn n :: *
- data Comp i n
- invoke :: Child i n -> Inh n -> Comp i n
- final :: Syn n -> Comp i n
- info :: i -> Comp i n -> Comp i n
- resume :: Comp i n' -> (Syn n' -> Comp i n) -> Comp i n
- inject :: i -> Comp i Inject
- sem_Inject :: Child i Inject
- data Inject
- lazyEval :: Comp i n -> Syn n
- oneStep :: Comp i n -> Outcome i n
- data Outcome i n
Documentation
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
).
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
.
resume :: Comp i n' -> (Syn n' -> Comp i n) -> Comp i nSource
Create a |Pending| computation that waits for the given computation.
sem_Inject :: Child i InjectSource
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.