Documentation

PolyFun.PFunctor.Dynamical.Responder.Behavior

State-free responder behavior #

An ordinary state-free responder behavior for P is the terminal coalgebra M (P ⊸ y). Given a proof-relevant responder coalgebra, Display.Coalgebra.toM maps a state and its current witness into the greatest displayed fixed point over that ordinary behavior:

Display.M (Display.responder S) (R.behavior state).

The displayed fixed point is not a Function.Fiber of a forgetful M-map. There is only a covariant chart from the total responder display to the base responder polynomial: a bare query cannot supply the precondition witness needed by the displayed child. Display.M retains that genuine branching instead of postulating a nonexistent lens.

Structural state-free reindexing keeps the source and target interface universes independent. Only its categorical composition laws retain the homogeneous source/intermediate response-universe constraint of FreeM.liftM.

The terminal P-coalgebra as a dynamical system whose states are state-free behaviors.

Equations
Instances For
    def PFunctor.Display.Coalgebra.Presented {P : PFunctor.{uA, uB}} {State : Type uS} (system : DynSystem State P) (F : State → Type uF) (tree : P.M) :
    Type (max uS uF)

    States presenting a fixed ordinary behavior, together with their current displayed witness. This is the indexed seed family used to quotient a state presentation through terminal displayed semantics.

    Equations
    Instances For
      def PFunctor.Display.Coalgebra.presentedStep {P : PFunctor.{uA, uB}} {S : P.Display} {State : Type uS} (system : DynSystem State P) (F : State → Type uF) (displayed : S.Coalgebra system.out F) (tree : P.M) :
      Presented system F tree → S.Obj (Presented system F) tree.dest

      One displayed step on behavior-indexed presentation states.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        def PFunctor.Display.Coalgebra.toM {P : PFunctor.{uA, uB}} {S : P.Display} {State : Type uS} (system : DynSystem State P) (F : State → Type uF) (displayed : S.Coalgebra system.out F) (state : State) (witness : F state) :
        S.M (system.behavior state)

        Map a proof-relevant state presentation into its state-free displayed behavior. Distinct or unreachable presentation states are intentionally identified when they generate the same coinductive evidence.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          theorem PFunctor.Display.Coalgebra.dest_toM {P : PFunctor.{uA, uB}} {S : P.Display} {State : Type uS} (system : DynSystem State P) (F : State → Type uF) (displayed : S.Coalgebra system.out F) (state : State) (witness : F state) :
          (toM system F displayed state witness).dest = Obj.map (fun (tree : P.M) (presentation : Presented system F tree) => M.corec (Presented system F) (presentedStep system F displayed) tree presentation) (system.behavior state).dest (presentedStep system F displayed (system.behavior state) ⟨state, ({ down := ⋯ }, witness)⟩)

          The first unfolding of state-free displayed semantics.

          The destructor is the canonical displayed coalgebra on terminal behavior states.

          Equations
          Instances For
            theorem PFunctor.Responder.behavior_eq_of_responderMap {R : PFunctor.{uA'', uB}} {State₁ : Type uC''} {State₂ : Type uD''} (left : Responder State₁ R) (right : Responder State₂ R) (mapState : State₂ → State₁) (answer_eq : ∀ (state : State₂) (operation : R.A), left.answer (mapState state) operation = right.answer state operation) (next_eq : ∀ (state : State₂) (operation : R.A), left.next (mapState state) operation = mapState (right.next state operation)) (state : State₂) :
            DynSystem.behavior left (mapState state) = DynSystem.behavior right state

            A map of responder states preserving answers and next states preserves the complete coinductive behavior.

            The canonical responder whose states are state-free responder behaviors.

            Equations
            Instances For
              theorem PFunctor.Responder.behavior_child {P : PFunctor.{uA, uB}} {State : Type uS} (R : Responder State P) (state : State) (query : P.A) :

              The child of a presented responder behavior after a query is the behavior of the presented responder's next state.

              @[simp]
              theorem PFunctor.Responder.terminal_answer_behavior {P : PFunctor.{uA, uB}} {State : Type uS} (R : Responder State P) (state : State) (query : P.A) :
              terminal.answer (DynSystem.behavior R state) query = R.answer state query
              @[simp]
              theorem PFunctor.Responder.terminal_next_behavior {P : PFunctor.{uA, uB}} {State : Type uS} (R : Responder State P) (state : State) (query : P.A) :
              terminal.next (DynSystem.behavior R state) query = DynSystem.behavior R (R.next state query)
              theorem PFunctor.Responder.runFree_terminal {Q : PFunctor.{uA', uB'}} {State : Type uS} (R : Responder State Q) {E : Type uE} (program : Q.FreeM E) (state : State) :
              terminal.runFree program (DynSystem.behavior R state) = have result := R.runFree program state; (result.1, DynSystem.behavior R result.2)

              Executing a finite program on terminal state-free behavior preserves the ordinary result and replaces the final presentation state by its behavior.

              Coinductive displayed response #

              def PFunctor.Responder.respondDisplayedEquiv {P : PFunctor.{uA, uB}} (S : P.Display) (behavior : (P.ihom y).M) :
              S.responder.M behavior ≃ ((query : P.A) → (precondition : S.position query) → S.direction query precondition (behavior.head.toFunB query PUnit.unit) × S.responder.M (behavior.children ⟨query, PUnit.unit⟩))

              Destructor equivalence for one displayed responder observation.

              This is the intrinsic form of Aberlé's coinductive DepMealy.appD: a query and precondition witness produce postcondition data and a displayed continuation over the selected ordinary behavior child.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                def PFunctor.Responder.respondDisplayed {P : PFunctor.{uA, uB}} (S : P.Display) {behavior : (P.ihom y).M} (displayedBehavior : S.responder.M behavior) (query : P.A) (precondition : S.position query) :
                S.direction query precondition (behavior.head.toFunB query PUnit.unit) × S.responder.M (behavior.children ⟨query, PUnit.unit⟩)

                Apply one coinductive displayed responder step.

                Equations
                Instances For
                  @[simp]
                  theorem PFunctor.Responder.respondDisplayed_post {P : PFunctor.{uA, uB}} (S : P.Display) {behavior : (P.ihom y).M} (displayedBehavior : S.responder.M behavior) (query : P.A) (precondition : S.position query) :
                  (respondDisplayed S displayedBehavior query precondition).1 = displayedBehavior.head query precondition
                  @[simp]
                  theorem PFunctor.Responder.respondDisplayed_next {P : PFunctor.{uA, uB}} (S : P.Display) {behavior : (P.ihom y).M} (displayedBehavior : S.responder.M behavior) (query : P.A) (precondition : S.position query) :
                  (respondDisplayed S displayedBehavior query precondition).2 = displayedBehavior.child ⟨query, PUnit.unit⟩ precondition
                  theorem PFunctor.Responder.respondDisplayedEquiv_transport {P : PFunctor.{uA, uB}} (S : P.Display) {left right : (P.ihom y).M} (h : left = right) (displayedBehavior : S.responder.M left) :
                  (respondDisplayedEquiv S right) (Display.M.transport h displayedBehavior) = Eq.rec (motive := fun (x : (P.ihom y).M) (h : left = x) => (query : P.A) → (precondition : S.position query) → S.direction query precondition (x.head.toFunB query PUnit.unit) × S.responder.M (x.children ⟨query, PUnit.unit⟩)) ((respondDisplayedEquiv S left) displayedBehavior) h

                  Transporting a displayed behavior transports its complete dependent respondDisplayed observation. This function-level form avoids exposing casts in the postcondition and continuation projections separately.

                  def PFunctor.Responder.IsDisplayedResponseBisimulation {P : PFunctor.{uA, uB}} (S : P.Display) (R : (behavior : (P.ihom y).M) → S.responder.M behavior → S.responder.M behavior → Prop) :

                  A cast-free, observation-shaped bisimulation for displayed responder behaviors. Related values return the same evidence for every query and precondition and have related answer-selected continuations.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    theorem PFunctor.Responder.respondDisplayed_bisim {P : PFunctor.{uA, uB}} (S : P.Display) (R : (behavior : (P.ihom y).M) → S.responder.M behavior → S.responder.M behavior → Prop) (hR : IsDisplayedResponseBisimulation S R) {behavior : (P.ihom y).M} {left right : S.responder.M behavior} (h : R behavior left right) :
                    left = right

                    Observation-shaped responder bisimulation implies equality.

                    def PFunctor.Responder.toDisplayedBehavior {P : PFunctor.{uA, uB}} {State : Type uS} (S : P.Display) (R : Responder State P) (I : State → Type uF) (displayedR : S.responder.Coalgebra (DynSystem.out R) I) (state : State) (witness : I state) :

                    Turn a responder state and its current witness into the corresponding state-free displayed behavior.

                    Equations
                    Instances For
                      theorem PFunctor.Responder.respondDisplayed_toDisplayedBehavior_post {P : PFunctor.{uA, uB}} {State : Type uS} (S : P.Display) (R : Responder State P) (I : State → Type uF) (displayedR : S.responder.Coalgebra (DynSystem.out R) I) (state : State) (witness : I state) (query : P.A) (precondition : S.position query) :
                      (respondDisplayed S (toDisplayedBehavior S R I displayedR state witness) query precondition).1 = ((S.responderCoalgebraEquiv R I) displayedR state witness query precondition).1

                      The postcondition component of state-free respondDisplayed is exactly the local displayed responder-coalgebra obligation.

                      theorem PFunctor.Responder.respondDisplayed_toDisplayedBehavior_next {P : PFunctor.{uA, uB}} {State : Type uS} (S : P.Display) (R : Responder State P) (I : State → Type uF) (displayedR : S.responder.Coalgebra (DynSystem.out R) I) (state : State) (witness : I state) (query : P.A) (precondition : S.position query) :
                      Display.M.transport ⋯ (respondDisplayed S (toDisplayedBehavior S R I displayedR state witness) query precondition).2 = toDisplayedBehavior S R I displayedR (R.next state query) ((S.responderCoalgebraEquiv R I) displayedR state witness query precondition).2

                      The continuation component of state-free respondDisplayed, transported along the ordinary behavior-child equation, is the displayed behavior generated from the locally preserved next-state witness.

                      theorem PFunctor.Responder.runFreeDisplayed_toDisplayedBehavior {P : PFunctor.{uA, uB}} {State : Type uS} (S : P.Display) (R : Responder State P) (I : State → Type uF) (displayedR : S.responder.Coalgebra (DynSystem.out R) I) {E : Type uE} {F : E → Type uC'} (program : P.FreeM E) (displayedProgram : FreeM.Displayed (S.toDisplayedAlgebra F) program) (state : State) (witness : I state) :
                      transportRunEvidence F S.responder.M ⋯ (runFreeDisplayed S terminal (Display.Coalgebra.terminal S.responder) displayedProgram (DynSystem.behavior R state) (toDisplayedBehavior S R I displayedR state witness)) = let result := R.runFree program state; have evidence := runFreeDisplayed S R displayedR displayedProgram state witness; (evidence.1, toDisplayedBehavior S R I displayedR result.2 evidence.2)

                      Executing a displayed finite program against a state-free behavior presented by a displayed responder agrees with executing it against the presenting responder, and presents the resulting final witness again.

                      Reindex a state-free responder behavior by using it as the state of the terminal responder and applying ordinary responder reindexing.

                      Equations
                      Instances For
                        theorem PFunctor.Responder.reindexBehavior_congr {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA', uB'}} {f g : Handler Q.FreeM P} (h : f = g) (behavior : (Q.ihom y).M) :
                        reindexBehavior f behavior = reindexBehavior g behavior

                        State-free behavior reindexing is invariant under equality of its free handler.

                        theorem PFunctor.Responder.reindexBehavior_behavior {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA', uB'}} {State : Type uS} (f : Handler Q.FreeM P) (R : Responder State Q) (state : State) :

                        The state-free reindexing of a presented behavior agrees with reindexing the presenting responder first.

                        @[simp]
                        theorem PFunctor.Responder.reindexBehavior_id {P : PFunctor.{uA, uB}} (behavior : (P.ihom y).M) :
                        reindexBehavior (Handler.id P) behavior = behavior
                        theorem PFunctor.Responder.reindexBehavior_comp {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA', uB}} {RPoly : PFunctor.{uA'', uB'}} (second : Handler RPoly.FreeM Q) (first : Handler Q.FreeM P) (behavior : (RPoly.ihom y).M) :
                        reindexBehavior first (reindexBehavior second behavior) = reindexBehavior (second.comp first) behavior

                        State-free responder reindexing is contravariantly functorial in the same categorical composition order as state-presented reindexing.

                        def PFunctor.Responder.reindexDisplayedBehavior {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA', uB'}} (S : P.Display) (T : Q.Display) (f : Handler Q.FreeM P) (displayedF : S.Handler T f) (behavior : (Q.ihom y).M) (displayedBehavior : T.responder.M behavior) :
                        S.responder.M (reindexBehavior f behavior)

                        Reindex state-free proof-relevant responder behavior through a displayed free handler. The construction is the state-free semantics of G3's reindexCoalgebra, evaluated at the canonical terminal responder.

                        Equations
                        • One or more equations did not get rendered due to their size.
                        Instances For
                          theorem PFunctor.Responder.reindexDisplayedBehavior_congr {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA', uB'}} (S : P.Display) (T : Q.Display) {f g : Handler Q.FreeM P} (h : f = g) (displayedF : S.Handler T f) (displayedG : S.Handler T g) (displayedEq : Display.Handler.transport h displayedF = displayedG) (behavior : (Q.ihom y).M) (displayedBehavior : T.responder.M behavior) :
                          Display.M.transport ⋯ (reindexDisplayedBehavior S T f displayedF behavior displayedBehavior) = reindexDisplayedBehavior S T g displayedG behavior displayedBehavior

                          Displayed state-free reindexing is invariant under simultaneous transport of the base handler and its displayed lift. The sole output transport is the canonical equality of the underlying ordinary behaviors.

                          theorem PFunctor.Responder.respondDisplayed_reindexDisplayedBehavior_post {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA', uB'}} (S : P.Display) (T : Q.Display) (f : Handler Q.FreeM P) (displayedF : S.Handler T f) (behavior : (Q.ihom y).M) (displayedBehavior : T.responder.M behavior) (query : P.A) (precondition : S.position query) :
                          (respondDisplayed S (reindexDisplayedBehavior S T f displayedF behavior displayedBehavior) query precondition).1 = (runFreeDisplayed T terminal (Display.Coalgebra.terminal T.responder) (displayedF query precondition) behavior displayedBehavior).1

                          The postcondition returned by one state-free displayed reindexing step is exactly the postcondition produced by executing the displayed handler program against the target displayed behavior.

                          theorem PFunctor.Responder.respondDisplayed_reindexDisplayedBehavior_next {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA', uB'}} (S : P.Display) (T : Q.Display) (f : Handler Q.FreeM P) (displayedF : S.Handler T f) (behavior : (Q.ihom y).M) (displayedBehavior : T.responder.M behavior) (query : P.A) (precondition : S.position query) :
                          let result := terminal.runFree (f query) behavior; have displayedResult := runFreeDisplayed T terminal (Display.Coalgebra.terminal T.responder) (displayedF query precondition) behavior displayedBehavior; Display.M.transport ⋯ (respondDisplayed S (reindexDisplayedBehavior S T f displayedF behavior displayedBehavior) query precondition).2 = reindexDisplayedBehavior S T f displayedF result.2 displayedResult.2

                          The continuation returned by one state-free displayed reindexing step is the recursively reindexed target continuation produced by displayed program execution, after the canonical ordinary behavior-child transport.

                          theorem PFunctor.Responder.reindexDisplayedBehavior_id {P : PFunctor.{uA, uB}} (S : P.Display) (behavior : (P.ihom y).M) (displayedBehavior : S.responder.M behavior) :
                          Display.M.transport ⋯ (reindexDisplayedBehavior S S (Handler.id P) (Display.Handler.id S) behavior displayedBehavior) = displayedBehavior

                          State-free displayed behavior reindexing preserves identity handlers, after the canonical equality of the underlying ordinary behaviors.

                          theorem PFunctor.Responder.reindexDisplayedBehavior_comp {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA', uB}} {RPoly : PFunctor.{uA'', uB'}} (S : P.Display) (T : Q.Display) (U : RPoly.Display) (second : Handler RPoly.FreeM Q) (dsecond : T.Handler U second) (first : Handler Q.FreeM P) (dfirst : S.Handler T first) (behavior : (RPoly.ihom y).M) (displayedBehavior : U.responder.M behavior) :
                          Display.M.transport ⋯ (reindexDisplayedBehavior S T first dfirst (reindexBehavior second behavior) (reindexDisplayedBehavior T U second dsecond behavior displayedBehavior)) = reindexDisplayedBehavior S U (second.comp first) (dsecond.comp dfirst) behavior displayedBehavior

                          Successive state-free displayed behavior reindexing agrees with reindexing by the displayed Kleisli composite, after the canonical equality of the underlying ordinary behaviors.