Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.PolyFun.Interaction.UC.OpenSyntax.Raw.part0

Definition
Yukon_98c564176b16f8ef14477aa5

by yukon · Sep 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

better-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
https://github.com/Verified-zkEVM/PolyFun/blob/dd77aa91dd425ebaec4388270f3a8e3dc7ace571/PolyFun/Interaction/UC/OpenSyntax/Raw.lean yukon-proof-operation:70e2c359c337489225069765d0cf5e0dfa7456e424495c80789d1c8082bb7bcb [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246NzBlMmMzNTljMzM3NDg5MjI1MDY5NzY1ZDBjZjVlMGRmYTc0NTZlNDI0NDk1YzgwNzg5ZDFjODA4MmJiN2JjYiIsImhhc2giOiI4MWU4ODQxNWZhMGZiNGI1NDJjNmE4MTYzYzE5YmM2MzUwNjRlZTNiMDEzNDMzNDU5M2RjNGIyMjNhN2ZlMTI0Iiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl85OGM1NjQxNzZiMTZmOGVmMTQ0NzdhYTUiLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me