circuits
Safe HaskellNone
LanguageGHC2024

Circuit.System

Description

A Moore machine fibered over a polynomial interface p.

  newtype SystemT t arr s p = SystemT (Body t s arr (Dir p) (Pos p))
  • The base is the state s.
  • The fiber/interface is the polynomial p, with positions Pos p and directions Dir p.
  • The span shape is s (s, Dir p) - Pos p.
  • Moore because the observable output Pos p depends on the state s, not directly on the current input direction. The direction is consumed to compute the next state; then the position is read from that state.

For a monomial Mono i o:

  Dir (Mono i o) = i
  Pos (Mono i o) = o

so System (->) s (Mono i o) collapses to the ordinary Moore body (s, i) -> (s, o). The mooreSystem constructor makes this explicit: it takes a transition s -> a -> s and an observation s -> b, then packages them as a Body.

For a general polynomial p, Pos p and Dir p can be branching: the polynomial layer handles sums and products of interfaces, so System is a Moore machine that can branch, offer choices, or run parallel interfaces, all while Body handles the state transition.

In the BLLL picture (Katis–Sabadini–Walters), an F-Moore machine is an F-algebra F E -> E plus an output E -> O. System fits this with state object E = s, endofunctor F = (-) ⊗ Dir p, transition d : s ⊗ Dir p -> s, and output obs : s -> Pos p bundled with the transition in the Body.

Process is the pointed monomial special case: where Process is the existential form ∃s. (s, s -> a -> s, s -> b), System is the polynomial-lens form of the same idea, with p describing the interactive interface.

This module defines the system type, conversions between eval and arrow forms, wiring combinators, and higher-level execution combinators.

Synopsis

Systems

newtype SystemT (t :: Type -> Type -> Type) (arr :: Type -> Type -> Type) s (p :: Poly) Source #

A dynamical system with interface p, carrier s, over base arrow arr, parameterised by the state-pairing tensor t.

Uncurried netlist form: the state and the current input direction are fed together under t, and the result is the next state together with the current output position. For the monomial Mono i o and t = (,) this is exactly the Moore body arr (s, i) (s, o) after collapsing the unit positions.

The cartesian specialisation SystemT (,) is kept as the type synonym System; use system and runSystem to construct and inspect it.

Constructors

SystemT (Body t s arr (Dir p) (Pos p)) 

type System = SystemT (,) Source #

Cartesian systems: the state-pairing tensor is (,).

system :: forall arr s (p :: Poly). arr (s, Dir p) (s, Pos p) -> System arr s p Source #

Construct a cartesian System from its underlying arrow.

runSystem :: forall arr s (p :: Poly). System arr s p -> arr (s, Dir p) (s, Pos p) Source #

Inspect a cartesian System as its underlying arrow.

mooreSystem :: (s -> a -> s) -> (s -> b) -> System (->) s (Mono a b) Source #

Build a monomial System from a step and an observation.

This is the pointed-Moore view of a stateful morphism, expressed directly in System terminology. The state transition s -> a -> s and the observation s -> b are explicit; the seed is supplied later (for example by systemToProcess).

Eval / arrow conversion

class SystemEval (p :: Poly) where Source #

Helpers for translating between the Eval presentation and the arrow presentation of a (->) system. These extend the netlist view to Sum.

Methods

evalToSystem :: Eval p x -> (Pos p, Dir p -> x) Source #

evalFromSystem :: Pos p -> (Dir p -> x) -> Eval p x Source #

probeDir :: Dir p Source #

Instances

Instances details
SystemEval 'Y Source # 
Instance details

Defined in Circuit.System

Methods

evalToSystem :: Eval 'Y x -> (Pos 'Y, Dir 'Y -> x) Source #

evalFromSystem :: Pos 'Y -> (Dir 'Y -> x) -> Eval 'Y x Source #

probeDir :: Dir 'Y Source #

