Documentation

PolyFun.PFunctor.Dynamical.Basic

Dynamical systems as dependent lenses #

Following Niu–Spivak, Polynomial Functors: A Mathematical Theory of Interaction (Chapter 4), a p-dynamical system with states S is a dependent lens out of the self-state y^ polynomial: DynSystem S p is definitionally Lens (selfMonomial S) p, so the entire PFunctor.Lens combinator library applies to dynamical systems on the nose — wrapping a system along a wiring lens is literally lens composition. The lens's position map is the system's expose (what the system reads off its state, valued in the positions p.A) and its direction map is update (how an incoming direction p.B (expose s) evolves the state); both are provided as definitional accessors under the dynamical names. Equivalently, repackaging expose / update as out : S → p.Obj S (DynSystem.out) exhibits a dynamical system as an F-coalgebra of the extension functor of p, with a Coalg p.Obj instance: dynamical systems are the coalgebras of polynomial functors.

The combinators that build new systems from old (parallel product, wrappers, wiring diagrams) live in PolyFun.PFunctor.Dynamical.Combinators; running a system lives in PolyFun.PFunctor.Dynamical.Run and …Dynamical.Trajectory.

@[reducible, inline]
abbrev PFunctor.DynSystem (S : Type u) (p : PFunctor.{uA, uB}) :
Type (max (max uB uA) u)

