YukonModule.PolyFun.Interaction.UC.OpenSyntax.Interp.part0
DefinitionYukon_6d42c1abc91f41b32e4fc1e5better-codes
Source module PolyFun.Interaction.UC.OpenSyntax.Interp.
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
/-!
# Tagless-final free model of open composition
This module defines `Interp`, the final (tagless-final / Church-encoded) free
model of `OpenTheory`.
An `Interp Atom Δ` stores no syntax tree. Instead it is determined entirely
by its universal interpretation function: for every lawful target `OpenTheory`
and every atom interpretation, it produces an object of boundary `Δ` in the
target.
This representation is convenient for proving universal properties because
its lawfulness reduces immediately to the target theory's laws.
See `OpenSyntax.Expr` for the quotiented initial model that supports
pattern matching and inspection.
-/
public section
universe u
namespace Interaction
namespace UC
namespace OpenSyntax
/--
`Interp Atom Δ` is the tagless-final free open-system expression of boundary
`Δ` generated by primitive atoms `Atom`.
An element stores its universal elimination principle: for every lawful target
open theory `T` and every atom interpretation, it produces an object of
boundary `Δ` in `T`.
-/
structure Interp (Atom : PortBoundary → Type u) (Δ : PortBoundary) where
/--
Interpret the free expression in an arbitrary target theory with the full
plug-wire factorization structure.
-/
run :
(T : OpenTheory.{max (u + 1) 3}) →
OpenTheory.HasPlugWireFactor T →
(∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) →
T.Obj Δ
namespace Interp
/--
Interpret a tagless-final expression in a target theory with the full
plug-wire factorization structure.
This is just the `run` field restated as a named eliminator.
-/
abbrev interpret {Atom : PortBoundary → Type u} {Δ : PortBoundary} (W : Interp Atom Δ)
(T : OpenTheory.{max (u + 1) 3}) (hT : OpenTheory.HasPlugWireFactor T)
(interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) : T.Obj Δ :=
W.run T hT interp
/--
Two tagless-final expressions are equal when they have the same interpretation
in every lawful target theory.
-/
@[ext]
theorem ext {Atom : PortBoundary → Type u} {Δ : PortBoundary} {W₁ W₂ : Interp Atom Δ}
(h : ∀ (T : OpenTheory.{max (u + 1) 3}) (hT : OpenTheory.HasPlugWireFactor T)
(interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ),
W₁.run T hT interp = W₂.run T hT interp) : W₁ = W₂ := by
cases W₁
cases W₂
simp only at h
congr
funext T hT interp
exact h T hT interp
/--
Inject a primitive open component into the tagless-final syntax.
-/
@[expose]
def atom {Atom : PortBoundary → Type u} {Δ : PortBoundary} : Atom Δ → Interp Atom Δ
| a => ⟨fun _ _ interp => interp a⟩
@[simp]
theorem interpret_atom {Atom : PortBoundary → Type u} {Δ : PortBoundary} (a : Atom Δ)
(T : OpenTheory.{max (u + 1) 3}) (hT : OpenTheory.HasPlugWireFactor T)
(interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) :
(atom a).interpret T hT interp = interp a :=
rfl
/--
Adapt the exposed boundary of a tagless-final expression.
-/
@[expose]
def map {Atom : PortBoundary → Type u} {Δ₁ Δ₂ : PortBoundary} (f : PortBoundary.Hom Δ₁ Δ₂) :
Interp Atom Δ₁ → Interp Atom Δ₂
| W => ⟨fun T hT interp => T.map f (W.run T hT interp)⟩
@[simp]
theorem interpret_map {Atom : PortBoundary → Type u} {Δ₁ Δ₂ : PortBoundary}
(f : PortBoundary.Hom Δ₁ Δ₂) (W : Interp Atom Δ₁) (T : OpenTheory.{max (u + 1) 3})
(hT : OpenTheory.HasPlugWireFactor T) (interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) :
(map f W).interpret T hT interp = T.map f (W.interpret T hT interp) :=
rfl
/--
Place two tagless-final expressions side by side.
-/
@[expose]
def par {Atom : PortBoundary → Type u} {Δ₁ Δ₂ : PortBoundary} :
Interp Atom Δ₁ → Interp Atom Δ₂ → Interp Atom (PortBoundary.tensor Δ₁ Δ₂)
| W₁, W₂ => ⟨fun T hT interp =>
T.par (W₁.run T hT interp) (W₂.run T hT interp)⟩
@[simp]
theorem interpret_par {Atom : PortBoundary → Type u} {Δ₁ Δ₂ : PortBoundary}
(W₁ : Interp Atom Δ₁) (W₂ : Interp Atom Δ₂) (T : OpenTheory.{max (u + 1) 3})
(hT : OpenTheory.HasPlugWireFactor T) (interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) :
(par W₁ W₂).interpret T hT interp =
T.par (W₁.interpret T hT interp) (W₂.interpret T hT interp) :=
rfl
/--
Connect one shared boundary between two tagless-final expressions.
-/
@[expose]
def wire {Atom : PortBoundary → Type u} {Δ₁ Γ Δ₂ : PortBoundary} :
Interp Atom (PortBoundary.tensor Δ₁ Γ) →
Interp Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂) →
Interp Atom (PortBoundary.tensor Δ₁ Δ₂)
| W₁, W₂ => ⟨fun T hT interp =>
T.wire (W₁.run T hT interp) (W₂.run T hT interp)⟩
@[simp]
theorem interpret_wire {Atom : PortBoundary → Type u} {Δ₁ Γ Δ₂ : PortBoundary}
(W₁ : Interp Atom (PortBoundary.tensor Δ₁ Γ))
(W₂ : Interp Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂))
(T : OpenTheory.{max (u + 1) 3}) (hT : OpenTheory.HasPlugWireFactor T)
(interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) :
(wire W₁ W₂).interpret T hT interp =
T.wire (W₁.interpret T hT interp) (W₂.interpret T hT interp) :=
rfl
/--
Close a tagless-final expression against a matching context.
-/
@[expose]
def plug {Atom : PortBoundary → Type u} {Δ : PortBoundary} :
Interp Atom Δ → Interp Atom (PortBoundary.swap Δ) → Interp Atom (PortBoundary.empty)
| W, K => ⟨fun T hT interp =>
T.plug (W.run T hT interp) (K.run T hT interp)⟩
@[simp]
theorem interpret_plug {Atom : PortBoundary → Type u} {Δ : PortBoundary} (W : Interp Atom Δ)
(K : Interp Atom (PortBoundary.swap Δ)) (T : OpenTheory.{max (u + 1) 3})
(hT : OpenTheory.HasPlugWireFactor T) (interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) :
(plug W K).interpret T hT interp =
T.plug (W.interpret T hT interp) (K.interpret T hT interp) :=
rfl
/--
The monoidal unit (closed system with no boundary).
-/
@[expose]
def unit {Atom : PortBoundary → Type u} : Interp Atom PortBoundary.empty :=
⟨fun _ hCC _ => OpenTheory.HasUnit.unit
(self := hCC.toIsCompactClosed.toIsTraced.toIsMonoidal.toHasUnit)⟩
@[simp]
theorem interpret_unit {Atom : PortBoundary → Type u} (T : OpenTheory.{max (u + 1) 3})
(hT : OpenTheory.HasPlugWireFactor T) (interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) :
(unit : Interp Atom _).interpret T hT interp = OpenTheory.HasUnit.unit (T := T) :=
rfl
/--
The identity wire (coevaluation) on boundary `Γ`.
-/
@[expose]
def idWire {Atom : PortBoundary → Type u} (Γ : PortBoundary) :
Interp Atom (PortBoundary.tensor (PortBoundary.swap Γ) Γ) :=
⟨fun _ hCC _ => OpenTheory.HasIdWire.idWire
(self := hCC.toIsCompactClosed.toHasIdWire) Γ⟩
@[simp]
theorem interpret_idWire {Atom : PortBoundary → Type u} (Γ : PortBoundary)
(T : OpenTheory.{max (u + 1) 3}) (hT : OpenTheory.HasPlugWireFactor T)
(interp : ∀ {Δ : PortBoundary}, Atom Δ → T.Obj Δ) :
(idWire Γ : Interp Atom _).interpret T hT interp = OpenTheory.HasIdWire.idWire (T := T) Γ :=
rfl
/--
The free lawful `OpenTheory` generated by tagless-final expressions over `Atom`.
-/
abbrev theory (Atom : PortBoundary → Type u) : OpenTheory.{max (u + 2) 4} where
Obj := Interp Atom
map := Interp.map
par := Interp.par
wire := Interp.wire
plug := Interp.plug
instance lawfulMap (Atom : PortBoundary → Type u) :
OpenTheory.IsLawfulMap (Interp.theory Atom) where
map_id := by
intro Δ W
change Interp Atom Δ at W
change Interp.map (PortBoundary.Hom.id Δ) W = W
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp [Interp.map]
map_comp := by
intro Δ₁ Δ₂ Δ₃ g f W
change Interp Atom Δ₁ at W
change Interp.map (PortBoundary.Hom.comp g f) W = Interp.map g (Interp.map f W)
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simpa [Interp.map] using
OpenTheory.map_comp (T := T) g f (W.run T hT interp)
instance lawfulPar (Atom : PortBoundary → Type u) :
OpenTheory.IsLawfulPar (Interp.theory Atom) where
map_id := OpenTheory.IsLawfulMap.map_id (T := Interp.theory Atom)
map_comp := OpenTheory.IsLawfulMap.map_comp (T := Interp.theory Atom)
map_par := by
intro Δ₁ Δ₁' Δ₂ Δ₂' f₁ f₂ W₁ W₂
change Interp Atom Δ₁ at W₁
change Interp Atom Δ₂ at W₂
change
Interp.map (PortBoundary.Hom.tensor f₁ f₂) (Interp.par W₁ W₂) =
Interp.par (Interp.map f₁ W₁) (Interp.map f₂ W₂)
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simpa [Interp.map, Interp.par] using
OpenTheory.map_par (T := T) f₁ f₂ (W₁.run T hT interp) (W₂.run T hT interp)
instance lawfulWire (Atom : PortBoundary → Type u) :
OpenTheory.IsLawfulWire (Interp.theory Atom) where
map_id := OpenTheory.IsLawfulMap.map_id (T := Interp.theory Atom)
map_comp := OpenTheory.IsLawfulMap.map_comp (T := Interp.theory Atom)
map_wire := by
intro Δ₁ Δ₁' Γ Δ₂ Δ₂' f₁ f₂ W₁ W₂
change Interp Atom (PortBoundary.tensor Δ₁ Γ) at W₁
change Interp Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂) at W₂
change
Interp.map (PortBoundary.Hom.tensor f₁ f₂) (Interp.wire W₁ W₂) =
Interp.wire
(Interp.map (PortBoundary.Hom.tensor f₁ (PortBoundary.Hom.id Γ)) W₁)
(Interp.map
(PortBoundary.Hom.tensor
(PortBoundary.Hom.id (PortBoundary.swap Γ))
f₂)
W₂)
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simpa [Interp.map, Interp.wire] using
OpenTheory.map_wire (T := T) f₁ f₂ (W₁.run T hT interp) (W₂.run T hT interp)
instance lawfulPlug (Atom : PortBoundary → Type u) :
OpenTheory.IsLawfulPlug (Interp.theory Atom) where
map_id := OpenTheory.IsLawfulMap.map_id (T := Interp.theory Atom)
map_comp := OpenTheory.IsLawfulMap.map_comp (T := Interp.theory Atom)
map_plug := by
intro Δ₁ Δ₂ f W K
change Interp Atom Δ₁ at W
change Interp Atom (PortBoundary.swap Δ₂) at K
change
Interp.plug (Interp.map f W) K =
Interp.plug W (Interp.map (PortBoundary.Hom.swap f) K)
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simpa [Interp.map, Interp.plug] using
OpenTheory.map_plug (T := T) f (W.run T hT interp) (K.run T hT interp)
instance lawful (Atom : PortBoundary → Type u) : OpenTheory.IsLawful (Interp.theory Atom) where
instance hasUnit (Atom : PortBoundary → Type u) : OpenTheory.HasUnit (Interp.theory Atom) where
unit := Interp.unit
instance hasIdWire (Atom : PortBoundary → Type u) :
OpenTheory.HasIdWire (Interp.theory Atom) where
idWire := Interp.idWire
instance isMonoidal (Atom : PortBoundary → Type u) :
OpenTheory.IsMonoidal (Interp.theory Atom) where
par_assoc := by
intro Δ₁ Δ₂ Δ₃ W₁ W₂ W₃
change Interp Atom Δ₁ at W₁
change Interp Atom Δ₂ at W₂
change Interp Atom Δ₃ at W₃
change
Interp.map (PortBoundary.Equiv.tensorAssoc Δ₁ Δ₂ Δ₃).toHom
(Interp.par (Interp.par W₁ W₂) W₃) =
Interp.par W₁ (Interp.par W₂ W₃)
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simpa [Interp.map, Interp.par] using
OpenTheory.par_assoc (T := T) (W₁.run T hT interp)
(W₂.run T hT interp) (W₃.run T hT interp)
par_comm := by
intro Δ₁ Δ₂ W₁ W₂
change Interp Atom Δ₁ at W₁
change Interp Atom Δ₂ at W₂
change
Interp.map (PortBoundary.Equiv.tensorComm Δ₁ Δ₂).toHom
(Interp.par W₁ W₂) =
Interp.par W₂ W₁
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simpa [Interp.map, Interp.par] using
OpenTheory.par_comm (T := T) (W₁.run T hT interp) (W₂.run T hT interp)
par_leftUnit := by
intro Δ W
change Interp Atom Δ at W
change
Interp.map (PortBoundary.Equiv.tensorEmptyLeft Δ).toHom
(Interp.par Interp.unit W) = W
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp [Interp.map, Interp.par, Interp.unit]
par_rightUnit := by
intro Δ W
change Interp Atom Δ at W
change
Interp.map (PortBoundary.Equiv.tensorEmptyRight Δ).toHom
(Interp.par W Interp.unit) = W
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp [Interp.map, Interp.par, Interp.unit]
instance isTraced (Atom : PortBoundary → Type u) :
OpenTheory.IsTraced (Interp.theory Atom) where
wire_assoc := by
intro Δ₁ Γ₁ Γ₂ Δ₃ W₁ W₂ W₃
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp only [Interp.wire]
exact OpenTheory.wire_assoc (T := T)
(W₁.run T hT interp) (W₂.run T hT interp) (W₃.run T hT interp)
wire_par_superpose := by
intro Δ₁ Δ₂ Γ Δ₃ W₁ W₂ W₃
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp only [Interp.wire, Interp.map, Interp.par]
exact OpenTheory.wire_par_superpose (T := T)
(W₁.run T hT interp) (W₂.run T hT interp) (W₃.run T hT interp)
wire_comm := by
intro Δ₁ Γ Δ₂ W₁ W₂
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp only [Interp.wire, Interp.map]
exact OpenTheory.wire_comm (T := T)
(W₁.run T hT interp) (W₂.run T hT interp)
instance isCompactClosed (Atom : PortBoundary → Type u) :
OpenTheory.IsCompactClosed (Interp.theory Atom) where
wire_idWire := by
intro Γ Δ₂ W₂
change Interp Atom (PortBoundary.tensor (PortBoundary.swap Γ) Δ₂) at W₂
change
Interp.wire (Interp.idWire Γ) W₂ = W₂
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp [Interp.wire, Interp.idWire]
wire_idWire_right := by
intro Γ Δ₁ W₁
change Interp Atom (PortBoundary.tensor Δ₁ Γ) at W₁
change
Interp.wire W₁ (Interp.idWire Γ) = W₁
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp [Interp.wire, Interp.idWire]
unit_eq := by
change
Interp.unit = Interp.map
(PortBoundary.Equiv.tensorEmptyLeft PortBoundary.empty).toHom
(Interp.idWire PortBoundary.empty)
refine Interp.ext ?_
intro T hT interp
simp only [Interp.unit, Interp.map, Interp.idWire]
exact @OpenTheory.unit_eq T hT.toIsCompactClosed
instance hasPlugWireFactor (Atom : PortBoundary → Type u) :
OpenTheory.HasPlugWireFactor (Interp.theory Atom) where
plug_eq_wire := by
intro Δ W K
change Interp Atom Δ at W
change Interp Atom (PortBoundary.swap Δ) at K
change
Interp.plug W K =
Interp.map (PortBoundary.Equiv.tensorEmptyLeft PortBoundary.empty).toHom
(Interp.wire
(Interp.map (PortBoundary.Equiv.tensorEmptyLeft Δ).symm.toHom W)
(Interp.map (PortBoundary.Equiv.tensorEmptyRight
(PortBoundary.swap Δ)).symm.toHom K))
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp [Interp.plug, Interp.map, Interp.wire,
OpenTheory.plug_eq_wire (T := T) (W.run T hT interp) (K.run T hT interp)]
plug_par_left := by
intro Δ₁ Δ₂ W₁ W₂ K
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp only [Interp.plug, Interp.par, Interp.map, Interp.wire]
exact OpenTheory.plug_par_left (T := T)
(W₁.run T hT interp) (W₂.run T hT interp) (K.run T hT interp)
plug_wire_left := by
intro Δ₁ Γ Δ₂ W₁ W₂ K
refine Interp.ext ?_
intro T hT interp
have : OpenTheory.HasPlugWireFactor T := hT
simp only [Interp.plug, Interp.wire, Interp.map]
exact OpenTheory.plug_wire_left (T := T)
(W₁.run T hT interp) (W₂.run T hT interp) (K.run T hT interp)
end Interp
end OpenSyntax
end UC
end Interaction
Source