Documentation

PolyFun.Interaction.Basic.Telescope

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

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 #

@[reducible, inline]
abbrev Interaction.TypeTree.Telescope {St : Type v} (round : St → TypeTree) (step : (s : St) → (round s).Path → St) :
St → Type (max u v)

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
Instances For
    @[reducible, inline]
    abbrev Interaction.TypeTree.Telescope.done {St : Type v} {round : St → TypeTree} {step : (s : St) → (round s).Path → St} (s : St) :
    Telescope round step s

    Constructor wrapper for terminating a TypeTree.Telescope.

    Equations
    Instances For
      @[reducible, inline]
      abbrev Interaction.TypeTree.Telescope.extend {St : Type v} {round : St → TypeTree} {step : (s : St) → (round s).Path → St} (s : St) (cont : (tr : (round s).Path) → Telescope round step (step s tr)) :
      Telescope round step s

      Constructor wrapper for extending a TypeTree.Telescope by one round.

      Equations
      Instances For
        def Interaction.TypeTree.Telescope.toTypeTreeAlgebra {St : Type v} {round : St → TypeTree} {step : (s : St) → (round s).Path → St} :

        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
          def Interaction.TypeTree.Telescope.toTypeTree {St : Type v} {round : St → TypeTree} {step : (s : St) → (round s).Path → St} {s : St} :
          Telescope round step s → TypeTree

          Fold a Telescope into a concrete TypeTree using the canonical substitution monoid: done is its unit and extend is its multiplication/append.

          Equations
          Instances For
            @[simp]
            theorem Interaction.TypeTree.Telescope.toTypeTree_done {St : Type v} {round : St → TypeTree} {step : (s : St) → (round s).Path → St} (s : St) :
            @[simp]
            theorem Interaction.TypeTree.Telescope.toTypeTree_extend {St : Type v} {round : St → TypeTree} {step : (s : St) → (round s).Path → St} (s : St) (cont : (tr : (round s).Path) → Telescope round step (step s tr)) :
            (extend s cont).toTypeTree = PFunctor.FreeM.append (round s) fun (tr : PFunctor.FreeM.Path (round s)) => (cont tr).toTypeTree
            theorem Interaction.TypeTree.Telescope.eq_toTypeTree {St : Type v} {round : St → TypeTree} {step : (s : St) → (round s).Path → St} (f : {s : St} → Telescope round step s → TypeTree) (hDone : ∀ (s : St), f (done s) = TypeTree.done) (hExtend : ∀ (s : St) (cont : (tr : (round s).Path) → Telescope round step (step s tr)), f (extend s cont) = substMonoid.mul.toFunA ⟨round s, fun (tr : substMonoid.carrier.B (round s)) => f (cont tr)⟩) {s : St} (tree : Telescope round step s) :
            f tree = tree.toTypeTree

            Universal property of toTypeTree: any interpretation that sends stopping leaves to TypeTree.done and transition layers to substitution multiplication agrees pointwise with toTypeTree.