SystemEval ('Const a) Source # 
Instance details

Defined in Circuit.System

Methods

evalToSystem :: Eval ('Const a) x -> (Pos ('Const a), Dir ('Const a) -> x) Source #

evalFromSystem :: Pos ('Const a) -> (Dir ('Const a) -> x) -> Eval ('Const a) x Source #

probeDir :: Dir ('Const a) Source #

SystemEval ('Exp a) Source # 
Instance details

Defined in Circuit.System

Methods

evalToSystem :: Eval ('Exp a) x -> (Pos ('Exp a), Dir ('Exp a) -> x) Source #

evalFromSystem :: Pos ('Exp a) -> (Dir ('Exp a) -> x) -> Eval ('Exp a) x Source #

probeDir :: Dir ('Exp a) Source #

(SystemEval p, SystemEval q) => SystemEval ('Comp p q) Source # 
Instance details

Defined in Circuit.System

Methods

evalToSystem :: Eval ('Comp p q) x -> (Pos ('Comp p q), Dir ('Comp p q) -> x) Source #

evalFromSystem :: Pos ('Comp p q) -> (Dir ('Comp p q) -> x) -> Eval ('Comp p q) x Source #

probeDir :: Dir ('Comp p q) Source #

(SystemEval p, SystemEval q) => SystemEval ('Prod p q) Source # 
Instance details

Defined in Circuit.System

Methods

evalToSystem :: Eval ('Prod p q) x -> (Pos ('Prod p q), Dir ('Prod p q) -> x) Source #

evalFromSystem :: Pos ('Prod p q) -> (Dir ('Prod p q) -> x) -> Eval ('Prod p q) x Source #

probeDir :: Dir ('Prod p q) Source #

(SystemEval p, SystemEval q) => SystemEval ('Sum p q) Source # 
Instance details

Defined in Circuit.System

Methods

evalToSystem :: Eval ('Sum p q) x -> (Pos ('Sum p q), Dir ('Sum p q) -> x) Source #

evalFromSystem :: Pos ('Sum p q) -> (Dir ('Sum p q) -> x) -> Eval ('Sum p q) x Source #

probeDir :: Dir ('Sum p q) Source #

(SystemEval p, SystemEval q) => SystemEval ('Tensor p q) Source # 
Instance details

Defined in Circuit.System

Methods

evalToSystem :: Eval ('Tensor p q) x -> (Pos ('Tensor p q), Dir ('Tensor p q) -> x) Source #

evalFromSystem :: Pos ('Tensor p q) -> (Dir ('Tensor p q) -> x) -> Eval ('Tensor p q) x Source #

probeDir :: Dir ('Tensor p q) Source #

fromEvalSystem :: forall (p :: Poly) s. SystemEval p => (s -> Eval p s) -> System (->) s p Source #

Convert an eval-form (->) system into the arrow form.

toEvalSystem :: forall (p :: Poly) s. SystemEval p => System (->) s p -> s -> Eval p s Source #

Convert an arrow-form (->) system back into eval form.

This is a Moore observation: the position is read from the state alone, with the direction supplied only to compute the next state. Correctness therefore requires that the system be Moore at the call site — the position must not depend on the direction. Internally the direction is probeDir, which is lazily unused for the polynomial shapes where it is defined; any strict forcing of the direction (a bang pattern, seq, or a strict tuple in a user-written body) will turn toEvalSystem into a runtime error rather than a wrong answer.

step :: forall (p :: Poly) s. SystemEval p => System (->) s p -> s -> Eval p s Source #

Run one step: observe the current p-output from state s.

Monomial helpers

monoDir :: Dir (Mono i o) -> i Source #

Extract the monomial direction from its 'Either Void' encoding.

monoIn :: i -> Dir (Mono i o) Source #

Inject a monomial direction into its 'Either Void' encoding.

Tensor wiring

parWiring :: forall s (p :: Poly) t (q :: Poly). System (->) s p -> System (->) t q -> System (->) (s, t) ('Tensor p q) Source #

Place two Moore systems side by side: interface p ⊗ q, state (s, t).

This is the entry point for acyclic wiring over the Dirichlet tensor — boxes in parallel, pins assigned jointly. The wired interface can be mapped with parT (wire-then-map).

Channel-pole view of systems

data SomePoles (t :: Type -> k1 -> k2) (arr :: k2 -> k2 -> Type) (a :: k1) (b :: k1) where Source #

An existentially-quantified pair of channel poles over a body, carrying its seed. The shape mirrors SomeBody.

Constructors

SomePoles :: forall {k1} {k2} s (t :: Type -> k1 -> k2) (arr :: k2 -> k2 -> Type) (a :: k1) (b :: k1). s -> Poles (Body t s arr) a b -> SomePoles t arr a b 

runSomePoles :: SomePoles (,) (->) a b -> [a] -> [b] Source #

Run an existentially-packed pair of poles over a list of inputs.

This is the (,) / (->) specialisation; SomePoles is parametric in the tensor and arrow so that other shapes can reuse the existential packaging.

systemToPolesWithProbe :: forall (p :: Poly) s. Dir p -> System (->) s p -> Poles (Body (,) s (->)) (Dir p) (Pos p) Source #

Convert a (->) System into companion/conjoint channel poles over Body.

The write pole runs the step and discards the output position; the read pole fabricates an observation by re-stepping the system with the supplied probe direction. This works only when the read can be reasonably approximated by a single probe direction; for an honest Moore observation prefer systemWithSeedToPoles.

systemWithSeedToPoles :: forall s (p :: Poly). s -> (s -> Pos p) -> System (->) s p -> SomePoles (,) (->) (Dir p) (Pos p) Source #

Convert a pointed System into companion/conjoint channel poles over Body.

The state carrier is the system's state s and the seed s0 is carried by SomePoles. The write pole steps with the supplied direction; the read pole observes the current state without stepping, using the supplied observation function.

Running monomial systems

runSystemMono :: System (->) s (Mono i o) -> s -> (o, i -> s) Source #

Run a monomial (->) system at a state, exposing the output position and the state-transition function.

Lenses

systemAsLens :: System (->) s (Mono i o) -> Morphism (Mono s s) (Mono i o) Source #

The coalgebra-as-lens isomorphism.

A monomial system System (->) s (Mono i o) is exactly a lens S y^S -> Mono i o: the current state s determines the output position o, and each input direction i determines the next state s.

This is the bridge to Spivak's presentation: System s p ≅ Poly(S y^S, p).

lensAsSystem :: Morphism (Mono s s) (Mono i o) -> System (->) s (Mono i o) Source #

Inverse of systemAsLens: build a system from a lens S y^S -> Mono i o.

duplicateSystem :: System (->) s (Mono o s) -> System (->) s ('Comp (Mono o s) (Mono o s)) Source #

Comultiplication for an observable system: the output position is the state. The result is a system over the two-step interface Mono o s ◁ Mono o s, so that feeding a pair of inputs (o1, o2) runs the original system for two steps.

Branches

branchSystem :: (s -> Bool) -> System (->) s (Mono i o) -> System (->) s (Mono i o) -> System (->) s ('Sum (Mono i o) (Mono i o)) Source #

Build a system whose interface is the coproduct of two monomial interfaces.

The carrier state selects the active branch at each step. This is the level-2 grammar operator on the span fragment: choice lives in the polynomial interface (Sum) rather than in the carrier-level 'if'.

runSystemSum :: System (->) s ('Sum (Mono i o) (Mono i o)) -> s -> (Either o o, i -> s) Source #

Run a system with a homogeneous sum-of-monomials interface.

branchSystemHet :: (s -> Bool) -> System (->) s (Mono i1 o1) -> System (->) s (Mono i2 o2) -> System (->) s ('Sum (Mono i1 o1) (Mono i2 o2)) Source #

Build a system whose interface is the coproduct of two different monomial interfaces. The carrier state selects the active branch at each step.

runSystemSumHet :: System (->) s ('Sum (Mono i1 o1) (Mono i2 o2)) -> s -> SumStep s o1 i1 o2 i2 Source #

Run a heterogeneous sum-interface system.

data SumStep s o1 i1 o2 i2 where Source #

A single step of a heterogeneous sum-interface system. The GADT encodes the position-dependent input type: the left branch consumes an i1, the right branch consumes an i2.

Constructors

SumStepL :: forall o1 i1 s o2 i2. o1 -> (i1 -> s) -> SumStep s o1 i1 o2 i2 
SumStepR :: forall o2 i2 s o1 i1. o2 -> (i2 -> s) -> SumStep s o1 i1 o2 i2 

Coalgebras

data Coalgebra s (p :: Poly) (q :: Poly) Source #

Spivak's [p,q]-coalgebra. State s is runtime, not a type index.

  • act gives the wiring pattern as a polynomial morphism.
  • upd takes a state and an input observation in p and returns an output observation in q, i.e. a Step pairing the presented position with its own direction consumer.

Constructors

Coalgebra 

Fields

type Step s (q :: Poly) = Eval q s Source #

A step observation in q, parameterized by state. Eval is already the GADT that pairs each position with its branch-appropriate direction consumer, so it avoids the flat 'Dir q' family that makes sums impossible.

coalgebraToSystem :: forall (q :: Poly) s. SystemEval q => Coalgebra s 'Y q -> System (->) s q Source #

Run a Coalgebra s 'Y q as a System over q.

composeCoalgebra :: forall (p :: Poly) (q :: Poly) s t. (Netlist p, Netlist q) => Coalgebra s 'Y p -> Coalgebra t 'Y q -> Coalgebra (s, t) 'Y ('Comp p q) Source #

Sequential composition of two closed coalgebras via the composition product.

systemToCoalgebraMono :: System (->) s (Mono i o) -> Coalgebra s 'Y (Mono i o) Source #

Convert a monomial System into a Coalgebra s 'Y (Mono i o).