Documentation

VCVio.Interaction.UC.OpenTheory

Open composition algebra with monoidal coherence #

This module defines OpenTheory, a boundary-indexed algebra of open systems, together with a granular hierarchy of lawfulness classes capturing increasingly strong equational properties. The split mirrors the categorical distinction between symmetric monoidal, traced symmetric monoidal (Joyal-Street-Verity), and compact closed categories.

Operations #

Class hierarchy #

Data classes (operations beyond the four primitives):

Naturality (Prop classes):

Symmetric monoidal coherence:

Trace algebra (JSV traced symmetric monoidal):

Compact closure (snake / zig-zag):

Plug factorization:

The chain IsMonoidalIsTracedIsCompactClosedHasPlugWireFactor lets each model declare exactly the strength it can honestly satisfy. The free models (Expr.theory, Interp.theory) instantiate the entire chain. The process-backed openTheory in OpenProcessModel.lean instantiates only IsLawful; its monoidal coherence and snake equations hold up to OpenProcessIso, not strict equality.

structure Interaction.UC.OpenTheory :
Type (u + 1)

OpenTheory is a boundary-indexed algebra of open systems.

For each directed boundary Δ, Obj Δ is the type of systems that still expose Δ to an external context. The structure then specifies three primitive composition operations:

  • map changes how an exposed boundary is presented, without changing the internal system;
  • par places two open systems side by side and exposes the tensor of their boundaries;
  • wire connects one shared boundary between two open systems and leaves the remaining outer boundaries exposed; and
  • plug closes an open system against a matching context on the swapped boundary, yielding a closed system.

Lawfulness is stratified into a granular class hierarchy starting at IsLawful and continuing through IsMonoidal, IsTraced, IsCompactClosed, and HasPlugWireFactor (see the module docstring).

Universe polymorphism: one ambient pair of universes for ports and messages on both sides of every boundary, keeping PortBoundary.swap inside the same family of objects.

  • Obj : PortBoundaryType u

    Obj Δ is the type of open systems exposing boundary Δ.

    The boundary is directed: Δ.In is what the surrounding context may send into the system, and Δ.Out is what the system may emit back out.

  • map {Δ₁ Δ₂ : PortBoundary} : Δ₁.Hom Δ₂self.Obj Δ₁self.Obj Δ₂

    Adapt the exposed boundary of an open system along a structural boundary morphism.

    This changes only the presentation of the boundary. The intended reading is that map φ W is the same internal system as W, but viewed through the interface adaptation φ.

  • par {Δ₁ Δ₂ : PortBoundary} : self.Obj Δ₁self.Obj Δ₂self.Obj (Δ₁.tensor Δ₂)

    Place two open systems side by side.

    The resulting system exposes the tensor of the two boundaries: the outside world may interact independently with either side.

  • wire {Δ₁ Γ Δ₂ : PortBoundary} : self.Obj (Δ₁.tensor Γ)self.Obj (Γ.swap.tensor Δ₂)self.Obj (Δ₁.tensor Δ₂)

    Connect one shared boundary between two open systems.

    If the left system exposes boundary Δ₁ ⊗ Γ and the right system exposes boundary swap Γ ⊗ Δ₂, then wire connects the shared middle boundary Γ internally and leaves only the outer boundaries Δ₁ and Δ₂ exposed.

    This is the first local composition primitive beyond plain parallel juxtaposition. It is the right operation for assembling open systems incrementally without forcing immediate total closure.

  • plug {Δ : PortBoundary} : self.Obj Δself.Obj Δ.swapself.Obj PortBoundary.empty

    Close an open system against a matching plug.

    If W : Obj Δ is an open system and K : Obj (PortBoundary.swap Δ) is a context exposing the opposite boundary, then plug W K is the structurally closed result of connecting those two boundaries together.

    This is the minimal closure operation needed for UC-style contextual comparison. More general partial internalization operations can be added later if they are genuinely needed.

