f27211f73f
Adds schema-based inductive type encoding to the engine, supporting both
plain inductives (Nat, List, Bool) and HITs (S¹, propositional truncation,
suspensions) via a single CTypeSchema/CtorSpec/CTypeArg structure.
New CType constructor:
- .ind (S : CTypeSchema) (params : List CType)
New CTerm constructors:
- .dimExpr (r : DimExpr)
- .ctor (S, ctorName, params, args)
- .indElim (S, params, motive, branches, target)
New CVal constructors:
- .vctor (S, ctorName, params, evaluatedArgs)
- .vdimExpr (DimExpr)
New CNeu constructor:
- .nIndElim (S, params, motive, branches, neuTarget)
Five-way mutual block in Syntax.lean (CType, CTerm, CTypeArg, CtorSpec,
CTypeSchema) with Repr derivation post-hoc. Tag layout per
docs/INDUCTIVE_TYPES.md §6: old tags preserved (no shifting). Existing
62/62 smoke + property tests pass unchanged through Rust.
Substitution / dim-absent / endpoint handling:
Subst.lean — substDim, substDimExpr, equation lemmas,
substDim_eq_substDimExpr (mutual with .params helpers).
DimLine.lean — CTerm.dimAbsent + CType.dimAbsent (mutual w/ helpers
for list / branches / params). Plus all five
auxiliary mutual blocks: substDim_absent_aux,
substDimExpr_absent_aux, dimAbsent_after_substDim_aux,
substDim_comm_aux — for both CTerm and CType.
Eval.lean: ctor → vctor (eval'd args); indElim β-reduces on canonical
vctor target via vApp chain over branch body, otherwise stuck via
.nIndElim; dimExpr → vdimExpr. Path-ctor boundary firing and
recursive-arg IH wiring marked TODO REL1.1 (β-reduction works for
non-recursive ctors today).
Readback.lean: vctor → .ctor, vdimExpr → .dimExpr, nIndElim → .indElim.
FFITest.lean: cvalSummary / ctermSummary extended with new constructor
arms.
Topolei (sibling repo) has not yet been migrated — see
docs/INDUCTIVE_TYPES.md §9.1 for the per-file impact map.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
329 lines
18 KiB
Text
329 lines
18 KiB
Text
/-
|
||
Topolei.Cubical.Syntax
|
||
======================
|
||
Deep embedding of the cubical term language (CCHM §2–3).
|
||
|
||
Grammar:
|
||
A, B ::= U | Π A B | Path A a b
|
||
t, u ::= x | λx.t | t u | ⟨i⟩t | t@r | transpⁱ A φ t | compⁱ A φ u t
|
||
|
||
CType and CTerm are mutually inductive because path types carry endpoint
|
||
terms, and terms carry path applications over DimExprs.
|
||
|
||
transp and comp store (i : DimVar) (A : CType) inline rather than DimLine,
|
||
because DimLine is defined later in the import chain (Subst → DimLine).
|
||
The typing rules in Typing.lean use DimLine as a convenient wrapper.
|
||
|
||
The path β-rule (⟨i⟩ t) @ r ↝ t[i := r]
|
||
and the four "fully-reducing" transport/comp cases (T1, T2, C1, C2)
|
||
are NbE theorems in `Cubical/Readback.lean`. The residual step-level
|
||
axioms — T3, T5, C4 (subject reduction + face congruence) and T4
|
||
(path-line shape preservation) — live in `TransportLaws.lean` /
|
||
`CompLaws.lean`.
|
||
-/
|
||
|
||
import CubicalTransport.Face
|
||
|
||
-- ── Syntax ────────────────────────────────────────────────────────────────────
|
||
|
||
mutual
|
||
/-- Types in the cubical calculus. -/
|
||
inductive CType where
|
||
| univ : CType -- U
|
||
| pi (A : CType) (B : CType) : CType -- Π A B
|
||
| path (A : CType) (a b : CTerm) : CType -- Path A a b
|
||
/-- Non-dependent Σ type (cells-spec §6.2, §8.1, §9.2).
|
||
|
||
`Sigma A B` — pairs whose first component has type `A` and whose
|
||
second has type `B`. Non-dependent: `B` does not refer to the
|
||
first component. Dependent Σ (where `B : A → CType`) is deferred
|
||
for the same reason as dependent Π — requires a term evaluator
|
||
to apply `B` to a term. -/
|
||
| sigma (A B : CType) : CType -- Σ A B
|
||
/-- Glue type (CCHM §6).
|
||
`Glue [φ ↦ (T, e)] A` — on face `φ` the type is `T` with `e : T ≃ A`
|
||
as witness; off face `φ` the type is `A`. The equivalence `e` is
|
||
inlined as five `CTerm` fields (f, fInv, sec, ret, coh) rather than
|
||
a nested `EquivData` so that `CType` / `CTerm` remain a closed
|
||
mutual inductive block — `EquivData` lives in `Equiv.lean` and is
|
||
downstream in the import chain. Use `EquivData.toGlueType` in
|
||
`Equiv.lean` for an ergonomic wrapper. -/
|
||
| glue (φ : FaceFormula) (T : CType)
|
||
(f fInv sec ret coh : CTerm)
|
||
(A : CType) : CType -- Glue [φ ↦ (T, e)] A
|
||
/-- Schema-defined inductive type (REL1, INDUCTIVE_TYPES.md).
|
||
|
||
`ind S params` is an instance of the schema `S` at the given
|
||
type parameters. `params.length = S.numParams` is a typing-side
|
||
condition (not enforced syntactically — see `HasType.ind` in
|
||
`Typing.lean`).
|
||
|
||
The schema `S` carries the constructor list (point + path
|
||
ctors) and their boundary partial-element systems. Both plain
|
||
inductives (`Nat`, `List A`, `Bool`) and HITs (`S¹`, `‖A‖₋₁`,
|
||
suspensions, pushouts) are encoded uniformly via
|
||
`CTypeSchema`. -/
|
||
| ind (S : CTypeSchema) (params : List CType) : CType -- ind S params
|
||
|
||
/-- Terms in the cubical calculus. -/
|
||
inductive CTerm where
|
||
| var (x : String) : CTerm -- x
|
||
| lam (x : String) (t : CTerm) : CTerm -- λx. t
|
||
| app (f a : CTerm) : CTerm -- f a
|
||
| plam (i : DimVar) (t : CTerm) : CTerm -- ⟨i⟩ t
|
||
| papp (t : CTerm) (r : DimExpr) : CTerm -- t @ r
|
||
| transp (i : DimVar) (A : CType) (φ : FaceFormula)
|
||
(t : CTerm) : CTerm -- transpⁱ A φ t
|
||
| comp (i : DimVar) (A : CType) (φ : FaceFormula)
|
||
(u t : CTerm) : CTerm -- compⁱ A φ u t
|
||
/-- Multi-clause heterogeneous composition.
|
||
`compⁱ A [φ₁ ↦ u₁, …, φₙ ↦ uₙ] t` — a partial element defined
|
||
over the union of the clause faces. Coherence (clauses agree
|
||
on overlaps and with `t` at `i = 0`) is a typing-level side
|
||
condition, not enforced syntactically. Used by CCHM path
|
||
transport and heterogeneous Π composition to express systems
|
||
that a single-clause `.comp` cannot represent. -/
|
||
| compN (i : DimVar) (A : CType)
|
||
(clauses : List (FaceFormula × CTerm))
|
||
(t : CTerm) : CTerm -- compⁱ A [φ₁↦u₁,…] t
|
||
/-- Glue introduction (CCHM §6.1).
|
||
`glueIn [φ ↦ t] a` — on face `φ`, equals `t : T`; off face `φ`,
|
||
equals `a : A`. Well-typedness requires `e.f t = a` on the
|
||
overlap (a typing-side condition, not enforced syntactically).
|
||
The equivalence `e` is carried by the type, not the term. -/
|
||
| glueIn (φ : FaceFormula) (t a : CTerm) : CTerm -- glue [φ↦t] a
|
||
/-- Glue elimination (CCHM §6.1).
|
||
`unglue [φ ↦ f] g` — extract the underlying `A`-value from a
|
||
glued term. On face `φ`, equals `f g` (apply the forward map);
|
||
off face `φ`, equals `g` (already an `A`-value). `f` is the
|
||
`f`-field of the equivalence witnessing `T ≃ A` — carried
|
||
explicitly at the term level because we don't have type
|
||
annotations on terms. -/
|
||
| unglue (φ : FaceFormula) (f g : CTerm) : CTerm -- unglue [φ↦f] g
|
||
/-- Σ introduction (pair). -/
|
||
| pair (a b : CTerm) : CTerm -- (a, b)
|
||
/-- Σ elimination (first projection). -/
|
||
| fst (t : CTerm) : CTerm -- t.1
|
||
/-- Σ elimination (second projection). -/
|
||
| snd (t : CTerm) : CTerm -- t.2
|
||
/-- A dimension expression lifted into the term language (REL1).
|
||
|
||
Used to fill `.dim`-typed argument positions of schema
|
||
constructors (path ctors) and to hand a `DimExpr` to any
|
||
future term-level operation that needs one. `DimExpr` is
|
||
de Morgan algebra over `DimVar` and 0/1; lifting it lets path
|
||
constructors take general dim arguments like `.meet i j`,
|
||
`.inv r`, etc., not just bare `.var`-shaped dim names. -/
|
||
| dimExpr (r : DimExpr) : CTerm -- ⟦ r ⟧
|
||
/-- Schema constructor application (REL1, INDUCTIVE_TYPES.md §2.4).
|
||
|
||
`ctor S c params args` applies the constructor named `c` of
|
||
schema `S` at parameters `params`, with `args.length =
|
||
(S.ctors.find c).args.length`.
|
||
|
||
Args are positional and follow `CtorSpec.args` order. `.dim`-
|
||
typed arg positions carry `CTerm.dimExpr r` (or any other
|
||
CTerm that evaluates to a dim) — eval consults the
|
||
constructor's boundary system on these to decide whether to
|
||
produce the canonical `vctor` or fire a boundary clause. -/
|
||
| ctor (S : CTypeSchema) (ctorName : String)
|
||
(params : List CType) (args : List CTerm) : CTerm
|
||
/-- Inductive eliminator (REL1, INDUCTIVE_TYPES.md §5).
|
||
|
||
`indElim S params motive branches target` eliminates a value
|
||
of type `.ind S params`.
|
||
|
||
- `motive` is a CTerm of (function-CType) shape `.pi (.ind S
|
||
params) .univ` — i.e. `λx : .ind S params. SomeType x`.
|
||
- `branches` is one entry per ctor in *schema-declaration
|
||
order*. Entry `(c, body)` says: when target reduces to the
|
||
ctor `c`, evaluate `body` applied to the ctor's args plus
|
||
(for each `.self` arg) the recursive elimination result.
|
||
- `target : .ind S params` is the term being eliminated.
|
||
|
||
For path constructors, the branch must respect boundary
|
||
coherence: at every face in the ctor's boundary system, the
|
||
branch agrees with the corresponding eliminated body. This
|
||
is a typing-level side condition (see `HasType.indElim`). -/
|
||
| indElim (S : CTypeSchema) (params : List CType)
|
||
(motive : CTerm)
|
||
(branches : List (String × CTerm))
|
||
(target : CTerm) : CTerm
|
||
|
||
/-- Argument shape for a schema constructor (REL1, §2.1).
|
||
|
||
Distinguishes ordinary CType-typed args (which may reference
|
||
schema parameters via `.param`) from recursive `.self` args
|
||
(the inductive being defined) and `.dim` args (used by path
|
||
constructors). Boundary clauses inside `CtorSpec` reference
|
||
args positionally; `.dim` args are addressed in face formulae
|
||
via `DimVar.mk "$d_k"` where `k` is the dim-arg index counted
|
||
among `.dim` arg positions only. -/
|
||
inductive CTypeArg where
|
||
/-- A non-recursive arg whose type is a closed CType. May
|
||
reference schema parameters via embedded `.param i` inside `A`
|
||
(parameter substitution happens at instantiation time). -/
|
||
| type (A : CType) : CTypeArg
|
||
/-- The `i`th schema parameter (zero-indexed against
|
||
`CTypeSchema.numParams`). -/
|
||
| param (i : Nat) : CTypeArg
|
||
/-- Recursive reference to the inductive type being defined. -/
|
||
| self : CTypeArg
|
||
/-- A dimension binder, used by path constructors. -/
|
||
| dim : CTypeArg
|
||
|
||
/-- Constructor specification (REL1, §2.2).
|
||
|
||
`name` is unique within the schema. `args` is the positional
|
||
arg list. `boundary` is the partial-element system for path
|
||
constructors (empty list ≡ point ctor). Each clause `(φ, body)`
|
||
says: on the face `φ` of the dim args, the constructor reduces
|
||
to `body`. Coherence obligations on the clauses are enforced
|
||
at typing time (see `HasType.ctor` in `Typing.lean`).
|
||
|
||
Boundary clause bodies are CTerms in a scope where the ctor's
|
||
args are bound positionally as `.var "$arg_k"`. Face formulae
|
||
reference dim args as `DimVar.mk "$d_k"`. -/
|
||
inductive CtorSpec where
|
||
| mk (name : String) (args : List CTypeArg)
|
||
(boundary : List (FaceFormula × CTerm)) : CtorSpec
|
||
|
||
/-- Schema for an inductive (or higher-inductive) type (REL1, §2.3).
|
||
|
||
`name` is the schema's symbolic name (used for diagnostics, not
|
||
identity — schemas are compared structurally). `numParams` is
|
||
the count of type parameters; `ctors` is the constructor list
|
||
in declaration order. Equality is structural (no interning).
|
||
|
||
The schema mutually depends on `CType` (via `.type`-typed args
|
||
and via `params : List CType` in `CType.ind`) and `CTerm` (via
|
||
boundary clauses), so all five types live in this `mutual`
|
||
block. -/
|
||
inductive CTypeSchema where
|
||
| mk (name : String) (numParams : Nat)
|
||
(ctors : List CtorSpec) : CTypeSchema
|
||
end
|
||
|
||
-- ── Repr derivations ─────────────────────────────────────────────────────────
|
||
-- All five mutual inductives get `Repr` instances post-hoc (Lean's
|
||
-- `deriving Repr` clause inside a mutual block of five doesn't always
|
||
-- compose; explicit `deriving instance` is the robust form).
|
||
|
||
deriving instance Repr for CType
|
||
deriving instance Repr for CTerm
|
||
deriving instance Repr for CTypeArg
|
||
deriving instance Repr for CtorSpec
|
||
deriving instance Repr for CTypeSchema
|
||
|
||
-- ── Dimension substitution ────────────────────────────────────────────────────
|
||
-- Substitute dimension variable i with DimExpr r throughout a term.
|
||
--
|
||
-- Scope inside transp/comp:
|
||
-- · j is the binder of the transport line, bound in A and in φ.
|
||
-- · The base term t (and system u) are in outer scope — we substitute there.
|
||
--
|
||
-- Approximation: `substDim` does NOT descend into A or φ — even when j ≠ i
|
||
-- and i would be free under the binder. Consequence: this substitution is
|
||
-- only faithful for *endpoint* calls (`substDimBool`), where downstream
|
||
-- uses the dimension-absent predicate to justify correctness. Full
|
||
-- DimExpr-in-FaceFormula substitution is deferred (see cells-spec §5.5).
|
||
|
||
mutual
|
||
def CTerm.substDim (i : DimVar) (r : DimExpr) : CTerm → CTerm
|
||
| .var x => .var x
|
||
| .lam x t => .lam x (t.substDim i r)
|
||
| .app f a => .app (f.substDim i r) (a.substDim i r)
|
||
| .plam j t => if j = i then .plam j t -- i bound; stop
|
||
else .plam j (t.substDim i r)
|
||
| .papp t s => .papp (t.substDim i r) (DimExpr.subst i r s)
|
||
-- transp/comp: leave A alone (approximation); descend into t, u and
|
||
-- substitute in φ via the general DimExpr face-formula substitution.
|
||
| .transp j A φ t => .transp j A (φ.substDim i r) (t.substDim i r)
|
||
| .comp j A φ u t => .comp j A (φ.substDim i r) (u.substDim i r) (t.substDim i r)
|
||
-- Multi-clause comp: substitute in each clause's face and body, and in t.
|
||
-- Uses an explicit recursive helper `substDim.clauses` so Lean can see
|
||
-- structural termination through the clause list.
|
||
| .compN j A clauses t =>
|
||
.compN j A (CTerm.substDim.clauses i r clauses) (t.substDim i r)
|
||
-- Glue introduction / elimination: descend into all sub-terms and
|
||
-- substitute into the face formula. Same approximation for types
|
||
-- as transp/comp (A not touched — the `φ` face formula carries the
|
||
-- whole dim-dependency story; in our approximation we still don't
|
||
-- recurse into CType sub-trees here, matching `.transp`/`.comp`).
|
||
| .glueIn φ t a => .glueIn (φ.substDim i r) (t.substDim i r) (a.substDim i r)
|
||
| .unglue φ f g => .unglue (φ.substDim i r) (f.substDim i r) (g.substDim i r)
|
||
-- Σ constructors: structural recursion into sub-terms.
|
||
| .pair a b => .pair (a.substDim i r) (b.substDim i r)
|
||
| .fst t => .fst (t.substDim i r)
|
||
| .snd t => .snd (t.substDim i r)
|
||
-- REL1 inductive-type constructors. Same CType-approximation as
|
||
-- transp/comp/glue: schemas and `params : List CType` are *not*
|
||
-- recursed into. The schemas are static and the params are
|
||
-- supplied externally to any binder we'd be substituting into.
|
||
| .dimExpr s => .dimExpr (DimExpr.subst i r s)
|
||
| .ctor S c params args =>
|
||
.ctor S c params (CTerm.substDim.list i r args)
|
||
| .indElim S params motive branches target =>
|
||
.indElim S params
|
||
(motive.substDim i r)
|
||
(CTerm.substDim.branches i r branches)
|
||
(target.substDim i r)
|
||
|
||
/-- Helper: apply `CTerm.substDim i r` to each clause body (and
|
||
`FaceFormula.substDim` to each face) in a system's clause list.
|
||
Defined mutually with `substDim` so Lean can verify termination. -/
|
||
def CTerm.substDim.clauses (i : DimVar) (r : DimExpr) :
|
||
List (FaceFormula × CTerm) → List (FaceFormula × CTerm)
|
||
| [] => []
|
||
| (φ, u) :: rest =>
|
||
(φ.substDim i r, u.substDim i r) :: CTerm.substDim.clauses i r rest
|
||
|
||
/-- Helper: apply `CTerm.substDim i r` to each element of a CTerm
|
||
list (ctor argument lists). Mutually recursive for termination. -/
|
||
def CTerm.substDim.list (i : DimVar) (r : DimExpr) :
|
||
List CTerm → List CTerm
|
||
| [] => []
|
||
| t :: rest => t.substDim i r :: CTerm.substDim.list i r rest
|
||
|
||
/-- Helper: apply `CTerm.substDim i r` to the body of each branch in
|
||
an `indElim`. Branch *names* are not affected; only bodies. -/
|
||
def CTerm.substDim.branches (i : DimVar) (r : DimExpr) :
|
||
List (String × CTerm) → List (String × CTerm)
|
||
| [] => []
|
||
| (n, b) :: rest =>
|
||
(n, b.substDim i r) :: CTerm.substDim.branches i r rest
|
||
end
|
||
|
||
-- ── One-step reduction ────────────────────────────────────────────────────────
|
||
-- `CTerm.step` is left *opaque*. Semantically it is what a CCHM-style
|
||
-- evaluator will compute. Keeping `step` opaque is required for
|
||
-- soundness: if `step` were a concrete `def` with a wildcard identity
|
||
-- arm, any axiom of the shape `step (.transp …) = t` would rfl-collapse
|
||
-- to `.transp … = t`, contradicting `CTerm.noConfusion`.
|
||
--
|
||
-- **Stage 4.4 decision (2026-04-23).** After the Phase 1 step↔eval
|
||
-- bridge + Stream B #2d + Stage 2.3, only one step-level axiom remains:
|
||
-- `transp_plam_is_plam_path` (T4, path-restricted form; Stage 4.2).
|
||
-- T1/T2/C1/C2/T5/`step_papp_plam` are NbE theorems in `Readback.lean`;
|
||
-- T3/C4 are theorems via `CTerm.step_preserves_type` (ValueTyping.lean);
|
||
-- glue β/η are theorems via `eval_unglue_of_glueIn`/`eval_glueIn_of_unglue`.
|
||
--
|
||
-- **Rust discharge flexibility.** The Rust backend has two valid
|
||
-- implementation strategies for `CTerm.step`:
|
||
--
|
||
-- · *Option A — native step*: implement `step` directly as a C ABI
|
||
-- entry point. The single T4 axiom is discharged by emitting the
|
||
-- CCHM comp-shaped body for path-typed transp-of-plam inputs, plus
|
||
-- identity behaviour on other shapes.
|
||
--
|
||
-- · *Option B — derived step*: define `step := readback ∘ eval .nil`
|
||
-- entirely in Rust (no separate `step` FFI entry). This matches
|
||
-- the Lean-side "bridge" intuition and keeps the Rust FFI surface
|
||
-- smaller by one function. Satisfies T4 on path-typed lines via
|
||
-- the `vPathTransp` → `.compN` readback arm.
|
||
--
|
||
-- The Lean-side spec is agnostic to which strategy Rust picks — both
|
||
-- satisfy the same axiom set. See FFI_DESIGN.md (Stage 4.5) for the
|
||
-- concrete recommendation.
|
||
|
||
opaque CTerm.step : CTerm → CTerm := id
|