YukonModule.PolyFun.Interaction.UC.OpenSyntax.Raw.part0
DefinitionYukon_98c564176b16f8ef14477aa5better-codes
Source module PolyFun.Interaction.UC.OpenSyntax.Raw.
Definition code
/-
Copyright (c) 2026 PolyFun Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Quang Dao
-/
module
public import Definitions.Def_Yukon_d78c3b8dcf2e093889a6f4e9
public import Batteries.Tactic.Lint
public import Mathlib.Data.PFunctor.Multivariate.Basic
public import Init
meta import Definitions.Def_Yukon_d78c3b8dcf2e093889a6f4e9
set_option backward.isDefEq.respectTransparency.types false
/-!
# Raw syntax trees for open composition
This module defines the raw (un-quotiented) syntax trees for open-system
expressions, together with a structural interpretation function into any
target `OpenTheory`.
The inductive `Raw Atom Δ` has five native constructors (`atom`, `map`, `par`,
`wire`, `idWire`) forming the minimal generating set for a compact closed
open-system algebra. The derived operations `plug` and `unit` are defined as
abbreviations. The raw tree is not quotiented, so syntactically distinct trees
are distinct values even when they would evaluate the same way in any lawful
`OpenTheory`; `Raw.map (Hom.id Δ) e` is a fresh `.map` node, not
definitionally equal to `e`.
The quotient of `Raw` by the `OpenTheory` equations is defined in
`OpenSyntax.Expr`. The tagless-final (Church-encoded) companion is defined in
`OpenSyntax.Interp`.
## Main definitions
* `Raw`: inductive syntax tree for open-system expressions.
* `Raw.interpret`: structural recursion into any target `OpenTheory`.
* `Raw.Equiv`: the smallest equivalence relation containing the `OpenTheory`
equations and closed under all constructors.
* `Raw.setoid`: packages `Raw.Equiv` as a `Setoid`.
-/
public section
universe u
namespace Interaction
namespace UC
namespace OpenSyntax
/--
`Raw Atom Δ` is the raw syntax tree for open-system expressions of boundary `Δ`
generated by primitive atoms `Atom`.
The five native constructors form the minimal generating set for a compact
closed open-system algebra. The derived operations `plug` and `unit` are
abbreviations defined below.
See `Expr` for the quotiented version.
-/
inductive Raw (Atom : PortBoundary → Type u) : PortBoundary → Type (u + 1) where
/-- Inject a primitive open component. -/
| atom {Δ : PortBoundary} : Atom Δ → Raw Atom Δ
/-- Adapt the exposed boundary along a structural morphism. -/
| map {Δ₁ Δ₂ : PortBoundary} :
PortBoundary.Hom Δ₁ Δ₂ → Raw Atom Δ₁ → Raw Atom Δ₂
/-- Place two open systems side by side. -/
| par {Δ₁ Δ₂ : PortBoundary} :
Raw Atom Δ₁ → Raw Atom Δ₂ → Raw Atom (PortBoundary.tensor Δ₁ Δ₂)
/-- Connect one shared boundary between two open systems. -/
| wire {Δ₁ Γ Δ₂ : PortBoundary} :
Raw Atom (PortBoundary.tensor Δ₁ Γ) →
Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂) →
Raw Atom (PortBoundary.tensor Δ₁ Δ₂)
/-- The identity wire (coevaluation) on boundary `Γ`. -/
| idWire (Γ : PortBoundary) :
Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Γ)
/-- The monoidal unit: `idWire` on the trivial boundary, mapped through a
unitor. Derived from the two primitives `map` and `idWire`. -/
abbrev Raw.unit {Atom : PortBoundary → Type u} : Raw Atom PortBoundary.empty :=
.map (PortBoundary.Equiv.tensorEmptyLeft PortBoundary.empty).toHom
(.idWire PortBoundary.empty)
/-- Close an open system against a matching context. Derived from `wire` by
embedding both operands into a tensored boundary and collapsing via a unitor. -/
abbrev Raw.plug {Atom : PortBoundary → Type u} {Δ : PortBoundary}
(e : Raw Atom Δ) (k : Raw Atom (PortBoundary.swap Δ)) :
Raw Atom PortBoundary.empty :=
.map (PortBoundary.Equiv.tensorEmptyLeft PortBoundary.empty).toHom
(.wire
(.map (PortBoundary.Equiv.tensorEmptyLeft Δ).symm.toHom e)
(.map (PortBoundary.Equiv.tensorEmptyRight
(PortBoundary.swap Δ)).symm.toHom k))
namespace Raw
/--
Interpret a raw expression in an arbitrary target open theory.
This is structural recursion: each constructor maps to the corresponding
`OpenTheory` operation. The target theory need not be lawful; lawfulness is
only required when reasoning about equivalence of interpretations.
-/
@[expose]
def interpret {Atom : PortBoundary → Type u} {Δ : PortBoundary} (e : Raw Atom Δ) (T : OpenTheory)
(interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ)
(idWireVal : ∀ (Γ : PortBoundary),
T.Obj (PortBoundary.tensor (PortBoundary.swap Γ) Γ)) : T.Obj Δ :=
match e with
| .atom a => interp a
| .map f e => T.map f (e.interpret T interp idWireVal)
| .par e₁ e₂ =>
T.par (e₁.interpret T interp idWireVal)
(e₂.interpret T interp idWireVal)
| .wire e₁ e₂ =>
T.wire (e₁.interpret T interp idWireVal)
(e₂.interpret T interp idWireVal)
| .idWire Γ => idWireVal Γ
variable {Atom : PortBoundary → Type u} {T : OpenTheory}
{interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ}
{idWireVal : ∀ (Γ : PortBoundary),
T.Obj (PortBoundary.tensor (PortBoundary.swap Γ) Γ)}
@[simp]
theorem interpret_atom {Δ : PortBoundary} (a : Atom Δ) :
(Raw.atom a).interpret T interp idWireVal = interp a :=
rfl
@[simp]
theorem interpret_map {Δ₁ Δ₂ : PortBoundary} (f : PortBoundary.Hom Δ₁ Δ₂) (e : Raw Atom Δ₁) :
(Raw.map f e).interpret T interp idWireVal =
T.map f (e.interpret T interp idWireVal) :=
rfl
@[simp]
theorem interpret_par {Δ₁ Δ₂ : PortBoundary} (e₁ : Raw Atom Δ₁) (e₂ : Raw Atom Δ₂) :
(Raw.par e₁ e₂).interpret T interp idWireVal =
T.par (e₁.interpret T interp idWireVal)
(e₂.interpret T interp idWireVal) :=
rfl
@[simp]
theorem interpret_wire {Δ₁ Γ Δ₂ : PortBoundary} (e₁ : Raw Atom (PortBoundary.tensor Δ₁ Γ))
(e₂ : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂)) :
(Raw.wire e₁ e₂).interpret T interp idWireVal =
T.wire (e₁.interpret T interp idWireVal)
(e₂.interpret T interp idWireVal) :=
rfl
@[simp]
theorem interpret_idWire (Γ : PortBoundary) :
(Raw.idWire Γ : Raw Atom _).interpret T interp idWireVal = idWireVal Γ :=
rfl
/--
`Raw.Equiv e₁ e₂` is the smallest equivalence relation on raw expressions at
the same boundary that contains the `OpenTheory` equations and is closed under
all constructors.
The equation constructors capture functoriality of `map`, naturality of `par`
and `wire`, monoidal coherence (`par_assoc`, `par_comm`, unit laws), and the
zig-zag identity (`wire_idWire`). The congruence constructors ensure that
equivalent sub-expressions can be substituted anywhere in a larger tree.
Since `plug` and `unit` are abbreviations, laws like `plug_eq_wire` and
`congr_plug` are now definitional and do not need dedicated constructors.
-/
inductive Equiv {Atom : PortBoundary → Type u} :
{Δ : PortBoundary} → Raw Atom Δ → Raw Atom Δ → Prop where
| refl {Δ : PortBoundary} {e : Raw Atom Δ} : Equiv e e
| symm {Δ : PortBoundary} {e₁ e₂ : Raw Atom Δ} :
Equiv e₁ e₂ → Equiv e₂ e₁
| trans {Δ : PortBoundary} {e₁ e₂ e₃ : Raw Atom Δ} :
Equiv e₁ e₂ → Equiv e₂ e₃ → Equiv e₁ e₃
| map_id {Δ : PortBoundary} {e : Raw Atom Δ} :
Equiv (.map (PortBoundary.Hom.id Δ) e) e
| map_comp {Δ₁ Δ₂ Δ₃ : PortBoundary}
{g : PortBoundary.Hom Δ₂ Δ₃}
{f : PortBoundary.Hom Δ₁ Δ₂}
{e : Raw Atom Δ₁} :
Equiv (.map (PortBoundary.Hom.comp g f) e) (.map g (.map f e))
| map_par {Δ₁ Δ₁' Δ₂ Δ₂' : PortBoundary}
{f₁ : PortBoundary.Hom Δ₁ Δ₁'}
{f₂ : PortBoundary.Hom Δ₂ Δ₂'}
{e₁ : Raw Atom Δ₁}
{e₂ : Raw Atom Δ₂} :
Equiv
(.map (PortBoundary.Hom.tensor f₁ f₂) (.par e₁ e₂))
(.par (.map f₁ e₁) (.map f₂ e₂))
| map_wire {Δ₁ Δ₁' Γ Δ₂ Δ₂' : PortBoundary}
{f₁ : PortBoundary.Hom Δ₁ Δ₁'}
{f₂ : PortBoundary.Hom Δ₂ Δ₂'}
{e₁ : Raw Atom (PortBoundary.tensor Δ₁ Γ)}
{e₂ : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂)} :
Equiv
(.map (PortBoundary.Hom.tensor f₁ f₂) (.wire e₁ e₂))
(.wire
(.map (PortBoundary.Hom.tensor f₁ (PortBoundary.Hom.id Γ)) e₁)
(.map
(PortBoundary.Hom.tensor
(PortBoundary.Hom.id (PortBoundary.swap Γ))
f₂)
e₂))
| map_plug {Δ₁ Δ₂ : PortBoundary}
{f : PortBoundary.Hom Δ₁ Δ₂}
{e : Raw Atom Δ₁}
{k : Raw Atom (PortBoundary.swap Δ₂)} :
Equiv
(Raw.plug (.map f e) k)
(Raw.plug e (.map (PortBoundary.Hom.swap f) k))
| par_assoc {Δ₁ Δ₂ Δ₃ : PortBoundary}
{e₁ : Raw Atom Δ₁}
{e₂ : Raw Atom Δ₂}
{e₃ : Raw Atom Δ₃} :
Equiv
(.map (PortBoundary.Equiv.tensorAssoc Δ₁ Δ₂ Δ₃).toHom
(.par (.par e₁ e₂) e₃))
(.par e₁ (.par e₂ e₃))
| par_comm {Δ₁ Δ₂ : PortBoundary}
{e₁ : Raw Atom Δ₁}
{e₂ : Raw Atom Δ₂} :
Equiv
(.map (PortBoundary.Equiv.tensorComm Δ₁ Δ₂).toHom
(.par e₁ e₂))
(.par e₂ e₁)
| par_leftUnit {Δ : PortBoundary}
{e : Raw Atom Δ} :
Equiv
(.map (PortBoundary.Equiv.tensorEmptyLeft Δ).toHom
(.par Raw.unit e))
e
| par_rightUnit {Δ : PortBoundary}
{e : Raw Atom Δ} :
Equiv
(.map (PortBoundary.Equiv.tensorEmptyRight Δ).toHom
(.par e Raw.unit))
e
| wire_idWire {Γ Δ₂ : PortBoundary}
{e₂ : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂)} :
Equiv
(.wire (.idWire Γ) e₂)
e₂
| wire_idWire_right {Γ Δ₁ : PortBoundary}
{e₁ : Raw Atom (PortBoundary.tensor Δ₁ Γ)} :
Equiv
(.wire e₁ (.idWire Γ))
e₁
| wire_assoc {Δ₁ Γ₁ Γ₂ Δ₃ : PortBoundary}
{e₁ : Raw Atom (PortBoundary.tensor Δ₁ Γ₁)}
{e₂ : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ₁) Γ₂)}
{e₃ : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ₂) Δ₃)} :
Equiv
(.wire (.wire e₁ e₂) e₃)
(.wire e₁ (.wire e₂ e₃))
| wire_par_superpose {Δ₁ Δ₂ Γ Δ₃ : PortBoundary}
{e₁ : Raw Atom Δ₁}
{e₂ : Raw Atom (PortBoundary.tensor Δ₂ Γ)}
{e₃ : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₃)} :
Equiv
(.wire
(.map (PortBoundary.Equiv.tensorAssoc Δ₁ Δ₂ Γ).symm.toHom
(.par e₁ e₂))
e₃)
(.map (PortBoundary.Equiv.tensorAssoc Δ₁ Δ₂ Δ₃).symm.toHom
(.par e₁ (.wire e₂ e₃)))
| wire_comm {Δ₁ Γ Δ₂ : PortBoundary}
{e₁ : Raw Atom (PortBoundary.tensor Δ₁ Γ)}
{e₂ : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂)} :
Equiv
(.wire e₁ e₂)
(.map (PortBoundary.Equiv.tensorComm Δ₂ Δ₁).toHom
(.wire
(.map (PortBoundary.Equiv.tensorComm
(PortBoundary.swap Γ) Δ₂).toHom e₂)
(.map (PortBoundary.Equiv.tensorComm Δ₁ Γ).toHom e₁)))
| plug_par_left {Δ₁ Δ₂ : PortBoundary}
{e₁ : Raw Atom Δ₁}
{e₂ : Raw Atom Δ₂}
{K : Raw Atom (PortBoundary.swap (PortBoundary.tensor Δ₁ Δ₂))} :
Equiv
(.plug (.par e₁ e₂) K)
(.plug e₁
(.map (PortBoundary.Equiv.tensorEmptyRight
(PortBoundary.swap Δ₁)).toHom
(.wire
(Γ := PortBoundary.swap Δ₂)
(Δ₂ := PortBoundary.empty)
K
(.map (PortBoundary.Equiv.tensorEmptyRight Δ₂).symm.toHom
e₂))))
| plug_wire_left {Δ₁ Γ Δ₂ : PortBoundary}
{e₁ : Raw Atom (PortBoundary.tensor Δ₁ Γ)}
{e₂ : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂)}
{K : Raw Atom (PortBoundary.swap (PortBoundary.tensor Δ₁ Δ₂))} :
Equiv
(.plug (.wire e₁ e₂) K)
(.plug e₁
(.wire
(Δ₁ := PortBoundary.swap Δ₁)
(Γ := PortBoundary.swap Δ₂)
(Δ₂ := PortBoundary.swap Γ)
K
(.map (PortBoundary.Equiv.tensorComm
(PortBoundary.swap Γ) Δ₂).toHom e₂)))
| congr_map {Δ₁ Δ₂ : PortBoundary}
{f : PortBoundary.Hom Δ₁ Δ₂}
{e₁ e₂ : Raw Atom Δ₁} :
Equiv e₁ e₂ → Equiv (.map f e₁) (.map f e₂)
| congr_par {Δ₁ Δ₂ : PortBoundary}
{e₁ e₁' : Raw Atom Δ₁}
{e₂ e₂' : Raw Atom Δ₂} :
Equiv e₁ e₁' → Equiv e₂ e₂' →
Equiv (.par e₁ e₂) (.par e₁' e₂')
| congr_wire {Δ₁ Γ Δ₂ : PortBoundary}
{e₁ e₁' : Raw Atom (PortBoundary.tensor Δ₁ Γ)}
{e₂ e₂' : Raw Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂)} :
Equiv e₁ e₁' → Equiv e₂ e₂' →
Equiv (.wire e₁ e₂) (.wire e₁' e₂')
/--
Equivalent raw expressions interpret the same way in any lawful `OpenTheory`.
-/
theorem Equiv.interpret_eq {Atom : PortBoundary → Type u} {Δ : PortBoundary} {e₁ e₂ : Raw Atom Δ}
(h : Equiv e₁ e₂) (T : OpenTheory) [OpenTheory.HasPlugWireFactor T]
(interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) :
e₁.interpret T interp OpenTheory.HasIdWire.idWire =
e₂.interpret T interp OpenTheory.HasIdWire.idWire := by
induction h with
| refl => rfl
| symm _ ih => exact ih.symm
| trans _ _ ih₁ ih₂ => exact ih₁.trans ih₂
| map_id => simp [interpret]
| map_comp => simp [interpret, OpenTheory.map_comp]
| map_par => simp [interpret, OpenTheory.map_par]
| map_wire => simp [interpret, OpenTheory.map_wire]
| map_plug =>
simp only [Raw.plug, interpret_map, interpret_wire]
rw [← OpenTheory.plug_eq_wire (T := T), ← OpenTheory.plug_eq_wire (T := T)]
exact OpenTheory.map_plug (T := T) _ _ _
| par_assoc => simp [interpret, OpenTheory.par_assoc]
| par_comm => simp [interpret, OpenTheory.par_comm]
| par_leftUnit =>
simp only [interpret]
rw [← OpenTheory.unit_eq (T := T)]
exact OpenTheory.par_leftUnit _
| par_rightUnit =>
simp only [interpret]
rw [← OpenTheory.unit_eq (T := T)]
exact OpenTheory.par_rightUnit _
| wire_idWire => simp [interpret, OpenTheory.wire_idWire]
| wire_idWire_right => simp [interpret, OpenTheory.wire_idWire_right]
| wire_assoc => simp only [interpret_wire]; exact OpenTheory.wire_assoc _ _ _
| wire_par_superpose =>
simp only [interpret_wire, interpret_map, interpret_par]
exact OpenTheory.wire_par_superpose _ _ _
| wire_comm =>
simp only [interpret_wire, interpret_map]
exact OpenTheory.wire_comm _ _
| plug_par_left =>
simp only [Raw.plug, interpret_map, interpret_wire, interpret_par]
rw [← OpenTheory.plug_eq_wire (T := T), ← OpenTheory.plug_eq_wire (T := T)]
exact OpenTheory.plug_par_left _ _ _
| plug_wire_left =>
simp only [Raw.plug, interpret_map, interpret_wire]
rw [← OpenTheory.plug_eq_wire (T := T), ← OpenTheory.plug_eq_wire (T := T)]
exact OpenTheory.plug_wire_left _ _ _
| congr_map _ ih => simp only [interpret_map]; rw [ih]
| congr_par _ _ ih₁ ih₂ => simp only [interpret_par]; rw [ih₁, ih₂]
| congr_wire _ _ ih₁ ih₂ => simp only [interpret_wire]; rw [ih₁, ih₂]
attribute [symm] Equiv.symm
attribute [trans] Equiv.trans
/--
The `Setoid` on `Raw Atom Δ` induced by `Raw.Equiv`.
-/
instance setoid (Atom : PortBoundary → Type u) (Δ : PortBoundary) :
Setoid (Raw Atom Δ) where
r := Equiv
iseqv := ⟨fun _ => .refl, fun h => .symm h, fun h₁ h₂ => .trans h₁ h₂⟩
end Raw
end OpenSyntax
end UC
end Interaction
Source