Skip to content
BANG

Question: how does BANG get value-indexed precision — starting with Nat (a floor for total recursion), reaching toward refinement and eventually dependent types — WITHOUT making type-checking undecidable or the kernel un-verifiable?

Why it matters — three threads converge here. (1) Nat = the floor that turns measure-recursion (factorial, countdown) TOTAL — #47 certifies only STRUCTURAL recursion because unbounded ℤ (ADR-0067) has no floor, so ($sum)(n-1) genuinely diverges on negatives and correctly stays Div. (2) Refinement types ({n : Int // n ≥ 0}) are the full form of "make illegal states unrepresentable" (SOUL) — negative-Nat, out-of-bounds indices, div-by-zero become unrepresentable BY CONSTRUCTION. (3) Dependent types NEED a total language (type-level computation must terminate to be decidable) — so the total fragment (#47) is their prerequisite brick.

The architecture (operator's direction — the load-bearing design):

SURFACE (user-facing)   refinement types   { n : Int // P n }      ergonomic; illegal states
                                                                    unrepresentable; Liquid Haskell / F* / Dafny lineage
UNDERLYING (kernel)     QUOTIENT props     P realized as a         proof-IRRELEVANT (a subsingleton) —
                        (truncation ∥P∥ =  quotient by the total   the checker needs only that a proof
                        the (-1)-trunc)    relation → subsingleton  EXISTS, never to compare witnesses
CHECKING                decidable          discharge P via a        FEASIBLE: no witness-tracking (proof
                                           `Decidable`/decision     irrelevance) + the total fragment (#47)
                                           procedure                ensures the predicate's own evaluation halts

Why the quotient layer is the crux: proof-RELEVANT dependent checking is where feasibility dies (you must compare proof terms, and with non-termination that's undecidable). Propositional truncation via QUOTIENT collapses all proofs of P to one point → proof irrelevance → checking a refinement = DECIDING P (a decision procedure), not comparing proofs. quotient underlying, refinement surface: the kernel manipulates quotient/truncated propositions (verified, decidable), the user writes the ergonomic subset type.

The axiom-clean bonus (bang-specific): Quot.sound is ALREADY one of BANG's trusted-3 axioms ({propext, Classical.choice, Quot.sound}). The quotient foundation is on-hand and adds NOTHING to the trust base — the underlying mechanism is already in the axiom budget. (And propext + proof irrelevance are the same proof-collapsing move at the Prop level.)

Nat, three ways (the concrete near-term instance — see also ADR-0073 §2 / #47):

                     free termination     arithmetic    new machinery         expressiveness
inductive Nat        ✓ (structural — #47  O(n) Peano    none (rides data)     just Nat
  Zero | Succ           certifies it AS-IS: n-1 = the
                        Succ-predecessor subterm)
refinement Nat       ✗ (needs measure +   O(1) Int      quotient props +      Nat, {0≤i<len}, {n>0}, …
  {n:Int // n≥0}         floor reasoning)                a decision procedure  (the general mechanism)
stratified (Lean's)  ✓ structural for proof/type-level ⊕ efficient Int runtime ⊕ verified bridge
                        — verified core + tested superset + explicit seam (the project's signature move)

Near-term: inductive Nat is the minimal win — it rides data + the #47 structural checker with ZERO new type machinery, making factorial-on-Nat total for free (measure-recursion collapses into structural recursion: n-1 IS match n { Succ(m) -> m }). Refinement types are the bigger, later fork this question is really about.

Options: (1) inductive Nat now (rides #47, no new machinery — the incremental floor). (2) refinement types with quotient-truncated decidable propositions (the operator's direction — the general "unrepresentable by construction" mechanism; needs a decision procedure + the truncation layer). (3) full dependent types (Π/Σ, Vec n) — the far end; rests on (2) + the total fragment. (4) none (stay simply-typed + inductive data).

Recommended: inductive Nat opportunistically now (it's free once #47 lands); record refinement- types-over-quotient-propositions as THE intended path to value-indexed precision (decidable by construction, axiom-clean via Quot.sound), design-first when it's taken up. It sits post-polymorphism (ADR-0027) — refinements interact with the poly lift (a refined generic type) and with grades (Q27).

Blocked on: the total fragment (#47, in flight — the termination floor + decidable type-level evaluation); polymorphism (ADR-0027) for refined generics; a decision-procedure story (how far: syntactic · Decidable instances · SMT). All post-v1.

Revisit signal: taking up Nat (do it the moment #47 lands — free total factorial); OR array/index safety, positivity, or div-by-zero pressure (the refinement payoff); OR when the type system's power axis (Q27 grades, ADR-0027 poly) is next lifted — refinements are the same "richer types" frontier.