A p-dynamical system with states S (Niu–Spivak §4.2, Def 4.18): a dependent lens selfMonomial S ⟹ p. Under the dynamical accessors this is

  • expose : S → p.A — the position the system currently presents (the lens's position map toFunA), and
  • update : (s : S) → p.B (expose s) → S — the next state, given a direction at the exposed position (the lens's direction map toFunB).

The identification is definitional — "a dynamical system is a lens" — so lens combinators, lens equalities, and the lens composition ∘ₗ apply to dynamical systems directly.

Equations
Instances For
    def PFunctor.DynSystem.expose {S : Type u} {p : PFunctor.{uA, uB}} (s : DynSystem S p) :
    S → p.A

    The position exposed at each state (the "output" of the system): the lens's position map under its dynamical name.

    Equations
    Instances For
      def PFunctor.DynSystem.update {S : Type u} {p : PFunctor.{uA, uB}} (s : DynSystem S p) (st : S) :
      p.B (s.expose st) → S

      The transition: given a direction at the exposed position, the next state. The lens's direction map under its dynamical name.

      Equations
      Instances For
        def PFunctor.DynSystem.mk' {S : Type u} {p : PFunctor.{uA, uB}} (expose : S → p.A) (update : (st : S) → p.B (expose st) → S) :

        Build a dynamical system from its dynamical data; definitionally Lens.mk (and so also writable as expose ⇆ update).

        Equations
        Instances For
          @[simp]
          theorem PFunctor.DynSystem.expose_mk' {S : Type u} {p : PFunctor.{uA, uB}} (e : S → p.A) (t : (st : S) → p.B (e st) → S) :
          (mk' e t).expose = e
          @[simp]
          theorem PFunctor.DynSystem.update_mk' {S : Type u} {p : PFunctor.{uA, uB}} (e : S → p.A) (t : (st : S) → p.B (e st) → S) :
          (mk' e t).update = t
          @[simp]

          Normalize the lens position map of a dynamical system to expose.

          @[simp]

          Normalize the lens direction map of a dynamical system to update.

          The coalgebra structure map #

          def PFunctor.DynSystem.out {S : Type u} {p : PFunctor.{uA, uB}} (s : DynSystem S p) (st : S) :
          ↑p S

          The coalgebra structure map of a dynamical system: at each state, the exposed position together with the transition function at that position. A DynSystem S p is exactly a coalgebra S → p.Obj S of the extension functor of p, unpacked into the expose / update accessors.

          Equations
          Instances For
            @[simp]
            theorem PFunctor.DynSystem.out_fst {S : Type u} {p : PFunctor.{uA, uB}} (s : DynSystem S p) (st : S) :
            (s.out st).fst = s.expose st
            @[simp]
            theorem PFunctor.DynSystem.out_snd {S : Type u} {p : PFunctor.{uA, uB}} (s : DynSystem S p) (st : S) (d : p.B (s.expose st)) :
            (s.out st).snd d = s.update st d
            @[reducible, inline]
            abbrev PFunctor.DynSystem.coalg {S : Type u} {p : PFunctor.{uA, uB}} (s : DynSystem S p) :
            Coalg (↑p) S

            Every dynamical system is an F-coalgebra of its interface's extension functor. Not an instance: the system s does not appear in the type Coalg p.Obj S, so synthesis could not select one.

            Equations
            Instances For

              Concrete steps and step relations #

              @[reducible, inline]
              abbrev PFunctor.DynSystem.Step {S : Type u} {p : PFunctor.{uA, uB}} (s : DynSystem S p) :
              Type (max u uB)

              A concrete step offered by s: its source state together with one direction available at the position exposed by that state. The target state is determined by s.update, so it is not stored separately.

              Equations
              Instances For
                @[reducible, inline]
                abbrev PFunctor.DynSystem.Step.source {S : Type u} {p : PFunctor.{uA, uB}} {s : DynSystem S p} (step : s.Step) :
                S

                The source state of a concrete step.

                Equations
                Instances For
                  @[reducible, inline]
                  abbrev PFunctor.DynSystem.Step.direction {S : Type u} {p : PFunctor.{uA, uB}} {s : DynSystem S p} (step : s.Step) :
                  p.B (s.expose step.source)

                  The direction selected by a concrete step at its source state.

                  Equations
                  Instances For
                    def PFunctor.DynSystem.Step.target {S : Type u} {p : PFunctor.{uA, uB}} {s : DynSystem S p} (step : s.Step) :
                    S

                    The target state determined by executing a concrete step.

                    Equations
                    Instances For
                      @[reducible, inline]
                      abbrev PFunctor.DynSystem.StepRel {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} (s₁ : DynSystem S₁ p) (s₂ : DynSystem S₂ q) :
                      Type (max (max (max uB u₁) uB₂) u₂)

                      A relation between concrete steps of two dynamical systems. Unlike a relation on bare directions, the source states are explicit first-class data.

                      Equations
                      Instances For

                        Equality of concrete steps, the identity for relational composition.

                        Equations
                        Instances For
                          @[simp]
                          theorem PFunctor.DynSystem.StepRel.id_apply {S : Type u} {p : PFunctor.{uA, uB}} (s : DynSystem S p) (step₁ step₂ : s.Step) :
                          id s step₁ step₂ ↔ step₁ = step₂
                          def PFunctor.DynSystem.StepRel.comp {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} {S₃ : Type u₃} {r : PFunctor.{uA₃, uB₃}} {s₃ : DynSystem S₃ r} (first : s₁.StepRel s₂) (second : s₂.StepRel s₃) :
                          s₁.StepRel s₃

                          Relational composition of step relations: Mathlib's Relation.Comp.

                          Equations
                          Instances For
                            @[simp]
                            theorem PFunctor.DynSystem.StepRel.comp_apply {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} {S₃ : Type u₃} {r : PFunctor.{uA₃, uB₃}} {s₃ : DynSystem S₃ r} (first : s₁.StepRel s₂) (second : s₂.StepRel s₃) (step₁ : s₁.Step) (step₃ : s₃.Step) :
                            first.comp second step₁ step₃ ↔ ∃ (step₂ : s₂.Step), first step₁ step₂ ∧ second step₂ step₃
                            @[simp]
                            theorem PFunctor.DynSystem.StepRel.comp_id {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (rel : s₁.StepRel s₂) :
                            rel.comp (id s₂) = rel
                            @[simp]
                            theorem PFunctor.DynSystem.StepRel.id_comp {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (rel : s₁.StepRel s₂) :
                            (id s₁).comp rel = rel
                            theorem PFunctor.DynSystem.StepRel.comp_assoc {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} {S₃ : Type u₃} {S₄ : Type u₄} {r : PFunctor.{uA₃, uB₃}} {t : PFunctor.{uA₄, uB₄}} {s₃ : DynSystem S₃ r} {s₄ : DynSystem S₄ t} (first : s₁.StepRel s₂) (second : s₂.StepRel s₃) (third : s₃.StepRel s₄) :
                            (first.comp second).comp third = first.comp (second.comp third)

                            Relational composition of concrete-step relations is associative.

                            @[reducible, inline, deprecated "use `⊤`, the top of the lattice of relations" (since := "2026-10-19")]
                            abbrev PFunctor.DynSystem.StepRel.top {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} :
                            s₁.StepRel s₂

                            The permissive relation accepting every pair of concrete steps.

                            Equations
                            Instances For
                              @[deprecated "use `Pi.top_apply`" (since := "2026-10-19")]
                              theorem PFunctor.DynSystem.StepRel.top_apply {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (step₁ : s₁.Step) (step₂ : s₂.Step) :
                              ⊤ step₁ step₂
                              def PFunctor.DynSystem.StepRel.reverse {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (rel : s₁.StepRel s₂) :
                              s₂.StepRel s₁

                              Reverse a step relation by flipping its arguments: flip.

                              Equations
                              Instances For
                                @[simp]
                                theorem PFunctor.DynSystem.StepRel.reverse_apply {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (rel : s₁.StepRel s₂) (step₂ : s₂.Step) (step₁ : s₁.Step) :
                                rel.reverse step₂ step₁ ↔ rel step₁ step₂
                                @[simp]
                                theorem PFunctor.DynSystem.StepRel.reverse_reverse {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (rel : s₁.StepRel s₂) :
                                rel.reverse.reverse = rel
                                @[simp]
                                theorem PFunctor.DynSystem.StepRel.reverse_top {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} :
                                theorem PFunctor.DynSystem.StepRel.reverse_comp {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} {S₃ : Type u₃} {r : PFunctor.{uA₃, uB₃}} {s₃ : DynSystem S₃ r} (first : s₁.StepRel s₂) (second : s₂.StepRel s₃) :
                                (first.comp second).reverse = second.reverse.comp first.reverse

                                Reversing a relational composite reverses the order of its factors.

                                @[reducible, inline, deprecated "use `⊓`, the meet of the lattice of relations" (since := "2026-10-19")]
                                abbrev PFunctor.DynSystem.StepRel.inter {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (first second : s₁.StepRel s₂) :
                                s₁.StepRel s₂

                                Conjunction of step relations.

                                Equations
                                • first.inter second = first ⊓ second
                                Instances For
                                  @[deprecated "use `Pi.inf_apply`" (since := "2026-10-19")]
                                  theorem PFunctor.DynSystem.StepRel.inter_apply {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (first second : s₁.StepRel s₂) (step₁ : s₁.Step) (step₂ : s₂.Step) :
                                  (first ⊓ second) step₁ step₂ ↔ first step₁ step₂ ∧ second step₁ step₂
                                  @[simp]
                                  theorem PFunctor.DynSystem.StepRel.reverse_inf {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (first second : s₁.StepRel s₂) :
                                  (first ⊓ second).reverse = first.reverse ⊓ second.reverse
                                  @[deprecated PFunctor.DynSystem.StepRel.reverse_inf (since := "2026-10-19")]
                                  theorem PFunctor.DynSystem.StepRel.reverse_inter {p : PFunctor.{uA, uB}} {q : PFunctor.{uA₂, uB₂}} {S₁ : Type u₁} {S₂ : Type u₂} {s₁ : DynSystem S₁ p} {s₂ : DynSystem S₂ q} (first second : s₁.StepRel s₂) :
                                  (first ⊓ second).reverse = first.reverse ⊓ second.reverse

                                  Alias of PFunctor.DynSystem.StepRel.reverse_inf.

                                  def PFunctor.DynSystem.StepRel.sync {p : PFunctor.{uA, uB}} {S₁ : Type u₁} {S₂ : Type u₂} (t₁ : DynSystem S₁ p) (t₂ : DynSystem S₂ p) :
                                  t₁.StepRel t₂

                                  Synchronized concrete steps over a shared interface expose equal positions and select equal directions up to transport along that equality.

                                  Equations
                                  Instances For
                                    @[simp]
                                    theorem PFunctor.DynSystem.StepRel.sync_apply {p : PFunctor.{uA, uB}} {S₁ : Type u₁} {S₂ : Type u₂} (t₁ : DynSystem S₁ p) (t₂ : DynSystem S₂ p) (st₁ : S₁) (d₁ : p.B (t₁.expose st₁)) (st₂ : S₂) (d₂ : p.B (t₂.expose st₂)) :
                                    sync t₁ t₂ ⟨st₁, d₁⟩ ⟨st₂, d₂⟩ ↔ t₁.expose st₁ = t₂.expose st₂ ∧ d₁ ≍ d₂

                                    Bundled dynamical systems #

                                    structure PFunctor.DynSystem.Machine (p : PFunctor.{uA, uB}) :
                                    Type (max (max (u + 1) uA) uB)

                                    A dynamical system with its state type bundled. Specialized bundles such as DynComputation, Labeled, Ticketed, and SafetySpec extend this common core, so their underlying dynamics are uniformly available as .toDynSystem.

                                    • State : Type u

                                      The state type of the machine.

                                    • toDynSystem : DynSystem self.State p

                                      The dynamical system on the bundled state type.

                                    Instances For

                                      Moore machines and deterministic automata #

                                      @[reducible, inline]
                                      abbrev PFunctor.MooreMachine (S : Type u) (O : Type uO) (I : Type uI) :
                                      Type (max (max uI uO) u)

                                      A Moore machine with states S, output set O and input set I: a dynamical system over the monomial interface O y^ I. Unpacking, expose : S → O is the Moore output and update : S → I → S is the transition function (Niu–Spivak §4.1).

                                      Equations
                                      Instances For
                                        def PFunctor.MooreMachine.output {S : Type u} {O : Type uO} {I : Type uI} (m : MooreMachine S O I) :
                                        S → O

                                        The Moore output at each state.

                                        Equations
                                        Instances For
                                          def PFunctor.MooreMachine.transition {S : Type u} {O : Type uO} {I : Type uI} (m : MooreMachine S O I) :
                                          S → I → S

                                          The transition function S → I → S.

                                          Equations
                                          Instances For
                                            def PFunctor.MooreMachine.mk' {S : Type u} {O : Type uO} {I : Type uI} (out : S → O) (tr : S → I → S) :

                                            Build a Moore machine from an output function and a transition function, using the classical field names; definitionally out ⇆ tr.

                                            Equations
                                            Instances For
                                              @[simp]
                                              theorem PFunctor.MooreMachine.output_mk' {S : Type u} {O : Type uO} {I : Type uI} (out : S → O) (tr : S → I → S) :
                                              (mk' out tr).output = out
                                              @[simp]
                                              theorem PFunctor.MooreMachine.transition_mk' {S : Type u} {O : Type uO} {I : Type uI} (out : S → O) (tr : S → I → S) :
                                              (mk' out tr).transition = tr
                                              structure PFunctor.DeterministicAutomaton (O : Type uO) (I : Type uI) :
                                              Type (max (max (u + 1) uI) uO)

                                              A deterministic automaton over input alphabet I with observation set O (commonly O = Bool for acceptance): a state machine with an output, a transition, and a distinguished start state (Niu–Spivak §4.1.1). It induces a MooreMachine via toMooreMachine.

                                              • State : Type u

                                                The set of states.

                                              • output : self.State → O

                                                The output observed at each state.

                                              • transition : self.State → I → self.State

                                                The transition function.

                                              • start : self.State

                                                The initial state.

                                              Instances For

                                                The Moore machine underlying a deterministic automaton (forgetting the start state).

                                                Equations
                                                Instances For

                                                  Closed systems, points, and sections #

                                                  @[reducible, inline]
                                                  abbrev PFunctor.Point (p : PFunctor.{uA, uB}) :
                                                  Type (max uB uA)

                                                  A point of an interface p is a lens y ⟹ p (the book's y ⟹ p): it picks a position and discards directions, so Point p ≅ p.A. It is the data of a generalized element of the interface, not enough on its own to close a system.

                                                  Equations
                                                  Instances For
                                                    def PFunctor.sectionLens {p : PFunctor.{uA, uB}} (σ : (a : p.A) → p.B a) :

                                                    The section p ⟹ y picking the direction σ a at each position a. Unpacking a Section p, the position map is trivial and the direction map is σ.

                                                    Equations
                                                    Instances For
                                                      @[reducible, inline]
                                                      abbrev PFunctor.Closed (S : Type u) :
                                                      Type (max (max uB uA) u)

                                                      A closed dynamical system on states S is a y-system: its interface is the composition unit, so the dynamics reduce to a pure state endofunction.

                                                      Equations
                                                      Instances For
                                                        def PFunctor.Closed.step {S : Type u} (s : Closed S) (st : S) :
                                                        S

                                                        The pure state transition of a closed system.

                                                        Equations
                                                        Instances For
                                                          def PFunctor.Closed.iterate {S : Type u} (s : Closed S) (st : S) :
                                                          ℕ → S

                                                          The state of a closed system after n steps from st: the n-fold iterate of step. The closed system runs autonomously, so its behaviour is this ℕ-indexed trajectory of states.

                                                          Equations
                                                          Instances For
                                                            @[simp]
                                                            theorem PFunctor.Closed.iterate_zero {S : Type u} (s : Closed S) (st : S) :
                                                            s.iterate st 0 = st
                                                            theorem PFunctor.Closed.iterate_succ {S : Type u} (s : Closed S) (st : S) (n : ℕ) :
                                                            s.iterate st (n + 1) = s.iterate (s.step st) n