Aether Catalog definitions — Bridges_GraphTheory_SemanticQuotientExtraction
DefinitionBridges_GraphTheory_SemanticQuotientExtractionaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.GraphTheory.SemanticQuotientExtraction, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/GraphTheory/SemanticQuotientExtraction.lean by skeleton subtraction
import Mathlib
/-!
# Semantic Quotient Extraction: Non-Convergent Soundness
## Overview
This file establishes that **extraction correctness is a manifestation of semantic quotient
invariance**, and therefore survives far beyond the classical boundaries of convergent rewriting.
We formalize the principle that equality saturation is sound because quotient semantics is sound,
not because rewriting converges.
## Mathematical Contribution
The central insight: an e-graph extractor is sound whenever the rewrite relation preserves
denotation under each step. No confluence, no termination, no orientation is required.
We formalize this in three settings:
1. **Abstract rewrite systems** — semantic invariance of equivalence closure (Theorem 1)
2. **Extraction soundness** — any extractor from the same e-class preserves semantics (Theorem 2)
3. **Compositional term languages** — context closure preserves soundness (Theorems 3–4)
4. **SK combinator calculus** — a non-confluent, non-normalizing bridge domain (Theorem 5)
## New Definitions
- `EGraphSound`: a class capturing step-soundness of a rewrite relation w.r.t. a denotation
- `SemanticsInvariant`: semantic invariance under equivalence closure
- `QuotientSoundExtractor`: an extractor that is sound via quotient semantics
- `ContextClosure`: closure of a relation under term constructors
- `SKTerm`, `SKStep`: SK combinator syntax and rewrite rules
- `SKDenote`: denotation of SK terms into function spaces
## Lineage
Builds on `Catalog/Pythagorean/EqualitySaturationExtraction.lean`:
- `extraction_semantics_preserved`
- `extract_eqvGen`
-/
open Relation
universe u v
/-! ## Part I: Core Definitions -/
/-- A semantics is e-graph sound if every rewrite step preserves denotation. -/
class EGraphSound
{α : Type u} {σ : Type v}
(denote : α → σ)
(step : α → α → Prop) : Prop where
sound_step : ∀ {a b}, step a b → denote a = denote b
/-- Semantic invariance under the equivalence closure generated by a rewrite relation. -/
def SemanticsInvariant
{α : Type u} {σ : Type v}
(denote : α → σ)
(R : α → α → Prop) : Prop :=
∀ ⦃a b : α⦄, EqvGen R a b → denote a = denote b
/-- An extractor is quotient-sound if it always returns a representative
semantically equal to the original term whenever it returns a term in the same e-class. -/
def QuotientSoundExtractor
{α : Type u} {σ : Type v}
(denote : α → σ)
(R : α → α → Prop)
(extract : α → α) : Prop :=
∀ a, EqvGen R a (extract a) ∧ denote (extract a) = denote a
/-! ## Part II: Theorem 1 — Semantic Invariance Without Convergence -/
/-
**Theorem 1: Semantic invariance of equivalence closure needs no convergence.**
The semantic content of equality saturation lives in the equivalence closure,
not in any normalization theorem.
> Confluence is sufficient for canonical forms, but unnecessary for semantic soundness.
This is proved by induction on `EqvGen`, handling reflexivity, symmetry, transitivity,
and the forward step case using the step-soundness hypothesis.
-/
theorem eqvGen_semantics_preserved_of_step_sound
{α : Type u} {σ : Type v}
(denote : α → σ)
(R : α → α → Prop)
(hR : ∀ ⦃a b : α⦄, R a b → denote a = denote b) :
∀ ⦃a b : α⦄, EqvGen R a b → denote a = denote b := by
intro a b;
intro hab
induction' hab with a b hab ih;
· grind +qlia;
· rfl;
· grind;
· grind
/-
Step soundness implies full semantic invariance.
-/
/-! ## Part III: Theorem 2 — Extraction Soundness Without Confluence -/
/-
**Theorem 2: Extraction soundness for arbitrary non-confluent rewrite systems.**
If an extractor returns any representative from the same e-class,
and the e-class relation is semantically sound, then extraction is sound.
No confluence, termination, or orientation hypotheses appear.
-/
/-
Constructing a `QuotientSoundExtractor` from step soundness and class membership.
-/
/-- The denotation factors through the quotient by `EqvGen R` when step soundness holds. -/
noncomputable def denoteLiftQuotient
{α : Type u} {σ : Type v}
(denote : α → σ)
(R : α → α → Prop)
(hR : ∀ ⦃a b : α⦄, R a b → denote a = denote b) :
Quot (EqvGen R) → σ :=
Quot.lift denote (eqvGen_semantics_preserved_of_step_sound denote R hR)
/-
The quotient lift agrees with direct evaluation.
-/
/-! ## Part IV: Theorem 3 — Context Closure for Compositional Languages -/
/-- A simple arithmetic term language. -/
inductive Term where
| var : Nat → Term
| const : Int → Term
| add : Term → Term → Term
| mul : Term → Term → Term
deriving Repr, BEq
/-- Denotation of terms into integers given an environment. -/
def Term.denote (ρ : Nat → Int) : Term → Int
| .var n => ρ n
| .const k => k
| .add t₁ t₂ => t₁.denote ρ + t₂.denote ρ
| .mul t₁ t₂ => t₁.denote ρ * t₂.denote ρ
/-- Contextual closure of a relation `R` under the term constructors.
This captures the idea of rewriting inside subterms. -/
inductive ContextClosure (R : Term → Term → Prop) : Term → Term → Prop where
| base (a b : Term) : R a b → ContextClosure R a b
| add_left (a b c : Term) : ContextClosure R a b → ContextClosure R (Term.add a c) (Term.add b c)
| add_right (a b c : Term) : ContextClosure R a b → ContextClosure R (Term.add c a) (Term.add c b)
| mul_left (a b c : Term) : ContextClosure R a b → ContextClosure R (Term.mul a c) (Term.mul b c)
| mul_right (a b c : Term) : ContextClosure R a b → ContextClosure R (Term.mul c a) (Term.mul c b)
/-
**Lemma: Context closure preserves denotation if the base relation does.**
If every base rewrite step preserves denotation, then rewriting anywhere
inside a term also preserves denotation. This uses induction on the
`ContextClosure` derivation.
-/
/-
**Theorem 3: Context closure preserves semantic soundness under equivalence closure.**
Soundness survives compositional embedding into larger programs. This is essential
if the abstract theorems are to justify real optimizers rather than isolated equation provers.
-/
/-
Extraction soundness for the compositional term language.
-/
/-! ## Part V: Theorem 4 — SK Combinator Bridge (Non-Confluent Domain) -/
/-- SK combinator terms — a famously non-normalizing calculus. -/
inductive SKTerm where
| S : SKTerm
| K : SKTerm
| app : SKTerm → SKTerm → SKTerm
deriving Repr, BEq
/-- One-step SK reduction rules.
- K x y → x
- S x y z → (x z) (y z)
These are non-confluent and non-normalizing in general. -/
inductive SKStep : SKTerm → SKTerm → Prop where
| K_red (x y : SKTerm) : SKStep (SKTerm.app (SKTerm.app SKTerm.K x) y) x
| S_red (x y z : SKTerm) : SKStep
(SKTerm.app (SKTerm.app (SKTerm.app SKTerm.S x) y) z)
(SKTerm.app (SKTerm.app x z) (SKTerm.app y z))
| app_left (a b c : SKTerm) : SKStep a b → SKStep (SKTerm.app a c) (SKTerm.app b c)
| app_right (a b c : SKTerm) : SKStep a b → SKStep (SKTerm.app c a) (SKTerm.app c b)
/-- An SK model provides a type and interpretation of S and K combinators. -/
structure SKModel where
carrier : Type
sk_S : carrier
sk_K : carrier
sk_app : carrier → carrier → carrier
/-- K x y = x -/
K_law : ∀ x y, sk_app (sk_app sk_K x) y = x
/-- S x y z = (x z) (y z) -/
S_law : ∀ x y z, sk_app (sk_app (sk_app sk_S x) y) z =
sk_app (sk_app x z) (sk_app y z)
/-- Denotation of SK terms into a model. -/
def SKTerm.denote (M : SKModel) : SKTerm → M.carrier
| .S => M.sk_S
| .K => M.sk_K
| .app t u => M.sk_app (t.denote M) (u.denote M)
/-
Each SK reduction step preserves denotation in any model.
-/
/-
**Theorem 4 (Cross-domain bridge): SK combinator equivalence preserves denotation
without normalization.**
The SK combinator calculus is famously non-normalizing — many terms have no normal form,
and the rewrite system is non-confluent modulo evaluation order. Yet semantic soundness
of extraction holds by the quotient principle alone.
-/
/-
Extraction soundness for SK combinators: any extractor returning an equivalent
term preserves semantics, even though normal forms may not exist.
-/
/-! ## Part VI: General Composition Theorem -/
/-
**Composition of sound extractors.**
If two extraction steps are each quotient-sound, their composition is also sound.
This enables modular optimizer pipelines where each pass may use a different
non-confluent rewrite system.
-/
/-! ## Part VII: Concrete Non-Confluent Example -/
/-- A concrete non-confluent rewrite system on arithmetic terms:
both `x + 0 → x` and `x → x + 0` are valid rewrites,
creating non-confluence and non-termination. -/
inductive NonConfluentArithStep : Term → Term → Prop where
| add_zero_elim (t : Term) : NonConfluentArithStep (Term.add t (Term.const 0)) t
| add_zero_intro (t : Term) : NonConfluentArithStep t (Term.add t (Term.const 0))
| comm_add (a b : Term) : NonConfluentArithStep (Term.add a b) (Term.add b a)
/-
The non-confluent arithmetic rewrites preserve denotation.
-/
/-
Even with non-confluent, non-terminating rewrites, equivalence closure
preserves semantics for arithmetic terms.
-/