Interaction trees as machines #
An interaction tree is itself a machine, in two ways.
ITree.toDynSystemreads the tree as a dynamical system over its raw polynomialITree.Poly F α. The state is the tree, the exposed position is its head node, and an answer selects the child. Its behavior is the raw M-type tree (ITree.behavior_toDynSystem).ITree.toDynComputationreads the tree as a returning computation overF + y, the resumption-with-tau encoding ofPolyFun.ITree.ResumptionWithTau. Silent steps become visible unit queries, so the bounded, chunked andIOrunners ofDynComputationapply to interaction trees, and a silent step can be counted like any other query. Its denotation isITree.toResumptionWithTau(ITree.denote_toDynComputation).
ITree.withSilentSteps lifts a handler of visible events to F + y: it acknowledges each silent
step with pure () and never invokes the visible handler on one. Silent steps still consume the
budget of the toDynComputation runners, and a finite budget makes no claim of termination or
productivity.
An interaction tree as a dynamical system over its raw polynomial: expose the head node of the M-type representation and update to the selected child.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The behavior of toDynSystem is the raw M-type representation.
An interaction tree as a returning computation over F + y: silent steps become visible unit
queries.
Equations
Instances For
The denotation of toDynComputation is the resumption-with-tau encoding.
Interpret visible operations by handler and acknowledge silent steps internally, so a
handler for F runs toDynComputation.
Equations
- ITree.withSilentSteps handler = handler.sum fun (x : PFunctor.y.A) => pure PUnit.unit
Instances For
Visible operations go to handler. The position is stated at the reduced type
F.A ⊕ PUnit, the form simp leaves the implicit arguments of Sum.inl in, so the lemma fires
under simp, simp only and rw alike.
Silent steps are acknowledged without consulting handler; stated at F.A ⊕ PUnit for the
same reason as withSilentSteps_visible.