lang::typecheck::levels
lang/src/typecheck/levels.mo
Level variables: the substitution half of universe polymorphism.
W1.1 put SortLevel and the COMPARISON helpers (level_const,
level_eq, level_le, level_lt, sort_level_of,
sort_term_of_level, level_of_type) in lang/types.mo, beside the
type they operate on. Those all answer a question about a level
without walking a Term, so they have no dependency beyond types
itself.
These do walk a Term, and that is why they live here instead:
subst_levels_term and free_level_vars reuse
term_map_children (lang/typecheck/traverse.mo), and traverse
imports types -- so putting them in types.mo is an import CYCLE,
not a style choice. Measured, not assumed: the first draft of this
work had them there and every dependent file failed with unbound variable term_map_children.
Why levels are name-keyed rather than de Bruijn, which is what makes
all of this short: a level variable can only be introduced at a DEF
BOUNDARY, so it is free by construction. There is no second index
space, and term_shift/term_subst/term_permute need no change --
they reach a sort through their existing catch-alls.
pub def subst_levels_term (t : Term) (binds : List (Pair Identifier SortLevel)) : TermSubstitute level variables throughout a TERM.
Four lines of real work because term_map_children already walks all
of Term's variants; only the sort arm needs saying, since a level
is DATA on that node rather than a child (traverse.mo documents
Term.sort as a leaf for exactly this reason, which is what makes
the catch-all safe here).
pub def solve_levels (param_ty : Term) (actual_ty : Term) (binds : List (Pair Identifier SortLevel)) : List (Pair Identifier SortLevel)The level instantiation half (W1.4): bind a call site's level variable from one argument.
The rule is deliberately narrow. Only a parameter whose type is
literally Sort (var u) contributes, and only when the argument's own
inferred type is a sort; u then takes that sort's level, normalized
to a concrete numeral when level_const folds it (Sort 1 arrives
here as succ (concrete 0) from type_check_sort_full).
First binding wins, and everything else is left FREE rather than
defaulted -- the same non-committal discipline solve_typevars
documents, and for the same reason: level_le (lang/types.mo)
answers false for a variable it cannot evaluate, so guessing a level
the call site did not determine turns a missing constraint into a
wrong one. Cumulativity is the unifier's job (unify_sort), which is
why the MINIMAL binding is the right one here.
Sort (max u v) parameters and non-sort arguments contribute nothing
(which of the two operands to bind is not determined); that is the
documented completeness gap, not an oversight.
pub def free_level_vars (t : Term) : List IdentifierEvery free level variable in a TERM, in first-seen order.
Spelled out per variant rather than routed through
term_map_children, because that combinator REBUILDS a term and
this one accumulates a list -- the shapes do not match. The arms
that matter are the binders and the sort; everything else either
holds no level or holds one only under a child listed here.