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:
isRealizableBy_ofFn— an immediately returning program, realized by the one-step machine whose states are its own results. Needs the returning map to be admissible.IsRealizableBy.precomp/IsRealizableWithin.precomp— input precomposition, realized bysetInit. The machine, its state representation, and both of its remaining step maps are untouched, so only the initialization obligation changes.IsRealizableBy.mapResult/IsRealizableWithin.mapResult— postcomposition on results, realized bymapResult. The readout gains aSum.mapand the transition is unchanged.IsRealizableBy.seqComp/IsRealizableWithin.seqComp— closure underFreeM.bind, realized byseqComp. The state is the coproduct of the two phases' states, and budgets add. NeedsIsDistributive.IsRealizableBy.wrap/IsRealizableWithin.wrap— interface transport along a lens, realized bywrap. Needs the lens to beLens.IsAdmissible.IsRealizableBy.mono/IsRealizableWithin.mono'— transport along aStepClass.Refines.
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 #
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.
A constant program is realizable whenever the constant is: the special case
of isRealizableBy_ofFn at a constant returning map.
Input precomposition #
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.
Input precomposition preserves the query budget: reindexing inputs performs no queries of its own.
Result postcomposition #
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.
Postcomposition on results preserves the query budget: mapping a returned value performs no queries of its own.
Sequential composition #
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.
Sequential composition of bounded realizations, with additive budgets. The
query budget is exactly the one the underlying ImplementsWithin.seqComp
supplies.
Interface transport #
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.
The position map is admissible.
- onPull : C.Hom (StepClass.HasProd.prod bd.head idxRep) (StepClass.HasOption.option bd.idx) (lens.pullHeadIdx β)
The flattened index pullback is admissible.
Instances For
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.
Interface transport preserves the query budget: a lens relabels positions and reindexes directions, leaving the branching structure alone.
Enlarging the step class #
Realizability transports along a refinement of step classes: a realization by an admissible machine for a small class is one for every larger class.
Bounded realizability transports along a refinement of step classes.