lang::typecheck::ctor_refine
lang/src/typecheck/ctor_refine.mo
Constructor index inversion for indexed families
(plans/type-system/dependent-elimination-refinement.md).
Inductive.params mixes uniform parameters and indices: type Vec (len : Nat) A { nil : Vec Nat.zero A, cons ... : Vec (Nat.succ len) A } declares
len as a header binder, but each constructor fixes it in its declared
return. A header position is an INDEX when some constructor's declared
return argument there is not the bare header binder.
Matching a constructor against a scrutinee type solves the constructor's
index variables from the scrutinee's index (cons against Vec (succ n) A gives len := n), proves it impossible (nil against Vec (succ n) A: two constructor heads clash), or refines a bound-variable index (cons
against Vec m A with m a local: inside the arm, m is succ len@d for
a fresh skolem len@d). Anything else is unknown, and every caller then
keeps its old behaviour: this module only ever adds information.
Pure: no infer import, so infer can use it without a cycle.
pub struct IndexSolution {
/// The constructor's index variables, bound to scrutinee subterms or to
/// fresh skolems.
subst : List (Pair Identifier Term),
/// Bound-variable indices of the scrutinee (outer de Bruijn index) and the
/// constructor index that replaces each inside the arm.
refine : List (Pair I64 Term),
/// The same for an index that is a LOCAL binder written by name (an
/// implicit `{m : Nat}` appears in a parameter's type as the free name `m`).
refine_named : List (Pair Identifier Term),
}What a constructor's declared indices tell us about one arm.
pub type IndexMatch {
solved (s : IndexSolution),
/// Two constructor heads clash: the arm can never run.
impossible,
/// Nothing safe can be concluded.
unknown,
}pub def index_positions (ind : Inductive) : List I64The header positions that some constructor fixes in its declared return.
Vec -> [0]; Option, List, Sigma, Eq (whose index is outside the
header) -> [], which makes every rule below a no-op for them.
pub def ctor_index_patterns (ind : Inductive) (c : InductConstructor) (positions : List I64) : List TermThis constructor's declared index patterns, one per index position. An unannotated constructor's pattern is the header binder itself.
pub def index_locals (ind : Inductive) (positions : List I64) : List IdentifierThe header binders at the index positions: the names a constructor's index pattern and field types may use as its own variables.
pub struct MatchEnv {
locals : List Identifier,
/// The enclosing local binders' names: a free variable spelled with one of
/// them is a local, not a global, and may be refined by name.
binders : List Identifier,
scope : Scope,
skolem_suffix : String,
}The matching context: which names are the constructor's index variables, the scope that says which heads are constructors, and the suffix that makes this arm's skolems distinct from any other arm's.
pub def empty_solution : IndexSolutionpub def solve_ctor (env : MatchEnv) (ind : Inductive) (c : InductConstructor) (sc_typ : Term) : IndexMatchSolve c against the scrutinee type sc_typ. impossible wins over
unknown, which wins over solved.
pub def match_index (env : MatchEnv) (pattern : Term) (target : Term) (acc : IndexSolution) : IndexMatchOne-way structural match of a declared index pattern against a scrutinee
index target. Binds the RAW target subterms (their spelling is the
caller's); constructor heads are compared by canonical name only.
pub def has_refinement (s : IndexSolution) : Boolpub def refine_field_types (ind : Inductive) (sc_typ : Term) (s : IndexSolution) (field_types : List Term)
: List TermField types for an arm. The uniform header params are substituted from the scrutinee's spine by name (exactly as before); the index variables take the solution's bindings instead of the scrutinee's raw index.
pub def refine_expected (s : IndexSolution) (expected : Term) : Termexpected with each refined local (by index or by name) replaced by its
constructor index, in the scrutinee's (outer) context.
pub def apply_subst (subst : List (Pair Identifier Term)) (t : Term) : Termpub def present_args (args : List (Option Term)) : List Termpub def nat_literal_bound : I64The largest Nat literal unfolded to a constructor chain; larger ones stay
as written and match nothing (unknown).
pub def nat_literal_term (n : I64) : TermA small Nat literal as its canonical unary constructor chain. Vec 3
must compare with Vec (succ (succ (succ zero))); Nat.of_i64 3 cannot
reduce in the checker (its body tests a native I64.lt).
pub struct IntroCtor {
ind : Inductive,
ctor : InductConstructor,
args : List Term,
}A constructor application of an indexed family, saturated: one argument per constructor field.
pub def intro_ctor (scope : Scope) (t : Term) : Option IntroCtort as a saturated constructor application of an indexed family, if it is
one. A constructor two families share, or a partial application, is none.
pub def names_constructor (scope : Scope) (id : Identifier) : BoolDoes id name a constructor in scope: Nat.zero through its owner, or a
bare zero owned by some family?
pub def same_constructor_ref (scope : Scope) (a : Identifier) (b : Identifier) : BoolDo a and b name the same constructor in two spellings (false and
Bool.false)? The tails must agree and the two spellings must share an
owning family.
pub def intro_index_bindings (scope : Scope) (ind : Inductive) (c : InductConstructor) (expected : Term)
: Option (List (Pair Identifier Term))The bindings for a constructor's index variables when it is checked against
expected: the solved values (cons : Vec 1 A gives len := zero, so the
tail is checked at Vec zero A), or none when the solution is not plain
(unknown, impossible, or a refinement of a variable index).
pub def intro_indices (scope : Scope) (arg_type : Term -> Option Term) (ic : IntroCtor) : Option (List Term)The indices a constructor application produces, one per index position:
the constructor's declared index patterns with its index variables solved
from the arguments. A field typed by the same family supplies its
argument's indices -- a nested constructor application's own, or what
arg_type reports for anything else (a typed local). None when an index
variable stays unsolved.
pub def intro_clash (scope : Scope) (arg_type : Term -> Option Term) (ic : IntroCtor) (expected : Term) : Option TermWhether an indexed constructor application can have type expected:
some found (the application's type, spelled with expected's uniform
arguments) when a computed index's constructor head clashes with
expected's; none when it fits or nothing safe can be concluded. A
variable index on either side is never a clash: it may be refined by an
enclosing match the checker does not track.
pub def with_indices (t : Term) (positions : List I64) (idx : List Term) : Termt's spine with the arguments at positions replaced, in order.