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.
PFunctor.DynSystem S p— ap-dynamical system with state setS, i.e. a lensselfMonomial S ⟹ p.PFunctor.MooreMachine S O I— the special case over the interfaceO y^ I(output setO, input setI), recovering classical Moore machines.PFunctor.DeterministicAutomaton O I— a Moore machine with a distinguished start state.
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.
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 maptoFunA), andupdate : (s : S) → p.B (expose s) → S— the next state, given a direction at the exposed position (the lens's direction maptoFunB).
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
- PFunctor.DynSystem S p = (PFunctor.selfMonomial S).Lens p
Instances For
The position exposed at each state (the "output" of the system): the lens's position map under its dynamical name.
Instances For
The transition: given a direction at the exposed position, the next state. The lens's direction map under its dynamical name.
Instances For
Build a dynamical system from its dynamical data; definitionally Lens.mk
(and so also writable as expose ⇆ update).
Equations
- PFunctor.DynSystem.mk' expose update = { toFunA := expose, toFunB := update }
Instances For
Normalize the lens position map of a dynamical system to expose.
Normalize the lens direction map of a dynamical system to update.
The coalgebra structure map #
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.
Instances For
Concrete steps and step relations #
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.
Instances For
The source state of a concrete step.
Instances For
A relation between concrete steps of two dynamical systems. Unlike a relation on bare directions, the source states are explicit first-class data.
Instances For
Equality of concrete steps, the identity for relational composition.
Equations
Instances For
Relational composition of step relations: Mathlib's Relation.Comp.
Equations
- first.comp second = Relation.Comp first second
Instances For
Relational composition of concrete-step relations is associative.
The permissive relation accepting every pair of concrete steps.
Equations
Instances For
Reverse a step relation by flipping its arguments: flip.
Instances For
Reversing a relational composite reverses the order of its factors.
Conjunction of step relations.
Instances For
Alias of PFunctor.DynSystem.StepRel.reverse_inf.
Synchronized concrete steps over a shared interface expose equal positions and select equal directions up to transport along that equality.
Equations
Instances For
Bundled dynamical systems #
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.
The dynamical system on the bundled state type.
Instances For
Moore machines and deterministic automata #
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
- PFunctor.MooreMachine S O I = PFunctor.DynSystem S (PFunctor.monomial O I)
Instances For
The Moore output at each state.
Equations
Instances For
The transition function S → I → S.
Equations
Instances For
Build a Moore machine from an output function and a transition function,
using the classical field names; definitionally out ⇆ tr.
Equations
- PFunctor.MooreMachine.mk' out tr = { toFunA := out, toFunB := tr }
Instances For
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.
The transition function.
- start : self.State
The initial state.
Instances For
The Moore machine underlying a deterministic automaton (forgetting the start state).
Equations
- a.toMooreMachine = { toFunA := a.output, toFunB := a.transition }
Instances For
Closed systems, points, and sections #
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
- p.Point = PFunctor.y.Lens p
Instances For
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
- PFunctor.sectionLens σ = PFunctor.Lens.toLinear (fun (x : p.A) => PUnit.unit) σ
Instances For
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
The pure state transition of a closed system.
Equations
- s.step st = PFunctor.DynSystem.update s st PUnit.unit
Instances For
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.