Instances For

    Operation-only data classes #

    HasUnit T distinguishes a closed object unit : T.Obj empty, intended to play the role of the symmetric monoidal unit.

    This is purely a data class. Whether unit actually behaves as a left/right unit for par (up to boundary equivalence) is the content of IsMonoidal.

    Instances

      HasIdWire T distinguishes a coevaluation morphism on every boundary, idWire Γ : T.Obj (swap Γ ⊗ Γ), intended to play the role of the categorical unit of duality between Γ and swap Γ.

      This is purely a data class. Whether idWire actually satisfies the zig-zag (snake) identities is the content of IsCompactClosed.

      • idWire (Γ : PortBoundary) : T.Obj (Γ.swap.tensor Γ)

        The identity-wire / coevaluation on boundary Γ: a process exposing swap Γ ⊗ Γ that behaves as a bidirectional relay.

      Instances

        Naturality (functoriality of map and naturality of par/wire/plug) #

        IsLawfulMap T states that boundary adaptation in T behaves functorially.

        This is the first law layer for OpenTheory, and the one we can state without committing to any further monoidal/coherence structure on boundaries.

        • map_id {Δ : PortBoundary} (W : T.Obj Δ) : T.map (PortBoundary.Hom.id Δ) W = W

          Adapting a system along the identity boundary morphism does nothing.

        • map_comp {Δ₁ Δ₂ Δ₃ : PortBoundary} (g : Δ₂.Hom Δ₃) (f : Δ₁.Hom Δ₂) (W : T.Obj Δ₁) : T.map (g.comp f) W = T.map g (T.map f W)

          Adapting along a composite boundary morphism is the same as adapting in two successive steps.

        Instances

          IsLawfulPar T states that parallel composition in T is natural with respect to boundary adaptation.

          This is the first structural law for par that does not require introducing a separate theory of boundary isomorphisms. Associativity and unit laws can be added later once that boundary-equivalence vocabulary is in place.

          Instances

            IsLawfulWire T states that partial wiring in T is natural with respect to boundary adaptation.

            This is the first law for local composition: adapting the still-exposed left/right outer boundaries can be pushed inside a wire.

            Transporting the shared middle boundary itself is a subtler question because PortBoundary.Hom.swap is contravariant. The corresponding law should be stated later using boundary equivalences or a more symmetric vocabulary.

            Instances

              IsLawfulPlug T states that plugging in T is natural with respect to boundary adaptation.

              This is the first structural law for plug: adapting the open side before closure is equivalent to adapting the matching plug on the swapped boundary.

              Instances

                IsLawful T is the first bundled law package for an open-composition theory.

                At this stage it only records:

                • functoriality of map,
                • naturality of par, and
                • naturality of wire, and
                • naturality of plug.

                Unit, associativity, and symmetry laws for open composition should be added later, once the library settles on the right notion of boundary equivalence.

                Instances

                  Symmetric monoidal coherence #

                  IsMonoidal T extends IsLawful T and HasUnit T with the symmetric monoidal coherence laws for par: associativity, commutativity (braiding), and left/right unit laws up to boundary equivalence.

                  Pentagon and hexagon coherence conditions are deferred: they are derivable in the free models and hold trivially for the concrete model up to process isomorphism.

                  Instances

                    Trace algebra (Joyal-Street-Verity traced symmetric monoidal) #

                    IsTraced T extends IsMonoidal T with the three trace axioms of a Joyal-Street-Verity traced symmetric monoidal category, formulated for the binary wire operator: wire associativity (vanishing II), wire-par superposition, and wire commutativity (yanking via the symmetry).

                    These axioms make sense without HasIdWire or any snake equation: they are purely about the algebra of wire itself and how it interacts with par. A model satisfies IsTraced exactly when its wire operation behaves like a JSV trace; the existence of duals (i.e., compact closure) is a separate class layered on top.

                    Instances

                      Compact closure (snake / zig-zag identities) #

                      IsCompactClosed T extends IsTraced T and HasIdWire T with the snake (zig-zag) identities relating the coevaluation idWire to wire, plus the identification unit_eq of the monoidal unit with the trivial coevaluation.

                      These laws say that swap Γ is a categorical dual of Γ, witnessed by idWire Γ as the coevaluation. In our setting the trace algebra and the duality structure are independent (since wire is a primitive, not derived from η/ε), so IsCompactClosed extends IsTraced rather than living side-by-side with it: a model that satisfies IsCompactClosed also has a JSV trace.

                      Instances

                        Plug-wire factorization #

                        HasPlugWireFactor T extends IsCompactClosed T with the three laws identifying plug as a derived operation: plug factors through wire via the unit (plug_eq_wire), and closure of a parallel or wired composite factors through closure of one component (plug_par_left/plug_wire_left).

                        This is the "everything bundle" used by downstream UC composition theorems: [HasPlugWireFactor T] automatically supplies all of IsCompactClosed T, IsTraced T, IsMonoidal T, IsLawful T, HasUnit T, and HasIdWire T through the inheritance chain.

                        Instances
                          @[reducible, inline]

                          Closed T is the type of closed systems in the open-composition theory T.

                          These are precisely the systems with no remaining exposed inputs or outputs.

                          Instances For
                            @[reducible, inline]

                            Plug T Δ is the type of contexts that can close a Δ-shaped open system in the theory T.

                            Such a context exposes the swapped boundary: it accepts what the open system emits, and emits what the open system accepts.

                            Instances For
                              @[reducible, inline]
                              abbrev Interaction.UC.OpenTheory.close (T : OpenTheory) {Δ : PortBoundary} :
                              T.Obj ΔT.Plug ΔT.Closed

                              Close an open system against a matching plug.

                              This is just the plug operation restated using the helper names Closed and Plug, which often match the UC / contextual-equivalence reading more closely than the raw swapped-boundary formulation.

                              Instances For
                                @[reducible, inline]
                                abbrev Interaction.UC.OpenTheory.mapEquiv (T : OpenTheory) {Δ₁ Δ₂ : PortBoundary} :
                                Δ₁.Equiv Δ₂T.Obj Δ₁T.Obj Δ₂

                                Transport an open system along a boundary equivalence.

                                This is the equivalence-level companion to map: instead of an arbitrary one-way boundary adaptation, it uses a canonical directed boundary isomorphism. In practice this is the convenient way to reassociate, swap, or drop empty boundary fragments once those facts have been expressed as PortBoundary.Equivs.

                                Instances For
                                  @[simp]

                                  Adapting along the identity boundary morphism leaves an open system unchanged.

                                  theorem Interaction.UC.OpenTheory.map_comp {T : OpenTheory} [T.IsLawfulMap] {Δ₁ Δ₂ Δ₃ : PortBoundary} (g : Δ₂.Hom Δ₃) (f : Δ₁.Hom Δ₂) (W : T.Obj Δ₁) :
                                  T.map (g.comp f) W = T.map g (T.map f W)

                                  Adapting along a composite boundary morphism is the same as adapting in two successive steps.

                                  @[simp]

                                  Mapping along the identity boundary equivalence does nothing.

                                  theorem Interaction.UC.OpenTheory.mapEquiv_trans {T : OpenTheory} [T.IsLawfulMap] {Δ₁ Δ₂ Δ₃ : PortBoundary} (e₁ : Δ₁.Equiv Δ₂) (e₂ : Δ₂.Equiv Δ₃) (W : T.Obj Δ₁) :
                                  T.mapEquiv (e₁.trans e₂) W = T.mapEquiv e₂ (T.mapEquiv e₁ W)

                                  Mapping along a composite boundary equivalence is the same as mapping in two successive equivalence-guided steps.

                                  @[simp]
                                  theorem Interaction.UC.OpenTheory.mapEquiv_symm_cancel {T : OpenTheory} [T.IsLawfulMap] {Δ₁ Δ₂ : PortBoundary} (e : Δ₁.Equiv Δ₂) (W : T.Obj Δ₁) :
                                  T.mapEquiv e.symm (T.mapEquiv e W) = W
                                  @[simp]
                                  theorem Interaction.UC.OpenTheory.mapEquiv_cancel_symm {T : OpenTheory} [T.IsLawfulMap] {Δ₁ Δ₂ : PortBoundary} (e : Δ₁.Equiv Δ₂) (W : T.Obj Δ₂) :
                                  T.mapEquiv e (T.mapEquiv e.symm W) = W
                                  theorem Interaction.UC.OpenTheory.map_par {T : OpenTheory} [T.IsLawfulPar] {Δ₁ Δ₁' Δ₂ Δ₂' : PortBoundary} (f₁ : Δ₁.Hom Δ₁') (f₂ : Δ₂.Hom Δ₂') (W₁ : T.Obj Δ₁) (W₂ : T.Obj Δ₂) :
                                  T.map (f₁.tensor f₂) (T.par W₁ W₂) = T.par (T.map f₁ W₁) (T.map f₂ W₂)

                                  Parallel composition is natural with respect to boundary adaptation.

                                  theorem Interaction.UC.OpenTheory.mapEquiv_par {T : OpenTheory} [T.IsLawfulPar] {Δ₁ Δ₁' Δ₂ Δ₂' : PortBoundary} (e₁ : Δ₁.Equiv Δ₁') (e₂ : Δ₂.Equiv Δ₂') (W₁ : T.Obj Δ₁) (W₂ : T.Obj Δ₂) :
                                  T.mapEquiv (e₁.tensorCongr e₂) (T.par W₁ W₂) = T.par (T.mapEquiv e₁ W₁) (T.mapEquiv e₂ W₂)

                                  Parallel composition is natural with respect to boundary equivalences.

                                  This is the equivalence-guided companion to map_par: canonical reshaping of the left and right boundaries may be pushed inside par.

                                  theorem Interaction.UC.OpenTheory.map_wire {T : OpenTheory} [T.IsLawfulWire] {Δ₁ Δ₁' Γ Δ₂ Δ₂' : PortBoundary} (f₁ : Δ₁.Hom Δ₁') (f₂ : Δ₂.Hom Δ₂') (W₁ : T.Obj (Δ₁.tensor Γ)) (W₂ : T.Obj (Γ.swap.tensor Δ₂)) :
                                  T.map (f₁.tensor f₂) (T.wire W₁ W₂) = T.wire (T.map (f₁.tensor (PortBoundary.Hom.id Γ)) W₁) (T.map ((PortBoundary.Hom.id Γ.swap).tensor f₂) W₂)

                                  Partial wiring is natural with respect to boundary adaptation.

                                  theorem Interaction.UC.OpenTheory.mapEquiv_wire {T : OpenTheory} [T.IsLawfulWire] {Δ₁ Δ₁' Γ Δ₂ Δ₂' : PortBoundary} (e₁ : Δ₁.Equiv Δ₁') (e₂ : Δ₂.Equiv Δ₂') (W₁ : T.Obj (Δ₁.tensor Γ)) (W₂ : T.Obj (Γ.swap.tensor Δ₂)) :
                                  T.mapEquiv (e₁.tensorCongr e₂) (T.wire W₁ W₂) = T.wire (T.mapEquiv (e₁.tensorCongr (PortBoundary.Equiv.refl Γ)) W₁) (T.mapEquiv ((PortBoundary.Equiv.refl Γ.swap).tensorCongr e₂) W₂)

                                  Partial wiring is natural with respect to boundary equivalences on the still exposed outer boundaries.

                                  As in map_wire, the shared middle boundary is held fixed in this first law layer. The point is that canonical reassociation or symmetry on the outer interfaces can already be pushed through wire without enlarging the primitive kernel of OpenTheory.

                                  theorem Interaction.UC.OpenTheory.map_plug {T : OpenTheory} [T.IsLawfulPlug] {Δ₁ Δ₂ : PortBoundary} (f : Δ₁.Hom Δ₂) (W : T.Obj Δ₁) (K : T.Obj Δ₂.swap) :
                                  T.plug (T.map f W) K = T.plug W (T.map f.swap K)

                                  Plugging is natural with respect to boundary adaptation.

                                  theorem Interaction.UC.OpenTheory.mapEquiv_plug {T : OpenTheory} [T.IsLawfulPlug] {Δ₁ Δ₂ : PortBoundary} (e : Δ₁.Equiv Δ₂) (W : T.Obj Δ₁) (K : T.Obj Δ₂.swap) :
                                  T.plug (T.mapEquiv e W) K = T.plug W (T.map e.toHom.swap K)

                                  Plugging is natural with respect to boundary equivalence.

                                  This is the boundary-equivalence form of map_plug: if the exposed side of the open system is reshaped by a canonical directed isomorphism, the same forward boundary adaptation can be pushed across the plug after swapping directions.

                                  The right-hand side is phrased with the swapped boundary Hom directly rather than wrapping it back into mapEquiv. That is intentional: once directions are reversed, the variance becomes clearer at the raw boundary-map level than through a second equivalence wrapper.

                                  Symmetric monoidal coherence #

                                  theorem Interaction.UC.OpenTheory.par_assoc {T : OpenTheory} [T.IsMonoidal] {Δ₁ Δ₂ Δ₃ : PortBoundary} (W₁ : T.Obj Δ₁) (W₂ : T.Obj Δ₂) (W₃ : T.Obj Δ₃) :
                                  T.mapEquiv (PortBoundary.Equiv.tensorAssoc Δ₁ Δ₂ Δ₃) (T.par (T.par W₁ W₂) W₃) = T.par W₁ (T.par W₂ W₃)

                                  Reassociating a nested parallel composition of three open systems.

                                  theorem Interaction.UC.OpenTheory.par_comm {T : OpenTheory} [T.IsMonoidal] {Δ₁ Δ₂ : PortBoundary} (W₁ : T.Obj Δ₁) (W₂ : T.Obj Δ₂) :
                                  T.mapEquiv (PortBoundary.Equiv.tensorComm Δ₁ Δ₂) (T.par W₁ W₂) = T.par W₂ W₁

                                  Swapping the components of a parallel composition along the tensor commutativity equivalence.

                                  @[simp]

                                  The monoidal unit is a left identity for parallel composition.

                                  @[simp]

                                  The monoidal unit is a right identity for parallel composition.

                                  Trace algebra #

                                  theorem Interaction.UC.OpenTheory.wire_par_superpose {T : OpenTheory} [T.IsTraced] {Δ₁ Δ₂ Γ Δ₃ : PortBoundary} (W₁ : T.Obj Δ₁) (W₂ : T.Obj (Δ₂.tensor Γ)) (W₃ : T.Obj (Γ.swap.tensor Δ₃)) :
                                  T.wire (T.mapEquiv (PortBoundary.Equiv.tensorAssoc Δ₁ Δ₂ Γ).symm (T.par W₁ W₂)) W₃ = T.mapEquiv (PortBoundary.Equiv.tensorAssoc Δ₁ Δ₂ Δ₃).symm (T.par W₁ (T.wire W₂ W₃))

                                  Wire-par superposition: the left factor of a parallel composition can be moved outside a wire when it doesn't share the contracted boundary.

                                  theorem Interaction.UC.OpenTheory.wire_assoc {T : OpenTheory} [T.IsTraced] {Δ₁ Γ₁ Γ₂ Δ₃ : PortBoundary} (W₁ : T.Obj (Δ₁.tensor Γ₁)) (W₂ : T.Obj (Γ₁.swap.tensor Γ₂)) (W₃ : T.Obj (Γ₂.swap.tensor Δ₃)) :
                                  T.wire (T.wire W₁ W₂) W₃ = T.wire W₁ (T.wire W₂ W₃)

                                  Wire associativity: sequential wiring can be reassociated.

                                  theorem Interaction.UC.OpenTheory.wire_comm {T : OpenTheory} [T.IsTraced] {Δ₁ Γ Δ₂ : PortBoundary} (W₁ : T.Obj (Δ₁.tensor Γ)) (W₂ : T.Obj (Γ.swap.tensor Δ₂)) :

                                  Wire commutativity: the roles of the two wire factors are interchangeable up to boundary reshaping.

                                  Compact closure (snake / zig-zag) #

                                  @[simp]
                                  theorem Interaction.UC.OpenTheory.wire_idWire {T : OpenTheory} [T.IsCompactClosed] {Γ Δ₂ : PortBoundary} (W₂ : T.Obj (Γ.swap.tensor Δ₂)) :
                                  T.wire (HasIdWire.idWire Γ) W₂ = W₂

                                  Left zig-zag: wiring the identity wire on the left is a no-op.

                                  @[simp]
                                  theorem Interaction.UC.OpenTheory.wire_idWire_right {T : OpenTheory} [T.IsCompactClosed] {Γ Δ₁ : PortBoundary} (W₁ : T.Obj (Δ₁.tensor Γ)) :
                                  T.wire W₁ (HasIdWire.idWire Γ) = W₁

                                  Right zig-zag: wiring the identity wire on the right is a no-op.

                                  Plug-wire factorization #

                                  theorem Interaction.UC.OpenTheory.plug_par_left {T : OpenTheory} [T.HasPlugWireFactor] {Δ₁ Δ₂ : PortBoundary} (W₁ : T.Obj Δ₁) (W₂ : T.Obj Δ₂) (K : T.Obj (Δ₁.tensor Δ₂).swap) :

                                  Plug-par factorization (left): plugging a parallel composition against a context factors through the left component.

                                  See HasPlugWireFactor.plug_par_left for the full docstring.

                                  theorem Interaction.UC.OpenTheory.plug_wire_left {T : OpenTheory} [T.HasPlugWireFactor] {Δ₁ Γ Δ₂ : PortBoundary} (W₁ : T.Obj (Δ₁.tensor Γ)) (W₂ : T.Obj (Γ.swap.tensor Δ₂)) (K : T.Obj (Δ₁.tensor Δ₂).swap) :
                                  T.plug (T.wire W₁ W₂) K = T.plug W₁ (T.wire K (T.mapEquiv (PortBoundary.Equiv.tensorComm Γ.swap Δ₂) W₂))

                                  Plug-wire factorization (left): closing a wired composition against a context factors through the left wire component.

                                  See HasPlugWireFactor.plug_wire_left for the full docstring.