Documentation

PolyFun.Realizability.Closure

Closure properties of admissible realizability #

Realizability is closed under the operations that leave a machine's dynamics intact or reindex them by an admissible map, and it transports along refinements of the ambient step class. Each theorem asks of the class exactly the structure its construction consumes:

Budget monotonicity and the bridge from the bounded to the unbounded predicate live in PolyFun.Realizability.Basic.

Where the structure is spent #

Distributivity is consumed in exactly one place, and only twice: the composite update? of a sequential composition splits on the state summand, and then on the first phase's readout, each time retaining the answer index. The readout side of the same composition needs no products at all — only comp_mem, elim_mem, and inr_mem.

None of this needs a decidable-equality test on interface positions, and that is a consequence of update? being partial: each phase's own transition already returns none on an answer it is not waiting for, so the composite inherits the tag test rather than performing it. With the total updateFlat no uniform equation holds and an equality-test axiom would be forced; see PolyFun.Realizability.Machine.

Interface transport is the one place a tag test does surface, because pulling an answer back along a lens must compare it against the position the lens exposes. That is why wrap takes a Lens.IsAdmissible hypothesis while seqComp takes none.

Immediately returning programs #

theorem PFunctor.DynSystem.DynComputation.isRealizableBy_ofFn {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {f : α → β} (hf : C.Hom bd.input bd.out f) :
IsRealizableBy C bd fun (input : α) => FreeM.pure (f input)

An immediately returning program is realizable exactly when its returning map is admissible. The realizing machine takes the result type itself as its state: head is the left injection and the flattened transition is the first projection.

theorem PFunctor.DynSystem.DynComputation.isRealizableBy_pure {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {value : β} (hvalue : C.Hom bd.input bd.out fun (x : α) => value) :
IsRealizableBy C bd fun (x : α) => FreeM.pure value

A constant program is realizable whenever the constant is: the special case of isRealizableBy_ofFn at a constant returning map.

Input precomposition #

theorem PFunctor.DynSystem.DynComputation.IsRealizableBy.precomp {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {program : α → p.FreeM β} {γ : Type u} {inputRep : C.Str γ} {f : γ → α} (h : IsRealizableBy C bd program) (hf : C.Hom inputRep bd.input f) :
IsRealizableBy C (bd.withInput inputRep) fun (input : γ) => program (f input)

Input precomposition along an admissible map. The realizing machine is the original one with a new initialization, so its readout and transition maps — and hence their admissibility proofs — are shared definitionally.

theorem PFunctor.DynSystem.DynComputation.IsRealizableWithin.precomp {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {program : α → p.FreeM β} {γ : Type u} {inputRep : C.Str γ} {f : γ → α} {k : ℕ} (h : IsRealizableWithin C bd program k) (hf : C.Hom inputRep bd.input f) :
IsRealizableWithin C (bd.withInput inputRep) (fun (input : γ) => program (f input)) k

Input precomposition preserves the query budget: reindexing inputs performs no queries of its own.

Result postcomposition #

theorem PFunctor.DynSystem.DynComputation.IsRealizableBy.mapResult {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {program : α → p.FreeM β} {γ : Type u} {outRep : C.Str γ} {g : β → γ} (h : IsRealizableBy C bd program) (hg : C.Hom bd.out outRep g) :
IsRealizableBy C (bd.withOut outRep) fun (input : α) => FreeM.map g (program input)

Postcomposition on results along an admissible map. The realizing machine is the original one with its readout postcomposed, which acts on the one-step readout β ⊕ p.A by Sum.map and leaves the flattened transition alone.

theorem PFunctor.DynSystem.DynComputation.IsRealizableWithin.mapResult {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {program : α → p.FreeM β} {γ : Type u} {outRep : C.Str γ} {g : β → γ} {k : ℕ} (h : IsRealizableWithin C bd program k) (hg : C.Hom bd.out outRep g) :
IsRealizableWithin C (bd.withOut outRep) (fun (input : α) => FreeM.map g (program input)) k

Postcomposition on results preserves the query budget: mapping a returned value performs no queries of its own.

Sequential composition #

theorem PFunctor.DynSystem.DynComputation.IsRealizableBy.seqComp {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} [D : C.IsDistributive] {γ : Type u} {outRep : C.Str γ} {program₁ : α → p.FreeM β} {program₂ : β → p.FreeM γ} (h₁ : IsRealizableBy C bd program₁) (h₂ : IsRealizableBy C (bd.mid outRep) program₂) :
IsRealizableBy C (bd.withOut outRep) fun (input : α) => (program₁ input).bind program₂

Closure under bind. A realization of the first phase and a realization of the second compose into a realization of their sequential composition.

The middle boundary is bd.mid outRep: the second phase reads the first's results and shares its interface. Distributivity is what the composite transition needs, and only there — the readout side needs no products at all.

theorem PFunctor.DynSystem.DynComputation.IsRealizableWithin.seqComp {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} [D : C.IsDistributive] {γ : Type u} {outRep : C.Str γ} {program₁ : α → p.FreeM β} {program₂ : β → p.FreeM γ} {k₁ k₂ : ℕ} (h₁ : IsRealizableWithin C bd program₁ k₁) (h₂ : IsRealizableWithin C (bd.mid outRep) program₂ k₂) :
IsRealizableWithin C (bd.withOut outRep) (fun (input : α) => (program₁ input).bind program₂) (k₁ + k₂)

Sequential composition of bounded realizations, with additive budgets. The query budget is exactly the one the underlying ImplementsWithin.seqComp supplies.

Interface transport #

structure PFunctor.Lens.IsAdmissible (C : StepClass) [C.HasProd] [C.HasSum] [C.HasOption] {p q : PFunctor.{u, u}} [DecidableEq q.A] {α β : Type u} (bd : DynSystem.DynComputation.Boundary C p α β) (posRep : C.Str q.A) (idxRep : C.Str q.Idx) (lens : p.Lens q) :

A lens is C-admissible, relative to a boundary for its source interface and representations for its target interface, when its position map and its flattened index pullback are C-morphisms.

Two fields rather than one existential: the pullback is uniquely determined by the lens, so it is Lens.pullHeadIdx and only its admissibility is a hypothesis.

Unlike Lens.IsCartesian this has no .id and no .comp, and that is not an oversight. pullHeadIdx compares the incoming answer's tag against the position the lens exposes, so even the identity lens's pullback performs a decidable equality test on positions — which is exactly the operation the rest of this layer is designed not to require of a step class. Admissibility of a lens is therefore a genuine hypothesis about the class, satisfiable by every realistic one but not derivable from the mixins. That is also why seqComp needs no such hypothesis: each phase's own update? performs its own tag test internally.

Instances For
    theorem PFunctor.DynSystem.DynComputation.IsRealizableBy.wrap {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {program : α → p.FreeM β} {q : PFunctor.{u, u}} [DecidableEq q.A] (posRep : C.Str q.A) (idxRep : C.Str q.Idx) {lens : p.Lens q} (hlens : Lens.IsAdmissible C bd posRep idxRep lens) (h : IsRealizableBy C bd program) :
    IsRealizableBy C (bd.withInterface posRep idxRep) fun (input : α) => FreeM.mapLens lens (program input)

    Interface transport along an admissible lens. The readout is post-composed with the lens's position map; the transition pulls an answer back along the lens before feeding it to the underlying computation.

    The resolved case needs no constant-map axiom: pullHeadIdx returns none at a resolved readout, and the underlying update? is none there anyway.

    theorem PFunctor.DynSystem.DynComputation.IsRealizableWithin.wrap {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {program : α → p.FreeM β} {q : PFunctor.{u, u}} [DecidableEq q.A] (posRep : C.Str q.A) (idxRep : C.Str q.Idx) {lens : p.Lens q} {k : ℕ} (hlens : Lens.IsAdmissible C bd posRep idxRep lens) (h : IsRealizableWithin C bd program k) :
    IsRealizableWithin C (bd.withInterface posRep idxRep) (fun (input : α) => FreeM.mapLens lens (program input)) k

    Interface transport preserves the query budget: a lens relabels positions and reindexes directions, leaving the branching structure alone.

    Enlarging the step class #

    theorem PFunctor.DynSystem.DynComputation.IsRealizableBy.mono {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {program : α → p.FreeM β} {D : StepClass} [D.HasProd] [D.HasSum] [D.HasOption] (Ref : C.Refines D) (h : IsRealizableBy C bd program) :

    Realizability transports along a refinement of step classes: a realization by an admissible machine for a small class is one for every larger class.

    theorem PFunctor.DynSystem.DynComputation.IsRealizableWithin.mono' {p : PFunctor.{u, u}} {α β : Type u} {C : StepClass} [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [DecidableEq p.A] {bd : Boundary C p α β} {program : α → p.FreeM β} {D : StepClass} [D.HasProd] [D.HasSum] [D.HasOption] {k : ℕ} (Ref : C.Refines D) (h : IsRealizableWithin C bd program k) :

    Bounded realizability transports along a refinement of step classes.