Well-founded stopping trees (TypeTree.Telescope) #
Telescope round step is the indexed W-type generated by either stopping at
the current state or extending by one protocol round and branching over all of
its paths. Equivalently, it is the initial algebra of the indexed
polynomial
H X s = PUnit ⊕ ((tr : Path (round s)) → X (step s tr)).
Given
- a state space
St : Type v, - a round assignment
round : St → TypeTree.{u}, - a state transition
step : (s : St) → Path (round s) → St,
an inhabitant of Telescope round step s₀ is a well-founded stopping tree.
It may be infinitely branching, and its branches need not have a common finite
height. Moreover, .done s is available at every state, so mere inhabitation
does not prove termination of the underlying state machine. A termination
certificate would instead restrict where stopping is allowed (for example by
a halting predicate or a well-founded ranking).
Universal property #
PFunctor.FreeM.StoppingTree.Algebra, fold, and fold_unique formalize the
initial-algebra universal property. toTypeTree is the fold into the algebra
(fun _ => TypeTree, .done, fun s cont => (round s).append cont).
References #
- Hancock–Setzer (2000), recursion over interaction interfaces.
- Niu–Spivak (2024), polynomial functors as the algebra of interaction.
Initial-algebra presentation of a state-machine telescope of TypeTrees.
At each state s : St, an inhabitant either stops (.done s) or extends
by running the round round s : TypeTree and recursing into
Telescope round step (step s tr) for every path tr. The inductive is
well-founded, but may be infinitely branching and is not itself a termination
certificate because stopping is permitted at every state.
The (round, step) data is exactly a coalgebra of the undecorated step
polynomial TypeTree.stepPoly — a PFunctor.DynSystem St TypeTree.stepPoly
unpacked on its states.
Equations
- Interaction.TypeTree.Telescope round step = PFunctor.FreeM.StoppingTree (fun (s : St) => (round s).Path) step
Instances For
Constructor wrapper for terminating a TypeTree.Telescope.
Instances For
Constructor wrapper for extending a TypeTree.Telescope by one round.
Equations
Instances For
The TypeTree-valued algebra interpreting a stopping leaf as the substitution
unit and a transition layer as substitution multiplication.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Universal property of toTypeTree: any interpretation that sends stopping
leaves to TypeTree.done and transition layers to substitution multiplication
agrees pointwise with toTypeTree.